1[/ Copyright 2006-2008 Daniel James. 2 / Distributed under the Boost Software License, Version 1.0. (See accompanying 3 / file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt) ] 4 5[section:hash_equality Equality Predicates and Hash Functions] 6 7While the associative containers use an ordering relation to specify how the 8elements are stored, the unordered associative containers use an equality 9predicate and a hash function. For example, [classref boost::unordered_map] 10is declared as: 11 12 template < 13 class Key, class Mapped, 14 class Hash = ``[classref boost::hash]``<Key>, 15 class Pred = std::equal_to<Key>, 16 class Alloc = std::allocator<std::pair<Key const, Mapped> > > 17 class ``[classref boost::unordered_map unordered_map]``; 18 19The hash function comes first as you might want to change the hash function 20but not the equality predicate. For example, if you wanted to use the 21[@http://www.isthe.com/chongo/tech/comp/fnv/ FNV-1 hash] you could write: 22 23[import src_code/dictionary.cpp] 24[case_sensitive_dictionary_fnv] 25 26There is an [@boost:/libs/unordered/examples/fnv1.hpp implementation 27of FNV-1] in the examples directory. 28 29If you wish to use a different equality function, 30you will also need to use a matching hash function. For 31example, to implement a case insensitive dictionary you need to define a 32case insensitive equality predicate and hash function: 33 34[case_insensitive_functions] 35 36Which you can then use in a case insensitive dictionary: 37 38[case_insensitive_dictionary] 39 40This is a simplified version of the example at 41[@boost:/libs/unordered/examples/case_insensitive.hpp /libs/unordered/examples/case_insensitive.hpp] 42which supports other locales and string types. 43 44[caution 45Be careful when using the equality (`==`) operator with custom equality 46predicates, especially if you're using a function pointer. If you compare two 47containers with different equality predicates then the result is undefined. 48For most stateless function objects this is impossible - since you can only 49compare objects with the same equality predicate you know the equality 50predicates must be equal. But if you're using function pointers or a stateful 51equality predicate (e.g. boost::function) then you can get into trouble. 52] 53 54[h2 Custom Types] 55 56Similarly, a custom hash function can be used for custom types: 57 58[import src_code/point1.cpp] 59[point_example1] 60 61Since the default hash function is [link hash Boost.Hash], 62we can [link hash.custom extend it to support the type] 63so that the hash function doesn't need to be explicitly given: 64 65[import src_code/point2.cpp] 66[point_example2] 67 68See the [link hash.custom Boost.Hash documentation] for more detail on how to 69do this. Remember that it relies on extensions to the draft standard - so it 70won't work for other implementations of the unordered associative containers, 71you'll need to explicitly use Boost.Hash. 72 73[table:access_methods Methods for accessing the hash and equality functions. 74 [[Method] [Description]] 75 76 [ 77 [`hasher hash_function() const`] 78 [Returns the container's hash function.] 79 ] 80 [ 81 [`key_equal key_eq() const`] 82 [Returns the container's key equality function.] 83 ] 84] 85 86[endsect] 87