| <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.75.2"> |
| <link rel="home" href="../index.html" title="The Boost C++ Libraries BoostBook Documentation Subset"> |
| <link rel="up" href="../unordered.html" title="Chapter 27. Boost.Unordered"> |
| <link rel="prev" href="hash_equality.html" title="Equality Predicates and Hash Functions"> |
| <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="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="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.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="id3022825"></a><p class="title"><b>Table 27.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. |
| (I don't think that the order of local iterators and iterators are |
| 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> |
| No comparison operators are defined in the standard, although <a class="link" href="rationale.html#unordered.rationale.equality_operators">implementations |
| might extend the containers to support <code class="computeroutput"><span class="special">==</span></code> |
| and <code class="computeroutput"><span class="special">!=</span></code></a>. |
| </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="id3023921"></a><p class="title"><b>Table 27.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="rationale.html"><img src="../../../doc/src/images/next.png" alt="Next"></a> |
| </div> |
| </body> |
| </html> |
