Fastest way to speed up map<string,int> .find() in c++ . Where the keys are in alphabetical order

Question

I have a map with about 100,000 pairs . Is there any way that i can speed up searching when using find(), given that the keys are in alphabetical order. Also how should i go about doing it. I know that you can specify a new comparator when you create the map. But will that speed up the find() function at all?

Thanks in advance.

[solved] Thanks a bunch guys i have decided to go with a vector and use lower and upperbound to "snip" some of the searching.

Also i am new here is there any way to mark this question as answered , or pick a best answer?

Answer 1

A different comparator will only speed up find if it manages to do the comparison faster (which, for strings will usually be pretty difficult).

If you're basically inserting all the data in order, then doing the searching, it may be faster to use a std::vector with std::lower_bound or std::upper_bound.

If you don't really care about ordering, and just want to find the data as quickly as possible, you might find that std::unordered_map works better for you.

Edit: Just for the record: the way you "might find" or "may find" those things is normally by profiling. Depending on the situation, it might be enough faster that it's pretty obvious even in simple testing, so profiling isn't really necessary, but if there's (much) doubt, or you want to quantify the effect, a profiler is probably the right way to do it.

Answer 2

std::map is already taking advantage of the fact the keys are in alphabetical order - it guarantees that itself. You aren't going to be able to improve it by changing the comparator (one assumes it's already a reasonably efficient string comparison).

Have you considered using unordered_map (aka hash_map in various implementations pre C++11? It should be able to search in O(1) instead of O(log(n)) for std::map.

You could also look into something slightly more exotic, like a trie, but that's not part of the standard library so you'd either have to find one elsewhere or roll your own, so I'd suggest unordered_map is a good place to start.

Answer 3

If you're using std::find to find elements, you should switch to using map::find (you don't really say in your question.) map::find uses the fact that the map is ordered to search much faster.

If that's still not good enough, you might look into a hash container such as unordered_map rather than map.