diff options
| author | Anas Nashif <anas.nashif@intel.com> | 2012-10-30 12:57:26 -0700 |
|---|---|---|
| committer | Anas Nashif <anas.nashif@intel.com> | 2012-10-30 12:57:26 -0700 |
| commit | 1a78a62555be32868418fe52f8e330c9d0f95d5a (patch) | |
| tree | d3765a80e7d3b9640ec2e930743630cd6b9fce2b /doc/html/unordered | |
| download | boost-1a78a62555be32868418fe52f8e330c9d0f95d5a.tar.gz boost-1a78a62555be32868418fe52f8e330c9d0f95d5a.tar.bz2 boost-1a78a62555be32868418fe52f8e330c9d0f95d5a.zip | |
Imported Upstream version 1.49.0upstream/1.49.0
Diffstat (limited to 'doc/html/unordered')
| -rwxr-xr-x | doc/html/unordered/bibliography.html | 50 | ||||
| -rwxr-xr-x | doc/html/unordered/buckets.html | 321 | ||||
| -rwxr-xr-x | doc/html/unordered/changes.html | 363 | ||||
| -rwxr-xr-x | doc/html/unordered/comparison.html | 519 | ||||
| -rwxr-xr-x | doc/html/unordered/compliance.html | 179 | ||||
| -rwxr-xr-x | doc/html/unordered/hash_equality.html | 259 | ||||
| -rwxr-xr-x | doc/html/unordered/rationale.html | 129 | ||||
| -rwxr-xr-x | doc/html/unordered/reference.html | 117 |
8 files changed, 1937 insertions, 0 deletions
diff --git a/doc/html/unordered/bibliography.html b/doc/html/unordered/bibliography.html new file mode 100755 index 0000000000..041e3531e1 --- /dev/null +++ b/doc/html/unordered/bibliography.html @@ -0,0 +1,50 @@ +<html> +<head> +<meta http-equiv="Content-Type" content="text/html; charset=US-ASCII"> +<title>Bibliography</title> +<link rel="stylesheet" href="../../../doc/src/boostbook.css" type="text/css"> +<meta name="generator" content="DocBook XSL Stylesheets V1.76.1"> +<link rel="home" href="../index.html" title="The Boost C++ Libraries BoostBook Documentation Subset"> +<link rel="up" href="../unordered.html" title="Chapter 33. Boost.Unordered"> +<link rel="prev" href="../boost/unordered_multimap.html" title="Class template unordered_multimap"> +<link rel="next" href="../variant.html" title="Chapter 34. Boost.Variant"> +</head> +<body bgcolor="white" text="black" link="#0000FF" vlink="#840084" alink="#0000FF"> +<table cellpadding="2" width="100%"><tr> +<td valign="top"><img alt="Boost C++ Libraries" width="277" height="86" src="../../../boost.png"></td> +<td align="center"><a href="../../../index.html">Home</a></td> +<td align="center"><a href="../../../libs/libraries.htm">Libraries</a></td> +<td align="center"><a href="http://www.boost.org/users/people.html">People</a></td> +<td align="center"><a href="http://www.boost.org/users/faq.html">FAQ</a></td> +<td align="center"><a href="../../../more/index.htm">More</a></td> +</tr></table> +<hr> +<div class="spirit-nav"> +<a accesskey="p" href="../boost/unordered_multimap.html"><img src="../../../doc/src/images/prev.png" alt="Prev"></a><a accesskey="u" href="../unordered.html"><img src="../../../doc/src/images/up.png" alt="Up"></a><a accesskey="h" href="../index.html"><img src="../../../doc/src/images/home.png" alt="Home"></a><a accesskey="n" href="../variant.html"><img src="../../../doc/src/images/next.png" alt="Next"></a> +</div> +<div class="section"> +<div class="titlepage"><div><div><h2 class="title" style="clear: both"> +<a name="unordered.bibliography"></a>Bibliography</h2></div></div></div> +<div class="bibliography"> +<div class="titlepage"><div><div><h3 class="title"> +<a name="id3695352"></a>Bibliography</h3></div></div></div> +<div class="biblioentry"> +<a name="id3695354"></a><p><span class="biblioset"><i>C/C++ Users Journal</i>. <span class="date">February, 2006. </span></span><span class="biblioset"><span class="authorgroup"><span class="firstname">Pete</span> <span class="surname">Becker</span>. </span>“<a href="http://www.ddj.com/cpp/184402066" target="_top">STL and TR1: Part III - Unordered containers</a>”. </span><p>An introducation to the standard unordered containers.</p></p> +</div> +</div> +</div> +<table xmlns:rev="http://www.cs.rpi.edu/~gregod/boost/tools/doc/revision" width="100%"><tr> +<td align="left"></td> +<td align="right"><div class="copyright-footer">Copyright © 2003, 2004 Jeremy B. Maitin-Shepard<br>Copyright © 2005-2008 Daniel + James<p> + Distributed under the Boost Software License, Version 1.0. (See accompanying + file LICENSE_1_0.txt or copy at <a href="http://www.boost.org/LICENSE_1_0.txt" target="_top">http://www.boost.org/LICENSE_1_0.txt</a>) + </p> +</div></td> +</tr></table> +<hr> +<div class="spirit-nav"> +<a accesskey="p" href="../boost/unordered_multimap.html"><img src="../../../doc/src/images/prev.png" alt="Prev"></a><a accesskey="u" href="../unordered.html"><img src="../../../doc/src/images/up.png" alt="Up"></a><a accesskey="h" href="../index.html"><img src="../../../doc/src/images/home.png" alt="Home"></a><a accesskey="n" href="../variant.html"><img src="../../../doc/src/images/next.png" alt="Next"></a> +</div> +</body> +</html> diff --git a/doc/html/unordered/buckets.html b/doc/html/unordered/buckets.html new file mode 100755 index 0000000000..6faf55eac2 --- /dev/null +++ b/doc/html/unordered/buckets.html @@ -0,0 +1,321 @@ +<html> +<head> +<meta http-equiv="Content-Type" content="text/html; charset=US-ASCII"> +<title>The Data Structure</title> +<link rel="stylesheet" href="../../../doc/src/boostbook.css" type="text/css"> +<meta name="generator" content="DocBook XSL Stylesheets V1.76.1"> +<link rel="home" href="../index.html" title="The Boost C++ Libraries BoostBook Documentation Subset"> +<link rel="up" href="../unordered.html" title="Chapter 33. Boost.Unordered"> +<link rel="prev" href="../unordered.html" title="Chapter 33. Boost.Unordered"> +<link rel="next" href="hash_equality.html" title="Equality Predicates and Hash Functions"> +</head> +<body bgcolor="white" text="black" link="#0000FF" vlink="#840084" alink="#0000FF"> +<table cellpadding="2" width="100%"><tr> +<td valign="top"><img alt="Boost C++ Libraries" width="277" height="86" src="../../../boost.png"></td> +<td align="center"><a href="../../../index.html">Home</a></td> +<td align="center"><a href="../../../libs/libraries.htm">Libraries</a></td> +<td align="center"><a href="http://www.boost.org/users/people.html">People</a></td> +<td align="center"><a href="http://www.boost.org/users/faq.html">FAQ</a></td> +<td align="center"><a href="../../../more/index.htm">More</a></td> +</tr></table> +<hr> +<div class="spirit-nav"> +<a accesskey="p" href="../unordered.html"><img src="../../../doc/src/images/prev.png" alt="Prev"></a><a accesskey="u" href="../unordered.html"><img src="../../../doc/src/images/up.png" alt="Up"></a><a accesskey="h" href="../index.html"><img src="../../../doc/src/images/home.png" alt="Home"></a><a accesskey="n" href="hash_equality.html"><img src="../../../doc/src/images/next.png" alt="Next"></a> +</div> +<div class="section"> +<div class="titlepage"><div><div><h2 class="title" style="clear: both"> +<a name="unordered.buckets"></a><a class="link" href="buckets.html" title="The Data Structure">The Data Structure</a> +</h2></div></div></div> +<p> + The containers are made up of a number of 'buckets', each of which can contain + any number of elements. For example, the following diagram shows an <code class="computeroutput"><a class="link" href="../boost/unordered_set.html" title="Class template unordered_set">unordered_set</a></code> with 7 buckets containing + 5 elements, <code class="computeroutput"><span class="identifier">A</span></code>, <code class="computeroutput"><span class="identifier">B</span></code>, <code class="computeroutput"><span class="identifier">C</span></code>, + <code class="computeroutput"><span class="identifier">D</span></code> and <code class="computeroutput"><span class="identifier">E</span></code> + (this is just for illustration, containers will typically have more buckets). + </p> +<p> + <span class="inlinemediaobject"><img src="../../../libs/unordered/doc/diagrams/buckets.png" align="middle"></span> + </p> +<p> + In order to decide which bucket to place an element in, the container applies + the hash function, <code class="computeroutput"><span class="identifier">Hash</span></code>, to + the element's key (for <code class="computeroutput"><span class="identifier">unordered_set</span></code> + and <code class="computeroutput"><span class="identifier">unordered_multiset</span></code> the + key is the whole element, but is referred to as the key so that the same terminology + can be used for sets and maps). This returns a value of type <code class="computeroutput"><span class="identifier">std</span><span class="special">::</span><span class="identifier">size_t</span></code>. + <code class="computeroutput"><span class="identifier">std</span><span class="special">::</span><span class="identifier">size_t</span></code> has a much greater range of values + then the number of buckets, so that container applies another transformation + to that value to choose a bucket to place the element in. + </p> +<p> + Retrieving the elements for a given key is simple. The same process is applied + to the key to find the correct bucket. Then the key is compared with the elements + in the bucket to find any elements that match (using the equality predicate + <code class="computeroutput"><span class="identifier">Pred</span></code>). If the hash function + has worked well the elements will be evenly distributed amongst the buckets + so only a small number of elements will need to be examined. + </p> +<p> + There is <a class="link" href="hash_equality.html" title="Equality Predicates and Hash Functions">more information on hash functions + and equality predicates in the next section</a>. + </p> +<p> + You can see in the diagram that <code class="computeroutput"><span class="identifier">A</span></code> + & <code class="computeroutput"><span class="identifier">D</span></code> have been placed in + the same bucket. When looking for elements in this bucket up to 2 comparisons + are made, making the search slower. This is known as a collision. To keep things + fast we try to keep collisions to a minimum. + </p> +<p> + </p> +<div class="table"> +<a name="id3640738"></a><p class="title"><b>Table 33.1. Methods for Accessing Buckets</b></p> +<div class="table-contents"><table class="table" summary="Methods for Accessing Buckets"> +<colgroup> +<col> +<col> +</colgroup> +<thead><tr> +<th><p>Method</p></th> +<th><p>Description</p></th> +</tr></thead> +<tbody> +<tr> +<td><code class="computeroutput"><span class="identifier">size_type</span> <span class="identifier">bucket_count</span><span class="special">()</span> <span class="keyword">const</span></code></td> +<td>The + number of buckets.</td> +</tr> +<tr> +<td><code class="computeroutput"><span class="identifier">size_type</span> <span class="identifier">max_bucket_count</span><span class="special">()</span> + <span class="keyword">const</span></code></td> +<td>An upper bound on the number of + buckets.</td> +</tr> +<tr> +<td><code class="computeroutput"><span class="identifier">size_type</span> <span class="identifier">bucket_size</span><span class="special">(</span><span class="identifier">size_type</span> <span class="identifier">n</span><span class="special">)</span> <span class="keyword">const</span></code></td> +<td>The + number of elements in bucket <code class="computeroutput"><span class="identifier">n</span></code>.</td> +</tr> +<tr> +<td><code class="computeroutput"><span class="identifier">size_type</span> <span class="identifier">bucket</span><span class="special">(</span><span class="identifier">key_type</span> <span class="keyword">const</span><span class="special">&</span> <span class="identifier">k</span><span class="special">)</span> <span class="keyword">const</span></code></td> +<td>Returns + the index of the bucket which would contain k</td> +</tr> +<tr> +<td><code class="computeroutput"><span class="identifier">local_iterator</span> + <span class="identifier">begin</span><span class="special">(</span><span class="identifier">size_type</span> <span class="identifier">n</span><span class="special">);</span></code></td> +<td rowspan="6">Return begin and end iterators for bucket + <code class="computeroutput"><span class="identifier">n</span></code>.</td> +</tr> +<tr><td><code class="computeroutput"><span class="identifier">local_iterator</span> + <span class="identifier">end</span><span class="special">(</span><span class="identifier">size_type</span> <span class="identifier">n</span><span class="special">);</span></code></td></tr> +<tr><td><code class="computeroutput"><span class="identifier">const_local_iterator</span> + <span class="identifier">begin</span><span class="special">(</span><span class="identifier">size_type</span> <span class="identifier">n</span><span class="special">)</span> <span class="keyword">const</span><span class="special">;</span></code></td></tr> +<tr><td><code class="computeroutput"><span class="identifier">const_local_iterator</span> <span class="identifier">end</span><span class="special">(</span><span class="identifier">size_type</span> <span class="identifier">n</span><span class="special">)</span> <span class="keyword">const</span><span class="special">;</span></code></td></tr> +<tr><td><code class="computeroutput"><span class="identifier">const_local_iterator</span> + <span class="identifier">cbegin</span><span class="special">(</span><span class="identifier">size_type</span> <span class="identifier">n</span><span class="special">)</span> <span class="keyword">const</span><span class="special">;</span></code></td></tr> +<tr><td><code class="computeroutput"><span class="identifier">const_local_iterator</span> <span class="identifier">cend</span><span class="special">(</span><span class="identifier">size_type</span> <span class="identifier">n</span><span class="special">)</span> <span class="keyword">const</span><span class="special">;</span></code></td></tr> +</tbody> +</table></div> +</div> +<p><br class="table-break"> + </p> +<h3> +<a name="unordered.buckets.h0"></a> + <span><a name="unordered.buckets.controlling_the_number_of_buckets"></a></span><a class="link" href="buckets.html#unordered.buckets.controlling_the_number_of_buckets">Controlling + the number of buckets</a> + </h3> +<p> + As more elements are added to an unordered associative container, the number + of elements in the buckets will increase causing performance to degrade. To + combat this the containers increase the bucket count as elements are inserted. + You can also tell the container to change the bucket count (if required) by + calling <code class="computeroutput"><span class="identifier">rehash</span></code>. + </p> +<p> + The standard leaves a lot of freedom to the implementer to decide how the number + of buckets are chosen, but it does make some requirements based on the container's + 'load factor', the average number of elements per bucket. Containers also have + a 'maximum load factor' which they should try to keep the load factor below. + </p> +<p> + You can't control the bucket count directly but there are two ways to influence + it: + </p> +<div class="itemizedlist"><ul class="itemizedlist" type="disc"> +<li class="listitem"> + Specify the minimum number of buckets when constructing a container or + when calling <code class="computeroutput"><span class="identifier">rehash</span></code>. + </li> +<li class="listitem"> + Suggest a maximum load factor by calling <code class="computeroutput"><span class="identifier">max_load_factor</span></code>. + </li> +</ul></div> +<p> + <code class="computeroutput"><span class="identifier">max_load_factor</span></code> doesn't let + you set the maximum load factor yourself, it just lets you give a <span class="emphasis"><em>hint</em></span>. + And even then, the draft standard doesn't actually require the container to + pay much attention to this value. The only time the load factor is <span class="emphasis"><em>required</em></span> + to be less than the maximum is following a call to <code class="computeroutput"><span class="identifier">rehash</span></code>. + But most implementations will try to keep the number of elements below the + max load factor, and set the maximum load factor to be the same as or close + to the hint - unless your hint is unreasonably small or large. + </p> +<div class="table"> +<a name="unordered.buckets.bucket_size"></a><p class="title"><b>Table 33.2. Methods for Controlling Bucket Size</b></p> +<div class="table-contents"><table class="table" summary="Methods for Controlling Bucket Size"> +<colgroup> +<col> +<col> +</colgroup> +<thead><tr> +<th> + <p> + Method + </p> + </th> +<th> + <p> + Description + </p> + </th> +</tr></thead> +<tbody> +<tr> +<td> + <p> + <code class="computeroutput"><span class="identifier">X</span><span class="special">(</span><span class="identifier">size_type</span> <span class="identifier">n</span><span class="special">)</span></code> + </p> + </td> +<td> + <p> + Construct an empty container with at least <code class="computeroutput"><span class="identifier">n</span></code> + buckets (<code class="computeroutput"><span class="identifier">X</span></code> is the + container type). + </p> + </td> +</tr> +<tr> +<td> + <p> + <code class="computeroutput"><span class="identifier">X</span><span class="special">(</span><span class="identifier">InputIterator</span> <span class="identifier">i</span><span class="special">,</span> <span class="identifier">InputIterator</span> + <span class="identifier">j</span><span class="special">,</span> + <span class="identifier">size_type</span> <span class="identifier">n</span><span class="special">)</span></code> + </p> + </td> +<td> + <p> + Construct an empty container with at least <code class="computeroutput"><span class="identifier">n</span></code> + buckets and insert elements from the range [<code class="computeroutput"><span class="identifier">i</span></code>, + <code class="computeroutput"><span class="identifier">j</span></code>) (<code class="computeroutput"><span class="identifier">X</span></code> is the container type). + </p> + </td> +</tr> +<tr> +<td> + <p> + <code class="computeroutput"><span class="keyword">float</span> <span class="identifier">load_factor</span><span class="special">()</span> <span class="keyword">const</span></code> + </p> + </td> +<td> + <p> + The average number of elements per bucket. + </p> + </td> +</tr> +<tr> +<td> + <p> + <code class="computeroutput"><span class="keyword">float</span> <span class="identifier">max_load_factor</span><span class="special">()</span> <span class="keyword">const</span></code> + </p> + </td> +<td> + <p> + Returns the current maximum load factor. + </p> + </td> +</tr> +<tr> +<td> + <p> + <code class="computeroutput"><span class="keyword">float</span> <span class="identifier">max_load_factor</span><span class="special">(</span><span class="keyword">float</span> <span class="identifier">z</span><span class="special">)</span></code> + </p> + </td> +<td> + <p> + Changes the container's maximum load factor, using <code class="computeroutput"><span class="identifier">z</span></code> as a hint. + </p> + </td> +</tr> +<tr> +<td> + <p> + <code class="computeroutput"><span class="keyword">void</span> <span class="identifier">rehash</span><span class="special">(</span><span class="identifier">size_type</span> + <span class="identifier">n</span><span class="special">)</span></code> + </p> + </td> +<td> + <p> + Changes the number of buckets so that there at least n buckets, and + so that the load factor is less than the maximum load factor. + </p> + </td> +</tr> +</tbody> +</table></div> +</div> +<br class="table-break"><h3> +<a name="unordered.buckets.h1"></a> + <span><a name="unordered.buckets.iterator_invalidation"></a></span><a class="link" href="buckets.html#unordered.buckets.iterator_invalidation">Iterator + Invalidation</a> + </h3> +<p> + It is not specified how member functions other than <code class="computeroutput"><span class="identifier">rehash</span></code> + affect the bucket count, although <code class="computeroutput"><span class="identifier">insert</span></code> + is only allowed to invalidate iterators when the insertion causes the load + factor to be greater than or equal to the maximum load factor. For most implementations + this means that insert will only change the number of buckets when this happens. + While iterators can be invalidated by calls to <code class="computeroutput"><span class="identifier">insert</span></code> + and <code class="computeroutput"><span class="identifier">rehash</span></code>, pointers and references + to the container's elements are never invalidated. + </p> +<p> + In a similar manner to using <code class="computeroutput"><span class="identifier">reserve</span></code> + for <code class="computeroutput"><span class="identifier">vector</span></code>s, it can be a good + idea to call <code class="computeroutput"><span class="identifier">rehash</span></code> before + inserting a large number of elements. This will get the expensive rehashing + out of the way and let you store iterators, safe in the knowledge that they + won't be invalidated. If you are inserting <code class="computeroutput"><span class="identifier">n</span></code> + elements into container <code class="computeroutput"><span class="identifier">x</span></code>, + you could first call: + </p> +<pre class="programlisting"><span class="identifier">x</span><span class="special">.</span><span class="identifier">rehash</span><span class="special">((</span><span class="identifier">x</span><span class="special">.</span><span class="identifier">size</span><span class="special">()</span> <span class="special">+</span> <span class="identifier">n</span><span class="special">)</span> <span class="special">/</span> <span class="identifier">x</span><span class="special">.</span><span class="identifier">max_load_factor</span><span class="special">()</span> <span class="special">+</span> <span class="number">1</span><span class="special">);</span> +</pre> +<div class="sidebar"> +<div class="titlepage"></div> +<p> + Note: <code class="computeroutput"><span class="identifier">rehash</span></code>'s argument is + the minimum number of buckets, not the number of elements, which is why the + new size is divided by the maximum load factor. The <code class="computeroutput"><span class="special">+</span> + <span class="number">1</span></code> guarantees there is no invalidation; + without it, reallocation could occur if the number of bucket exactly divides + the target size, since the container is allowed to rehash when the load factor + is equal to the maximum load factor. + </p> +</div> +</div> +<table xmlns:rev="http://www.cs.rpi.edu/~gregod/boost/tools/doc/revision" width="100%"><tr> +<td align="left"></td> +<td align="right"><div class="copyright-footer">Copyright © 2003, 2004 Jeremy B. Maitin-Shepard<br>Copyright © 2005-2008 Daniel + James<p> + Distributed under the Boost Software License, Version 1.0. (See accompanying + file LICENSE_1_0.txt or copy at <a href="http://www.boost.org/LICENSE_1_0.txt" target="_top">http://www.boost.org/LICENSE_1_0.txt</a>) + </p> +</div></td> +</tr></table> +<hr> +<div class="spirit-nav"> +<a accesskey="p" href="../unordered.html"><img src="../../../doc/src/images/prev.png" alt="Prev"></a><a accesskey="u" href="../unordered.html"><img src="../../../doc/src/images/up.png" alt="Up"></a><a accesskey="h" href="../index.html"><img src="../../../doc/src/images/home.png" alt="Home"></a><a accesskey="n" href="hash_equality.html"><img src="../../../doc/src/images/next.png" alt="Next"></a> +</div> +</body> +</html> diff --git a/doc/html/unordered/changes.html b/doc/html/unordered/changes.html new file mode 100755 index 0000000000..27da1b22d9 --- /dev/null +++ b/doc/html/unordered/changes.html @@ -0,0 +1,363 @@ +<html> +<head> +<meta http-equiv="Content-Type" content="text/html; charset=US-ASCII"> +<title>Change Log</title> +<link rel="stylesheet" href="../../../doc/src/boostbook.css" type="text/css"> +<meta name="generator" content="DocBook XSL Stylesheets V1.76.1"> +<link rel="home" href="../index.html" title="The Boost C++ Libraries BoostBook Documentation Subset"> +<link rel="up" href="../unordered.html" title="Chapter 33. Boost.Unordered"> +<link rel="prev" href="rationale.html" title="Implementation Rationale"> +<link rel="next" href="reference.html" title="Reference"> +</head> +<body bgcolor="white" text="black" link="#0000FF" vlink="#840084" alink="#0000FF"> +<table cellpadding="2" width="100%"><tr> +<td valign="top"><img alt="Boost C++ Libraries" width="277" height="86" src="../../../boost.png"></td> +<td align="center"><a href="../../../index.html">Home</a></td> +<td align="center"><a href="../../../libs/libraries.htm">Libraries</a></td> +<td align="center"><a href="http://www.boost.org/users/people.html">People</a></td> +<td align="center"><a href="http://www.boost.org/users/faq.html">FAQ</a></td> +<td align="center"><a href="../../../more/index.htm">More</a></td> +</tr></table> +<hr> +<div class="spirit-nav"> +<a accesskey="p" href="rationale.html"><img src="../../../doc/src/images/prev.png" alt="Prev"></a><a accesskey="u" href="../unordered.html"><img src="../../../doc/src/images/up.png" alt="Up"></a><a accesskey="h" href="../index.html"><img src="../../../doc/src/images/home.png" alt="Home"></a><a accesskey="n" href="reference.html"><img src="../../../doc/src/images/next.png" alt="Next"></a> +</div> +<div class="section"> +<div class="titlepage"><div><div><h2 class="title" style="clear: both"> +<a name="unordered.changes"></a><a class="link" href="changes.html" title="Change Log">Change Log</a> +</h2></div></div></div> +<h3> +<a name="unordered.changes.h0"></a> + <span><a name="unordered.changes.review_version"></a></span><a class="link" href="changes.html#unordered.changes.review_version">Review + Version</a> + </h3> +<p> + Initial review version, for the review conducted from 7th December 2007 to + 16th December 2007. + </p> +<h3> +<a name="unordered.changes.h1"></a> + <span><a name="unordered.changes.1_35_0_add_on___31st_march_2008"></a></span><a class="link" href="changes.html#unordered.changes.1_35_0_add_on___31st_march_2008">1.35.0 + Add-on - 31st March 2008</a> + </h3> +<p> + Unofficial release uploaded to vault, to be used with Boost 1.35.0. Incorporated + many of the suggestions from the review. + </p> +<div class="itemizedlist"><ul class="itemizedlist" type="disc"> +<li class="listitem"> + Improved portability thanks to Boost regression testing. + </li> +<li class="listitem"> + Fix lots of typos, and clearer text in the documentation. + </li> +<li class="listitem"> + Fix floating point to <code class="computeroutput"><span class="identifier">std</span><span class="special">::</span><span class="identifier">size_t</span></code> + conversion when calculating sizes from the max load factor, and use <code class="computeroutput"><span class="keyword">double</span></code> in the calculation for greater accuracy. + </li> +<li class="listitem"> + Fix some errors in the examples. + </li> +</ul></div> +<h3> +<a name="unordered.changes.h2"></a> + <span><a name="unordered.changes.boost_1_36_0"></a></span><a class="link" href="changes.html#unordered.changes.boost_1_36_0">Boost + 1.36.0</a> + </h3> +<p> + First official release. + </p> +<div class="itemizedlist"><ul class="itemizedlist" type="disc"> +<li class="listitem"> + Rearrange the internals. + </li> +<li class="listitem"> + Move semantics - full support when rvalue references are available, emulated + using a cut down version of the Adobe move library when they are not. + </li> +<li class="listitem"> + Emplace support when rvalue references and variadic template are available. + </li> +<li class="listitem"> + More efficient node allocation when rvalue references and variadic template + are available. + </li> +<li class="listitem"> + Added equality operators. + </li> +</ul></div> +<h3> +<a name="unordered.changes.h3"></a> + <span><a name="unordered.changes.boost_1_37_0"></a></span><a class="link" href="changes.html#unordered.changes.boost_1_37_0">Boost + 1.37.0</a> + </h3> +<div class="itemizedlist"><ul class="itemizedlist" type="disc"> +<li class="listitem"> + Rename overload of <code class="computeroutput"><span class="identifier">emplace</span></code> + with hint, to <code class="computeroutput"><span class="identifier">emplace_hint</span></code> + as specified in <a href="http://www.open-std.org/JTC1/SC22/WG21/docs/papers/2008/n2691.pdf" target="_top">n2691</a>. + </li> +<li class="listitem"> + Provide forwarding headers at <code class="computeroutput"><span class="special"><</span><span class="identifier">boost</span><span class="special">/</span><span class="identifier">unordered</span><span class="special">/</span><span class="identifier">unordered_map_fwd</span><span class="special">.</span><span class="identifier">hpp</span><span class="special">></span></code> + and <code class="computeroutput"><span class="special"><</span><span class="identifier">boost</span><span class="special">/</span><span class="identifier">unordered</span><span class="special">/</span><span class="identifier">unordered_set_fwd</span><span class="special">.</span><span class="identifier">hpp</span><span class="special">></span></code>. + </li> +<li class="listitem"> + Move all the implementation inside <code class="computeroutput"><span class="identifier">boost</span><span class="special">/</span><span class="identifier">unordered</span></code>, + to assist modularization and hopefully make it easier to track changes + in subversion. + </li> +</ul></div> +<h3> +<a name="unordered.changes.h4"></a> + <span><a name="unordered.changes.boost_1_38_0"></a></span><a class="link" href="changes.html#unordered.changes.boost_1_38_0">Boost + 1.38.0</a> + </h3> +<div class="itemizedlist"><ul class="itemizedlist" type="disc"> +<li class="listitem"> + Use <a href="../../../libs/utility/swap.html" target="_top"><code class="computeroutput"><span class="identifier">boost</span><span class="special">::</span><span class="identifier">swap</span></code></a>. + </li> +<li class="listitem"> + <a href="https://svn.boost.org/trac/boost/ticket/2237" target="_top">Ticket 2237</a>: + Document that the equality and inequality operators are undefined for two + objects if their equality predicates aren't equivalent. Thanks to Daniel + Krügler. + </li> +<li class="listitem"> + <a href="https://svn.boost.org/trac/boost/ticket/1710" target="_top">Ticket 1710</a>: + Use a larger prime number list. Thanks to Thorsten Ottosen and Hervé Brönnimann. + </li> +<li class="listitem"> + Use <a href="../../../libs/type_traits/doc/html/boost_typetraits/category/alignment.html" target="_top">aligned + storage</a> to store the types. This changes the way the allocator + is used to construct nodes. It used to construct the node with two calls + to the allocator's <code class="computeroutput"><span class="identifier">construct</span></code> + method - once for the pointers and once for the value. It now constructs + the node with a single call to construct and then constructs the value + using in place construction. + </li> +<li class="listitem"> + Add support for C++0x initializer lists where they're available (currently + only g++ 4.4 in C++0x mode). + </li> +</ul></div> +<h3> +<a name="unordered.changes.h5"></a> + <span><a name="unordered.changes.boost_1_39_0"></a></span><a class="link" href="changes.html#unordered.changes.boost_1_39_0">Boost + 1.39.0</a> + </h3> +<div class="itemizedlist"><ul class="itemizedlist" type="disc"> +<li class="listitem"> + <a href="https://svn.boost.org/trac/boost/ticket/2756" target="_top">Ticket 2756</a>: + Avoid a warning on Visual C++ 2009. + </li> +<li class="listitem"> + Some other minor internal changes to the implementation, tests and documentation. + </li> +<li class="listitem"> + Avoid an unnecessary copy in <code class="computeroutput"><span class="keyword">operator</span><span class="special">[]</span></code>. + </li> +<li class="listitem"> + <a href="https://svn.boost.org/trac/boost/ticket/2975" target="_top">Ticket 2975</a>: + Fix length of prime number list. + </li> +</ul></div> +<h3> +<a name="unordered.changes.h6"></a> + <span><a name="unordered.changes.boost_1_40_0"></a></span><a class="link" href="changes.html#unordered.changes.boost_1_40_0">Boost + 1.40.0</a> + </h3> +<div class="itemizedlist"><ul class="itemizedlist" type="disc"> +<li class="listitem"> + <a href="https://svn.boost.org/trac/boost/ticket/2975" target="_top">Ticket 2975</a>: + Store the prime list as a preprocessor sequence - so that it will always + get the length right if it changes again in the future. + </li> +<li class="listitem"> + <a href="https://svn.boost.org/trac/boost/ticket/1978" target="_top">Ticket 1978</a>: + Implement <code class="computeroutput"><span class="identifier">emplace</span></code> for all + compilers. + </li> +<li class="listitem"> + <a href="https://svn.boost.org/trac/boost/ticket/2908" target="_top">Ticket 2908</a>, + <a href="https://svn.boost.org/trac/boost/ticket/3096" target="_top">Ticket 3096</a>: + Some workarounds for old versions of borland, including adding explicit + destructors to all containers. + </li> +<li class="listitem"> + <a href="https://svn.boost.org/trac/boost/ticket/3082" target="_top">Ticket 3082</a>: + Disable incorrect Visual C++ warnings. + </li> +<li class="listitem"> + Better configuration for C++0x features when the headers aren't available. + </li> +<li class="listitem"> + Create less buckets by default. + </li> +</ul></div> +<h3> +<a name="unordered.changes.h7"></a> + <span><a name="unordered.changes.boost_1_41_0___major_update"></a></span><a class="link" href="changes.html#unordered.changes.boost_1_41_0___major_update">Boost + 1.41.0 - Major update</a> + </h3> +<div class="itemizedlist"><ul class="itemizedlist" type="disc"> +<li class="listitem"> + The original version made heavy use of macros to sidestep some of the older + compilers' poor template support. But since I no longer support those compilers + and the macro use was starting to become a maintenance burden it has been + rewritten to use templates instead of macros for the implementation classes. + </li> +<li class="listitem"> + The container objcet is now smaller thanks to using <code class="computeroutput"><span class="identifier">boost</span><span class="special">::</span><span class="identifier">compressed_pair</span></code> + for EBO and a slightly different function buffer - now using a bool instead + of a member pointer. + </li> +<li class="listitem"> + Buckets are allocated lazily which means that constructing an empty container + will not allocate any memory. + </li> +</ul></div> +<h3> +<a name="unordered.changes.h8"></a> + <span><a name="unordered.changes.boost_1_42_0"></a></span><a class="link" href="changes.html#unordered.changes.boost_1_42_0">Boost + 1.42.0</a> + </h3> +<div class="itemizedlist"><ul class="itemizedlist" type="disc"> +<li class="listitem"> + Support instantiating the containers with incomplete value types. + </li> +<li class="listitem"> + Reduced the number of warnings (mostly in tests). + </li> +<li class="listitem"> + Improved codegear compatibility. + </li> +<li class="listitem"> + <a href="http://svn.boost.org/trac/boost/ticket/3693" target="_top">Ticket 3693</a>: + Add <code class="computeroutput"><span class="identifier">erase_return_void</span></code> as + a temporary workaround for the current <code class="computeroutput"><span class="identifier">erase</span></code> + which can be inefficient because it has to find the next element to return + an iterator. + </li> +<li class="listitem"> + Add templated find overload for compatible keys. + </li> +<li class="listitem"> + <a href="http://svn.boost.org/trac/boost/ticket/3773" target="_top">Ticket 3773</a>: + Add missing <code class="computeroutput"><span class="identifier">std</span></code> qualifier + to <code class="computeroutput"><span class="identifier">ptrdiff_t</span></code>. + </li> +<li class="listitem"> + Some code formatting changes to fit almost all lines into 80 characters. + </li> +</ul></div> +<h3> +<a name="unordered.changes.h9"></a> + <span><a name="unordered.changes.boost_1_43_0"></a></span><a class="link" href="changes.html#unordered.changes.boost_1_43_0">Boost + 1.43.0</a> + </h3> +<div class="itemizedlist"><ul class="itemizedlist" type="disc"> +<li class="listitem"> + <a href="http://svn.boost.org/trac/boost/ticket/3966" target="_top">Ticket 3966</a>: + <code class="computeroutput"><span class="identifier">erase_return_void</span></code> is now + <code class="computeroutput"><span class="identifier">quick_erase</span></code>, which is the + <a href="http://home.roadrunner.com/~hinnant/issue_review/lwg-active.html#579" target="_top">current + forerunner for resolving the slow erase by iterator</a>, although there's + a strong possibility that this may change in the future. The old method + name remains for backwards compatibility but is considered deprecated and + will be removed in a future release. + </li> +<li class="listitem"> + Use Boost.Exception. + </li> +<li class="listitem"> + Stop using deprecated <code class="computeroutput"><span class="identifier">BOOST_HAS_</span><span class="special">*</span></code> macros. + </li> +</ul></div> +<h3> +<a name="unordered.changes.h10"></a> + <span><a name="unordered.changes.boost_1_45_0"></a></span><a class="link" href="changes.html#unordered.changes.boost_1_45_0">Boost + 1.45.0</a> + </h3> +<div class="itemizedlist"><ul class="itemizedlist" type="disc"><li class="listitem"> + Fix a bug when inserting into an <code class="computeroutput"><span class="identifier">unordered_map</span></code> + or <code class="computeroutput"><span class="identifier">unordered_set</span></code> using + iterators which returns <code class="computeroutput"><span class="identifier">value_type</span></code> + by copy. + </li></ul></div> +<h3> +<a name="unordered.changes.h11"></a> + <span><a name="unordered.changes.boost_1_48_0___major_update"></a></span><a class="link" href="changes.html#unordered.changes.boost_1_48_0___major_update">Boost + 1.48.0 - Major update</a> + </h3> +<p> + This is major change which has been converted to use Boost.Move's move emulation, + and be more compliant with the C++11 standard. See the <a class="link" href="compliance.html" title="C++11 Compliance">compliance + section</a> for details. + </p> +<p> + The container now meets C++11's complexity requirements, but to do so uses + a little more memory. This means that <code class="computeroutput"><span class="identifier">quick_erase</span></code> + and <code class="computeroutput"><span class="identifier">erase_return_void</span></code> are no + longer required, they'll be removed in a future version. + </p> +<p> + C++11 support has resulted in some breaking changes: + </p> +<div class="itemizedlist"><ul class="itemizedlist" type="disc"> +<li class="listitem"> + Equality comparison has been changed to the C++11 specification. In a container + with equivalent keys, elements in a group with equal keys used to have + to be in the same order to be considered equal, now they can be a permutation + of each other. To use the old behavior define the macro <code class="computeroutput"><span class="identifier">BOOST_UNORDERED_DEPRECATED_EQUALITY</span></code>. + </li> +<li class="listitem"> + The behaviour of swap is different when the two containers to be swapped + has unequal allocators. It used to allocate new nodes using the appropriate + allocators, it now swaps the allocators if the allocator has a member structure + <code class="computeroutput"><span class="identifier">propagate_on_container_swap</span></code>, + such that <code class="computeroutput"><span class="identifier">propagate_on_container_swap</span><span class="special">::</span><span class="identifier">value</span></code> + is true. + </li> +<li class="listitem"> + Allocator's <code class="computeroutput"><span class="identifier">construct</span></code> and + <code class="computeroutput"><span class="identifier">destroy</span></code> functions are called + with raw pointers, rather than the allocator's <code class="computeroutput"><span class="identifier">pointer</span></code> + type. + </li> +<li class="listitem"> + <code class="computeroutput"><span class="identifier">emplace</span></code> used to emulate + the variadic pair constructors that appeared in early C++0x drafts. Since + they were removed it no longer does so. It does emulate the new <code class="computeroutput"><span class="identifier">piecewise_construct</span></code> pair constructors + - only you need to use <code class="computeroutput"><span class="identifier">boost</span><span class="special">::</span><span class="identifier">piecewise_construct</span></code>. + To use the old emulation of the variadic consturctors define <code class="computeroutput"><span class="identifier">BOOST_UNORDERED_DEPRECATED_PAIR_CONSTRUCT</span></code>. + </li> +</ul></div> +<h3> +<a name="unordered.changes.h12"></a> + <span><a name="unordered.changes.boost_1_49_0"></a></span><a class="link" href="changes.html#unordered.changes.boost_1_49_0">Boost + 1.49.0</a> + </h3> +<div class="itemizedlist"><ul class="itemizedlist" type="disc"> +<li class="listitem"> + Fix warning due to accidental odd assignment. + </li> +<li class="listitem"> + Slightly better error messages. + </li> +</ul></div> +</div> +<table xmlns:rev="http://www.cs.rpi.edu/~gregod/boost/tools/doc/revision" width="100%"><tr> +<td align="left"></td> +<td align="right"><div class="copyright-footer">Copyright © 2003, 2004 Jeremy B. Maitin-Shepard<br>Copyright © 2005-2008 Daniel + James<p> + Distributed under the Boost Software License, Version 1.0. (See accompanying + file LICENSE_1_0.txt or copy at <a href="http://www.boost.org/LICENSE_1_0.txt" target="_top">http://www.boost.org/LICENSE_1_0.txt</a>) + </p> +</div></td> +</tr></table> +<hr> +<div class="spirit-nav"> +<a accesskey="p" href="rationale.html"><img src="../../../doc/src/images/prev.png" alt="Prev"></a><a accesskey="u" href="../unordered.html"><img src="../../../doc/src/images/up.png" alt="Up"></a><a accesskey="h" href="../index.html"><img src="../../../doc/src/images/home.png" alt="Home"></a><a accesskey="n" href="reference.html"><img src="../../../doc/src/images/next.png" alt="Next"></a> +</div> +</body> +</html> diff --git a/doc/html/unordered/comparison.html b/doc/html/unordered/comparison.html new file mode 100755 index 0000000000..ffceedfd2e --- /dev/null +++ b/doc/html/unordered/comparison.html @@ -0,0 +1,519 @@ +<html> +<head> +<meta http-equiv="Content-Type" content="text/html; charset=US-ASCII"> +<title>Comparison with Associative Containers</title> +<link rel="stylesheet" href="../../../doc/src/boostbook.css" type="text/css"> +<meta name="generator" content="DocBook XSL Stylesheets V1.76.1"> +<link rel="home" href="../index.html" title="The Boost C++ Libraries BoostBook Documentation Subset"> +<link rel="up" href="../unordered.html" title="Chapter 33. Boost.Unordered"> +<link rel="prev" href="hash_equality.html" title="Equality Predicates and Hash Functions"> +<link rel="next" href="compliance.html" title="C++11 Compliance"> +</head> +<body bgcolor="white" text="black" link="#0000FF" vlink="#840084" alink="#0000FF"> +<table cellpadding="2" width="100%"><tr> +<td valign="top"><img alt="Boost C++ Libraries" width="277" height="86" src="../../../boost.png"></td> +<td align="center"><a href="../../../index.html">Home</a></td> +<td align="center"><a href="../../../libs/libraries.htm">Libraries</a></td> +<td align="center"><a href="http://www.boost.org/users/people.html">People</a></td> +<td align="center"><a href="http://www.boost.org/users/faq.html">FAQ</a></td> +<td align="center"><a href="../../../more/index.htm">More</a></td> +</tr></table> +<hr> +<div class="spirit-nav"> +<a accesskey="p" href="hash_equality.html"><img src="../../../doc/src/images/prev.png" alt="Prev"></a><a accesskey="u" href="../unordered.html"><img src="../../../doc/src/images/up.png" alt="Up"></a><a accesskey="h" href="../index.html"><img src="../../../doc/src/images/home.png" alt="Home"></a><a accesskey="n" href="compliance.html"><img src="../../../doc/src/images/next.png" alt="Next"></a> +</div> +<div class="section"> +<div class="titlepage"><div><div><h2 class="title" style="clear: both"> +<a name="unordered.comparison"></a><a class="link" href="comparison.html" title="Comparison with Associative Containers">Comparison with Associative Containers</a> +</h2></div></div></div> +<div class="table"> +<a name="unordered.comparison.interface_differences"></a><p class="title"><b>Table 33.4. Interface differences.</b></p> +<div class="table-contents"><table class="table" summary="Interface differences."> +<colgroup> +<col> +<col> +</colgroup> +<thead><tr> +<th> + <p> + Associative Containers + </p> + </th> +<th> + <p> + Unordered Associative Containers + </p> + </th> +</tr></thead> +<tbody> +<tr> +<td> + <p> + Parameterized by an ordering relation <code class="computeroutput"><span class="identifier">Compare</span></code> + </p> + </td> +<td> + <p> + Parameterized by a function object <code class="computeroutput"><span class="identifier">Hash</span></code> + and an equivalence relation <code class="computeroutput"><span class="identifier">Pred</span></code> + </p> + </td> +</tr> +<tr> +<td> + <p> + Keys can be compared using <code class="computeroutput"><span class="identifier">key_compare</span></code> + which is accessed by member function <code class="computeroutput"><span class="identifier">key_comp</span><span class="special">()</span></code>, values can be compared using + <code class="computeroutput"><span class="identifier">value_compare</span></code> which + is accessed by member function <code class="computeroutput"><span class="identifier">value_comp</span><span class="special">()</span></code>. + </p> + </td> +<td> + <p> + Keys can be hashed using <code class="computeroutput"><span class="identifier">hasher</span></code> + which is accessed by member function <code class="computeroutput"><span class="identifier">hash_function</span><span class="special">()</span></code>, and checked for equality using + <code class="computeroutput"><span class="identifier">key_equal</span></code> which is + accessed by member function <code class="computeroutput"><span class="identifier">key_eq</span><span class="special">()</span></code>. There is no function object for + compared or hashing values. + </p> + </td> +</tr> +<tr> +<td> + <p> + Constructors have optional extra parameters for the comparison object. + </p> + </td> +<td> + <p> + Constructors have optional extra parameters for the initial minimum + number of buckets, a hash function and an equality object. + </p> + </td> +</tr> +<tr> +<td> + <p> + Keys <code class="computeroutput"><span class="identifier">k1</span></code>, <code class="computeroutput"><span class="identifier">k2</span></code> are considered equivalent if + <code class="computeroutput"><span class="special">!</span><span class="identifier">Compare</span><span class="special">(</span><span class="identifier">k1</span><span class="special">,</span> <span class="identifier">k2</span><span class="special">)</span> <span class="special">&&</span> + <span class="special">!</span><span class="identifier">Compare</span><span class="special">(</span><span class="identifier">k2</span><span class="special">,</span> <span class="identifier">k1</span><span class="special">)</span></code> + </p> + </td> +<td> + <p> + Keys <code class="computeroutput"><span class="identifier">k1</span></code>, <code class="computeroutput"><span class="identifier">k2</span></code> are considered equivalent if + <code class="computeroutput"><span class="identifier">Pred</span><span class="special">(</span><span class="identifier">k1</span><span class="special">,</span> <span class="identifier">k2</span><span class="special">)</span></code> + </p> + </td> +</tr> +<tr> +<td> + <p> + Member function <code class="computeroutput"><span class="identifier">lower_bound</span><span class="special">(</span><span class="identifier">k</span><span class="special">)</span></code> and <code class="computeroutput"><span class="identifier">upper_bound</span><span class="special">(</span><span class="identifier">k</span><span class="special">)</span></code> + </p> + </td> +<td> + <p> + No equivalent. Since the elements aren't ordered <code class="computeroutput"><span class="identifier">lower_bound</span></code> + and <code class="computeroutput"><span class="identifier">upper_bound</span></code> would + be meaningless. + </p> + </td> +</tr> +<tr> +<td> + <p> + <code class="computeroutput"><span class="identifier">equal_range</span><span class="special">(</span><span class="identifier">k</span><span class="special">)</span></code> + returns an empty range at the position that k would be inserted if + k isn't present in the container. + </p> + </td> +<td> + <p> + <code class="computeroutput"><span class="identifier">equal_range</span><span class="special">(</span><span class="identifier">k</span><span class="special">)</span></code> + returns a range at the end of the container if k isn't present in + the container. It can't return a positioned range as k could be inserted + into multiple place. To find out the bucket that k would be inserted + into use <code class="computeroutput"><span class="identifier">bucket</span><span class="special">(</span><span class="identifier">k</span><span class="special">)</span></code>. + But remember that an insert can cause the container to rehash - meaning + that the element can be inserted into a different bucket. + </p> + </td> +</tr> +<tr> +<td> + <p> + <code class="computeroutput"><span class="identifier">iterator</span></code>, <code class="computeroutput"><span class="identifier">const_iterator</span></code> are of the bidirectional + category. + </p> + </td> +<td> + <p> + <code class="computeroutput"><span class="identifier">iterator</span></code>, <code class="computeroutput"><span class="identifier">const_iterator</span></code> are of at least + the forward category. + </p> + </td> +</tr> +<tr> +<td> + <p> + Iterators, pointers and references to the container's elements are + never invalidated. + </p> + </td> +<td> + <p> + <a class="link" href="buckets.html#unordered.buckets.iterator_invalidation">Iterators + can be invalidated by calls to insert or rehash</a>. Pointers + and references to the container's elements are never invalidated. + </p> + </td> +</tr> +<tr> +<td> + <p> + Iterators iterate through the container in the order defined by the + comparison object. + </p> + </td> +<td> + <p> + Iterators iterate through the container in an arbitrary order, that + can change as elements are inserted. Although, equivalent elements + are always adjacent. + </p> + </td> +</tr> +<tr> +<td> + <p> + No equivalent + </p> + </td> +<td> + <p> + Local iterators can be used to iterate through individual buckets. + (The order of local iterators and iterators aren't required to have + any correspondence.) + </p> + </td> +</tr> +<tr> +<td> + <p> + Can be compared using the <code class="computeroutput"><span class="special">==</span></code>, + <code class="computeroutput"><span class="special">!=</span></code>, <code class="computeroutput"><span class="special"><</span></code>, + <code class="computeroutput"><span class="special"><=</span></code>, <code class="computeroutput"><span class="special">></span></code>, <code class="computeroutput"><span class="special">>=</span></code> + operators. + </p> + </td> +<td> + <p> + Can be compared using the <code class="computeroutput"><span class="special">==</span></code> + and <code class="computeroutput"><span class="special">!=</span></code> operators. + </p> + </td> +</tr> +<tr> +<td> + </td> +<td> + <p> + When inserting with a hint, implementations are permitted to ignore + the hint. + </p> + </td> +</tr> +<tr> +<td> + <p> + <code class="computeroutput"><span class="identifier">erase</span></code> never throws + an exception + </p> + </td> +<td> + <p> + The containers' hash or predicate function can throw exceptions from + <code class="computeroutput"><span class="identifier">erase</span></code> + </p> + </td> +</tr> +</tbody> +</table></div> +</div> +<br class="table-break"><div class="table"> +<a name="unordered.comparison.complexity_guarantees"></a><p class="title"><b>Table 33.5. Complexity Guarantees</b></p> +<div class="table-contents"><table class="table" summary="Complexity Guarantees"> +<colgroup> +<col> +<col> +<col> +</colgroup> +<thead><tr> +<th> + <p> + Operation + </p> + </th> +<th> + <p> + Associative Containers + </p> + </th> +<th> + <p> + Unordered Associative Containers + </p> + </th> +</tr></thead> +<tbody> +<tr> +<td> + <p> + Construction of empty container + </p> + </td> +<td> + <p> + constant + </p> + </td> +<td> + <p> + O(<span class="emphasis"><em>n</em></span>) where <span class="emphasis"><em>n</em></span> is the minimum + number of buckets. + </p> + </td> +</tr> +<tr> +<td> + <p> + Construction of container from a range of <span class="emphasis"><em>N</em></span> + elements + </p> + </td> +<td> + <p> + O(<span class="emphasis"><em>N</em></span> log <span class="emphasis"><em>N</em></span>), O(<span class="emphasis"><em>N</em></span>) + if the range is sorted with <code class="computeroutput"><span class="identifier">value_comp</span><span class="special">()</span></code> + </p> + </td> +<td> + <p> + Average case O(<span class="emphasis"><em>N</em></span>), worst case O(<span class="emphasis"><em>N</em></span><sup>2</sup>) + </p> + </td> +</tr> +<tr> +<td> + <p> + Insert a single element + </p> + </td> +<td> + <p> + logarithmic + </p> + </td> +<td> + <p> + Average case constant, worst case linear + </p> + </td> +</tr> +<tr> +<td> + <p> + Insert a single element with a hint + </p> + </td> +<td> + <p> + Amortized constant if t elements inserted right after hint, logarithmic + otherwise + </p> + </td> +<td> + <p> + Average case constant, worst case linear (ie. the same as a normal + insert). + </p> + </td> +</tr> +<tr> +<td> + <p> + Inserting a range of <span class="emphasis"><em>N</em></span> elements + </p> + </td> +<td> + <p> + <span class="emphasis"><em>N</em></span> log(<code class="computeroutput"><span class="identifier">size</span><span class="special">()</span></code>+<span class="emphasis"><em>N</em></span>) + </p> + </td> +<td> + <p> + Average case O(<span class="emphasis"><em>N</em></span>), worst case O(<span class="emphasis"><em>N</em></span> + * <code class="computeroutput"><span class="identifier">size</span><span class="special">()</span></code>) + </p> + </td> +</tr> +<tr> +<td> + <p> + Erase by key, <code class="computeroutput"><span class="identifier">k</span></code> + </p> + </td> +<td> + <p> + O(log(<code class="computeroutput"><span class="identifier">size</span><span class="special">()</span></code>) + + <code class="computeroutput"><span class="identifier">count</span><span class="special">(</span><span class="identifier">k</span><span class="special">)</span></code>) + </p> + </td> +<td> + <p> + Average case: O(<code class="computeroutput"><span class="identifier">count</span><span class="special">(</span><span class="identifier">k</span><span class="special">)</span></code>), Worst case: O(<code class="computeroutput"><span class="identifier">size</span><span class="special">()</span></code>) + </p> + </td> +</tr> +<tr> +<td> + <p> + Erase a single element by iterator + </p> + </td> +<td> + <p> + Amortized constant + </p> + </td> +<td> + <p> + Average case: O(1), Worst case: O(<code class="computeroutput"><span class="identifier">size</span><span class="special">()</span></code>) + </p> + </td> +</tr> +<tr> +<td> + <p> + Erase a range of <span class="emphasis"><em>N</em></span> elements + </p> + </td> +<td> + <p> + O(log(<code class="computeroutput"><span class="identifier">size</span><span class="special">()</span></code>) + + <span class="emphasis"><em>N</em></span>) + </p> + </td> +<td> + <p> + Average case: O(<span class="emphasis"><em>N</em></span>), Worst case: O(<code class="computeroutput"><span class="identifier">size</span><span class="special">()</span></code>) + </p> + </td> +</tr> +<tr> +<td> + <p> + Clearing the container + </p> + </td> +<td> + <p> + O(<code class="computeroutput"><span class="identifier">size</span><span class="special">()</span></code>) + </p> + </td> +<td> + <p> + O(<code class="computeroutput"><span class="identifier">size</span><span class="special">()</span></code>) + </p> + </td> +</tr> +<tr> +<td> + <p> + Find + </p> + </td> +<td> + <p> + logarithmic + </p> + </td> +<td> + <p> + Average case: O(1), Worst case: O(<code class="computeroutput"><span class="identifier">size</span><span class="special">()</span></code>) + </p> + </td> +</tr> +<tr> +<td> + <p> + Count + </p> + </td> +<td> + <p> + O(log(<code class="computeroutput"><span class="identifier">size</span><span class="special">()</span></code>) + + <code class="computeroutput"><span class="identifier">count</span><span class="special">(</span><span class="identifier">k</span><span class="special">)</span></code>) + </p> + </td> +<td> + <p> + Average case: O(1), Worst case: O(<code class="computeroutput"><span class="identifier">size</span><span class="special">()</span></code>) + </p> + </td> +</tr> +<tr> +<td> + <p> + <code class="computeroutput"><span class="identifier">equal_range</span><span class="special">(</span><span class="identifier">k</span><span class="special">)</span></code> + </p> + </td> +<td> + <p> + logarithmic + </p> + </td> +<td> + <p> + Average case: O(<code class="computeroutput"><span class="identifier">count</span><span class="special">(</span><span class="identifier">k</span><span class="special">)</span></code>), Worst case: O(<code class="computeroutput"><span class="identifier">size</span><span class="special">()</span></code>) + </p> + </td> +</tr> +<tr> +<td> + <p> + <code class="computeroutput"><span class="identifier">lower_bound</span></code>,<code class="computeroutput"><span class="identifier">upper_bound</span></code> + </p> + </td> +<td> + <p> + logarithmic + </p> + </td> +<td> + <p> + n/a + </p> + </td> +</tr> +</tbody> +</table></div> +</div> +<br class="table-break"> +</div> +<table xmlns:rev="http://www.cs.rpi.edu/~gregod/boost/tools/doc/revision" width="100%"><tr> +<td align="left"></td> +<td align="right"><div class="copyright-footer">Copyright © 2003, 2004 Jeremy B. Maitin-Shepard<br>Copyright © 2005-2008 Daniel + James<p> + Distributed under the Boost Software License, Version 1.0. (See accompanying + file LICENSE_1_0.txt or copy at <a href="http://www.boost.org/LICENSE_1_0.txt" target="_top">http://www.boost.org/LICENSE_1_0.txt</a>) + </p> +</div></td> +</tr></table> +<hr> +<div class="spirit-nav"> +<a accesskey="p" href="hash_equality.html"><img src="../../../doc/src/images/prev.png" alt="Prev"></a><a accesskey="u" href="../unordered.html"><img src="../../../doc/src/images/up.png" alt="Up"></a><a accesskey="h" href="../index.html"><img src="../../../doc/src/images/home.png" alt="Home"></a><a accesskey="n" href="compliance.html"><img src="../../../doc/src/images/next.png" alt="Next"></a> +</div> +</body> +</html> diff --git a/doc/html/unordered/compliance.html b/doc/html/unordered/compliance.html new file mode 100755 index 0000000000..543b0f6427 --- /dev/null +++ b/doc/html/unordered/compliance.html @@ -0,0 +1,179 @@ +<html> +<head> +<meta http-equiv="Content-Type" content="text/html; charset=US-ASCII"> +<title>C++11 Compliance</title> +<link rel="stylesheet" href="../../../doc/src/boostbook.css" type="text/css"> +<meta name="generator" content="DocBook XSL Stylesheets V1.76.1"> +<link rel="home" href="../index.html" title="The Boost C++ Libraries BoostBook Documentation Subset"> +<link rel="up" href="../unordered.html" title="Chapter 33. Boost.Unordered"> +<link rel="prev" href="comparison.html" title="Comparison with Associative Containers"> +<link rel="next" href="rationale.html" title="Implementation Rationale"> +</head> +<body bgcolor="white" text="black" link="#0000FF" vlink="#840084" alink="#0000FF"> +<table cellpadding="2" width="100%"><tr> +<td valign="top"><img alt="Boost C++ Libraries" width="277" height="86" src="../../../boost.png"></td> +<td align="center"><a href="../../../index.html">Home</a></td> +<td align="center"><a href="../../../libs/libraries.htm">Libraries</a></td> +<td align="center"><a href="http://www.boost.org/users/people.html">People</a></td> +<td align="center"><a href="http://www.boost.org/users/faq.html">FAQ</a></td> +<td align="center"><a href="../../../more/index.htm">More</a></td> +</tr></table> +<hr> +<div class="spirit-nav"> +<a accesskey="p" href="comparison.html"><img src="../../../doc/src/images/prev.png" alt="Prev"></a><a accesskey="u" href="../unordered.html"><img src="../../../doc/src/images/up.png" alt="Up"></a><a accesskey="h" href="../index.html"><img src="../../../doc/src/images/home.png" alt="Home"></a><a accesskey="n" href="rationale.html"><img src="../../../doc/src/images/next.png" alt="Next"></a> +</div> +<div class="section"> +<div class="titlepage"><div><div><h2 class="title" style="clear: both"> +<a name="unordered.compliance"></a><a class="link" href="compliance.html" title="C++11 Compliance">C++11 Compliance</a> +</h2></div></div></div> +<div class="toc"><dl> +<dt><span class="section"><a href="compliance.html#unordered.compliance.move">Move emulation</a></span></dt> +<dt><span class="section"><a href="compliance.html#unordered.compliance.allocator_compliance">Use of allocators</a></span></dt> +<dt><span class="section"><a href="compliance.html#unordered.compliance.pairs">Pairs</a></span></dt> +<dt><span class="section"><a href="compliance.html#unordered.compliance.misc">Miscellaneous</a></span></dt> +</dl></div> +<div class="section"> +<div class="titlepage"><div><div><h3 class="title"> +<a name="unordered.compliance.move"></a><a class="link" href="compliance.html#unordered.compliance.move" title="Move emulation">Move emulation</a> +</h3></div></div></div> +<p> + Support for move semantics is implemented using Boost.Move. If rvalue references + are available it will use them, but if not it uses a close, but imperfect + emulation. On such compilers you'll need to use Boost.Move to take advantage + of using movable container elements, also note that: + </p> +<div class="itemizedlist"><ul class="itemizedlist" type="disc"> +<li class="listitem"> + Non-copyable objects can be stored in the containers, but without support + for rvalue references the container will not be movable. + </li> +<li class="listitem"> + Argument forwarding is not perfect. + </li> +</ul></div> +</div> +<div class="section"> +<div class="titlepage"><div><div><h3 class="title"> +<a name="unordered.compliance.allocator_compliance"></a><a class="link" href="compliance.html#unordered.compliance.allocator_compliance" title="Use of allocators">Use of allocators</a> +</h3></div></div></div> +<p> + C++11 introduced a new allocator system. It's backwards compatible due to + the lax requirements for allocators in the old standard, but might need some + changes for allocators which worked with the old versions of the unordered + containers. It uses a traits class, <code class="computeroutput"><span class="identifier">allocator_traits</span></code> + to handle the allocator adding extra functionality, and making some methods + and types optional. During development a stable release of <code class="computeroutput"><span class="identifier">allocator_traits</span></code> wasn't available so an + internal partial implementation is always used in this version. Hopefully + a future version will use the standard implementation where available. + </p> +<p> + The member functions <code class="computeroutput"><span class="identifier">construct</span></code>, + <code class="computeroutput"><span class="identifier">destroy</span></code> and <code class="computeroutput"><span class="identifier">max_size</span></code> are now optional, if they're not + available a fallback is used. A full implementation of <code class="computeroutput"><span class="identifier">allocator_traits</span></code> + requires sophisticated member function detection so that the fallback is + used whenever the member function call is not well formed. This requires + support for SFINAE expressions, which are available on GCC from version 4.4 + and Clang. + </p> +<p> + On other compilers, there's just a test to see if the allocator has a member, + but no check that it can be called. So rather than using a fallback there + will just be a compile error. + </p> +<p> + <code class="computeroutput"><span class="identifier">propagate_on_container_copy_assignment</span></code>, + <code class="computeroutput"><span class="identifier">propagate_on_container_move_assignment</span></code>, + <code class="computeroutput"><span class="identifier">propagate_on_container_swap</span></code> + and <code class="computeroutput"><span class="identifier">select_on_container_copy_construction</span></code> + are also supported. Due to imperfect move emulation, some assignments might + check <code class="computeroutput"><span class="identifier">propagate_on_container_copy_assignment</span></code> + on some compilers and <code class="computeroutput"><span class="identifier">propagate_on_container_move_assignment</span></code> + on others. + </p> +<p> + The use of the allocator's construct and destruct methods might be a bit + surprising. Nodes are constructed and destructed using the allocator, but + the elements are stored in aligned space within the node and constructed + and destructed by calling the constructor and destructor directly. + </p> +<p> + In C++11 the allocator's construct function has the signature: + </p> +<pre class="programlisting"><span class="keyword">template</span> <span class="special"><</span><span class="keyword">class</span> <span class="identifier">U</span><span class="special">,</span> <span class="keyword">class</span><span class="special">...</span> <span class="identifier">Args</span><span class="special">></span> +<span class="keyword">void</span> <span class="identifier">construct</span><span class="special">(</span><span class="identifier">U</span><span class="special">*</span> <span class="identifier">p</span><span class="special">,</span> <span class="identifier">Args</span><span class="special">&&...</span> <span class="identifier">args</span><span class="special">);</span> +</pre> +<p> + which supports calling <code class="computeroutput"><span class="identifier">construct</span></code> + for the contained object, but most existing allocators don't support this. + If member function detection was good enough then with old allocators it + would fall back to calling the element's constructor directly but in general, + detection isn't good enough to do this which is why Boost.Unordered just + calls the constructor directly every time. In most cases this will work okay. + </p> +<p> + <code class="computeroutput"><span class="identifier">pointer_traits</span></code> aren't used. + Instead, pointer types are obtained from rebound allocators, this can cause + problems if the allocator can't be used with incomplete types. If <code class="computeroutput"><span class="identifier">const_pointer</span></code> is not defined in the allocator, + <code class="computeroutput"><span class="identifier">boost</span><span class="special">::</span><span class="identifier">pointer_to_other</span><span class="special"><</span><span class="identifier">pointer</span><span class="special">,</span> <span class="keyword">const</span> <span class="identifier">value_type</span><span class="special">>::</span><span class="identifier">type</span></code> + is used to obtain a const pointer. + </p> +</div> +<div class="section"> +<div class="titlepage"><div><div><h3 class="title"> +<a name="unordered.compliance.pairs"></a><a class="link" href="compliance.html#unordered.compliance.pairs" title="Pairs">Pairs</a> +</h3></div></div></div> +<p> + Since the containers use <code class="computeroutput"><span class="identifier">std</span><span class="special">::</span><span class="identifier">pair</span></code> + they're limited to the version from the current standard library. But since + C++11 <code class="computeroutput"><span class="identifier">std</span><span class="special">::</span><span class="identifier">pair</span></code>'s <code class="computeroutput"><span class="identifier">piecewise_construct</span></code> + based constructor is very useful, <code class="computeroutput"><span class="identifier">emplace</span></code> + emulates it with a <code class="computeroutput"><span class="identifier">piecewise_construct</span></code> + in the <code class="computeroutput"><span class="identifier">boost</span><span class="special">::</span><span class="identifier">unordered</span></code> namespace. So for example, the + following will work: + </p> +<pre class="programlisting"><span class="identifier">boost</span><span class="special">::</span><span class="identifier">unordered_multimap</span><span class="special"><</span><span class="identifier">std</span><span class="special">::</span><span class="identifier">string</span><span class="special">,</span> <span class="identifier">std</span><span class="special">::</span><span class="identifier">complex</span><span class="special">></span> <span class="identifier">x</span><span class="special">;</span> + +<span class="identifier">x</span><span class="special">.</span><span class="identifier">emplace</span><span class="special">(</span> + <span class="identifier">boost</span><span class="special">::</span><span class="identifier">unordered</span><span class="special">::</span><span class="identifier">piecewise_construct</span><span class="special">,</span> + <span class="identifier">boost</span><span class="special">::</span><span class="identifier">make_tuple</span><span class="special">(</span><span class="string">"key"</span><span class="special">),</span> <span class="identifier">boost</span><span class="special">::</span><span class="identifier">make_tuple</span><span class="special">(</span><span class="number">1</span><span class="special">,</span> <span class="number">2</span><span class="special">));</span> +</pre> +<p> + Older drafts of the standard also supported variadic constructors for <code class="computeroutput"><span class="identifier">std</span><span class="special">::</span><span class="identifier">pair</span></code>, + where the first argument would be used for the first part of the pair, and + the remaining for the second part. + </p> +</div> +<div class="section"> +<div class="titlepage"><div><div><h3 class="title"> +<a name="unordered.compliance.misc"></a><a class="link" href="compliance.html#unordered.compliance.misc" title="Miscellaneous">Miscellaneous</a> +</h3></div></div></div> +<p> + When swapping, <code class="computeroutput"><span class="identifier">Pred</span></code> and + <code class="computeroutput"><span class="identifier">Hash</span></code> are not currently swapped + by calling <code class="computeroutput"><span class="identifier">swap</span></code>, their copy + constructors are used. As a consequence when swapping an exception may be + throw from their copy constructor. + </p> +<p> + Variadic constructor arguments for <code class="computeroutput"><span class="identifier">emplace</span></code> + are only used when both rvalue references and variadic template parameters + are available. Otherwise <code class="computeroutput"><span class="identifier">emplace</span></code> + can only take up to 10 constructors arguments. + </p> +</div> +</div> +<table xmlns:rev="http://www.cs.rpi.edu/~gregod/boost/tools/doc/revision" width="100%"><tr> +<td align="left"></td> +<td align="right"><div class="copyright-footer">Copyright © 2003, 2004 Jeremy B. Maitin-Shepard<br>Copyright © 2005-2008 Daniel + James<p> + Distributed under the Boost Software License, Version 1.0. (See accompanying + file LICENSE_1_0.txt or copy at <a href="http://www.boost.org/LICENSE_1_0.txt" target="_top">http://www.boost.org/LICENSE_1_0.txt</a>) + </p> +</div></td> +</tr></table> +<hr> +<div class="spirit-nav"> +<a accesskey="p" href="comparison.html"><img src="../../../doc/src/images/prev.png" alt="Prev"></a><a accesskey="u" href="../unordered.html"><img src="../../../doc/src/images/up.png" alt="Up"></a><a accesskey="h" href="../index.html"><img src="../../../doc/src/images/home.png" alt="Home"></a><a accesskey="n" href="rationale.html"><img src="../../../doc/src/images/next.png" alt="Next"></a> +</div> +</body> +</html> diff --git a/doc/html/unordered/hash_equality.html b/doc/html/unordered/hash_equality.html new file mode 100755 index 0000000000..dc2e43c457 --- /dev/null +++ b/doc/html/unordered/hash_equality.html @@ -0,0 +1,259 @@ +<html> +<head> +<meta http-equiv="Content-Type" content="text/html; charset=US-ASCII"> +<title>Equality Predicates and Hash Functions</title> +<link rel="stylesheet" href="../../../doc/src/boostbook.css" type="text/css"> +<meta name="generator" content="DocBook XSL Stylesheets V1.76.1"> +<link rel="home" href="../index.html" title="The Boost C++ Libraries BoostBook Documentation Subset"> +<link rel="up" href="../unordered.html" title="Chapter 33. Boost.Unordered"> +<link rel="prev" href="buckets.html" title="The Data Structure"> +<link rel="next" href="comparison.html" title="Comparison with Associative Containers"> +</head> +<body bgcolor="white" text="black" link="#0000FF" vlink="#840084" alink="#0000FF"> +<table cellpadding="2" width="100%"><tr> +<td valign="top"><img alt="Boost C++ Libraries" width="277" height="86" src="../../../boost.png"></td> +<td align="center"><a href="../../../index.html">Home</a></td> +<td align="center"><a href="../../../libs/libraries.htm">Libraries</a></td> +<td align="center"><a href="http://www.boost.org/users/people.html">People</a></td> +<td align="center"><a href="http://www.boost.org/users/faq.html">FAQ</a></td> +<td align="center"><a href="../../../more/index.htm">More</a></td> +</tr></table> +<hr> +<div class="spirit-nav"> +<a accesskey="p" href="buckets.html"><img src="../../../doc/src/images/prev.png" alt="Prev"></a><a accesskey="u" href="../unordered.html"><img src="../../../doc/src/images/up.png" alt="Up"></a><a accesskey="h" href="../index.html"><img src="../../../doc/src/images/home.png" alt="Home"></a><a accesskey="n" href="comparison.html"><img src="../../../doc/src/images/next.png" alt="Next"></a> +</div> +<div class="section"> +<div class="titlepage"><div><div><h2 class="title" style="clear: both"> +<a name="unordered.hash_equality"></a><a class="link" href="hash_equality.html" title="Equality Predicates and Hash Functions">Equality Predicates and Hash Functions</a> +</h2></div></div></div> +<p> + While the associative containers use an ordering relation to specify how the + elements are stored, the unordered associative containers use an equality predicate + and a hash function. For example, <code class="computeroutput"><a class="link" href="../boost/unordered_map.html" title="Class template unordered_map">boost::unordered_map</a></code> + is declared as: + </p> +<pre class="programlisting"><span class="keyword">template</span> <span class="special"><</span> + <span class="keyword">class</span> <span class="identifier">Key</span><span class="special">,</span> <span class="keyword">class</span> <span class="identifier">Mapped</span><span class="special">,</span> + <span class="keyword">class</span> <span class="identifier">Hash</span> <span class="special">=</span> <code class="computeroutput"><a class="link" href="../boost/hash.html" title="Struct template hash">boost::hash</a></code><span class="special"><</span><span class="identifier">Key</span><span class="special">>,</span> + <span class="keyword">class</span> <span class="identifier">Pred</span> <span class="special">=</span> <span class="identifier">std</span><span class="special">::</span><span class="identifier">equal_to</span><span class="special"><</span><span class="identifier">Key</span><span class="special">>,</span> + <span class="keyword">class</span> <span class="identifier">Alloc</span> <span class="special">=</span> <span class="identifier">std</span><span class="special">::</span><span class="identifier">allocator</span><span class="special"><</span><span class="identifier">std</span><span class="special">::</span><span class="identifier">pair</span><span class="special"><</span><span class="identifier">Key</span> <span class="keyword">const</span><span class="special">,</span> <span class="identifier">Mapped</span><span class="special">></span> <span class="special">></span> <span class="special">></span> +<span class="keyword">class</span> <code class="computeroutput"><a class="link" href="../boost/unordered_map.html" title="Class template unordered_map">unordered_map</a></code><span class="special">;</span> +</pre> +<p> + The hash function comes first as you might want to change the hash function + but not the equality predicate. For example, if you wanted to use the <a href="http://www.isthe.com/chongo/tech/comp/fnv/" target="_top">FNV-1 hash</a> you could + write: + </p> +<p> +</p> +<pre class="programlisting"><span class="identifier">boost</span><span class="special">::</span><span class="identifier">unordered_map</span><span class="special"><</span><span class="identifier">std</span><span class="special">::</span><span class="identifier">string</span><span class="special">,</span> <span class="keyword">int</span><span class="special">,</span> <span class="identifier">hash</span><span class="special">::</span><span class="identifier">fnv_1</span><span class="special">></span> + <span class="identifier">dictionary</span><span class="special">;</span> +</pre> +<p> + </p> +<p> + There is an <a href="../../../libs/unordered/examples/fnv1.hpp" target="_top">implementation + of FNV-1</a> in the examples directory. + </p> +<p> + If you wish to use a different equality function, you will also need to use + a matching hash function. For example, to implement a case insensitive dictionary + you need to define a case insensitive equality predicate and hash function: + </p> +<p> +</p> +<pre class="programlisting"><span class="keyword">struct</span> <span class="identifier">iequal_to</span> + <span class="special">:</span> <span class="identifier">std</span><span class="special">::</span><span class="identifier">binary_function</span><span class="special"><</span><span class="identifier">std</span><span class="special">::</span><span class="identifier">string</span><span class="special">,</span> <span class="identifier">std</span><span class="special">::</span><span class="identifier">string</span><span class="special">,</span> <span class="keyword">bool</span><span class="special">></span> +<span class="special">{</span> + <span class="keyword">bool</span> <span class="keyword">operator</span><span class="special">()(</span><span class="identifier">std</span><span class="special">::</span><span class="identifier">string</span> <span class="keyword">const</span><span class="special">&</span> <span class="identifier">x</span><span class="special">,</span> + <span class="identifier">std</span><span class="special">::</span><span class="identifier">string</span> <span class="keyword">const</span><span class="special">&</span> <span class="identifier">y</span><span class="special">)</span> <span class="keyword">const</span> + <span class="special">{</span> + <span class="keyword">return</span> <span class="identifier">boost</span><span class="special">::</span><span class="identifier">algorithm</span><span class="special">::</span><span class="identifier">iequals</span><span class="special">(</span><span class="identifier">x</span><span class="special">,</span> <span class="identifier">y</span><span class="special">,</span> <span class="identifier">std</span><span class="special">::</span><span class="identifier">locale</span><span class="special">());</span> + <span class="special">}</span> +<span class="special">};</span> + +<span class="keyword">struct</span> <span class="identifier">ihash</span> + <span class="special">:</span> <span class="identifier">std</span><span class="special">::</span><span class="identifier">unary_function</span><span class="special"><</span><span class="identifier">std</span><span class="special">::</span><span class="identifier">string</span><span class="special">,</span> <span class="identifier">std</span><span class="special">::</span><span class="identifier">size_t</span><span class="special">></span> +<span class="special">{</span> + <span class="identifier">std</span><span class="special">::</span><span class="identifier">size_t</span> <span class="keyword">operator</span><span class="special">()(</span><span class="identifier">std</span><span class="special">::</span><span class="identifier">string</span> <span class="keyword">const</span><span class="special">&</span> <span class="identifier">x</span><span class="special">)</span> <span class="keyword">const</span> + <span class="special">{</span> + <span class="identifier">std</span><span class="special">::</span><span class="identifier">size_t</span> <span class="identifier">seed</span> <span class="special">=</span> <span class="number">0</span><span class="special">;</span> + <span class="identifier">std</span><span class="special">::</span><span class="identifier">locale</span> <span class="identifier">locale</span><span class="special">;</span> + + <span class="keyword">for</span><span class="special">(</span><span class="identifier">std</span><span class="special">::</span><span class="identifier">string</span><span class="special">::</span><span class="identifier">const_iterator</span> <span class="identifier">it</span> <span class="special">=</span> <span class="identifier">x</span><span class="special">.</span><span class="identifier">begin</span><span class="special">();</span> + <span class="identifier">it</span> <span class="special">!=</span> <span class="identifier">x</span><span class="special">.</span><span class="identifier">end</span><span class="special">();</span> <span class="special">++</span><span class="identifier">it</span><span class="special">)</span> + <span class="special">{</span> + <span class="identifier">boost</span><span class="special">::</span><span class="identifier">hash_combine</span><span class="special">(</span><span class="identifier">seed</span><span class="special">,</span> <span class="identifier">std</span><span class="special">::</span><span class="identifier">toupper</span><span class="special">(*</span><span class="identifier">it</span><span class="special">,</span> <span class="identifier">locale</span><span class="special">));</span> + <span class="special">}</span> + + <span class="keyword">return</span> <span class="identifier">seed</span><span class="special">;</span> + <span class="special">}</span> +<span class="special">};</span> +</pre> +<p> + </p> +<p> + Which you can then use in a case insensitive dictionary: + </p> +<p> +</p> +<pre class="programlisting"><span class="identifier">boost</span><span class="special">::</span><span class="identifier">unordered_map</span><span class="special"><</span><span class="identifier">std</span><span class="special">::</span><span class="identifier">string</span><span class="special">,</span> <span class="keyword">int</span><span class="special">,</span> <span class="identifier">ihash</span><span class="special">,</span> <span class="identifier">iequal_to</span><span class="special">></span> + <span class="identifier">idictionary</span><span class="special">;</span> +</pre> +<p> + </p> +<p> + This is a simplified version of the example at <a href="../../../libs/unordered/examples/case_insensitive.hpp" target="_top">/libs/unordered/examples/case_insensitive.hpp</a> + which supports other locales and string types. + </p> +<div class="caution"><table border="0" summary="Caution"> +<tr> +<td rowspan="2" align="center" valign="top" width="25"><img alt="[Caution]" src="../../../doc/src/images/caution.png"></td> +<th align="left">Caution</th> +</tr> +<tr><td align="left" valign="top"><p> + Be careful when using the equality (<code class="computeroutput"><span class="special">==</span></code>) + operator with custom equality predicates, especially if you're using a function + pointer. If you compare two containers with different equality predicates + then the result is undefined. For most stateless function objects this is + impossible - since you can only compare objects with the same equality predicate + you know the equality predicates must be equal. But if you're using function + pointers or a stateful equality predicate (e.g. boost::function) then you + can get into trouble. + </p></td></tr> +</table></div> +<h3> +<a name="unordered.hash_equality.h0"></a> + <span><a name="unordered.hash_equality.custom_types"></a></span><a class="link" href="hash_equality.html#unordered.hash_equality.custom_types">Custom + Types</a> + </h3> +<p> + Similarly, a custom hash function can be used for custom types: + </p> +<p> +</p> +<pre class="programlisting"><span class="keyword">struct</span> <span class="identifier">point</span> <span class="special">{</span> + <span class="keyword">int</span> <span class="identifier">x</span><span class="special">;</span> + <span class="keyword">int</span> <span class="identifier">y</span><span class="special">;</span> +<span class="special">};</span> + +<span class="keyword">bool</span> <span class="keyword">operator</span><span class="special">==(</span><span class="identifier">point</span> <span class="keyword">const</span><span class="special">&</span> <span class="identifier">p1</span><span class="special">,</span> <span class="identifier">point</span> <span class="keyword">const</span><span class="special">&</span> <span class="identifier">p2</span><span class="special">)</span> +<span class="special">{</span> + <span class="keyword">return</span> <span class="identifier">p1</span><span class="special">.</span><span class="identifier">x</span> <span class="special">==</span> <span class="identifier">p2</span><span class="special">.</span><span class="identifier">x</span> <span class="special">&&</span> <span class="identifier">p1</span><span class="special">.</span><span class="identifier">y</span> <span class="special">==</span> <span class="identifier">p2</span><span class="special">.</span><span class="identifier">y</span><span class="special">;</span> +<span class="special">}</span> + +<span class="keyword">struct</span> <span class="identifier">point_hash</span> + <span class="special">:</span> <span class="identifier">std</span><span class="special">::</span><span class="identifier">unary_function</span><span class="special"><</span><span class="identifier">point</span><span class="special">,</span> <span class="identifier">std</span><span class="special">::</span><span class="identifier">size_t</span><span class="special">></span> +<span class="special">{</span> + <span class="identifier">std</span><span class="special">::</span><span class="identifier">size_t</span> <span class="keyword">operator</span><span class="special">()(</span><span class="identifier">point</span> <span class="keyword">const</span><span class="special">&</span> <span class="identifier">p</span><span class="special">)</span> <span class="keyword">const</span> + <span class="special">{</span> + <span class="identifier">std</span><span class="special">::</span><span class="identifier">size_t</span> <span class="identifier">seed</span> <span class="special">=</span> <span class="number">0</span><span class="special">;</span> + <span class="identifier">boost</span><span class="special">::</span><span class="identifier">hash_combine</span><span class="special">(</span><span class="identifier">seed</span><span class="special">,</span> <span class="identifier">p</span><span class="special">.</span><span class="identifier">x</span><span class="special">);</span> + <span class="identifier">boost</span><span class="special">::</span><span class="identifier">hash_combine</span><span class="special">(</span><span class="identifier">seed</span><span class="special">,</span> <span class="identifier">p</span><span class="special">.</span><span class="identifier">y</span><span class="special">);</span> + <span class="keyword">return</span> <span class="identifier">seed</span><span class="special">;</span> + <span class="special">}</span> +<span class="special">};</span> + +<span class="identifier">boost</span><span class="special">::</span><span class="identifier">unordered_multiset</span><span class="special"><</span><span class="identifier">point</span><span class="special">,</span> <span class="identifier">point_hash</span><span class="special">></span> <span class="identifier">points</span><span class="special">;</span> +</pre> +<p> + </p> +<p> + Since the default hash function is <a class="link" href="../hash.html" title="Chapter 10. Boost.Functional/Hash">Boost.Hash</a>, + we can <a class="link" href="../hash/custom.html" title="Extending boost::hash for a custom data type">extend it to support the type</a> so + that the hash function doesn't need to be explicitly given: + </p> +<p> +</p> +<pre class="programlisting"><span class="keyword">struct</span> <span class="identifier">point</span> <span class="special">{</span> + <span class="keyword">int</span> <span class="identifier">x</span><span class="special">;</span> + <span class="keyword">int</span> <span class="identifier">y</span><span class="special">;</span> +<span class="special">};</span> + +<span class="keyword">bool</span> <span class="keyword">operator</span><span class="special">==(</span><span class="identifier">point</span> <span class="keyword">const</span><span class="special">&</span> <span class="identifier">p1</span><span class="special">,</span> <span class="identifier">point</span> <span class="keyword">const</span><span class="special">&</span> <span class="identifier">p2</span><span class="special">)</span> +<span class="special">{</span> + <span class="keyword">return</span> <span class="identifier">p1</span><span class="special">.</span><span class="identifier">x</span> <span class="special">==</span> <span class="identifier">p2</span><span class="special">.</span><span class="identifier">x</span> <span class="special">&&</span> <span class="identifier">p1</span><span class="special">.</span><span class="identifier">y</span> <span class="special">==</span> <span class="identifier">p2</span><span class="special">.</span><span class="identifier">y</span><span class="special">;</span> +<span class="special">}</span> + +<span class="identifier">std</span><span class="special">::</span><span class="identifier">size_t</span> <span class="identifier">hash_value</span><span class="special">(</span><span class="identifier">point</span> <span class="keyword">const</span><span class="special">&</span> <span class="identifier">p</span><span class="special">)</span> <span class="special">{</span> + <span class="identifier">std</span><span class="special">::</span><span class="identifier">size_t</span> <span class="identifier">seed</span> <span class="special">=</span> <span class="number">0</span><span class="special">;</span> + <span class="identifier">boost</span><span class="special">::</span><span class="identifier">hash_combine</span><span class="special">(</span><span class="identifier">seed</span><span class="special">,</span> <span class="identifier">p</span><span class="special">.</span><span class="identifier">x</span><span class="special">);</span> + <span class="identifier">boost</span><span class="special">::</span><span class="identifier">hash_combine</span><span class="special">(</span><span class="identifier">seed</span><span class="special">,</span> <span class="identifier">p</span><span class="special">.</span><span class="identifier">y</span><span class="special">);</span> + <span class="keyword">return</span> <span class="identifier">seed</span><span class="special">;</span> +<span class="special">}</span> + +<span class="comment">// Now the default function objects work.</span> +<span class="identifier">boost</span><span class="special">::</span><span class="identifier">unordered_multiset</span><span class="special"><</span><span class="identifier">point</span><span class="special">></span> <span class="identifier">points</span><span class="special">;</span> +</pre> +<p> + </p> +<p> + See the <a class="link" href="../hash/custom.html" title="Extending boost::hash for a custom data type">Boost.Hash documentation</a> for more + detail on how to do this. Remember that it relies on extensions to the draft + standard - so it won't work for other implementations of the unordered associative + containers, you'll need to explicitly use Boost.Hash. + </p> +<div class="table"> +<a name="unordered.hash_equality.access_methods"></a><p class="title"><b>Table 33.3. Methods for accessing the hash and equality functions.</b></p> +<div class="table-contents"><table class="table" summary="Methods for accessing the hash and equality functions."> +<colgroup> +<col> +<col> +</colgroup> +<thead><tr> +<th> + <p> + Method + </p> + </th> +<th> + <p> + Description + </p> + </th> +</tr></thead> +<tbody> +<tr> +<td> + <p> + <code class="computeroutput"><span class="identifier">hasher</span> <span class="identifier">hash_function</span><span class="special">()</span> <span class="keyword">const</span></code> + </p> + </td> +<td> + <p> + Returns the container's hash function. + </p> + </td> +</tr> +<tr> +<td> + <p> + <code class="computeroutput"><span class="identifier">key_equal</span> <span class="identifier">key_eq</span><span class="special">()</span> <span class="keyword">const</span></code> + </p> + </td> +<td> + <p> + Returns the container's key equality function. + </p> + </td> +</tr> +</tbody> +</table></div> +</div> +<br class="table-break"> +</div> +<table xmlns:rev="http://www.cs.rpi.edu/~gregod/boost/tools/doc/revision" width="100%"><tr> +<td align="left"></td> +<td align="right"><div class="copyright-footer">Copyright © 2003, 2004 Jeremy B. Maitin-Shepard<br>Copyright © 2005-2008 Daniel + James<p> + Distributed under the Boost Software License, Version 1.0. (See accompanying + file LICENSE_1_0.txt or copy at <a href="http://www.boost.org/LICENSE_1_0.txt" target="_top">http://www.boost.org/LICENSE_1_0.txt</a>) + </p> +</div></td> +</tr></table> +<hr> +<div class="spirit-nav"> +<a accesskey="p" href="buckets.html"><img src="../../../doc/src/images/prev.png" alt="Prev"></a><a accesskey="u" href="../unordered.html"><img src="../../../doc/src/images/up.png" alt="Up"></a><a accesskey="h" href="../index.html"><img src="../../../doc/src/images/home.png" alt="Home"></a><a accesskey="n" href="comparison.html"><img src="../../../doc/src/images/next.png" alt="Next"></a> +</div> +</body> +</html> diff --git a/doc/html/unordered/rationale.html b/doc/html/unordered/rationale.html new file mode 100755 index 0000000000..74c988bc2f --- /dev/null +++ b/doc/html/unordered/rationale.html @@ -0,0 +1,129 @@ +<html> +<head> +<meta http-equiv="Content-Type" content="text/html; charset=US-ASCII"> +<title>Implementation Rationale</title> +<link rel="stylesheet" href="../../../doc/src/boostbook.css" type="text/css"> +<meta name="generator" content="DocBook XSL Stylesheets V1.76.1"> +<link rel="home" href="../index.html" title="The Boost C++ Libraries BoostBook Documentation Subset"> +<link rel="up" href="../unordered.html" title="Chapter 33. Boost.Unordered"> +<link rel="prev" href="compliance.html" title="C++11 Compliance"> +<link rel="next" href="changes.html" title="Change Log"> +</head> +<body bgcolor="white" text="black" link="#0000FF" vlink="#840084" alink="#0000FF"> +<table cellpadding="2" width="100%"><tr> +<td valign="top"><img alt="Boost C++ Libraries" width="277" height="86" src="../../../boost.png"></td> +<td align="center"><a href="../../../index.html">Home</a></td> +<td align="center"><a href="../../../libs/libraries.htm">Libraries</a></td> +<td align="center"><a href="http://www.boost.org/users/people.html">People</a></td> +<td align="center"><a href="http://www.boost.org/users/faq.html">FAQ</a></td> +<td align="center"><a href="../../../more/index.htm">More</a></td> +</tr></table> +<hr> +<div class="spirit-nav"> +<a accesskey="p" href="compliance.html"><img src="../../../doc/src/images/prev.png" alt="Prev"></a><a accesskey="u" href="../unordered.html"><img src="../../../doc/src/images/up.png" alt="Up"></a><a accesskey="h" href="../index.html"><img src="../../../doc/src/images/home.png" alt="Home"></a><a accesskey="n" href="changes.html"><img src="../../../doc/src/images/next.png" alt="Next"></a> +</div> +<div class="section"> +<div class="titlepage"><div><div><h2 class="title" style="clear: both"> +<a name="unordered.rationale"></a><a class="link" href="rationale.html" title="Implementation Rationale">Implementation Rationale</a> +</h2></div></div></div> +<p> + The intent of this library is to implement the unordered containers in the + draft standard, so the interface was fixed. But there are still some implementation + decisions to make. The priorities are conformance to the standard and portability. + </p> +<p> + The <a href="http://en.wikipedia.org/wiki/Hash_table" target="_top">wikipedia article + on hash tables</a> has a good summary of the implementation issues for + hash tables in general. + </p> +<h3> +<a name="unordered.rationale.h0"></a> + <span><a name="unordered.rationale.data_structure"></a></span><a class="link" href="rationale.html#unordered.rationale.data_structure">Data + Structure</a> + </h3> +<p> + By specifying an interface for accessing the buckets of the container the standard + pretty much requires that the hash table uses chained addressing. + </p> +<p> + It would be conceivable to write a hash table that uses another method. For + example, it could use open addressing, and use the lookup chain to act as a + bucket but there are a some serious problems with this: + </p> +<div class="itemizedlist"><ul class="itemizedlist" type="disc"> +<li class="listitem"> + The draft standard requires that pointers to elements aren't invalidated, + so the elements can't be stored in one array, but will need a layer of + indirection instead - losing the efficiency and most of the memory gain, + the main advantages of open addressing. + </li> +<li class="listitem"> + Local iterators would be very inefficient and may not be able to meet the + complexity requirements. + </li> +<li class="listitem"> + There are also the restrictions on when iterators can be invalidated. Since + open addressing degrades badly when there are a high number of collisions + the restrictions could prevent a rehash when it's really needed. The maximum + load factor could be set to a fairly low value to work around this - but + the standard requires that it is initially set to 1.0. + </li> +<li class="listitem"> + And since the standard is written with a eye towards chained addressing, + users will be surprised if the performance doesn't reflect that. + </li> +</ul></div> +<p> + So chained addressing is used. + </p> +<h3> +<a name="unordered.rationale.h1"></a> + <span><a name="unordered.rationale.number_of_buckets"></a></span><a class="link" href="rationale.html#unordered.rationale.number_of_buckets">Number + of Buckets</a> + </h3> +<p> + There are two popular methods for choosing the number of buckets in a hash + table. One is to have a prime number of buckets, another is to use a power + of 2. + </p> +<p> + Using a prime number of buckets, and choosing a bucket by using the modulus + of the hash function's result will usually give a good result. The downside + is that the required modulus operation is fairly expensive. + </p> +<p> + Using a power of 2 allows for much quicker selection of the bucket to use, + but at the expense of loosing the upper bits of the hash value. For some specially + designed hash functions it is possible to do this and still get a good result + but as the containers can take arbitrary hash functions this can't be relied + on. + </p> +<p> + To avoid this a transformation could be applied to the hash function, for an + example see <a href="http://www.concentric.net/~Ttwang/tech/inthash.htm" target="_top">Thomas + Wang's article on integer hash functions</a>. Unfortunately, a transformation + like Wang's requires knowledge of the number of bits in the hash value, so + it isn't portable enough. This leaves more expensive methods, such as Knuth's + Multiplicative Method (mentioned in Wang's article). These don't tend to work + as well as taking the modulus of a prime, and the extra computation required + might negate efficiency advantage of power of 2 hash tables. + </p> +<p> + So, this implementation uses a prime number for the hash table size. + </p> +</div> +<table xmlns:rev="http://www.cs.rpi.edu/~gregod/boost/tools/doc/revision" width="100%"><tr> +<td align="left"></td> +<td align="right"><div class="copyright-footer">Copyright © 2003, 2004 Jeremy B. Maitin-Shepard<br>Copyright © 2005-2008 Daniel + James<p> + Distributed under the Boost Software License, Version 1.0. (See accompanying + file LICENSE_1_0.txt or copy at <a href="http://www.boost.org/LICENSE_1_0.txt" target="_top">http://www.boost.org/LICENSE_1_0.txt</a>) + </p> +</div></td> +</tr></table> +<hr> +<div class="spirit-nav"> +<a accesskey="p" href="compliance.html"><img src="../../../doc/src/images/prev.png" alt="Prev"></a><a accesskey="u" href="../unordered.html"><img src="../../../doc/src/images/up.png" alt="Up"></a><a accesskey="h" href="../index.html"><img src="../../../doc/src/images/home.png" alt="Home"></a><a accesskey="n" href="changes.html"><img src="../../../doc/src/images/next.png" alt="Next"></a> +</div> +</body> +</html> diff --git a/doc/html/unordered/reference.html b/doc/html/unordered/reference.html new file mode 100755 index 0000000000..c432f9707a --- /dev/null +++ b/doc/html/unordered/reference.html @@ -0,0 +1,117 @@ +<html> +<head> +<meta http-equiv="Content-Type" content="text/html; charset=US-ASCII"> +<title>Reference</title> +<link rel="stylesheet" href="../../../doc/src/boostbook.css" type="text/css"> +<meta name="generator" content="DocBook XSL Stylesheets V1.76.1"> +<link rel="home" href="../index.html" title="The Boost C++ Libraries BoostBook Documentation Subset"> +<link rel="up" href="../unordered.html" title="Chapter 33. Boost.Unordered"> +<link rel="prev" href="changes.html" title="Change Log"> +<link rel="next" href="../boost/unordered_set.html" title="Class template unordered_set"> +</head> +<body bgcolor="white" text="black" link="#0000FF" vlink="#840084" alink="#0000FF"> +<table cellpadding="2" width="100%"><tr> +<td valign="top"><img alt="Boost C++ Libraries" width="277" height="86" src="../../../boost.png"></td> +<td align="center"><a href="../../../index.html">Home</a></td> +<td align="center"><a href="../../../libs/libraries.htm">Libraries</a></td> +<td align="center"><a href="http://www.boost.org/users/people.html">People</a></td> +<td align="center"><a href="http://www.boost.org/users/faq.html">FAQ</a></td> +<td align="center"><a href="../../../more/index.htm">More</a></td> +</tr></table> +<hr> +<div class="spirit-nav"> +<a accesskey="p" href="changes.html"><img src="../../../doc/src/images/prev.png" alt="Prev"></a><a accesskey="u" href="../unordered.html"><img src="../../../doc/src/images/up.png" alt="Up"></a><a accesskey="h" href="../index.html"><img src="../../../doc/src/images/home.png" alt="Home"></a><a accesskey="n" href="../boost/unordered_set.html"><img src="../../../doc/src/images/next.png" alt="Next"></a> +</div> +<div class="section"> +<div class="titlepage"><div><div><h2 class="title" style="clear: both"> +<a name="unordered.reference"></a>Reference</h2></div></div></div> +<div class="toc"><dl> +<dt><span class="section"><a href="reference.html#header.boost.unordered_set_hpp">Header <boost/unordered_set.hpp></a></span></dt> +<dt><span class="section"><a href="reference.html#header.boost.unordered_map_hpp">Header <boost/unordered_map.hpp></a></span></dt> +</dl></div> +<div class="section"> +<div class="titlepage"><div><div><h3 class="title"> +<a name="header.boost.unordered_set_hpp"></a>Header <<a href="../../../boost/unordered_set.hpp" target="_top">boost/unordered_set.hpp</a>></h3></div></div></div> +<pre class="synopsis"><span class="keyword">namespace</span> <span class="identifier">boost</span> <span class="special">{</span> + <span class="keyword">template</span><span class="special"><</span><span class="keyword">typename</span> Value<span class="special">,</span> <span class="keyword">typename</span> Hash <span class="special">=</span> <span class="identifier">boost</span><span class="special">::</span><span class="identifier">hash</span><span class="special"><</span><span class="identifier">Value</span><span class="special">></span><span class="special">,</span> + <span class="keyword">typename</span> Pred <span class="special">=</span> <span class="identifier">std</span><span class="special">::</span><span class="identifier">equal_to</span><span class="special"><</span><span class="identifier">Value</span><span class="special">></span><span class="special">,</span> + <span class="keyword">typename</span> Alloc <span class="special">=</span> <span class="identifier">std</span><span class="special">::</span><span class="identifier">allocator</span><span class="special"><</span><span class="identifier">Value</span><span class="special">></span> <span class="special">></span> + <span class="keyword">class</span> <a class="link" href="../boost/unordered_set.html" title="Class template unordered_set">unordered_set</a><span class="special">;</span> + <span class="keyword">template</span><span class="special"><</span><span class="keyword">typename</span> Value<span class="special">,</span> <span class="keyword">typename</span> Hash<span class="special">,</span> <span class="keyword">typename</span> Pred<span class="special">,</span> <span class="keyword">typename</span> Alloc<span class="special">></span> + <span class="keyword">bool</span> <a class="link" href="../boost/unordered_set.html#boost.unordered_set.operator==_id1644606"><span class="keyword">operator</span><span class="special">==</span></a><span class="special">(</span><span class="identifier">unordered_set</span><span class="special"><</span><span class="identifier">Value</span><span class="special">,</span> <span class="identifier">Hash</span><span class="special">,</span> <span class="identifier">Pred</span><span class="special">,</span> <span class="identifier">Alloc</span><span class="special">></span> <span class="keyword">const</span><span class="special">&</span><span class="special">,</span> + <span class="identifier">unordered_set</span><span class="special"><</span><span class="identifier">Value</span><span class="special">,</span> <span class="identifier">Hash</span><span class="special">,</span> <span class="identifier">Pred</span><span class="special">,</span> <span class="identifier">Alloc</span><span class="special">></span> <span class="keyword">const</span><span class="special">&</span><span class="special">)</span><span class="special">;</span> + <span class="keyword">template</span><span class="special"><</span><span class="keyword">typename</span> Value<span class="special">,</span> <span class="keyword">typename</span> Hash<span class="special">,</span> <span class="keyword">typename</span> Pred<span class="special">,</span> <span class="keyword">typename</span> Alloc<span class="special">></span> + <span class="keyword">bool</span> <a class="link" href="../boost/unordered_set.html#boost.unordered_set.operator!=_id1644715"><span class="keyword">operator</span><span class="special">!=</span></a><span class="special">(</span><span class="identifier">unordered_set</span><span class="special"><</span><span class="identifier">Value</span><span class="special">,</span> <span class="identifier">Hash</span><span class="special">,</span> <span class="identifier">Pred</span><span class="special">,</span> <span class="identifier">Alloc</span><span class="special">></span> <span class="keyword">const</span><span class="special">&</span><span class="special">,</span> + <span class="identifier">unordered_set</span><span class="special"><</span><span class="identifier">Value</span><span class="special">,</span> <span class="identifier">Hash</span><span class="special">,</span> <span class="identifier">Pred</span><span class="special">,</span> <span class="identifier">Alloc</span><span class="special">></span> <span class="keyword">const</span><span class="special">&</span><span class="special">)</span><span class="special">;</span> + <span class="keyword">template</span><span class="special"><</span><span class="keyword">typename</span> Value<span class="special">,</span> <span class="keyword">typename</span> Hash<span class="special">,</span> <span class="keyword">typename</span> Pred<span class="special">,</span> <span class="keyword">typename</span> Alloc<span class="special">></span> + <span class="keyword">void</span> <a class="link" href="../boost/unordered_set.html#boost.unordered_set.swap_id1644831"><span class="identifier">swap</span></a><span class="special">(</span><span class="identifier">unordered_set</span><span class="special"><</span><span class="identifier">Value</span><span class="special">,</span> <span class="identifier">Hash</span><span class="special">,</span> <span class="identifier">Pred</span><span class="special">,</span> <span class="identifier">Alloc</span><span class="special">></span><span class="special">&</span><span class="special">,</span> + <span class="identifier">unordered_set</span><span class="special"><</span><span class="identifier">Value</span><span class="special">,</span> <span class="identifier">Hash</span><span class="special">,</span> <span class="identifier">Pred</span><span class="special">,</span> <span class="identifier">Alloc</span><span class="special">></span><span class="special">&</span><span class="special">)</span><span class="special">;</span> + <span class="keyword">template</span><span class="special"><</span><span class="keyword">typename</span> Value<span class="special">,</span> <span class="keyword">typename</span> Hash <span class="special">=</span> <span class="identifier">boost</span><span class="special">::</span><span class="identifier">hash</span><span class="special"><</span><span class="identifier">Value</span><span class="special">></span><span class="special">,</span> + <span class="keyword">typename</span> Pred <span class="special">=</span> <span class="identifier">std</span><span class="special">::</span><span class="identifier">equal_to</span><span class="special"><</span><span class="identifier">Value</span><span class="special">></span><span class="special">,</span> + <span class="keyword">typename</span> Alloc <span class="special">=</span> <span class="identifier">std</span><span class="special">::</span><span class="identifier">allocator</span><span class="special"><</span><span class="identifier">Value</span><span class="special">></span> <span class="special">></span> + <span class="keyword">class</span> <a class="link" href="../boost/unordered_multiset.html" title="Class template unordered_multiset">unordered_multiset</a><span class="special">;</span> + <span class="keyword">template</span><span class="special"><</span><span class="keyword">typename</span> Value<span class="special">,</span> <span class="keyword">typename</span> Hash<span class="special">,</span> <span class="keyword">typename</span> Pred<span class="special">,</span> <span class="keyword">typename</span> Alloc<span class="special">></span> + <span class="keyword">bool</span> <a class="link" href="../boost/unordered_multiset.html#boost.unordered_multiset.operator==_id1640908"><span class="keyword">operator</span><span class="special">==</span></a><span class="special">(</span><span class="identifier">unordered_multiset</span><span class="special"><</span><span class="identifier">Value</span><span class="special">,</span> <span class="identifier">Hash</span><span class="special">,</span> <span class="identifier">Pred</span><span class="special">,</span> <span class="identifier">Alloc</span><span class="special">></span> <span class="keyword">const</span><span class="special">&</span><span class="special">,</span> + <span class="identifier">unordered_multiset</span><span class="special"><</span><span class="identifier">Value</span><span class="special">,</span> <span class="identifier">Hash</span><span class="special">,</span> <span class="identifier">Pred</span><span class="special">,</span> <span class="identifier">Alloc</span><span class="special">></span> <span class="keyword">const</span><span class="special">&</span><span class="special">)</span><span class="special">;</span> + <span class="keyword">template</span><span class="special"><</span><span class="keyword">typename</span> Value<span class="special">,</span> <span class="keyword">typename</span> Hash<span class="special">,</span> <span class="keyword">typename</span> Pred<span class="special">,</span> <span class="keyword">typename</span> Alloc<span class="special">></span> + <span class="keyword">bool</span> <a class="link" href="../boost/unordered_multiset.html#boost.unordered_multiset.operator!=_id1641019"><span class="keyword">operator</span><span class="special">!=</span></a><span class="special">(</span><span class="identifier">unordered_multiset</span><span class="special"><</span><span class="identifier">Value</span><span class="special">,</span> <span class="identifier">Hash</span><span class="special">,</span> <span class="identifier">Pred</span><span class="special">,</span> <span class="identifier">Alloc</span><span class="special">></span> <span class="keyword">const</span><span class="special">&</span><span class="special">,</span> + <span class="identifier">unordered_multiset</span><span class="special"><</span><span class="identifier">Value</span><span class="special">,</span> <span class="identifier">Hash</span><span class="special">,</span> <span class="identifier">Pred</span><span class="special">,</span> <span class="identifier">Alloc</span><span class="special">></span> <span class="keyword">const</span><span class="special">&</span><span class="special">)</span><span class="special">;</span> + <span class="keyword">template</span><span class="special"><</span><span class="keyword">typename</span> Value<span class="special">,</span> <span class="keyword">typename</span> Hash<span class="special">,</span> <span class="keyword">typename</span> Pred<span class="special">,</span> <span class="keyword">typename</span> Alloc<span class="special">></span> + <span class="keyword">void</span> <a class="link" href="../boost/unordered_multiset.html#boost.unordered_multiset.swap_id1639863"><span class="identifier">swap</span></a><span class="special">(</span><span class="identifier">unordered_multiset</span><span class="special"><</span><span class="identifier">Value</span><span class="special">,</span> <span class="identifier">Hash</span><span class="special">,</span> <span class="identifier">Pred</span><span class="special">,</span> <span class="identifier">Alloc</span><span class="special">></span><span class="special">&</span><span class="special">,</span> + <span class="identifier">unordered_multiset</span><span class="special"><</span><span class="identifier">Value</span><span class="special">,</span> <span class="identifier">Hash</span><span class="special">,</span> <span class="identifier">Pred</span><span class="special">,</span> <span class="identifier">Alloc</span><span class="special">></span><span class="special">&</span><span class="special">)</span><span class="special">;</span> +<span class="special">}</span></pre> +</div> +<div class="section"> +<div class="titlepage"><div><div><h3 class="title"> +<a name="header.boost.unordered_map_hpp"></a>Header <<a href="../../../boost/unordered_map.hpp" target="_top">boost/unordered_map.hpp</a>></h3></div></div></div> +<pre class="synopsis"><span class="keyword">namespace</span> <span class="identifier">boost</span> <span class="special">{</span> + <span class="keyword">template</span><span class="special"><</span><span class="keyword">typename</span> Key<span class="special">,</span> <span class="keyword">typename</span> Mapped<span class="special">,</span> <span class="keyword">typename</span> Hash <span class="special">=</span> <span class="identifier">boost</span><span class="special">::</span><span class="identifier">hash</span><span class="special"><</span><span class="identifier">Key</span><span class="special">></span><span class="special">,</span> + <span class="keyword">typename</span> Pred <span class="special">=</span> <span class="identifier">std</span><span class="special">::</span><span class="identifier">equal_to</span><span class="special"><</span><span class="identifier">Key</span><span class="special">></span><span class="special">,</span> + <span class="keyword">typename</span> Alloc <span class="special">=</span> <span class="identifier">std</span><span class="special">::</span><span class="identifier">allocator</span><span class="special"><</span><span class="identifier">std</span><span class="special">::</span><span class="identifier">pair</span><span class="special"><</span><span class="identifier">Key</span> <span class="keyword">const</span><span class="special">,</span> <span class="identifier">Mapped</span><span class="special">>></span> <span class="special">></span> + <span class="keyword">class</span> <a class="link" href="../boost/unordered_map.html" title="Class template unordered_map">unordered_map</a><span class="special">;</span> + <span class="keyword">template</span><span class="special"><</span><span class="keyword">typename</span> Key<span class="special">,</span> <span class="keyword">typename</span> Mapped<span class="special">,</span> <span class="keyword">typename</span> Hash<span class="special">,</span> <span class="keyword">typename</span> Pred<span class="special">,</span> + <span class="keyword">typename</span> Alloc<span class="special">></span> + <span class="keyword">bool</span> <a class="link" href="../boost/unordered_map.html#boost.unordered_map.operator==_id1636876"><span class="keyword">operator</span><span class="special">==</span></a><span class="special">(</span><span class="identifier">unordered_map</span><span class="special"><</span><span class="identifier">Key</span><span class="special">,</span> <span class="identifier">Mapped</span><span class="special">,</span> <span class="identifier">Hash</span><span class="special">,</span> <span class="identifier">Pred</span><span class="special">,</span> <span class="identifier">Alloc</span><span class="special">></span> <span class="keyword">const</span><span class="special">&</span><span class="special">,</span> + <span class="identifier">unordered_map</span><span class="special"><</span><span class="identifier">Key</span><span class="special">,</span> <span class="identifier">Mapped</span><span class="special">,</span> <span class="identifier">Hash</span><span class="special">,</span> <span class="identifier">Pred</span><span class="special">,</span> <span class="identifier">Alloc</span><span class="special">></span> <span class="keyword">const</span><span class="special">&</span><span class="special">)</span><span class="special">;</span> + <span class="keyword">template</span><span class="special"><</span><span class="keyword">typename</span> Key<span class="special">,</span> <span class="keyword">typename</span> Mapped<span class="special">,</span> <span class="keyword">typename</span> Hash<span class="special">,</span> <span class="keyword">typename</span> Pred<span class="special">,</span> + <span class="keyword">typename</span> Alloc<span class="special">></span> + <span class="keyword">bool</span> <a class="link" href="../boost/unordered_map.html#boost.unordered_map.operator!=_id1636992"><span class="keyword">operator</span><span class="special">!=</span></a><span class="special">(</span><span class="identifier">unordered_map</span><span class="special"><</span><span class="identifier">Key</span><span class="special">,</span> <span class="identifier">Mapped</span><span class="special">,</span> <span class="identifier">Hash</span><span class="special">,</span> <span class="identifier">Pred</span><span class="special">,</span> <span class="identifier">Alloc</span><span class="special">></span> <span class="keyword">const</span><span class="special">&</span><span class="special">,</span> + <span class="identifier">unordered_map</span><span class="special"><</span><span class="identifier">Key</span><span class="special">,</span> <span class="identifier">Mapped</span><span class="special">,</span> <span class="identifier">Hash</span><span class="special">,</span> <span class="identifier">Pred</span><span class="special">,</span> <span class="identifier">Alloc</span><span class="special">></span> <span class="keyword">const</span><span class="special">&</span><span class="special">)</span><span class="special">;</span> + <span class="keyword">template</span><span class="special"><</span><span class="keyword">typename</span> Key<span class="special">,</span> <span class="keyword">typename</span> Mapped<span class="special">,</span> <span class="keyword">typename</span> Hash<span class="special">,</span> <span class="keyword">typename</span> Pred<span class="special">,</span> + <span class="keyword">typename</span> Alloc<span class="special">></span> + <span class="keyword">void</span> <a class="link" href="../boost/unordered_map.html#boost.unordered_map.swap_id1637113"><span class="identifier">swap</span></a><span class="special">(</span><span class="identifier">unordered_map</span><span class="special"><</span><span class="identifier">Key</span><span class="special">,</span> <span class="identifier">Mapped</span><span class="special">,</span> <span class="identifier">Hash</span><span class="special">,</span> <span class="identifier">Pred</span><span class="special">,</span> <span class="identifier">Alloc</span><span class="special">></span><span class="special">&</span><span class="special">,</span> + <span class="identifier">unordered_map</span><span class="special"><</span><span class="identifier">Key</span><span class="special">,</span> <span class="identifier">Mapped</span><span class="special">,</span> <span class="identifier">Hash</span><span class="special">,</span> <span class="identifier">Pred</span><span class="special">,</span> <span class="identifier">Alloc</span><span class="special">></span><span class="special">&</span><span class="special">)</span><span class="special">;</span> + <span class="keyword">template</span><span class="special"><</span><span class="keyword">typename</span> Key<span class="special">,</span> <span class="keyword">typename</span> Mapped<span class="special">,</span> <span class="keyword">typename</span> Hash <span class="special">=</span> <span class="identifier">boost</span><span class="special">::</span><span class="identifier">hash</span><span class="special"><</span><span class="identifier">Key</span><span class="special">></span><span class="special">,</span> + <span class="keyword">typename</span> Pred <span class="special">=</span> <span class="identifier">std</span><span class="special">::</span><span class="identifier">equal_to</span><span class="special"><</span><span class="identifier">Key</span><span class="special">></span><span class="special">,</span> + <span class="keyword">typename</span> Alloc <span class="special">=</span> <span class="identifier">std</span><span class="special">::</span><span class="identifier">allocator</span><span class="special"><</span><span class="identifier">std</span><span class="special">::</span><span class="identifier">pair</span><span class="special"><</span><span class="identifier">Key</span> <span class="keyword">const</span><span class="special">,</span> <span class="identifier">Mapped</span><span class="special">>></span> <span class="special">></span> + <span class="keyword">class</span> <a class="link" href="../boost/unordered_multimap.html" title="Class template unordered_multimap">unordered_multimap</a><span class="special">;</span> + <span class="keyword">template</span><span class="special"><</span><span class="keyword">typename</span> Key<span class="special">,</span> <span class="keyword">typename</span> Mapped<span class="special">,</span> <span class="keyword">typename</span> Hash<span class="special">,</span> <span class="keyword">typename</span> Pred<span class="special">,</span> + <span class="keyword">typename</span> Alloc<span class="special">></span> + <span class="keyword">bool</span> <a class="link" href="../boost/unordered_multimap.html#boost.unordered_multimap.operator==_id1634242"><span class="keyword">operator</span><span class="special">==</span></a><span class="special">(</span><span class="identifier">unordered_multimap</span><span class="special"><</span><span class="identifier">Key</span><span class="special">,</span> <span class="identifier">Mapped</span><span class="special">,</span> <span class="identifier">Hash</span><span class="special">,</span> <span class="identifier">Pred</span><span class="special">,</span> <span class="identifier">Alloc</span><span class="special">></span> <span class="keyword">const</span><span class="special">&</span><span class="special">,</span> + <span class="identifier">unordered_multimap</span><span class="special"><</span><span class="identifier">Key</span><span class="special">,</span> <span class="identifier">Mapped</span><span class="special">,</span> <span class="identifier">Hash</span><span class="special">,</span> <span class="identifier">Pred</span><span class="special">,</span> <span class="identifier">Alloc</span><span class="special">></span> <span class="keyword">const</span><span class="special">&</span><span class="special">)</span><span class="special">;</span> + <span class="keyword">template</span><span class="special"><</span><span class="keyword">typename</span> Key<span class="special">,</span> <span class="keyword">typename</span> Mapped<span class="special">,</span> <span class="keyword">typename</span> Hash<span class="special">,</span> <span class="keyword">typename</span> Pred<span class="special">,</span> + <span class="keyword">typename</span> Alloc<span class="special">></span> + <span class="keyword">bool</span> <a class="link" href="../boost/unordered_multimap.html#boost.unordered_multimap.operator!=_id1634358"><span class="keyword">operator</span><span class="special">!=</span></a><span class="special">(</span><span class="identifier">unordered_multimap</span><span class="special"><</span><span class="identifier">Key</span><span class="special">,</span> <span class="identifier">Mapped</span><span class="special">,</span> <span class="identifier">Hash</span><span class="special">,</span> <span class="identifier">Pred</span><span class="special">,</span> <span class="identifier">Alloc</span><span class="special">></span> <span class="keyword">const</span><span class="special">&</span><span class="special">,</span> + <span class="identifier">unordered_multimap</span><span class="special"><</span><span class="identifier">Key</span><span class="special">,</span> <span class="identifier">Mapped</span><span class="special">,</span> <span class="identifier">Hash</span><span class="special">,</span> <span class="identifier">Pred</span><span class="special">,</span> <span class="identifier">Alloc</span><span class="special">></span> <span class="keyword">const</span><span class="special">&</span><span class="special">)</span><span class="special">;</span> + <span class="keyword">template</span><span class="special"><</span><span class="keyword">typename</span> Key<span class="special">,</span> <span class="keyword">typename</span> Mapped<span class="special">,</span> <span class="keyword">typename</span> Hash<span class="special">,</span> <span class="keyword">typename</span> Pred<span class="special">,</span> + <span class="keyword">typename</span> Alloc<span class="special">></span> + <span class="keyword">void</span> <a class="link" href="../boost/unordered_multimap.html#boost.unordered_multimap.swap_id1634481"><span class="identifier">swap</span></a><span class="special">(</span><span class="identifier">unordered_multimap</span><span class="special"><</span><span class="identifier">Key</span><span class="special">,</span> <span class="identifier">Mapped</span><span class="special">,</span> <span class="identifier">Hash</span><span class="special">,</span> <span class="identifier">Pred</span><span class="special">,</span> <span class="identifier">Alloc</span><span class="special">></span><span class="special">&</span><span class="special">,</span> + <span class="identifier">unordered_multimap</span><span class="special"><</span><span class="identifier">Key</span><span class="special">,</span> <span class="identifier">Mapped</span><span class="special">,</span> <span class="identifier">Hash</span><span class="special">,</span> <span class="identifier">Pred</span><span class="special">,</span> <span class="identifier">Alloc</span><span class="special">></span><span class="special">&</span><span class="special">)</span><span class="special">;</span> +<span class="special">}</span></pre> +</div> +</div> +<table xmlns:rev="http://www.cs.rpi.edu/~gregod/boost/tools/doc/revision" width="100%"><tr> +<td align="left"></td> +<td align="right"><div class="copyright-footer">Copyright © 2003, 2004 Jeremy B. Maitin-Shepard<br>Copyright © 2005-2008 Daniel + James<p> + Distributed under the Boost Software License, Version 1.0. (See accompanying + file LICENSE_1_0.txt or copy at <a href="http://www.boost.org/LICENSE_1_0.txt" target="_top">http://www.boost.org/LICENSE_1_0.txt</a>) + </p> +</div></td> +</tr></table> +<hr> +<div class="spirit-nav"> +<a accesskey="p" href="changes.html"><img src="../../../doc/src/images/prev.png" alt="Prev"></a><a accesskey="u" href="../unordered.html"><img src="../../../doc/src/images/up.png" alt="Up"></a><a accesskey="h" href="../index.html"><img src="../../../doc/src/images/home.png" alt="Home"></a><a accesskey="n" href="../boost/unordered_set.html"><img src="../../../doc/src/images/next.png" alt="Next"></a> +</div> +</body> +</html> |