EDIT: According to StackOverflow, it should be “C++ standard library” instead of “STL”.
In C++11, there are some new container classes in the STL. One that is pretty useful in competitive programming (at least IMO) is unordered_map, which is essentially a hashmap, in which queries and insertions can be made in O(1) time.
For builtin data types, the syntax works pretty much the same as the ordinary map. However, for custom classes and structs, a hash function needs to be defined instead of a custom comparator, as shown in the code below:
struct S { int x, y, z; };
namespace std {
template <> struct hash<S> {
size_t operator()(const S &s) const {
int hash = 17;
hash = hash * 31 + hash<int>()(s.x);
hash = hash * 31 + hash<int>()(s.y);
hash = hash * 31 + hash<int>()(s.z);
return hash;
}
};
}
The hash method used is the Bernstein Hash, which, according to various sources, works pretty well in practice, though no one exactly understands why.
For more information about hash functions, this link is a good read.