Unordered associative containers (C++)

History

The first widely used implementation of hash tables in the C++ language was hash_map, hash_set, hash_multimap, hash_multiset class templates of the Silicon Graphics (SGI) Standard Template Library (STL). Due to their usefulness, they were later included in several other implementations of the C++ Standard Library (e.g., the GNU Compiler Collection's (GCC) libstdc++ and the Visual C++ (MSVC) standard library).

The hash_* class templates were proposed into C++ Technical Report 1 (C++ TR1) and were accepted under names unordered_*. Later, they were incorporated into the C++11 revision of the C++ standard. An implementation is also available in the Boost C++ Libraries as ``.

Overview of functions

The containers are defined in headers named after the names of the containers, e.g., unordered_set is defined in header ``. All containers satisfy the requirements of the Container concept, which means they have begin(), end(), size(), max_size(), empty(), and swap() methods.

Usage example

import std;

using std::string;
using std::unordered_map;

const unordered_map<string, int> MONTHS {
    {"January", 31},
    {"February", 28},
    {"March", 31},
    {"April", 30},
    {"May", 31},
    {"June", 30},
    {"July", 31},
    {"August", 31},
    {"September", 30},
    {"October", 31},
    {"November", 30},
    {"December", 31}
};
 
int main(int argc, char* argv[]) {
    std::println("September -> {}", MONTHS["September"]);
    std::println("April -> {}", MONTHS["April"]);
    std::println("December -> {}", MONTHS["December"]);
    std::println("February -> {}", MONTHS["February"]);
    return 0;
}

Custom hash functions

To use custom objects in std::unordered_map, a custom hasher must be defined. This function takes a const reference to the custom type and returns a size_t.

import std;

using std::hash;
 
struct Vector3 {
    int i;
    int j;
    int k;
};

struct HashVector3 {
    size_t operator()(const Vector3& x) const {
        return hash<int>()(x.i) ^ hash<int>()(x.j) ^ hash<int>()(x.k);
    }
};

The user defined function can be used as is in std::unordered_map, by passing it as a template parameter

unordered_map<Vector3, int, HashVector3> myPointToIntMap;

Or can be set as the default hash function by specializing std::hash:

namespace std {
    template <>
    class hash<Vector3> {
    public:
        size_t operator()(const Vector3& x) const {
            return hash<int>()(x.i) ^ hash<int>()(x.j) ^ hash<int>()(x.k);
        }
    };
}

//...
unordered_map<Vector3, int> myPointToIntMap;

References

References

1. "hash_map<Key, Data, HashFcn, EqualKey, Alloc>". [[Silicon Graphics]] (SGI).
2. "libstdc++: hash_map Class Template Reference".
3. Austern, Matthew. (9 April 2003). "A Proposal to Add Hash Tables to the Standard Library (revision 4)".
4. Becker, Pete. (21 August 2010). "Working Draft, Standard for Programming Language C++".
5. "Class template unordered_map". Boost.