ceph/src/boost/libs/unordered/doc/hash_equality.qbk

   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
   7 While the associative containers use an ordering relation to specify how the
   8 elements are stored, the unordered associative containers use an equality
   9 predicate and a hash function. For example, [classref boost::unordered_map]
  10 is 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
  19 The hash function comes first as you might want to change the hash function
  20 but 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
  26 There is an [@boost:/libs/unordered/examples/fnv1.hpp implementation
  27 of FNV-1] in the examples directory.
  28
  29 If you wish to use a different equality function,
  30 you will also need to use a matching hash function. For
  31 example, to implement a case insensitive dictionary you need to define a
  32 case insensitive equality predicate and hash function:
  33
  34 [case_insensitive_functions]
  35
  36 Which you can then use in a case insensitive dictionary:
  37
  38 [case_insensitive_dictionary]
  39
  40 This is a simplified version of the example at
  41 [@boost:/libs/unordered/examples/case_insensitive.hpp /libs/unordered/examples/case_insensitive.hpp]
  42 which supports other locales and string types.
  43
  44 [caution
  45 Be careful when using the equality (`==`) operator with custom equality
  46 predicates, especially if you're using a function pointer. If you compare two
  47 containers with different equality predicates then the result is undefined.
  48 For most stateless function objects this is impossible - since you can only
  49 compare objects with the same equality predicate you know the equality
  50 predicates must be equal. But if you're using function pointers or a stateful
  51 equality predicate (e.g. boost::function) then you can get into trouble.
  52 ]
  53
  54 [h2 Custom Types]
  55
  56 Similarly, a custom hash function can be used for custom types:
  57
  58 [import src_code/point1.cpp]
  59 [point_example1]
  60
  61 Since the default hash function is [link hash Boost.Hash],
  62 we can [link hash.custom extend it to support the type]
  63 so that the hash function doesn't need to be explicitly given:
  64
  65 [import src_code/point2.cpp]
  66 [point_example2]
  67
  68 See the [link hash.custom Boost.Hash documentation] for more detail on how to
  69 do this.  Remember that it relies on extensions to the draft standard - so it
  70 won't work for other implementations of the unordered associative containers,
  71 you'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]