STL MAP should use find() or [n] identifier to find element in map?

Question

I am confused which is more efficient?

As we can access map directly, why do we need to use find?

I just need to know which way is more efficient.

#include <iostream>
#include <map>
using namespace std;

int main ()
{
  map<char,int> mymap;
  map<char,int>::iterator it;

  mymap['a']=50;
  mymap['b']=100;
  mymap['c']=150;
  mymap['d']=200;

  //one way

  it=mymap.find('b');
  cout << (*it).second <<endl;

  //another way
      cout << mymap['b'] <<endl;

  return 0;
}

thanks in advance! :)

Passably

Answer 1

Using find means that you don't inadvertently create a new element in the map if the key doesn't exist, and -- more importantly -- this means that you can use find to look up an element if all you have is a constant reference to the map.

That of course means that you should check the return value of find. Typically it goes like this:

void somewhere(const std::map<K, T> & mymap, K const & key)
{
    auto it = mymap.find(key);
    if (it == mymap.end()) { /* not found! */ }
    else                   { do_something_with(it->second); }
}

Thinkable

+1 This is absolutely important when you dont want to create the element if its not found. – Conjunctive

Answer 2

As we can access map directly, why do we need to use find?

Because map<>::operator[] is sometimes nasty. If an element doesn't exist then:

• it inserts it
• value initialize it
• returns reference of value

Thus it always returns a valid reference of value, even if a key din't exist previously. This behavior is not intended many times.

On the other hand map<>::find() is safer; because it returns end(), if a value doesn't exit. Another advantage of find() is that it returns an iterator which contains references to key (first) and value(second) both.

Suppositive

map<>::find() is safer. Well, actually not. The simplest example is the code in the question, where the user is not verifying whether the iterator is valid. In that particular case map<>::operator[] is safer as it guarantees that the program does not have undefined behavior. – Henrieta

@DavidRodríguez-dribeas, that's wrong. Since there is no if check in the code, doesn't mean that it's not needed/intended. The code example is too localized. In real world, a sane coder will have a find() followed by an if condition. Writing dirty code to save an undefined behavior is not a solution. – Suppositive

@iammilind: I guess the issue is with the definition of safe. My point is that the semantics are different, and you can claim that find will not modify the container, but that does not make the find operation safer. Rather on the opposite end: with operator[] you are guaranteed that you get a reference, so it is safe to use it (yes, it modifies the container, no you don't cause undefined behavior), while with find, user code needs to check the return value, as it is not safe to dereference it automatically. To me more error prone means less safe. – Henrieta

Answer 3

The [] operator in map is not constant it is logarithmic. Most of the books stress on this fact and point out it is a bit misleading. So both find and [] operator are with the same complexity.

Please note that the [] operator will create the entry even if it does not exist while find will return end() in that case.

Holo

Answer 4

This code and doc is picked from cplusplus.com

// accessing mapped values
#include <iostream>
#include <map>
#include <string>
using namespace std;

int main ()
{
  map<char,string> mymap;

  mymap['a']="an element";
  mymap['b']="another element";
  mymap['c']=mymap['b'];

  cout << "mymap['a'] is " << mymap['a'] << endl;
  cout << "mymap['b'] is " << mymap['b'] << endl;
  cout << "mymap['c'] is " << mymap['c'] << endl;
  cout << "mymap['d'] is " << mymap['d'] << endl;

  cout << "mymap now contains " << (int) mymap.size() << " elements." << endl;

  return 0;
}

OP:
mymap['a'] is an element
mymap['b'] is another element
mymap['c'] is another element
mymap['d'] is
mymap now contains 4 elements.

Notice how the last access (to element 'd') inserts a new element in the map with that key and initialized to its default value (an empty string) even though it is accessed only to retrieve its value. Member function map::find does not produce this effect.

Rale