1<!DOCTYPE html PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN" "http://www.w3.org/TR/html4/loose.dtd"> 2<html> 3<head> 4<meta http-equiv="Content-Type" content="text/html; charset=UTF-8"> 5<title>Comparison with Associative Containers</title> 6<link rel="stylesheet" href="../../../doc/src/boostbook.css" type="text/css"> 7<meta name="generator" content="DocBook XSL Stylesheets V1.79.1"> 8<link rel="home" href="../index.html" title="The Boost C++ Libraries BoostBook Documentation Subset"> 9<link rel="up" href="../unordered.html" title="Chapter 44. Boost.Unordered"> 10<link rel="prev" href="hash_equality.html" title="Equality Predicates and Hash Functions"> 11<link rel="next" href="compliance.html" title="Standard Compliance"> 12</head> 13<body bgcolor="white" text="black" link="#0000FF" vlink="#840084" alink="#0000FF"> 14<table cellpadding="2" width="100%"><tr> 15<td valign="top"><img alt="Boost C++ Libraries" width="277" height="86" src="../../../boost.png"></td> 16<td align="center"><a href="../../../index.html">Home</a></td> 17<td align="center"><a href="../../../libs/libraries.htm">Libraries</a></td> 18<td align="center"><a href="http://www.boost.org/users/people.html">People</a></td> 19<td align="center"><a href="http://www.boost.org/users/faq.html">FAQ</a></td> 20<td align="center"><a href="../../../more/index.htm">More</a></td> 21</tr></table> 22<hr> 23<div class="spirit-nav"> 24<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> 25</div> 26<div class="section"> 27<div class="titlepage"><div><div><h2 class="title" style="clear: both"> 28<a name="unordered.comparison"></a><a class="link" href="comparison.html" title="Comparison with Associative Containers">Comparison with Associative Containers</a> 29</h2></div></div></div> 30<div class="table"> 31<a name="unordered.comparison.interface_differences"></a><p class="title"><b>Table 44.4. Interface differences.</b></p> 32<div class="table-contents"><table class="table" summary="Interface differences."> 33<colgroup> 34<col> 35<col> 36</colgroup> 37<thead><tr> 38<th> 39 <p> 40 Associative Containers 41 </p> 42 </th> 43<th> 44 <p> 45 Unordered Associative Containers 46 </p> 47 </th> 48</tr></thead> 49<tbody> 50<tr> 51<td> 52 <p> 53 Parameterized by an ordering relation <code class="computeroutput"><span class="identifier">Compare</span></code> 54 </p> 55 </td> 56<td> 57 <p> 58 Parameterized by a function object <code class="computeroutput"><span class="identifier">Hash</span></code> 59 and an equivalence relation <code class="computeroutput"><span class="identifier">Pred</span></code> 60 </p> 61 </td> 62</tr> 63<tr> 64<td> 65 <p> 66 Keys can be compared using <code class="computeroutput"><span class="identifier">key_compare</span></code> 67 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 68 <code class="computeroutput"><span class="identifier">value_compare</span></code> which 69 is accessed by member function <code class="computeroutput"><span class="identifier">value_comp</span><span class="special">()</span></code>. 70 </p> 71 </td> 72<td> 73 <p> 74 Keys can be hashed using <code class="computeroutput"><span class="identifier">hasher</span></code> 75 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 76 <code class="computeroutput"><span class="identifier">key_equal</span></code> which is 77 accessed by member function <code class="computeroutput"><span class="identifier">key_eq</span><span class="special">()</span></code>. There is no function object for 78 compared or hashing values. 79 </p> 80 </td> 81</tr> 82<tr> 83<td> 84 <p> 85 Constructors have optional extra parameters for the comparison object. 86 </p> 87 </td> 88<td> 89 <p> 90 Constructors have optional extra parameters for the initial minimum 91 number of buckets, a hash function and an equality object. 92 </p> 93 </td> 94</tr> 95<tr> 96<td> 97 <p> 98 Keys <code class="computeroutput"><span class="identifier">k1</span></code>, <code class="computeroutput"><span class="identifier">k2</span></code> are considered equivalent if 99 <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> 100 <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> 101 </p> 102 </td> 103<td> 104 <p> 105 Keys <code class="computeroutput"><span class="identifier">k1</span></code>, <code class="computeroutput"><span class="identifier">k2</span></code> are considered equivalent if 106 <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> 107 </p> 108 </td> 109</tr> 110<tr> 111<td> 112 <p> 113 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> 114 </p> 115 </td> 116<td> 117 <p> 118 No equivalent. Since the elements aren't ordered <code class="computeroutput"><span class="identifier">lower_bound</span></code> 119 and <code class="computeroutput"><span class="identifier">upper_bound</span></code> would 120 be meaningless. 121 </p> 122 </td> 123</tr> 124<tr> 125<td> 126 <p> 127 <code class="computeroutput"><span class="identifier">equal_range</span><span class="special">(</span><span class="identifier">k</span><span class="special">)</span></code> 128 returns an empty range at the position that k would be inserted if 129 k isn't present in the container. 130 </p> 131 </td> 132<td> 133 <p> 134 <code class="computeroutput"><span class="identifier">equal_range</span><span class="special">(</span><span class="identifier">k</span><span class="special">)</span></code> 135 returns a range at the end of the container if k isn't present in 136 the container. It can't return a positioned range as k could be inserted 137 into multiple place. To find out the bucket that k would be inserted 138 into use <code class="computeroutput"><span class="identifier">bucket</span><span class="special">(</span><span class="identifier">k</span><span class="special">)</span></code>. 139 But remember that an insert can cause the container to rehash - meaning 140 that the element can be inserted into a different bucket. 141 </p> 142 </td> 143</tr> 144<tr> 145<td> 146 <p> 147 <code class="computeroutput"><span class="identifier">iterator</span></code>, <code class="computeroutput"><span class="identifier">const_iterator</span></code> are of the bidirectional 148 category. 149 </p> 150 </td> 151<td> 152 <p> 153 <code class="computeroutput"><span class="identifier">iterator</span></code>, <code class="computeroutput"><span class="identifier">const_iterator</span></code> are of at least 154 the forward category. 155 </p> 156 </td> 157</tr> 158<tr> 159<td> 160 <p> 161 Iterators, pointers and references to the container's elements are 162 never invalidated. 163 </p> 164 </td> 165<td> 166 <p> 167 <a class="link" href="buckets.html#unordered.buckets.iterator_invalidation">Iterators 168 can be invalidated by calls to insert or rehash</a>. Pointers 169 and references to the container's elements are never invalidated. 170 </p> 171 </td> 172</tr> 173<tr> 174<td> 175 <p> 176 Iterators iterate through the container in the order defined by the 177 comparison object. 178 </p> 179 </td> 180<td> 181 <p> 182 Iterators iterate through the container in an arbitrary order, that 183 can change as elements are inserted, although equivalent elements 184 are always adjacent. 185 </p> 186 </td> 187</tr> 188<tr> 189<td> 190 <p> 191 No equivalent 192 </p> 193 </td> 194<td> 195 <p> 196 Local iterators can be used to iterate through individual buckets. 197 (The order of local iterators and iterators aren't required to have 198 any correspondence.) 199 </p> 200 </td> 201</tr> 202<tr> 203<td> 204 <p> 205 Can be compared using the <code class="computeroutput"><span class="special">==</span></code>, 206 <code class="computeroutput"><span class="special">!=</span></code>, <code class="computeroutput"><span class="special"><</span></code>, 207 <code class="computeroutput"><span class="special"><=</span></code>, <code class="computeroutput"><span class="special">></span></code>, <code class="computeroutput"><span class="special">>=</span></code> 208 operators. 209 </p> 210 </td> 211<td> 212 <p> 213 Can be compared using the <code class="computeroutput"><span class="special">==</span></code> 214 and <code class="computeroutput"><span class="special">!=</span></code> operators. 215 </p> 216 </td> 217</tr> 218<tr> 219<td> 220 </td> 221<td> 222 <p> 223 When inserting with a hint, implementations are permitted to ignore 224 the hint. 225 </p> 226 </td> 227</tr> 228<tr> 229<td> 230 <p> 231 <code class="computeroutput"><span class="identifier">erase</span></code> never throws 232 an exception 233 </p> 234 </td> 235<td> 236 <p> 237 The containers' hash or predicate function can throw exceptions from 238 <code class="computeroutput"><span class="identifier">erase</span></code> 239 </p> 240 </td> 241</tr> 242</tbody> 243</table></div> 244</div> 245<br class="table-break"><div class="table"> 246<a name="unordered.comparison.complexity_guarantees"></a><p class="title"><b>Table 44.5. Complexity Guarantees</b></p> 247<div class="table-contents"><table class="table" summary="Complexity Guarantees"> 248<colgroup> 249<col> 250<col> 251<col> 252</colgroup> 253<thead><tr> 254<th> 255 <p> 256 Operation 257 </p> 258 </th> 259<th> 260 <p> 261 Associative Containers 262 </p> 263 </th> 264<th> 265 <p> 266 Unordered Associative Containers 267 </p> 268 </th> 269</tr></thead> 270<tbody> 271<tr> 272<td> 273 <p> 274 Construction of empty container 275 </p> 276 </td> 277<td> 278 <p> 279 constant 280 </p> 281 </td> 282<td> 283 <p> 284 O(<span class="emphasis"><em>n</em></span>) where <span class="emphasis"><em>n</em></span> is the minimum 285 number of buckets. 286 </p> 287 </td> 288</tr> 289<tr> 290<td> 291 <p> 292 Construction of container from a range of <span class="emphasis"><em>N</em></span> 293 elements 294 </p> 295 </td> 296<td> 297 <p> 298 O(<span class="emphasis"><em>N</em></span> log <span class="emphasis"><em>N</em></span>), O(<span class="emphasis"><em>N</em></span>) 299 if the range is sorted with <code class="computeroutput"><span class="identifier">value_comp</span><span class="special">()</span></code> 300 </p> 301 </td> 302<td> 303 <p> 304 Average case O(<span class="emphasis"><em>N</em></span>), worst case O(<span class="emphasis"><em>N</em></span><sup>2</sup>) 305 </p> 306 </td> 307</tr> 308<tr> 309<td> 310 <p> 311 Insert a single element 312 </p> 313 </td> 314<td> 315 <p> 316 logarithmic 317 </p> 318 </td> 319<td> 320 <p> 321 Average case constant, worst case linear 322 </p> 323 </td> 324</tr> 325<tr> 326<td> 327 <p> 328 Insert a single element with a hint 329 </p> 330 </td> 331<td> 332 <p> 333 Amortized constant if t elements inserted right after hint, logarithmic 334 otherwise 335 </p> 336 </td> 337<td> 338 <p> 339 Average case constant, worst case linear (ie. the same as a normal 340 insert). 341 </p> 342 </td> 343</tr> 344<tr> 345<td> 346 <p> 347 Inserting a range of <span class="emphasis"><em>N</em></span> elements 348 </p> 349 </td> 350<td> 351 <p> 352 <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>) 353 </p> 354 </td> 355<td> 356 <p> 357 Average case O(<span class="emphasis"><em>N</em></span>), worst case O(<span class="emphasis"><em>N</em></span> 358 * <code class="computeroutput"><span class="identifier">size</span><span class="special">()</span></code>) 359 </p> 360 </td> 361</tr> 362<tr> 363<td> 364 <p> 365 Erase by key, <code class="computeroutput"><span class="identifier">k</span></code> 366 </p> 367 </td> 368<td> 369 <p> 370 O(log(<code class="computeroutput"><span class="identifier">size</span><span class="special">()</span></code>) 371 + <code class="computeroutput"><span class="identifier">count</span><span class="special">(</span><span class="identifier">k</span><span class="special">)</span></code>) 372 </p> 373 </td> 374<td> 375 <p> 376 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>) 377 </p> 378 </td> 379</tr> 380<tr> 381<td> 382 <p> 383 Erase a single element by iterator 384 </p> 385 </td> 386<td> 387 <p> 388 Amortized constant 389 </p> 390 </td> 391<td> 392 <p> 393 Average case: O(1), Worst case: O(<code class="computeroutput"><span class="identifier">size</span><span class="special">()</span></code>) 394 </p> 395 </td> 396</tr> 397<tr> 398<td> 399 <p> 400 Erase a range of <span class="emphasis"><em>N</em></span> elements 401 </p> 402 </td> 403<td> 404 <p> 405 O(log(<code class="computeroutput"><span class="identifier">size</span><span class="special">()</span></code>) 406 + <span class="emphasis"><em>N</em></span>) 407 </p> 408 </td> 409<td> 410 <p> 411 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>) 412 </p> 413 </td> 414</tr> 415<tr> 416<td> 417 <p> 418 Clearing the container 419 </p> 420 </td> 421<td> 422 <p> 423 O(<code class="computeroutput"><span class="identifier">size</span><span class="special">()</span></code>) 424 </p> 425 </td> 426<td> 427 <p> 428 O(<code class="computeroutput"><span class="identifier">size</span><span class="special">()</span></code>) 429 </p> 430 </td> 431</tr> 432<tr> 433<td> 434 <p> 435 Find 436 </p> 437 </td> 438<td> 439 <p> 440 logarithmic 441 </p> 442 </td> 443<td> 444 <p> 445 Average case: O(1), Worst case: O(<code class="computeroutput"><span class="identifier">size</span><span class="special">()</span></code>) 446 </p> 447 </td> 448</tr> 449<tr> 450<td> 451 <p> 452 Count 453 </p> 454 </td> 455<td> 456 <p> 457 O(log(<code class="computeroutput"><span class="identifier">size</span><span class="special">()</span></code>) 458 + <code class="computeroutput"><span class="identifier">count</span><span class="special">(</span><span class="identifier">k</span><span class="special">)</span></code>) 459 </p> 460 </td> 461<td> 462 <p> 463 Average case: O(1), Worst case: O(<code class="computeroutput"><span class="identifier">size</span><span class="special">()</span></code>) 464 </p> 465 </td> 466</tr> 467<tr> 468<td> 469 <p> 470 <code class="computeroutput"><span class="identifier">equal_range</span><span class="special">(</span><span class="identifier">k</span><span class="special">)</span></code> 471 </p> 472 </td> 473<td> 474 <p> 475 logarithmic 476 </p> 477 </td> 478<td> 479 <p> 480 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>) 481 </p> 482 </td> 483</tr> 484<tr> 485<td> 486 <p> 487 <code class="computeroutput"><span class="identifier">lower_bound</span></code>,<code class="computeroutput"><span class="identifier">upper_bound</span></code> 488 </p> 489 </td> 490<td> 491 <p> 492 logarithmic 493 </p> 494 </td> 495<td> 496 <p> 497 n/a 498 </p> 499 </td> 500</tr> 501</tbody> 502</table></div> 503</div> 504<br class="table-break"> 505</div> 506<table xmlns:rev="http://www.cs.rpi.edu/~gregod/boost/tools/doc/revision" width="100%"><tr> 507<td align="left"></td> 508<td align="right"><div class="copyright-footer">Copyright © 2003, 2004 Jeremy B. Maitin-Shepard<br>Copyright © 2005-2008 Daniel 509 James<p> 510 Distributed under the Boost Software License, Version 1.0. (See accompanying 511 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>) 512 </p> 513</div></td> 514</tr></table> 515<hr> 516<div class="spirit-nav"> 517<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> 518</div> 519</body> 520</html> 521
