Find in a map by value - preference of methods in terms of speed

Question

Four methods come to my mind to find in a map by value. What would be the order of preference of the methods in terms of speed?

Assuming both key and value are unique among themselves.

std::map<int, std::string> or std::unordered_map<int, std::string>

1. Use boost::bimap if boost library is available
2. Use std::find_if with a predicate/functor with some equality comparison logic
3. At the time of populating std::map<int, string>, create & populate another std::map<std::string, int> and perform a map::find on the second map.
4. Iterate through the whole map and check if (iter->second == value_to_find), if found break;

I will be performing find by key at all times and once or twice by value.

Answer 1

Options 2 and 4 are doing exactly the same thing: Iterate the whole map entry-by-entry until a matching entry is found. The runtime in both cases is O(n).

The options 1 and 3 are also equivalent. Runtime will be O(log n) for a map and O(1) for an unordered map. When you pick option 3 you are essentially reinventing the boost:bimap.

So I would recommend you to go for option 1 and use the boost:bimap when available. When boost isn't available for whatever reason, you should rebuild the functionality and use two maps and implement the code to keep them synchronized yourself.

This is, of course, all under the premise that you are going to store so many values in this data-structure that it actually matters. When the amount of entries is small, just using a std::vector and iterating it manually can actually be the superior solution in regards to speed.