]>
Commit | Line | Data |
---|---|---|
7c673cae FG |
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 | [def __hash-table__ [@http://en.wikipedia.org/wiki/Hash_table | |
6 | hash table]] | |
7 | [def __hash-function__ [@http://en.wikipedia.org/wiki/Hash_function | |
8 | hash function]] | |
9 | ||
10 | [section:intro Introduction] | |
11 | ||
12 | For accessing data based on key lookup, the C++ standard library offers `std::set`, | |
13 | `std::map`, `std::multiset` and `std::multimap`. These are generally | |
14 | implemented using balanced binary trees so that lookup time has | |
15 | logarithmic complexity. That is generally okay, but in many cases a | |
16 | __hash-table__ can perform better, as accessing data has constant complexity, | |
17 | on average. The worst case complexity is linear, but that occurs rarely and | |
18 | with some care, can be avoided. | |
19 | ||
20 | Also, the existing containers require a 'less than' comparison object | |
21 | to order their elements. For some data types this is impossible to implement | |
22 | or isn't practical. In contrast, a hash table only needs an equality function | |
23 | and a hash function for the key. | |
24 | ||
25 | With this in mind, unordered associative containers were added to the C++ | |
26 | standard. This is an implementation of the containers described in C++11, | |
27 | with some [link unordered.compliance deviations from the standard] in | |
28 | order to work with non-C++11 compilers and libraries. | |
29 | ||
30 | `unordered_set` and `unordered_multiset` are defined in the header | |
31 | <[headerref boost/unordered_set.hpp]> | |
32 | ||
33 | namespace boost { | |
34 | template < | |
35 | class Key, | |
36 | class Hash = ``[classref boost::hash]``<Key>, | |
37 | class Pred = std::equal_to<Key>, | |
38 | class Alloc = std::allocator<Key> > | |
39 | class ``[classref boost::unordered_set unordered_set]``; | |
40 | ||
41 | template< | |
42 | class Key, | |
43 | class Hash = ``[classref boost::hash]``<Key>, | |
44 | class Pred = std::equal_to<Key>, | |
45 | class Alloc = std::allocator<Key> > | |
46 | class ``[classref boost::unordered_multiset unordered_multiset]``; | |
47 | } | |
48 | ||
49 | `unordered_map` and `unordered_multimap` are defined in the header | |
50 | <[headerref boost/unordered_map.hpp]> | |
51 | ||
52 | namespace boost { | |
53 | template < | |
54 | class Key, class Mapped, | |
55 | class Hash = ``[classref boost::hash]``<Key>, | |
56 | class Pred = std::equal_to<Key>, | |
57 | class Alloc = std::allocator<std::pair<Key const, Mapped> > > | |
58 | class ``[classref boost::unordered_map unordered_map]``; | |
59 | ||
60 | template< | |
61 | class Key, class Mapped, | |
62 | class Hash = ``[classref boost::hash]``<Key>, | |
63 | class Pred = std::equal_to<Key>, | |
64 | class Alloc = std::allocator<std::pair<Key const, Mapped> > > | |
65 | class ``[classref boost::unordered_multimap unordered_multimap]``; | |
66 | } | |
67 | ||
68 | When using Boost.TR1, these classes are included from `<unordered_set>` and | |
69 | `<unordered_map>`, with the classes added to the `std::tr1` namespace. | |
70 | ||
71 | The containers are used in a similar manner to the normal associative | |
72 | containers: | |
73 | ||
74 | [import src_code/intro.cpp] | |
75 | [intro_example1_2] | |
76 | ||
77 | But since the elements aren't ordered, the output of: | |
78 | ||
79 | [intro_example1_3] | |
80 | ||
81 | can be in any order. For example, it might be: | |
82 | ||
83 | two,2 | |
84 | one,1 | |
85 | three,3 | |
86 | ||
87 | To store an object in an unordered associative container requires both an | |
88 | key equality function and a hash function. The default function objects in | |
89 | the standard containers support a few basic types including integer types, | |
90 | floating point types, pointer types, and the standard strings. Since | |
91 | Boost.Unordered uses [classref boost::hash] it also supports some other types, | |
92 | including standard containers. To use any types not supported by these methods | |
93 | you have to [link hash.custom extend Boost.Hash to support the type] or use | |
94 | your own custom equality predicates and hash functions. See the | |
95 | [link unordered.hash_equality Equality Predicates and Hash Functions] section | |
96 | for more details. | |
97 | ||
98 | There are other differences, which are listed in the | |
99 | [link unordered.comparison Comparison with Associative Containers] section. | |
100 | ||
101 | [endsect] |