Note: STL here refers to SGI STL , not to be confused with the C++ Standard Library , which only recently include hash maps/sets in C++11 . For pre-C++11 users, hash maps/sets are included under the name unordered_map/unordered_set in std::tr1 as explained in the article:
From: http://www.drdobbs.com/cpp/c-stl-hash-containers-and-performance/198800559
tl;dr:
hash_maps store key/value pairs that have unique keys. hash_sets store unique values. hash_multimaps store key/value pairs with nonunique keys. hash_multisets store nonunique values When to use hash functions: =========================== trade offs - how often do the key/value pair change vs frequency & performance of accesses vs memory allocation Hash function: ============== Most primitives hash to themselves: integers, characters, and longs all simply cast to size_t SizeTCastHasher - hash based on memory location ShiftedPairHasher - hash a pair of integers (bitwise shift first integer, then XOR, to fit both integers in a size_t) Memory allocation: ================== Map --> RB tree , a few pointers, Hashmap - 193 buckets Must Benchmark: =============== Hash function calculation time vs hash function collision resolution Boost: ====== hash_combine