Searching a multimap in reverse order

Is there a method for searching a multimap (开发者_StackOverflowC/C++ STL) in reverse order in logarithmic complexity ?

Your question can be interpreted two ways. If you mean that you've inserted a bunch of elements with the same key and you want to find the last-inserted element with that key, then you can try equal_range(key), which returns a pair of iterators (one pointing to the first element, the other the last). However I don't know if multimap gives any guarantees about the order in which elements with the same key are stored.

ALternatively, if you mean you want to traverse the multimap in reverse order, you can use rbegin() and rend() to get reverse iterators.

I'm pretty sure that since a multimap is basically a tree representation, the only search mechanism is to traverse the tree - there's no "forward" and "backward".

You can find the first matching element with lower_bound, one past the last match with upper_bound, or the full range that matches a key with equal_range. EDIT: All of these methods run in logarithmic complexity.

Could you go into more detail about what you need?

I am guessing that you are looking for a search algorithm to locate a key in a std::multimap, that

1. guarantees O(log n) to locate any key in a multimap of n keys

2. guarantees O(1) to locate the key that is the largest key held by the multimap

There is no such thing built-in. Most (all?) multimaps are implemented as balanced trees, and the call to multimap::find() tests the middle of the map first, since that's where the root of the tree is. You can see for yourself if you implement a noisy operator<.

Would simply testing the key pointed to by rbegin() before calling multimap::find() satisfy your requirements?

If by "last inserted" you actually meant the element most recently added to the map, then there is no way to find it at all, multimap and other associative containers do not retain the information about the order of insertion.

You could just use upper_bound and lower_bound as normal but reverse your iteration code.

The last matching element is found with:

ub = m.upper_bound(1);
lb = m.lower_bound(1);
if (ub != lb) {
  --ub;
  return ub->second;
}

Or with just one lookup:

ub = m.upper_bound(1);
if (ub != m.begin()) {
  --ub;
  if (ub->first == 1) {
    return ub->second;
  }
}