STL Lookups


 
If you want fast lookups using STL, you currently have two choices:
 
1) Use a sorted container, like [multi]set or [multi]map and the find() member function
2) Use a non-sorted container, sort it (using std::sort() or similar function), and search using std::binary_search() (or lower_bound() et al)
 
Both of these options provide log N search performance, which is nothing to sniff at. But there’s a potentially much faster option: hash tables. Hash tables can provide constant-time lookup performance in the best case. The tradeoff is that worst case performance is linear. Unfortunately, the STL doesn’t provide hash tables. This makes me sad.
 
Hash tables were originally proposed for the C++ Standard over 10 years ago, but weren’t adopted, primarily because the proposed interface was still too new and unproven.
 
Some vendors have provided non-standard solutions, but with TR1, there’s a new option, very likely to be adopted into the new version of C++ Standard within the next couple of years. That new option has an exciting new name. Wait for it …
Unordered associative containers
OK, maybe not so exciting. What is exciting is that now there’s a third option for doing fast lookups. These containers have lots of interesting dials and levers — more so than sets or maps — that allow you to tweak the size/space tradeoff for maximum performance. This makes me happy. More next time.
 
Advertisements
This entry was posted in C++. Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s