ceph/src/boost/libs/functional/hash/doc/tutorial.qbk

   1
   2 [/ Copyright 2005-2008 Daniel James.
   3  / Distributed under the Boost Software License, Version 1.0. (See accompanying
   4  / file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt) ]
   5
   6 [def __multi-index-short__ [@boost:/libs/multi_index/doc/index.html
   7     Boost.MultiIndex]]
   8
   9 [section:tutorial Tutorial]
  10
  11 When using a hash index with __multi-index-short__, you don't need to do
  12 anything to use [classref boost::hash] as it uses it by default.
  13 To find out how to use a user-defined type, read the
  14 [link hash.custom section on extending boost::hash for a custom data type].
  15
  16 If your standard library supplies its own implementation of the unordered
  17 associative containers and you wish to use
  18 [classref boost::hash], just use an extra template parameter:
  19
  20     std::unordered_multiset<int, ``[classref boost::hash]``<int> >
  21             set_of_ints;
  22
  23     std::unordered_set<std::pair<int, int>, ``[classref boost::hash]``<std::pair<int, int> >
  24             set_of_pairs;
  25
  26     std::unordered_map<int, std::string, ``[classref boost::hash]``<int> > map_int_to_string;
  27
  28 To use [classref boost::hash] directly, create an instance and call it as a function:
  29
  30     #include <``[headerref boost/functional/hash.hpp]``>
  31
  32     int main()
  33     {
  34         ``[classref boost::hash]``<std::string> string_hash;
  35
  36         std::size_t h = string_hash("Hash me");
  37     }
  38
  39 For an example of generic use, here is a function to generate a vector
  40 containing the hashes of the elements of a container:
  41
  42     template <class Container>
  43     std::vector<std::size_t> get_hashes(Container const& x)
  44     {
  45         std::vector<std::size_t> hashes;
  46         std::transform(x.begin(), x.end(), std::insert_iterator(hashes),
  47             ``[classref boost::hash]``<typename Container::value_type>());
  48
  49         return hashes;
  50     }
  51
  52 [endsect]
  53
  54 [section:custom Extending boost::hash for a custom data type]
  55
  56 [classref boost::hash] is implemented by calling the function
  57 [funcref boost::hash_value hash_value].
  58 The namespace isn't specified so that it can detect overloads via argument
  59 dependant lookup. So if there is a free function `hash_value` in the same
  60 namespace as a custom type, it will get called.
  61
  62 If you have a structure `library::book`, where each `book` is uniquely
  63 defined by it's member `id`:
  64
  65     namespace library
  66     {
  67         struct book
  68         {
  69             int id;
  70             std::string author;
  71             std::string title;
  72
  73             // ....
  74         };
  75
  76         bool operator==(book const& a, book const& b)
  77         {
  78             return a.id == b.id;
  79         }
  80     }
  81
  82 Then all you would need to do is write the function `library::hash_value`:
  83
  84     namespace library
  85     {
  86         std::size_t hash_value(book const& b)
  87         {
  88             ``[classref boost::hash]``<int> hasher;
  89             return hasher(b.id);
  90         }
  91     }
  92
  93 And you can now use [classref boost::hash] with book:
  94
  95     library::book knife(3458, "Zane Grey", "The Hash Knife Outfit");
  96     library::book dandelion(1354, "Paul J. Shanley",
  97         "Hash & Dandelion Greens");
  98
  99     ``[classref boost::hash]``<library::book> book_hasher;
 100     std::size_t knife_hash_value = book_hasher(knife);
 101
 102     // If std::unordered_set is available:
 103     std::unordered_set<library::book, ``[classref boost::hash]``<library::book> > books;
 104     books.insert(knife);
 105     books.insert(library::book(2443, "Lindgren, Torgny", "Hash"));
 106     books.insert(library::book(1953, "Snyder, Bernadette M.",
 107         "Heavenly Hash: A Tasty Mix of a Mother's Meditations"));
 108
 109     assert(books.find(knife) != books.end());
 110     assert(books.find(dandelion) == books.end());
 111
 112 The full example can be found in:
 113 [@boost:/libs/functional/hash/examples/books.hpp /libs/functional/hash/examples/books.hpp]
 114 and
 115 [@boost:/libs/functional/hash/examples/books.cpp /libs/functional/hash/examples/books.cpp].
 116
 117 [tip
 118 When writing a hash function, first look at how the equality function works.
 119 Objects that are equal must generate the same hash value.
 120 When objects are not equal they should generate different hash values.
 121 In this object equality was based just on the id so the hash function
 122 only hashes the id. If it was based on the object's name and author
 123 then the hash function should take them into account
 124 (how to do this is discussed in the next section).
 125 ]
 126
 127 [endsect]
 128
 129 [section:combine Combining hash values]
 130
 131 Say you have a point class, representing a two dimensional location:
 132
 133     class point
 134     {
 135         int x;
 136         int y;
 137     public:
 138         point() : x(0), y(0) {}
 139         point(int x, int y) : x(x), y(y) {}
 140
 141         bool operator==(point const& other) const
 142         {
 143             return x == other.x && y == other.y;
 144         }
 145     };
 146
 147 and you wish to use it as the key for an `unordered_map`. You need to
 148 customise the hash for this structure. To do this we need to combine
 149 the hash values for `x` and `y`. The function
 150 [funcref boost::hash_combine] is supplied for this purpose:
 151
 152     class point
 153     {
 154         ...
 155
 156         friend std::size_t hash_value(point const& p)
 157         {
 158             std::size_t seed = 0;
 159             ``[funcref boost::hash_combine]``(seed, p.x);
 160             ``[funcref boost::hash_combine]``(seed, p.y);
 161
 162             return seed;
 163         }
 164
 165         ...
 166     };
 167
 168 Calls to hash_combine incrementally build the hash from the different members
 169 of point, it can be repeatedly called for any number of elements. It calls
 170 [funcref boost::hash_value hash_value] on the supplied element, and combines it with the seed.
 171
 172 Full code for this example is at
 173 [@boost:/libs/functional/hash/examples/point.cpp /libs/functional/hash/examples/point.cpp].
 174
 175 [note
 176 When using [funcref boost::hash_combine] the order of the
 177 calls matters.
 178 '''
 179 <programlisting>
 180     std::size_t seed = 0;
 181     boost::hash_combine(seed, 1);
 182     boost::hash_combine(seed, 2);
 183 </programlisting>
 184 results in a different seed to:
 185 <programlisting>
 186     std::size_t seed = 0;
 187     boost::hash_combine(seed, 2);
 188     boost::hash_combine(seed, 1);
 189 </programlisting>
 190 '''
 191 If you are calculating a hash value for data where the order of the data
 192 doesn't matter in comparisons (e.g. a set) you will have to ensure that the
 193 data is always supplied in the same order.
 194 ]
 195
 196 To calculate the hash of an iterator range you can use [funcref boost::hash_range]:
 197
 198     std::vector<std::string> some_strings;
 199     std::size_t hash = ``[funcref boost::hash_range]``(some_strings.begin(), some_strings.end());
 200
 201 Note that when writing template classes, you might not want to include the main
 202 hash header as it's quite an expensive include that brings in a lot of other
 203 headers, so instead you can include the `<boost/functional/hash_fwd.hpp>`
 204 header which forward declares [classref boost::hash],
 205 [funcref boost::hash_range] and [funcref boost::hash_combine]. You'll need to
 206 include the main header before instantiating [classref boost::hash]. When using
 207 a container that uses [classref boost::hash] it should do that for you, so your
 208 type will work fine with the boost hash containers. There's an example of this
 209 in [@boost:/libs/functional/hash/examples/template.hpp template.hpp] and
 210 [@boost:/libs/functional/hash/examples/template.cpp template.cpp].
 211
 212 [endsect]