CODEWITHSUNDEEP
c++stlfind
Gallium Nitride
Gallium Nitride

Reputation: 313

C++ map start search from iterator position

My question is the following:

After using find on a std::map to get an iterator pointed to the desired element pair, is it possible to reuse that iterator on subsequent find()'s to take advantage of knowing that the elements im looking for afterwards are close to the first found element? Something like:

std::map<key, value> map_elements;
std::map<key, value>::iterator it;

it = map_elements.find(some_key);
it = it.find(a_close_key)

Thank you in advance

Upvotes: 2

Views: 1533

Answers (2)

Galimov Albert
Galimov Albert

Reputation: 7357

Your question is not complete about how far Item1(found by map::find) can be far from Item2. In some case its more effecient to make new map::find; in some cases you can just iterate your iterator to find where your second item can be. Using just search map::find it will be O(log n) complexity and it can be around 10-20 steps.

So, if you know your Item2 is not so far, you can just iterate it iterator to find it out. Most important thing here is how to check you must stop search. std::map uses std::less<T> by default to arrange items, so it can be used to find out container is not containing Item2 at all. Something like this(not tested):

std::map<key, value> map_elements;
std::map<key, value>::iterator it, it2;

it2 = it = map_elements.find(some_key);
bool found=false;
while( it2!=map_elements.end() && !(a_close_key < it2->first) ) {
   if( !(a_close_key < it2->first) && !(it2->first < a_close_key) ) {
      //Equivalency is not ==, but its what used in std::map
      found=true;
      break;
   }
   it2++;
}
if( found ) {
   //.... use it2
}

Inside if( found ) block your iterator it2 value should be same as if you called map_elements.lower_bound(a_close_key)

Upvotes: 1

Jerry Coffin
Jerry Coffin

Reputation: 490168

If you're sure it's really nearby, you could use std::find (instead of map::find) to do a linear search for the item. If it's within approximately log(N) items of the current position, this is likely to be a win (where N is the number of items in the map).

Also note that you'll have to figure out whether you want a search before or after the current position, and specify current, end() if it's after, and begin(), current if it's before. If it's before, you'll want to do a reverse search (find_end, if memory serves) since the target is presumably close to the end of that range.

Upvotes: 3

Related Questions