| <?xml version="1.0" encoding="UTF-8" standalone="no"?> |
| <!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. |
| Containers |
| |
| </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> |
| The unordered containers in libstdc++ may cache the hash code for each |
| element alongside the element itself. In some cases not recalculating |
| the hash code every time it's needed can improve performance, but the |
| additional memory overhead can also reduce performance, so whether an |
| unordered associative container caches the hash code or not depends on |
| a number of factors. The caching policy for GCC 4.8 is described below. |
| </p><p> |
| The C++ standard requires that <code class="code">erase</code> and <code class="code">swap</code> |
| operations must not throw exceptions. Those operations might need an |
| element's hash code, but cannot use the hash function if it could |
| throw. |
| This means the hash codes will be cached unless the hash function |
| has a non-throwing exception specification such as <code class="code">noexcept</code> |
| or <code class="code">throw()</code>. |
| </p><p> |
| Secondly, libstdc++ also needs the hash code in the implementation of |
| <code class="code">local_iterator</code> and <code class="code">const_local_iterator</code> in |
| order to know when the iterator has reached the end of the bucket. |
| This means that the local iterator types will embed a copy of the hash |
| function when possible. |
| Because the local iterator types must be DefaultConstructible and |
| CopyAssignable, if the hash function type does not model those concepts |
| then it cannot be embedded and so the hash code must be cached. |
| Note that a hash function might not be safe to use when |
| default-constructed (e.g if it a function pointer) so a hash |
| function that is contained in a local iterator won't be used until |
| the iterator is valid, so the hash function has been copied from a |
| correctly-initialized object. |
| </p><p> |
| If the hash function is non-throwing, DefaultConstructible and |
| CopyAssignable then libstdc++ doesn't need to cache the hash code for |
| correctness, but might still do so for performance if computing a |
| hash code is an expensive operation, as it may be for arbitrarily |
| long strings. |
| As an extension libstdc++ provides a trait type to describe whether |
| a hash function is fast. By default hash functions are assumed to be |
| fast unless the trait is specialized for the hash function and the |
| trait's value is false, in which case the hash code will always be |
| cached. |
| The trait can be specialized for user-defined hash functions like so: |
| </p><pre class="programlisting"> |
| #include <unordered_set> |
| |
| struct hasher |
| { |
| std::size_t operator()(int val) const noexcept |
| { |
| // Some very slow computation of a hash code from an int ! |
| ... |
| } |
| } |
| |
| namespace std |
| { |
| template<> |
| struct __is_fast_hash<hasher> : std::false_type |
| { }; |
| } |
| </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> |
