libstdc++-v3/doc/html/manual/unordered_associative.html

   1 <?xml version="1.0" encoding="UTF-8" standalone="no"?>
   2 <!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd"><html xmlns="http://www.w3.org/1999/xhtml"><head><meta http-equiv="Content-Type" content="text/html; charset=UTF-8" /><title>Unordered Associative</title><meta name="generator" content="DocBook XSL-NS Stylesheets V1.78.1" /><meta name="keywords" content="ISO C++, library" /><meta name="keywords" content="ISO C++, runtime, library" /><link rel="home" href="../index.html" title="The GNU C++ Library" /><link rel="up" href="containers.html" title="Chapter 9.  Containers" /><link rel="prev" href="associative.html" title="Associative" /><link rel="next" href="containers_and_c.html" title="Interacting with C" /></head><body><div class="navheader"><table width="100%" summary="Navigation header"><tr><th colspan="3" align="center">Unordered Associative</th></tr><tr><td width="20%" align="left"><a accesskey="p" href="associative.html">Prev</a> </td><th width="60%" align="center">Chapter 9.
   3   Containers
   4
   5 </th><td width="20%" align="right"> <a accesskey="n" href="containers_and_c.html">Next</a></td></tr></table><hr /></div><div class="section"><div class="titlepage"><div><div><h2 class="title" style="clear: both"><a id="std.containers.unordered"></a>Unordered Associative</h2></div></div></div><div class="section"><div class="titlepage"><div><div><h3 class="title"><a id="containers.unordered.hash"></a>Hash Code</h3></div></div></div><div class="section"><div class="titlepage"><div><div><h4 class="title"><a id="containers.unordered.cache"></a>Hash Code Caching Policy</h4></div></div></div><p>
   6       The unordered containers in libstdc++ may cache the hash code for each
   7       element alongside the element itself. In some cases not recalculating
   8       the hash code every time it's needed can improve performance, but the
   9       additional memory overhead can also reduce performance, so whether an
  10       unordered associative container caches the hash code or not depends on
  11       a number of factors. The caching policy for GCC 4.8 is described below.
  12     </p><p>
  13       The C++ standard requires that <code class="code">erase</code> and <code class="code">swap</code>
  14       operations must not throw exceptions. Those operations might need an
  15       element's hash code, but cannot use the hash function if it could
  16       throw.
  17       This means the hash codes will be cached unless the hash function
  18       has a non-throwing exception specification such as <code class="code">noexcept</code>
  19       or <code class="code">throw()</code>.
  20     </p><p>
  21       Secondly, libstdc++ also needs the hash code in the implementation of
  22       <code class="code">local_iterator</code> and <code class="code">const_local_iterator</code> in
  23       order to know when the iterator has reached the end of the bucket.
  24       This means that the local iterator types will embed a copy of the hash
  25       function when possible.
  26       Because the local iterator types must be DefaultConstructible and
  27       CopyAssignable, if the hash function type does not model those concepts
  28       then it cannot be embedded and so the hash code must be cached.
  29       Note that a hash function might not be safe to use when
  30       default-constructed (e.g if it a function pointer) so a hash
  31       function that is contained in a local iterator won't be used until
  32       the iterator is valid, so the hash function has been copied from a
  33       correctly-initialized object.
  34     </p><p>
  35       If the hash function is non-throwing, DefaultConstructible and
  36       CopyAssignable then libstdc++ doesn't need to cache the hash code for
  37       correctness, but might still do so for performance if computing a
  38       hash code is an expensive operation, as it may be for arbitrarily
  39       long strings.
  40       As an extension libstdc++ provides a trait type to describe whether
  41       a hash function is fast. By default hash functions are assumed to be
  42       fast unless the trait is specialized for the hash function and the
  43       trait's value is false, in which case the hash code will always be
  44       cached.
  45       The trait can be specialized for user-defined hash functions like so:
  46     </p><pre class="programlisting">
  47       #include &lt;unordered_set&gt;
  48
  49       struct hasher
  50       {
  51         std::size_t operator()(int val) const noexcept
  52         {
  53           // Some very slow computation of a hash code from an int !
  54           ...
  55         }
  56       }
  57
  58       namespace std
  59       {
  60         template&lt;&gt;
  61           struct __is_fast_hash&lt;hasher&gt; : std::false_type
  62           { };
  63       }
  64     </pre></div></div></div><div class="navfooter"><hr /><table width="100%" summary="Navigation footer"><tr><td width="40%" align="left"><a accesskey="p" href="associative.html">Prev</a> </td><td width="20%" align="center"><a accesskey="u" href="containers.html">Up</a></td><td width="40%" align="right"> <a accesskey="n" href="containers_and_c.html">Next</a></td></tr><tr><td width="40%" align="left" valign="top">Associative </td><td width="20%" align="center"><a accesskey="h" href="../index.html">Home</a></td><td width="40%" align="right" valign="top"> Interacting with C</td></tr></table></div></body></html>