unordered_associative.html revision 1.1.1.2
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.insert_hints"></a>Insertion Hints</h3></div></div></div><p> 6 Here is how the hinting works in the libstdc++ implementation of unordered 7 containers, and the rationale behind this behavior. 8 </p><p> 9 In the following text, the phrase <span class="emphasis"><em>equivalent to</em></span> refer 10 to the result of the invocation of the equal predicate imposed on the 11 container by its <code class="code">key_equal</code> object, which defaults to (basically) 12 <span class="quote">���<span class="quote">==</span>���</span>. 13 </p><p> 14 Unordered containers can be seen as a <code class="code">std::vector</code> of 15 <code class="code">std::forward_list</code>. The <code class="code">std::vector</code> represents 16 the buckets and each <code class="code">std::forward_list</code> is the list of nodes 17 belonging to the same bucket. When inserting an element in such a data 18 structure we first need to compute the element hash code to find the 19 bucket to insert the element to, the second step depends on the uniqueness 20 of elements in the container. 21 </p><p> 22 In the case of <code class="code">std::unordered_set</code> and 23 <code class="code">std::unordered_map</code> you need to look through all bucket's 24 elements for an equivalent one. If there is none the insertion can be 25 achieved, otherwise the insertion fails. As we always need to loop though 26 all bucket's elements, the hint doesn't tell us if the element is already 27 present, and we don't have any constraint on where the new element is to 28 be inserted, the hint won't be of any help and will then be ignored. 29 </p><p> 30 In the case of <code class="code">std::unordered_multiset</code> 31 and <code class="code">std::unordered_multimap</code> equivalent elements must be 32 linked together so that the <code class="code">equal_range(const key_type&)</code> 33 can return the range of iterators pointing to all equivalent elements. 34 This is where hinting can be used to point to another equivalent element 35 already part of the container and so skip all non equivalent elements of 36 the bucket. So to be useful the hint shall point to an element equivalent 37 to the one being inserted. The new element will be then inserted right 38 after the hint. Note that because of an implementation detail inserting 39 after a node can require updating the bucket of the following node. To 40 check if the next bucket is to be modified we need to compute the 41 following node's hash code. So if you want your hint to be really efficient 42 it should be followed by another equivalent element, the implementation 43 will detect this equivalence and won't compute next element hash code. 44 </p><p> 45 It is highly advised to start using unordered containers hints only if you 46 have a benchmark that will demonstrate the benefit of it. If you don't then do 47 not use hints, it might do more harm than good. 48 </p></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> 49 The unordered containers in libstdc++ may cache the hash code for each 50 element alongside the element itself. In some cases not recalculating 51 the hash code every time it's needed can improve performance, but the 52 additional memory overhead can also reduce performance, so whether an 53 unordered associative container caches the hash code or not depends on 54 the properties described below. 55 </p><p> 56 The C++ standard requires that <code class="code">erase</code> and <code class="code">swap</code> 57 operations must not throw exceptions. Those operations might need an 58 element's hash code, but cannot use the hash function if it could 59 throw. 60 This means the hash codes will be cached unless the hash function 61 has a non-throwing exception specification such as <code class="code">noexcept</code> 62 or <code class="code">throw()</code>. 63 </p><p> 64 If the hash function is non-throwing then libstdc++ doesn't need to 65 cache the hash code for 66 correctness, but might still do so for performance if computing a 67 hash code is an expensive operation, as it may be for arbitrarily 68 long strings. 69 As an extension libstdc++ provides a trait type to describe whether 70 a hash function is fast. By default hash functions are assumed to be 71 fast unless the trait is specialized for the hash function and the 72 trait's value is false, in which case the hash code will always be 73 cached. 74 The trait can be specialized for user-defined hash functions like so: 75 </p><pre class="programlisting"> 76 #include <unordered_set> 77 78 struct hasher 79 { 80 std::size_t operator()(int val) const noexcept 81 { 82 // Some very slow computation of a hash code from an int ! 83 ... 84 } 85 } 86 87 namespace std 88 { 89 template<> 90 struct __is_fast_hash<hasher> : std::false_type 91 { }; 92 } 93 </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>