Fastest way to determine whether an element is contained in a multimap?

Question

Assume a multimap<string, string>. I want to test whether an element, say pair<string, string>("foo", "bar") is contained. Sure I can go with something like

auto range(myMap.equal_range("foo"));
auto it = find(range.first, range.second, pair<string, string>("foo", "bar"));

but that would mean linear search within range. Since the multimap should be ordered I would prefer to benefit from the order and search with logarithmic complexity. Is that possible?

Answer 1

If this is a typical pattern of access, I would say that the multimap is the wrong container?

Something like the following may be more appropriate?

std::map<std::string, std::set<std::string>>

Okay, insertion and removal is more complex, but a find matches the requirements that you have.

Answer 2

You want to simply use find():

 multimap<T> m;
 T t;
 // ...
 multimap<T>::iterator r = m.find(t);
 if (r != m.end()) {
     // hit
 }

Answer 3

There are no guarantees on the relative order of elements with equivalent keys in C++98 so depending on your build environment, you're looking at linear complexity for searching the range.

You could use a custom multimap by creating a map that maps to a set:

// std namespace removed for brevity
map< string, set<string> > myMap;

This might be useful if you expect lots of values with the same keys. Otherwise, your original solution looks nicer as iterating this isn't as clean. Should write a function for searching this container.

Answer 4

Multimaps are typically implemented as red-black trees (GNU C++ does this). Doing a search on them through their iterators will thus be O(log n).