Searching an element by a key value in STL map

Question

Is it necessary to do a loop (with the related iterators) to search an element in a STL map? Or does it work with .find(key_value) STL method?

If I could do both ways I suppose that .find method it works more efficient, could you also confirm it?

For example:

1.Doing this by a loop:

map<string,User> mapUser;
map<string,User>::iterator it=mapUser.begin(); 
while(it != mapUser.end()){
  if(it->first == ID){
      //ID found
  }
  ++it;
}

2.Doing this by .find(key_value):

map<string,User> mapUser;
map<string,User>::iterator it=mapUser.find(ID); 
    if(it != mapUser.end()){   
          // ... ID found (there is a key value in STL map equal to ID)
    }else
          // ID not found

That's what maps are for dude. – 101010 Nov 18 '15 at 18:10 — 101010, Nov 18 '15 at 18:10

score 0 · Answer 1 · edited May 23 '17 at 12:23

0

std::map is implemented as a R-B Binary Tree, so find is O(logN). There's no way to make this "more efficient". Searching by iteration is O(N) and incredibly inefficient, completely defeating the point of using a std::map in the first place.

I recommend you look up what a std::map is and how it compares to something like a std::vector.

edited May 23 '17 at 12:23

Community

1
1

answered Nov 18 '15 at 18:13

Colin Basnett

4,052
2
30
49

Searching an element by a key value in STL map

1 Answers1