<!--
Copyright 2005-2006 Daniel James.
Distributed under the Boost Software License, Version 1.0. (See accompanying
file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
-->

<library-reference>
  <section id="hash.reference.specification">
    <para>For the full specification, see section 6.3 of the
        <ulink url="http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2005/n1836.pdf">C++ Standard Library Technical Report</ulink>
        and issue 6.18 of the
        <ulink url="http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2005/n1837.pdf">Library Extension Technical Report Issues List</ulink> (page 63).
    </para>
  </section>
  <header name="boost/functional/hash.hpp">
    <para>
      Defines <code><classname>boost::hash</classname></code>,
      and helper functions.
    </para>

    <namespace name="boost">

      <!--
        boost::hash
        -->

      <struct name="hash">
        <template>
          <template-type-parameter name="T"/>
        </template>

        <inherit access="public">
          <classname>std::unary_function&lt;T, std::size_t&gt;</classname>
        </inherit>

        <purpose>A <ulink url="http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2005/n1836.pdf">TR1</ulink> compliant hash function object.</purpose>

        <method name="operator()" cv="const">
          <type>std::size_t</type>
          <parameter name="val">
            <paramtype>T const&amp;</paramtype>
          </parameter>
          <returns><para>
            <programlisting><functionname>hash_value</functionname>(val)</programlisting>
          </para></returns>
          <notes>
            <para>
              The call to <code><functionname>hash_value</functionname></code>
              is unqualified, so that custom overloads can be
              found via argument dependent lookup.
            </para>
            <para>
              This is not defined when the macro <code>BOOST_HASH_NO_EXTENSIONS</code>
              is defined. The specializations are still defined, so only the specializations
              required by TR1 are defined.
            </para>
          </notes>
          <throws><para>
            Only throws if
            <code><functionname>hash_value</functionname>(T)</code> throws.
          </para></throws>
        </method>
      </struct>

      <struct-specialization name="hash">
        <template></template>
        <specialization>
          <template-arg>bool</template-arg>
        </specialization>
        <method name="operator()" cv="const">
          <type>std::size_t</type>
          <parameter name="val">
            <paramtype>bool</paramtype>
          </parameter>
          <returns>
            <para>Unspecified in TR1, except that equal arguments yield the same result.</para>
            <para><functionname>hash_value</functionname>(val) in Boost.</para>
          </returns>
          <throws><para>Doesn't throw</para></throws>
        </method>
      </struct-specialization>

      <struct-specialization name="hash">
        <template></template>
        <specialization>
          <template-arg>char</template-arg>
        </specialization>
        <method name="operator()" cv="const">
          <type>std::size_t</type>
          <parameter name="val">
            <paramtype>char</paramtype>
          </parameter>
          <returns>
            <para>Unspecified in TR1, except that equal arguments yield the same result.</para>
            <para><functionname>hash_value</functionname>(val) in Boost.</para>
          </returns>
          <throws><para>Doesn't throw</para></throws>
        </method>
      </struct-specialization>

      <struct-specialization name="hash">
        <template></template>
        <specialization>
          <template-arg>signed char</template-arg>
        </specialization>
        <method name="operator()" cv="const">
          <type>std::size_t</type>
          <parameter name="val">
            <paramtype>signed char</paramtype>
          </parameter>
          <returns>
            <para>Unspecified in TR1, except that equal arguments yield the same result.</para>
            <para><functionname>hash_value</functionname>(val) in Boost.</para>
          </returns>
          <throws><para>Doesn't throw</para></throws>
        </method>
      </struct-specialization>

      <struct-specialization name="hash">
        <template></template>
        <specialization>
          <template-arg>unsigned char</template-arg>
        </specialization>
        <method name="operator()" cv="const">
          <type>std::size_t</type>
          <parameter name="val">
            <paramtype>unsigned char</paramtype>
          </parameter>
          <returns>
            <para>Unspecified in TR1, except that equal arguments yield the same result.</para>
            <para><functionname>hash_value</functionname>(val) in Boost.</para>
          </returns>
          <throws><para>Doesn't throw</para></throws>
        </method>
      </struct-specialization>

      <struct-specialization name="hash">
        <template></template>
        <specialization>
          <template-arg>wchar_t</template-arg>
        </specialization>
        <method name="operator()" cv="const">
          <type>std::size_t</type>
          <parameter name="val">
            <paramtype>wchar_t</paramtype>
          </parameter>
          <returns>
            <para>Unspecified in TR1, except that equal arguments yield the same result.</para>
            <para><functionname>hash_value</functionname>(val) in Boost.</para>
          </returns>
          <throws><para>Doesn't throw</para></throws>
        </method>
      </struct-specialization>

      <struct-specialization name="hash">
        <template></template>
        <specialization>
          <template-arg>short</template-arg>
        </specialization>
        <method name="operator()" cv="const">
          <type>std::size_t</type>
          <parameter name="val">
            <paramtype>short</paramtype>
          </parameter>
          <returns>
            <para>Unspecified in TR1, except that equal arguments yield the same result.</para>
            <para><functionname>hash_value</functionname>(val) in Boost.</para>
          </returns>
          <throws><para>Doesn't throw</para></throws>
        </method>
      </struct-specialization>

      <struct-specialization name="hash">
        <template></template>
        <specialization>
          <template-arg>unsigned short</template-arg>
        </specialization>
        <method name="operator()" cv="const">
          <type>std::size_t</type>
          <parameter name="val">
            <paramtype>unsigned short</paramtype>
          </parameter>
          <returns>
            <para>Unspecified in TR1, except that equal arguments yield the same result.</para>
            <para><functionname>hash_value</functionname>(val) in Boost.</para>
          </returns>
          <throws><para>Doesn't throw</para></throws>
        </method>
      </struct-specialization>

      <struct-specialization name="hash">
        <template></template>
        <specialization>
          <template-arg>int</template-arg>
        </specialization>
        <method name="operator()" cv="const">
          <type>std::size_t</type>
          <parameter name="val">
            <paramtype>int</paramtype>
          </parameter>
          <returns>
            <para>Unspecified in TR1, except that equal arguments yield the same result.</para>
            <para><functionname>hash_value</functionname>(val) in Boost.</para>
          </returns>
          <throws><para>Doesn't throw</para></throws>
        </method>
      </struct-specialization>

      <struct-specialization name="hash">
        <template></template>
        <specialization>
          <template-arg>unsigned int</template-arg>
        </specialization>
        <method name="operator()" cv="const">
          <type>std::size_t</type>
          <parameter name="val">
            <paramtype>unsigned int</paramtype>
          </parameter>
          <returns>
            <para>Unspecified in TR1, except that equal arguments yield the same result.</para>
            <para><functionname>hash_value</functionname>(val) in Boost.</para>
          </returns>
          <throws><para>Doesn't throw</para></throws>
        </method>
      </struct-specialization>

      <struct-specialization name="hash">
        <template></template>
        <specialization>
          <template-arg>long</template-arg>
        </specialization>
        <method name="operator()" cv="const">
          <type>std::size_t</type>
          <parameter name="val">
            <paramtype>long</paramtype>
          </parameter>
          <returns>
            <para>Unspecified in TR1, except that equal arguments yield the same result.</para>
            <para><functionname>hash_value</functionname>(val) in Boost.</para>
          </returns>
          <throws><para>Doesn't throw</para></throws>
        </method>
      </struct-specialization>

      <struct-specialization name="hash">
        <template></template>
        <specialization>
          <template-arg>unsigned long</template-arg>
        </specialization>
        <method name="operator()" cv="const">
          <type>std::size_t</type>
          <parameter name="val">
            <paramtype>unsigned long</paramtype>
          </parameter>
          <returns>
            <para>Unspecified in TR1, except that equal arguments yield the same result.</para>
            <para><functionname>hash_value</functionname>(val) in Boost.</para>
          </returns>
          <throws><para>Doesn't throw</para></throws>
        </method>
      </struct-specialization>

      <struct-specialization name="hash">
        <template></template>
        <specialization>
          <template-arg>float</template-arg>
        </specialization>
        <method name="operator()" cv="const">
          <type>std::size_t</type>
          <parameter name="val">
            <paramtype>float</paramtype>
          </parameter>
          <returns>
            <para>Unspecified in TR1, except that equal arguments yield the same result.</para>
            <para><functionname>hash_value</functionname>(val) in Boost.</para>
          </returns>
          <throws><para>Doesn't throw</para></throws>
        </method>
      </struct-specialization>

      <struct-specialization name="hash">
        <template></template>
        <specialization>
          <template-arg>double</template-arg>
        </specialization>
        <method name="operator()" cv="const">
          <type>std::size_t</type>
          <parameter name="val">
            <paramtype>double</paramtype>
          </parameter>
          <returns>
            <para>Unspecified in TR1, except that equal arguments yield the same result.</para>
            <para><functionname>hash_value</functionname>(val) in Boost.</para>
          </returns>
          <throws><para>Doesn't throw</para></throws>
        </method>
      </struct-specialization>

      <struct-specialization name="hash">
        <template></template>
        <specialization>
          <template-arg>long double</template-arg>
        </specialization>
        <method name="operator()" cv="const">
          <type>std::size_t</type>
          <parameter name="val">
            <paramtype>long double</paramtype>
          </parameter>
          <returns>
            <para>Unspecified in TR1, except that equal arguments yield the same result.</para>
            <para><functionname>hash_value</functionname>(val) in Boost.</para>
          </returns>
          <throws><para>Doesn't throw</para></throws>
        </method>
      </struct-specialization>

      <struct-specialization name="hash">
        <template></template>
        <specialization>
          <template-arg>std::string</template-arg>
        </specialization>
        <method name="operator()" cv="const">
          <type>std::size_t</type>
          <parameter name="val">
            <paramtype>std::string const&amp;</paramtype>
          </parameter>
          <returns>
            <para>Unspecified in TR1, except that equal arguments yield the same result.</para>
            <para><functionname>hash_value</functionname>(val) in Boost.</para>
          </returns>
          <throws><para>Doesn't throw</para></throws>
        </method>
      </struct-specialization>

      <struct-specialization name="hash">
        <template></template>
        <specialization>
          <template-arg>std::wstring</template-arg>
        </specialization>
        <method name="operator()" cv="const">
          <type>std::size_t</type>
          <parameter name="val">
            <paramtype>std::wstring const&amp;</paramtype>
          </parameter>
          <returns>
            <para>Unspecified in TR1, except that equal arguments yield the same result.</para>
            <para><functionname>hash_value</functionname>(val) in Boost.</para>
          </returns>
          <throws><para>Doesn't throw</para></throws>
        </method>
      </struct-specialization>

      <struct-specialization name="hash">
        <template>
          <template-type-parameter name="T"/>
        </template>
        <specialization>
          <template-arg>T*</template-arg>
        </specialization>
        <method name="operator()" cv="const">
          <type>std::size_t</type>
          <parameter name="val">
            <paramtype>T*</paramtype>
          </parameter>
          <returns>
            <para>Unspecified in TR1, except that equal arguments yield the same result.</para>
          </returns>
          <throws><para>Doesn't throw</para></throws>
        </method>
      </struct-specialization>

      <!--
        boost::hash_combine
        -->

      <function name="hash_combine">
        <template>
          <template-type-parameter name="T"/>
        </template>
        <type>void</type>
        <parameter name="seed"><paramtype>size_t &amp;</paramtype></parameter>
        <parameter name="v"><paramtype>T const&amp;</paramtype></parameter>
        <purpose>
            Called repeatedly to incrementally create a hash value from
            several variables.
        </purpose>
        <effects><programlisting>seed ^= <functionname>hash_value</functionname>(v) + 0x9e3779b9 + (seed &lt;&lt; 6) + (seed &gt;&gt; 2);</programlisting></effects>
        <notes>
          <para><functionname>hash_value</functionname> is called without
          qualification, so that overloads can be found via ADL.</para>
          <para>This is an extension to TR1</para>
        </notes>
        <throws>
          Only throws if <functionname>hash_value</functionname>(T) throws.
          Strong exception safety, as long as <functionname>hash_value</functionname>(T)
          also has strong exception safety.
        </throws>
      </function>

      <!--
        boost::hash_range
        -->

      <overloaded-function name="hash_range">
        <signature>
          <template>
            <template-type-parameter name="It"/>
          </template>
          <type>std::size_t</type>
          <parameter name="first"><paramtype>It</paramtype></parameter>
          <parameter name="last"><paramtype>It</paramtype></parameter>
        </signature>

        <signature>
          <template>
            <template-type-parameter name="It"/>
          </template>
          <type>void</type>
          <parameter name="seed"><paramtype>std::size_t&amp;</paramtype></parameter>
          <parameter name="first"><paramtype>It</paramtype></parameter>
          <parameter name="last"><paramtype>It</paramtype></parameter>
        </signature>

        <purpose>
            Calculate the combined hash value of the elements of an iterator
            range.
        </purpose>
        <effects>
          <para>For the two argument overload:
<programlisting>
size_t seed = 0;

for(; first != last; ++first)
{
    <functionname>hash_combine</functionname>(seed, *first);
}

return seed;
</programlisting>
          </para>For the three arguments overload:
<programlisting>
for(; first != last; ++first)
{
    <functionname>hash_combine</functionname>(seed, *first);
}
</programlisting>
          <para>
          </para>
        </effects>
        <notes>
          <para>
            <code>hash_range</code> is sensitive to the order of the elements
            so it wouldn't be appropriate to use this with an unordered
            container.
          </para>
          <para>This is an extension to TR1</para>
        </notes>
        <throws><para>
          Only throws if <code><functionname>hash_value</functionname>(std::iterator_traits&lt;It&gt;::value_type)</code>
          throws. <code>hash_range(std::size_t&amp;, It, It)</code> has basic exception safety as long as
          <code><functionname>hash_value</functionname>(std::iterator_traits&lt;It&gt;::value_type)</code>
          has basic exception safety.
        </para></throws>
      </overloaded-function>

      <!--
        boost::hash_value - integers
        -->

      <overloaded-function name="hash_value">
        <purpose>
            Implementation of the hash function.
        </purpose>

        <signature>
          <type>std::size_t</type>
          <parameter name="val"><paramtype>int</paramtype></parameter>
        </signature>

        <signature>
          <type>std::size_t</type>
          <parameter name="val"><paramtype>unsigned int</paramtype></parameter>
        </signature>

        <signature>
          <type>std::size_t</type>
          <parameter name="val"><paramtype>long</paramtype></parameter>
        </signature>

        <signature>
          <type>std::size_t</type>
          <parameter name="val"><paramtype>unsigned long</paramtype></parameter>
        </signature>

        <signature>
          <type>std::size_t</type>
          <parameter name="val"><paramtype>float</paramtype></parameter>
        </signature>

        <signature>
          <type>std::size_t</type>
          <parameter name="val"><paramtype>double</paramtype></parameter>
        </signature>

        <signature>
          <type>std::size_t</type>
          <parameter name="val"><paramtype>long double</paramtype></parameter>
        </signature>

        <signature>
          <template><template-type-parameter name="T"/></template>
          <type>std::size_t</type>
          <parameter name="val"><paramtype>T* const&amp;</paramtype></parameter>
        </signature>

        <signature>
          <template>
            <template-type-parameter name="T"/>
            <template-nontype-parameter name="N"><type>unsigned</type></template-nontype-parameter>
          </template>
          <type>std::size_t</type>
          <parameter><paramtype>T (&amp;val)[N]</paramtype></parameter>
        </signature>

        <signature>
          <template>
            <template-type-parameter name="T"/>
            <template-nontype-parameter name="N"><type>unsigned</type></template-nontype-parameter>
          </template>
          <type>std::size_t</type>
          <parameter><paramtype>const T (&amp;val)[N]</paramtype></parameter>
        </signature>

        <signature>
          <template>
            <template-type-parameter name="Ch"/>
            <template-type-parameter name="A"/>
          </template>
          <type>std::size_t</type>
          <parameter name="val">
              <paramtype>std::basic_string&lt;Ch, std::char_traits&lt;Ch&gt;, A&gt; const&amp;</paramtype>
          </parameter>
        </signature>
              
       <signature>
          <template>
            <template-type-parameter name="A"/>
            <template-type-parameter name="B"/>
          </template>
          <type>std::size_t</type>
          <parameter name="val"><paramtype>std::pair&lt;A, B&gt; const&amp;</paramtype></parameter>
        </signature>

        <signature>
          <template>
            <template-type-parameter name="T"/>
            <template-type-parameter name="A"/>
          </template>
          <type>std::size_t</type>
          <parameter name="val"><paramtype>std::vector&lt;T, A&gt; const&amp;</paramtype></parameter>
        </signature>

        <signature>
          <template>
            <template-type-parameter name="T"/>
            <template-type-parameter name="A"/>
          </template>
          <type>std::size_t</type>
          <parameter name="val"><paramtype>std::list&lt;T, A&gt; const&amp;</paramtype></parameter>
        </signature>

        <signature>
          <template>
            <template-type-parameter name="T"/>
            <template-type-parameter name="A"/>
          </template>
          <type>std::size_t</type>
          <parameter name="val"><paramtype>std::deque&lt;T, A&gt; const&amp;</paramtype></parameter>
        </signature>

        <signature>
          <template>
            <template-type-parameter name="K"/>
            <template-type-parameter name="C"/>
            <template-type-parameter name="A"/>
          </template>
          <type>std::size_t</type>
          <parameter name="val"><paramtype>std::set&lt;K, C, A&gt; const&amp;</paramtype></parameter>
        </signature>

        <signature>
          <template>
            <template-type-parameter name="K"/>
            <template-type-parameter name="C"/>
            <template-type-parameter name="A"/>
          </template>
          <type>std::size_t</type>
          <parameter name="val"><paramtype>std::multiset&lt;K, C, A&gt; const&amp;</paramtype></parameter>
        </signature>

        <signature>
          <template>
            <template-type-parameter name="K"/>
            <template-type-parameter name="T"/>
            <template-type-parameter name="C"/>
            <template-type-parameter name="A"/>
          </template>
          <type>std::size_t</type>
          <parameter name="val"><paramtype>std::map&lt;K, T, C, A&gt; const&amp;</paramtype></parameter>
        </signature>

        <signature>
          <template>
            <template-type-parameter name="K"/>
            <template-type-parameter name="T"/>
            <template-type-parameter name="C"/>
            <template-type-parameter name="A"/>
          </template>
          <type>std::size_t</type>
          <parameter name="val"><paramtype>std::multimap&lt;K, T, C, A&gt; const&amp;</paramtype></parameter>
        </signature>

        <description><para>
          Generally shouldn't be called directly by users, instead they should use
          <classname>boost::hash</classname>, <functionname>boost::hash_range</functionname>
          or <functionname>boost::hash_combine</functionname> which
          call <code>hash_value</code> without namespace qualification so that overloads
          for custom types are found via ADL.
        </para></description>

        <notes>
          <para>This is an extension to TR1</para>
        </notes>

        <throws>
            Only throws if a user supplied version of
            <code><functionname>hash_value</functionname></code>
            throws for an element of a container, or
            one of the types stored in a pair.
        </throws>

        <returns>
          <informaltable>
            <tgroup cols="2">
              <thead>
                <row>
                  <entry>Types</entry>
                  <entry>Returns</entry>
                </row>
              </thead>
              <tbody>
                <row>
                  <entry><code>int</code>, <code>unsigned int</code>, <code>long</code>, <code>unsigned long</code></entry>
                  <entry><code>val</code></entry>
                </row>
                <row>
                  <entry><code>float</code>, <code>double</code>, <code>long double</code></entry>
                  <entry>An unspecified value, except that equal arguments shall yield the same result.</entry>
                </row>
                <row>
                  <entry><code>T*</code></entry>
                  <entry>An unspecified value, except that equal arguments shall yield the same result.</entry>
                </row>
                <row>
                  <entry>
                    <code>T&#160;val[N]</code>,
                    <code>const&#160;T&#160;val[N]</code>
                  </entry>
                  <entry><code>hash_range(val, val+N)</code></entry>
                </row>
                <row>
                  <entry>
                    <code>std:basic_string&lt;Ch,&#160;std::char_traits&lt;Ch&gt;,&#160;A&gt;</code>,
                    <code>std::vector&lt;T,&#160;A&gt;</code>,
                    <code>std::list&lt;T,&#160;A&gt;</code>,
                    <code>std::deque&lt;T,&#160;A&gt;</code>,
                    <code>std::set&lt;K,&#160;C,&#160;A&gt;</code>,
                    <code>std::multiset&lt;K,&#160;C,&#160;A&gt;</code>,
                    <code>std::map&lt;K,&#160;T,&#160;C,&#160;A&gt;</code>,
                    <code>std::multimap&lt;K,&#160;T,&#160;C,&#160;A&gt;</code>
                  </entry>
                  <entry><code>hash_range(val.begin(), val.end())</code></entry>
                </row>
                <row>
                  <entry><code>std::pair&lt;A, B&gt;</code></entry>
                  <entry><programlisting>size_t seed = 0;
<functionname>hash_combine</functionname>(seed, val.first);
<functionname>hash_combine</functionname>(seed, val.second);
return seed;</programlisting></entry>
                </row>
              </tbody>
            </tgroup>
          </informaltable>
        </returns>
      </overloaded-function>
    </namespace>
  </header>
</library-reference>

