3 Copyright Daniel James 2005-2009
4 Distributed under the Boost Software License, Version 1.0. (See accompanying
5 file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
9 <section id=
"hash.reference.specification">
10 <para>For the full specification, see section
6.3 of the
11 <ulink url=
"http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2005/n1836.pdf">C++ Standard Library Technical Report
</ulink>
13 <ulink url=
"http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2005/n1837.pdf">Library Extension Technical Report Issues List
</ulink> (page
63).
16 <header name=
"boost/functional/hash.hpp">
18 Defines
<code><classname>boost::hash
</classname></code>,
22 <namespace name=
"boost">
30 <template-type-parameter name=
"T"/>
33 <inherit access=
"public">
34 <classname>std::unary_function
<T, std::size_t
></classname>
37 <purpose><simpara>A
<ulink url=
"http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2005/n1836.pdf">TR1
</ulink> compliant hash function object.
</simpara></purpose>
39 <method name=
"operator()" cv=
"const">
40 <type>std::size_t
</type>
41 <parameter name=
"val">
42 <paramtype>T const
&</paramtype>
45 <programlisting><functionname>hash_value
</functionname>(val)
</programlisting>
49 The call to
<code><functionname>hash_value
</functionname></code>
50 is unqualified, so that custom overloads can be
51 found via argument dependent lookup.
54 This is not defined when the macro
<code>BOOST_HASH_NO_EXTENSIONS
</code>
55 is defined. The specializations are still defined, so only the specializations
56 required by TR1 are defined.
61 <code><functionname>hash_value
</functionname>(T)
</code> throws.
66 <struct-specialization name=
"hash">
69 <template-arg>bool
</template-arg>
71 <method name=
"operator()" cv=
"const">
72 <type>std::size_t
</type>
73 <parameter name=
"val">
74 <paramtype>bool
</paramtype>
77 <para>Unspecified in TR1, except that equal arguments yield the same result.
</para>
78 <para><functionname>hash_value
</functionname>(val) in Boost.
</para>
80 <throws><para>Doesn't throw
</para></throws>
82 </struct-specialization>
84 <struct-specialization name=
"hash">
87 <template-arg>char
</template-arg>
89 <method name=
"operator()" cv=
"const">
90 <type>std::size_t
</type>
91 <parameter name=
"val">
92 <paramtype>char
</paramtype>
95 <para>Unspecified in TR1, except that equal arguments yield the same result.
</para>
96 <para><functionname>hash_value
</functionname>(val) in Boost.
</para>
98 <throws><para>Doesn't throw
</para></throws>
100 </struct-specialization>
102 <struct-specialization name=
"hash">
103 <template></template>
105 <template-arg>signed char
</template-arg>
107 <method name=
"operator()" cv=
"const">
108 <type>std::size_t
</type>
109 <parameter name=
"val">
110 <paramtype>signed char
</paramtype>
113 <para>Unspecified in TR1, except that equal arguments yield the same result.
</para>
114 <para><functionname>hash_value
</functionname>(val) in Boost.
</para>
116 <throws><para>Doesn't throw
</para></throws>
118 </struct-specialization>
120 <struct-specialization name=
"hash">
121 <template></template>
123 <template-arg>unsigned char
</template-arg>
125 <method name=
"operator()" cv=
"const">
126 <type>std::size_t
</type>
127 <parameter name=
"val">
128 <paramtype>unsigned char
</paramtype>
131 <para>Unspecified in TR1, except that equal arguments yield the same result.
</para>
132 <para><functionname>hash_value
</functionname>(val) in Boost.
</para>
134 <throws><para>Doesn't throw
</para></throws>
136 </struct-specialization>
138 <struct-specialization name=
"hash">
139 <template></template>
141 <template-arg>wchar_t
</template-arg>
143 <method name=
"operator()" cv=
"const">
144 <type>std::size_t
</type>
145 <parameter name=
"val">
146 <paramtype>wchar_t
</paramtype>
149 <para>Unspecified in TR1, except that equal arguments yield the same result.
</para>
150 <para><functionname>hash_value
</functionname>(val) in Boost.
</para>
152 <throws><para>Doesn't throw
</para></throws>
154 </struct-specialization>
156 <struct-specialization name=
"hash">
157 <template></template>
159 <template-arg>short
</template-arg>
161 <method name=
"operator()" cv=
"const">
162 <type>std::size_t
</type>
163 <parameter name=
"val">
164 <paramtype>short
</paramtype>
167 <para>Unspecified in TR1, except that equal arguments yield the same result.
</para>
168 <para><functionname>hash_value
</functionname>(val) in Boost.
</para>
170 <throws><para>Doesn't throw
</para></throws>
172 </struct-specialization>
174 <struct-specialization name=
"hash">
175 <template></template>
177 <template-arg>unsigned short
</template-arg>
179 <method name=
"operator()" cv=
"const">
180 <type>std::size_t
</type>
181 <parameter name=
"val">
182 <paramtype>unsigned short
</paramtype>
185 <para>Unspecified in TR1, except that equal arguments yield the same result.
</para>
186 <para><functionname>hash_value
</functionname>(val) in Boost.
</para>
188 <throws><para>Doesn't throw
</para></throws>
190 </struct-specialization>
192 <struct-specialization name=
"hash">
193 <template></template>
195 <template-arg>int
</template-arg>
197 <method name=
"operator()" cv=
"const">
198 <type>std::size_t
</type>
199 <parameter name=
"val">
200 <paramtype>int
</paramtype>
203 <para>Unspecified in TR1, except that equal arguments yield the same result.
</para>
204 <para><functionname>hash_value
</functionname>(val) in Boost.
</para>
206 <throws><para>Doesn't throw
</para></throws>
208 </struct-specialization>
210 <struct-specialization name=
"hash">
211 <template></template>
213 <template-arg>unsigned int
</template-arg>
215 <method name=
"operator()" cv=
"const">
216 <type>std::size_t
</type>
217 <parameter name=
"val">
218 <paramtype>unsigned int
</paramtype>
221 <para>Unspecified in TR1, except that equal arguments yield the same result.
</para>
222 <para><functionname>hash_value
</functionname>(val) in Boost.
</para>
224 <throws><para>Doesn't throw
</para></throws>
226 </struct-specialization>
228 <struct-specialization name=
"hash">
229 <template></template>
231 <template-arg>long
</template-arg>
233 <method name=
"operator()" cv=
"const">
234 <type>std::size_t
</type>
235 <parameter name=
"val">
236 <paramtype>long
</paramtype>
239 <para>Unspecified in TR1, except that equal arguments yield the same result.
</para>
240 <para><functionname>hash_value
</functionname>(val) in Boost.
</para>
242 <throws><para>Doesn't throw
</para></throws>
244 </struct-specialization>
246 <struct-specialization name=
"hash">
247 <template></template>
249 <template-arg>unsigned long
</template-arg>
251 <method name=
"operator()" cv=
"const">
252 <type>std::size_t
</type>
253 <parameter name=
"val">
254 <paramtype>unsigned long
</paramtype>
257 <para>Unspecified in TR1, except that equal arguments yield the same result.
</para>
258 <para><functionname>hash_value
</functionname>(val) in Boost.
</para>
260 <throws><para>Doesn't throw
</para></throws>
262 </struct-specialization>
264 <struct-specialization name=
"hash">
265 <template></template>
267 <template-arg>long long
</template-arg>
269 <method name=
"operator()" cv=
"const">
270 <type>std::size_t
</type>
271 <parameter name=
"val">
272 <paramtype>long long
</paramtype>
275 <para>Unspecified in TR1, except that equal arguments yield the same result.
</para>
276 <para><functionname>hash_value
</functionname>(val) in Boost.
</para>
278 <throws><para>Doesn't throw
</para></throws>
280 </struct-specialization>
282 <struct-specialization name=
"hash">
283 <template></template>
285 <template-arg>unsigned long long
</template-arg>
287 <method name=
"operator()" cv=
"const">
288 <type>std::size_t
</type>
289 <parameter name=
"val">
290 <paramtype>unsigned long long
</paramtype>
293 <para>Unspecified in TR1, except that equal arguments yield the same result.
</para>
294 <para><functionname>hash_value
</functionname>(val) in Boost.
</para>
296 <throws><para>Doesn't throw
</para></throws>
298 </struct-specialization>
300 <struct-specialization name=
"hash">
301 <template></template>
303 <template-arg>float
</template-arg>
305 <method name=
"operator()" cv=
"const">
306 <type>std::size_t
</type>
307 <parameter name=
"val">
308 <paramtype>float
</paramtype>
311 <para>Unspecified in TR1, except that equal arguments yield the same result.
</para>
312 <para><functionname>hash_value
</functionname>(val) in Boost.
</para>
314 <throws><para>Doesn't throw
</para></throws>
316 </struct-specialization>
318 <struct-specialization name=
"hash">
319 <template></template>
321 <template-arg>double
</template-arg>
323 <method name=
"operator()" cv=
"const">
324 <type>std::size_t
</type>
325 <parameter name=
"val">
326 <paramtype>double
</paramtype>
329 <para>Unspecified in TR1, except that equal arguments yield the same result.
</para>
330 <para><functionname>hash_value
</functionname>(val) in Boost.
</para>
332 <throws><para>Doesn't throw
</para></throws>
334 </struct-specialization>
336 <struct-specialization name=
"hash">
337 <template></template>
339 <template-arg>long double
</template-arg>
341 <method name=
"operator()" cv=
"const">
342 <type>std::size_t
</type>
343 <parameter name=
"val">
344 <paramtype>long double
</paramtype>
347 <para>Unspecified in TR1, except that equal arguments yield the same result.
</para>
348 <para><functionname>hash_value
</functionname>(val) in Boost.
</para>
350 <throws><para>Doesn't throw
</para></throws>
352 </struct-specialization>
354 <struct-specialization name=
"hash">
355 <template></template>
357 <template-arg>std::string
</template-arg>
359 <method name=
"operator()" cv=
"const">
360 <type>std::size_t
</type>
361 <parameter name=
"val">
362 <paramtype>std::string const
&</paramtype>
365 <para>Unspecified in TR1, except that equal arguments yield the same result.
</para>
366 <para><functionname>hash_value
</functionname>(val) in Boost.
</para>
368 <throws><para>Doesn't throw
</para></throws>
370 </struct-specialization>
372 <struct-specialization name=
"hash">
373 <template></template>
375 <template-arg>std::wstring
</template-arg>
377 <method name=
"operator()" cv=
"const">
378 <type>std::size_t
</type>
379 <parameter name=
"val">
380 <paramtype>std::wstring const
&</paramtype>
383 <para>Unspecified in TR1, except that equal arguments yield the same result.
</para>
384 <para><functionname>hash_value
</functionname>(val) in Boost.
</para>
386 <throws><para>Doesn't throw
</para></throws>
388 </struct-specialization>
390 <struct-specialization name=
"hash">
392 <template-type-parameter name=
"T"/>
395 <template-arg>T*
</template-arg>
397 <method name=
"operator()" cv=
"const">
398 <type>std::size_t
</type>
399 <parameter name=
"val">
400 <paramtype>T*
</paramtype>
403 <para>Unspecified in TR1, except that equal arguments yield the same result.
</para>
405 <throws><para>Doesn't throw
</para></throws>
407 </struct-specialization>
409 <free-function-group name=
"Support functions (Boost extension).">
415 <function name=
"hash_combine">
417 <template-type-parameter name=
"T"/>
420 <parameter name=
"seed"><paramtype>size_t
&</paramtype></parameter>
421 <parameter name=
"v"><paramtype>T const
&</paramtype></parameter>
423 Called repeatedly to incrementally create a hash value from
426 <effects><programlisting>seed ^=
<functionname>hash_value
</functionname>(v) +
0x9e3779b9 + (seed
<< 6) + (seed
>> 2);
</programlisting></effects>
428 <para><functionname>hash_value
</functionname> is called without
429 qualification, so that overloads can be found via ADL.
</para>
430 <para>This is an extension to TR1
</para>
433 Only throws if
<functionname>hash_value
</functionname>(T) throws.
434 Strong exception safety, as long as
<functionname>hash_value
</functionname>(T)
435 also has strong exception safety.
443 <overloaded-function name=
"hash_range">
446 <template-type-parameter name=
"It"/>
448 <type>std::size_t
</type>
449 <parameter name=
"first"><paramtype>It
</paramtype></parameter>
450 <parameter name=
"last"><paramtype>It
</paramtype></parameter>
455 <template-type-parameter name=
"It"/>
458 <parameter name=
"seed"><paramtype>std::size_t
&</paramtype></parameter>
459 <parameter name=
"first"><paramtype>It
</paramtype></parameter>
460 <parameter name=
"last"><paramtype>It
</paramtype></parameter>
464 Calculate the combined hash value of the elements of an iterator
468 <para>For the two argument overload:
472 for(; first != last; ++first)
474 <functionname>hash_combine
</functionname>(seed, *first);
479 </para>For the three arguments overload:
481 for(; first != last; ++first)
483 <functionname>hash_combine
</functionname>(seed, *first);
491 <code>hash_range
</code> is sensitive to the order of the elements
492 so it wouldn't be appropriate to use this with an unordered
495 <para>This is an extension to TR1
</para>
498 Only throws if
<code><functionname>hash_value
</functionname>(std::iterator_traits
<It
>::value_type)
</code>
499 throws.
<code>hash_range(std::size_t
&, It, It)
</code> has basic exception safety as long as
500 <code><functionname>hash_value
</functionname>(std::iterator_traits
<It
>::value_type)
</code>
501 has basic exception safety.
503 </overloaded-function>
505 </free-function-group>
507 <free-function-group name=
"Overloadable hash implementation (Boost extension).">
510 boost::hash_value - integers
513 <overloaded-function name=
"hash_value">
515 Implementation of the hash function.
519 <type>std::size_t
</type>
520 <parameter name=
"val"><paramtype>bool
</paramtype></parameter>
524 <type>std::size_t
</type>
525 <parameter name=
"val"><paramtype>char
</paramtype></parameter>
529 <type>std::size_t
</type>
530 <parameter name=
"val"><paramtype>signed char
</paramtype></parameter>
534 <type>std::size_t
</type>
535 <parameter name=
"val"><paramtype>unsigned char
</paramtype></parameter>
539 <type>std::size_t
</type>
540 <parameter name=
"val"><paramtype>wchar_t
</paramtype></parameter>
544 <type>std::size_t
</type>
545 <parameter name=
"val"><paramtype>short
</paramtype></parameter>
549 <type>std::size_t
</type>
550 <parameter name=
"val"><paramtype>unsigned short
</paramtype></parameter>
554 <type>std::size_t
</type>
555 <parameter name=
"val"><paramtype>int
</paramtype></parameter>
559 <type>std::size_t
</type>
560 <parameter name=
"val"><paramtype>unsigned int
</paramtype></parameter>
564 <type>std::size_t
</type>
565 <parameter name=
"val"><paramtype>long
</paramtype></parameter>
569 <type>std::size_t
</type>
570 <parameter name=
"val"><paramtype>unsigned long
</paramtype></parameter>
574 <type>std::size_t
</type>
575 <parameter name=
"val"><paramtype>long long
</paramtype></parameter>
579 <type>std::size_t
</type>
580 <parameter name=
"val"><paramtype>unsigned long long
</paramtype></parameter>
584 <type>std::size_t
</type>
585 <parameter name=
"val"><paramtype>float
</paramtype></parameter>
589 <type>std::size_t
</type>
590 <parameter name=
"val"><paramtype>double
</paramtype></parameter>
594 <type>std::size_t
</type>
595 <parameter name=
"val"><paramtype>long double
</paramtype></parameter>
599 <template><template-type-parameter name=
"T"/></template>
600 <type>std::size_t
</type>
601 <parameter name=
"val"><paramtype>T* const
&</paramtype></parameter>
606 <template-type-parameter name=
"T"/>
607 <template-nontype-parameter name=
"N"><type>unsigned
</type></template-nontype-parameter>
609 <type>std::size_t
</type>
610 <parameter><paramtype>T (
&val)[N]
</paramtype></parameter>
615 <template-type-parameter name=
"T"/>
616 <template-nontype-parameter name=
"N"><type>unsigned
</type></template-nontype-parameter>
618 <type>std::size_t
</type>
619 <parameter><paramtype>const T (
&val)[N]
</paramtype></parameter>
624 <template-type-parameter name=
"Ch"/>
625 <template-type-parameter name=
"A"/>
627 <type>std::size_t
</type>
628 <parameter name=
"val">
629 <paramtype>std::basic_string
<Ch, std::char_traits
<Ch
>, A
> const
&</paramtype>
635 <template-type-parameter name=
"A"/>
636 <template-type-parameter name=
"B"/>
638 <type>std::size_t
</type>
639 <parameter name=
"val"><paramtype>std::pair
<A, B
> const
&</paramtype></parameter>
644 <template-type-parameter name=
"T"/>
645 <template-type-parameter name=
"A"/>
647 <type>std::size_t
</type>
648 <parameter name=
"val"><paramtype>std::vector
<T, A
> const
&</paramtype></parameter>
653 <template-type-parameter name=
"T"/>
654 <template-type-parameter name=
"A"/>
656 <type>std::size_t
</type>
657 <parameter name=
"val"><paramtype>std::list
<T, A
> const
&</paramtype></parameter>
662 <template-type-parameter name=
"T"/>
663 <template-type-parameter name=
"A"/>
665 <type>std::size_t
</type>
666 <parameter name=
"val"><paramtype>std::deque
<T, A
> const
&</paramtype></parameter>
671 <template-type-parameter name=
"K"/>
672 <template-type-parameter name=
"C"/>
673 <template-type-parameter name=
"A"/>
675 <type>std::size_t
</type>
676 <parameter name=
"val"><paramtype>std::set
<K, C, A
> const
&</paramtype></parameter>
681 <template-type-parameter name=
"K"/>
682 <template-type-parameter name=
"C"/>
683 <template-type-parameter name=
"A"/>
685 <type>std::size_t
</type>
686 <parameter name=
"val"><paramtype>std::multiset
<K, C, A
> const
&</paramtype></parameter>
691 <template-type-parameter name=
"K"/>
692 <template-type-parameter name=
"T"/>
693 <template-type-parameter name=
"C"/>
694 <template-type-parameter name=
"A"/>
696 <type>std::size_t
</type>
697 <parameter name=
"val"><paramtype>std::map
<K, T, C, A
> const
&</paramtype></parameter>
702 <template-type-parameter name=
"K"/>
703 <template-type-parameter name=
"T"/>
704 <template-type-parameter name=
"C"/>
705 <template-type-parameter name=
"A"/>
707 <type>std::size_t
</type>
708 <parameter name=
"val"><paramtype>std::multimap
<K, T, C, A
> const
&</paramtype></parameter>
713 <template-type-parameter name=
"T"/>
715 <type>std::size_t
</type>
716 <parameter name=
"val"><paramtype>std::complex
<T
> const
&</paramtype></parameter>
720 Generally shouldn't be called directly by users, instead they should use
721 <classname>boost::hash
</classname>,
<functionname>boost::hash_range
</functionname>
722 or
<functionname>boost::hash_combine
</functionname> which
723 call
<code>hash_value
</code> without namespace qualification so that overloads
724 for custom types are found via ADL.
725 </para></description>
728 <para>This is an extension to TR1
</para>
732 Only throws if a user supplied version of
733 <code><functionname>hash_value
</functionname></code>
734 throws for an element of a container, or
735 one of the types stored in a pair.
744 <entry>Returns
</entry>
749 <entry><code>bool
</code>,
750 <code>char
</code>,
<code>signed char
</code>,
<code>unsigned char
</code>,
<code>wchar_t
</code>,
751 <code>short
</code>,
<code>unsigned short
</code>,
752 <code>int
</code>,
<code>unsigned int
</code>,
<code>long
</code>,
<code>unsigned long
</code>
754 <entry><code>val
</code></entry>
757 <entry><code>long long
</code>,
<code>unsigned long long
</code></entry>
758 <entry><code>val
</code> when
<code>abs(val)
<= std::numeric_limits
<std::size_t
>::max()
</code>.
</entry>
761 <entry><code>float
</code>,
<code>double
</code>,
<code>long double
</code></entry>
762 <entry>An unspecified value, except that equal arguments shall yield the same result.
</entry>
765 <entry><code>T*
</code></entry>
766 <entry>An unspecified value, except that equal arguments shall yield the same result.
</entry>
770 <code>T
 val[N]
</code>,
771 <code>const
 T
 val[N]
</code>
773 <entry><code>hash_range(val, val+N)
</code></entry>
777 <code>std:basic_string
<Ch,
 std::char_traits
<Ch
>,
 A
></code>,
778 <code>std::vector
<T,
 A
></code>,
779 <code>std::list
<T,
 A
></code>,
780 <code>std::deque
<T,
 A
></code>,
781 <code>std::set
<K,
 C,
 A
></code>,
782 <code>std::multiset
<K,
 C,
 A
></code>,
783 <code>std::map
<K,
 T,
 C,
 A
></code>,
784 <code>std::multimap
<K,
 T,
 C,
 A
></code>
786 <entry><code>hash_range(val.begin(), val.end())
</code></entry>
789 <entry><code>std::pair
<A, B
></code></entry>
790 <entry><programlisting>size_t seed =
0;
791 <functionname>hash_combine
</functionname>(seed, val.first);
792 <functionname>hash_combine
</functionname>(seed, val.second);
793 return seed;
</programlisting></entry>
797 <code>std::complex
<T
></code>
799 <entry>When
<code>T
</code> is a built in type and
<code>val.imag() ==
0</code>, the result is equal to
<code>hash_value(val.real())
</code>. Otherwise an unspecified value, except that equal arguments shall yield the same result.
</entry>
805 </overloaded-function>
806 </free-function-group>