...one of the most highly
regarded and expertly designed C++ library projects in the
world.
— Herb Sutter and Andrei
Alexandrescu, C++
Coding Standards
While the associative containers use an ordering relation to specify how the
elements are stored, the unordered associative containers use an equality predicate
and a hash function. For example, boost::unordered_map
is declared as:
template < class Key, class Mapped, class Hash =boost::hash
<Key>, class Pred = std::equal_to<Key>, class Alloc = std::allocator<std::pair<Key const, Mapped> > > classunordered_map
;
The hash function comes first as you might want to change the hash function but not the equality predicate. For example, if you wanted to use the FNV-1 hash you could write:
boost::unordered_map<std::string, int, hash::fnv_1> dictionary;
There is an implementation of FNV-1 in the examples directory.
If you wish to use a different equality function, you will also need to use a matching hash function. For example, to implement a case insensitive dictionary you need to define a case insensitive equality predicate and hash function:
struct iequal_to { bool operator()(std::string const& x, std::string const& y) const { return boost::algorithm::iequals(x, y, std::locale()); } }; struct ihash { std::size_t operator()(std::string const& x) const { std::size_t seed = 0; std::locale locale; for(std::string::const_iterator it = x.begin(); it != x.end(); ++it) { boost::hash_combine(seed, std::toupper(*it, locale)); } return seed; } };
Which you can then use in a case insensitive dictionary:
boost::unordered_map<std::string, int, ihash, iequal_to> idictionary;
This is a simplified version of the example at /libs/unordered/examples/case_insensitive.hpp which supports other locales and string types.
Caution | |
---|---|
Be careful when using the equality ( |
Similarly, a custom hash function can be used for custom types:
struct point { int x; int y; }; bool operator==(point const& p1, point const& p2) { return p1.x == p2.x && p1.y == p2.y; } struct point_hash { std::size_t operator()(point const& p) const { std::size_t seed = 0; boost::hash_combine(seed, p.x); boost::hash_combine(seed, p.y); return seed; } }; boost::unordered_multiset<point, point_hash> points;
Since the default hash function is Boost.Hash, we can extend it to support the type so that the hash function doesn't need to be explicitly given:
struct point { int x; int y; }; bool operator==(point const& p1, point const& p2) { return p1.x == p2.x && p1.y == p2.y; } std::size_t hash_value(point const& p) { std::size_t seed = 0; boost::hash_combine(seed, p.x); boost::hash_combine(seed, p.y); return seed; } // Now the default function objects work. boost::unordered_multiset<point> points;
See the Boost.Hash documentation for more detail on how to do this. Remember that it relies on extensions to the draft standard - so it won't work for other implementations of the unordered associative containers, you'll need to explicitly use Boost.Hash.
Table 44.3. Methods for accessing the hash and equality functions.
Method |
Description |
---|---|
|
Returns the container's hash function. |
|
Returns the container's key equality function. |