13

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! :)

mister
  • 3,303
  • 10
  • 31
  • 48

4 Answers4

24

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); }
}
Kerrek SB
  • 464,522
  • 92
  • 875
  • 1,084
5

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.

iammilind
  • 68,093
  • 33
  • 169
  • 336
  • *`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. – David Rodríguez - dribeas May 14 '12 at 11:20
  • 1
    @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. – iammilind May 14 '12 at 11:34
  • 2
    @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*. – David Rodríguez - dribeas May 14 '12 at 13:00
2

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.

Ivaylo Strandjev
  • 69,226
  • 18
  • 123
  • 176
1

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.

tuxuday
  • 2,977
  • 17
  • 18