Skip to content

R
riscv-gcc-1
Switch branch/tag
Find file
Normal viewHistoryPermalink
tables.html 15 KB
Newer Older
TODO: Update.
8f94053d
 
Phil Edwards committed
1 2 3 4 5 6 7 8 9 10 11 12 
<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN">
<html>
<head><meta http-equiv="Content-Type" content="text/html;charset=iso-8859-1">
<title>Tables</title>
<link href="style.css" rel="stylesheet" type="text/css">
</head>

<body bgcolor="#ffffff">

<h1>Tables</h1>

<p>Most of the requirements on containers are presented in the ISO standard
Intro.3: Date tweak.
04b7c941
 
Phil Edwards committed
13 14 15 16 17 
   in the form of tables.  In order to avoid massive duplication of effort
   while documenting all the classes, we follow the standard's lead and
   present the base information here.  Individual classes will only document
   their departures from these tables (removed functions, additional functions,
   changes, etc).
TODO: Update.
8f94053d
 
Phil Edwards committed
18 19 
</p>
Intro.3: Date tweak.
04b7c941
 
Phil Edwards committed
20 21 22 23 24 25 
<p>We will not try to duplicate all of the surrounding text (footnotes,
   explanations, etc) from the standard, because that would also entail a
   duplication of effort.  Some of the surrounding text has been paraphrased
   here for clarity.  If you are uncertain about the meaning or interpretation
   of these notes, consult a good textbook, and/or purchase your own copy of
   the standard (it's cheap, see our FAQ).
TODO: Update.
8f94053d
 
Phil Edwards committed
26 27 
</p>
Intro.3: Date tweak.
04b7c941
 
Phil Edwards committed
28 29 30 31 32 33 
<p>The table numbers are the same as those used in the standard.  Tables can
   be jumped to using their number, e.g., &quot;tables.html#67&quot;.  Only
   Tables 65 through 69 are presented.  Some of the active Defect Reports
   are also noted or incorporated.
</p>
TODO: Update.
8f94053d
 
Phil Edwards committed
34 35 36 37 
<hr />

<a name="65"><p>
<table cellpadding="3" cellspacing="5" align="center" rules="rows" border="3"
TODO: Update.
4df6abc6
 
Phil Edwards committed
38 
       cols="5" title="Table 65">
TODO: Update.
8f94053d
 
Phil Edwards committed
39 
<caption><h2>Table 65 --- Container Requirements</h2></caption>
TODO: Update.
4df6abc6
 
Phil Edwards committed
40 
<tr><th colspan="5">
TODO: Update.
8f94053d
 
Phil Edwards committed
41 42 43 44 45 
Anything calling itself a container must meet these minimum requirements.
</th></tr>
<tr>
<td><strong>expression</strong></td>
<td><strong>result type</strong></td>
TODO: Update.
4df6abc6
 
Phil Edwards committed
46 
<td><strong>operational semantics</strong></td>
Intro.3: Date tweak.
04b7c941
 
Phil Edwards committed
47 
<td><strong>notes, pre-/post-conditions, assertions</strong></td>
TODO: Update.
8f94053d
 
Phil Edwards committed
48 49 50 51 
<td><strong>complexity</strong></td>
</tr>

<tr>
Intro.3: Date tweak.
04b7c941
 
Phil Edwards committed
52 53 
<td>X::value_type</td>
<td>T</td>
TODO: Update.
4df6abc6
 
Phil Edwards committed
54 
<td>&nbsp;</td>
Intro.3: Date tweak.
04b7c941
 
Phil Edwards committed
55 56 57 58 59 60 61 62 
<td>T is Assignable</td>
<td>compile time</td>
</tr>

<tr>
<td>X::reference</td>
<td>lvalue of T</td>
<td>&nbsp;</td>
TODO: Update.
4df6abc6
 
Phil Edwards committed
63 
<td>&nbsp;</td>
Intro.3: Date tweak.
04b7c941
 
Phil Edwards committed
64 65 66 67 68 69 70 
<td>compile time</td>
</tr>

<tr>
<td>X::const_reference</td>
<td>const lvalue of T</td>
<td>&nbsp;</td>
TODO: Update.
4df6abc6
 
Phil Edwards committed
71 
<td>&nbsp;</td>
Intro.3: Date tweak.
04b7c941
 
Phil Edwards committed
72 73 74 75 76 77 
<td>compile time</td>
</tr>

<tr>
<td>X::iterator</td>
<td>iterator type pointing to T</td>
TODO: Update.
4df6abc6
 
Phil Edwards committed
78 
<td>&nbsp;</td>
Intro.3: Date tweak.
04b7c941
 
Phil Edwards committed
79 80 81 82 83 84 85 86 
<td>Any iterator category except output iterator.
    Convertible to X::const_iterator.</td>
<td>compile time</td>
</tr>

<tr>
<td>X::const_iterator</td>
<td>iterator type pointing to const T</td>
TODO: Update.
4df6abc6
 
Phil Edwards committed
87 
<td>&nbsp;</td>
Intro.3: Date tweak.
04b7c941
 
Phil Edwards committed
88 89 90 91 92 93 94 
<td>Any iterator category except output iterator.</td>
<td>compile time</td>
</tr>

<tr>
<td>X::difference_type</td>
<td>signed integral type</td>
TODO: Update.
4df6abc6
 
Phil Edwards committed
95 
<td>&nbsp;</td>
Intro.3: Date tweak.
04b7c941
 
Phil Edwards committed
96 97 98 99 100 101 102 
<td>identical to the difference type of X::iterator and X::const_iterator</td>
<td>compile time</td>
</tr>

<tr>
<td>X::size_type</td>
<td>unsigned integral type</td>
TODO: Update.
4df6abc6
 
Phil Edwards committed
103 
<td>&nbsp;</td>
Intro.3: Date tweak.
04b7c941
 
Phil Edwards committed
104 105 106 107 108 109 110 
<td>size_type can represent any non-negative value of difference_type</td>
<td>compile time</td>
</tr>

<tr>
<td>X u;</td>
<td>&nbsp;</td>
TODO: Update.
4df6abc6
 
Phil Edwards committed
111 
<td>&nbsp;</td>
Intro.3: Date tweak.
04b7c941
 
Phil Edwards committed
112 113 114 115 116 117 118 
<td>post: u.size() == 0</td>
<td>constant</td>
</tr>

<tr>
<td>X();</td>
<td>&nbsp;</td>
TODO: Update.
4df6abc6
 
Phil Edwards committed
119 
<td>&nbsp;</td>
Intro.3: Date tweak.
04b7c941
 
Phil Edwards committed
120 121 122 123 124 125 126 
<td>X().size == 0</td>
<td>constant</td>
</tr>

<tr>
<td>X(a);</td>
<td>&nbsp;</td>
TODO: Update.
4df6abc6
 
Phil Edwards committed
127 
<td>&nbsp;</td>
Intro.3: Date tweak.
04b7c941
 
Phil Edwards committed
128 129 130 131 132 133 134 
<td>a == X(a)</td>
<td>linear</td>
</tr>

<tr>
<td>X u(a);<br />X u = a;</td>
<td>&nbsp;</td>
TODO: Update.
4df6abc6
 
Phil Edwards committed
135 
<td>&nbsp;</td>
Intro.3: Date tweak.
04b7c941
 
Phil Edwards committed
136 137 138 139 140 141 142 
<td>post: u == a.  Equivalent to: X u; u = a;</td>
<td>linear</td>
</tr>

<tr>
<td>(&amp;a)-&gt;~X();</td>
<td>void</td>
TODO: Update.
4df6abc6
 
Phil Edwards committed
143 
<td>&nbsp;</td>
Intro.3: Date tweak.
04b7c941
 
Phil Edwards committed
144 145 146 147 148 149 150 151 
<td>dtor is applied to every element of a; all the memory is deallocated</td>
<td>linear</td>
</tr>

<tr>
<td>a.begin()</td>
<td>iterator; const_iterator for constant a</td>
<td>&nbsp;</td>
TODO: Update.
4df6abc6
 
Phil Edwards committed
152 
<td>&nbsp;</td>
Intro.3: Date tweak.
04b7c941
 
Phil Edwards committed
153 154 155 156 157 158 159 
<td>constant</td>
</tr>

<tr>
<td>a.end()</td>
<td>iterator; const_iterator for constant a</td>
<td>&nbsp;</td>
TODO: Update.
4df6abc6
 
Phil Edwards committed
160 
<td>&nbsp;</td>
Intro.3: Date tweak.
04b7c941
 
Phil Edwards committed
161 
<td>constant</td>
TODO: Update.
8f94053d
 
Phil Edwards committed
162 163 164 
</tr>

<tr>
Intro.3: Date tweak.
04b7c941
 
Phil Edwards committed
165 166 
<td>a == b</td>
<td>convertible to bool</td>
TODO: Update.
4df6abc6
 
Phil Edwards committed
167 
<td>&nbsp;</td>
Intro.3: Date tweak.
04b7c941
 
Phil Edwards committed
168 169 170 
<td>== is an equivalence relation.  a.size()==b.size() &amp;&amp;
    equal(a.begin(),a.end(),b.begin())</td>
<td>linear</td>
TODO: Update.
8f94053d
 
Phil Edwards committed
171 172 173 
</tr>

<tr>
Intro.3: Date tweak.
04b7c941
 
Phil Edwards committed
174 175 
<td>a != b</td>
<td>convertible to bool</td>
TODO: Update.
4df6abc6
 
Phil Edwards committed
176 
<td>&nbsp;</td>
Intro.3: Date tweak.
04b7c941
 
Phil Edwards committed
177 178 
<td>equivalent to !(a==b)</td>
<td>linear</td>
TODO: Update.
8f94053d
 
Phil Edwards committed
179 180 181 
</tr>

<tr>
Intro.3: Date tweak.
04b7c941
 
Phil Edwards committed
182 183 
<td>a.swap(b)</td>
<td>void</td>
TODO: Update.
4df6abc6
 
Phil Edwards committed
184 
<td>&nbsp;</td>
Intro.3: Date tweak.
04b7c941
 
Phil Edwards committed
185 186 187 188 189 190 191 
<td>swap(a,b)</td>
<td>may or may not have constant complexity</td>
</tr>

<tr>
<td>r = a</td>
<td>X&amp;</td>
TODO: Update.
4df6abc6
 
Phil Edwards committed
192 
<td>&nbsp;</td>
Intro.3: Date tweak.
04b7c941
 
Phil Edwards committed
193 194 195 196 197 198 199 200 201 
<td>r == a</td>
<td>linear</td>
</tr>

<!-- a fifth column, "operation semantics," magically appears in the table
     at this point... wtf?  -->
<tr>
<td>a.size()</td>
<td>size_type</td>
TODO: Update.
4df6abc6
 
Phil Edwards committed
202 
<td>a.end() - a.begin()</td>
Intro.3: Date tweak.
04b7c941
 
Phil Edwards committed
203 204 205 206 207 208 209 
<td>&nbsp;</td>
<td>may or may not have constant complexity</td>
</tr>

<tr>
<td>a.max_size()</td>
<td>size_type</td>
TODO: Update.
4df6abc6
 
Phil Edwards committed
210 
<td>size() of the largest possible container</td>
Intro.3: Date tweak.
04b7c941
 
Phil Edwards committed
211 212 213 214 215 216 217 
<td>&nbsp;</td>
<td>may or may not have constant complexity</td>
</tr>

<tr>
<td>a.empty()</td>
<td>convertible to bool</td>
TODO: Update.
4df6abc6
 
Phil Edwards committed
218 
<td>a.size() == 0</td>
Intro.3: Date tweak.
04b7c941
 
Phil Edwards committed
219 220 221 222 223 224 225 
<td>&nbsp;</td>
<td>constant</td>
</tr>

<tr>
<td>a &lt; b</td>
<td>convertible to bool</td>
TODO: Update.
4df6abc6
 
Phil Edwards committed
226 
<td>lexographical_compare( a.begin, a.end(), b.begin(), b.end())</td>
Intro.3: Date tweak.
04b7c941
 
Phil Edwards committed
227 228 229 230 231 232 233 
<td>pre: &lt; is defined for T and is a total ordering relation</td>
<td>linear</td>
</tr>

<tr>
<td>a &gt; b</td>
<td>convertible to bool</td>
TODO: Update.
4df6abc6
 
Phil Edwards committed
234 
<td>b &lt; a</td>
Intro.3: Date tweak.
04b7c941
 
Phil Edwards committed
235 236 237 238 239 240 241 
<td>&nbsp;</td>
<td>linear</td>
</tr>

<tr>
<td>a &lt;= b</td>
<td>convertible to bool</td>
TODO: Update.
4df6abc6
 
Phil Edwards committed
242 
<td>!(a &gt; b)</td>
Intro.3: Date tweak.
04b7c941
 
Phil Edwards committed
243 244 245 246 247 248 249 
<td>&nbsp;</td>
<td>linear</td>
</tr>

<tr>
<td>a &gt;= b</td>
<td>convertible to bool</td>
TODO: Update.
4df6abc6
 
Phil Edwards committed
250 
<td>!(a &lt; b)</td>
Intro.3: Date tweak.
04b7c941
 
Phil Edwards committed
251 252 
<td>&nbsp;</td>
<td>linear</td>
TODO: Update.
8f94053d
 
Phil Edwards committed
253 254 255 256 257 258 
</tr>
</table title="Table 65"></p></a>


<a name="66"><p>
<table cellpadding="3" cellspacing="5" align="center" rules="rows" border="3"
Intro.3: Date tweak.
04b7c941
 
Phil Edwards committed
259 
       cols="4" title="Table 66">
TODO: Update.
8f94053d
 
Phil Edwards committed
260 261 262 263 
<caption><h2>Table 66 --- Reversible Container Requirements</h2></caption>
<tr><th colspan="4">
If a container's iterator is bidirectional or random-access, then the
container also meets these requirements.
Intro.3: Date tweak.
04b7c941
 
Phil Edwards committed
264 
Deque, list, vector, map, multimap, set, and multiset are such containers.
TODO: Update.
8f94053d
 
Phil Edwards committed
265 266 267 268 
</th></tr>
<tr>
<td><strong>expression</strong></td>
<td><strong>result type</strong></td>
Intro.3: Date tweak.
04b7c941
 
Phil Edwards committed
269 
<td><strong>notes, pre-/post-conditions, assertions</strong></td>
TODO: Update.
8f94053d
 
Phil Edwards committed
270 271 272 273 
<td><strong>complexity</strong></td>
</tr>

<tr>
Intro.3: Date tweak.
04b7c941
 
Phil Edwards committed
274 275 276 277 
<td>X::reverse_iterator</td>
<td>iterator type pointing to T</td>
<td>reverse_iterator&lt;iterator&gt;</td>
<td>compile time</td>
TODO: Update.
8f94053d
 
Phil Edwards committed
278 279 280 
</tr>

<tr>
Intro.3: Date tweak.
04b7c941
 
Phil Edwards committed
281 282 283 284 
<td>X::const_reverse_iterator</td>
<td>iterator type pointing to const T</td>
<td>reverse_iterator&lt;const_iterator&gt;</td>
<td>compile time</td>
TODO: Update.
8f94053d
 
Phil Edwards committed
285 286 287 
</tr>

<tr>
Intro.3: Date tweak.
04b7c941
 
Phil Edwards committed
288 289 290 291 
<td>a.rbegin()</td>
<td>reverse_iterator; const_reverse_iterator for constant a</td>
<td>reverse_iterator(end())</td>
<td>constant</td>
TODO: Update.
8f94053d
 
Phil Edwards committed
292 293 294 
</tr>

<tr>
Intro.3: Date tweak.
04b7c941
 
Phil Edwards committed
295 296 297 298 
<td>a.rend()</td>
<td>reverse_iterator; const_reverse_iterator for constant a</td>
<td>reverse_iterator(begin())</td>
<td>constant</td>
TODO: Update.
8f94053d
 
Phil Edwards committed
299 300 301 302 303 304 305 306 
</tr>
</table title="Table 66"></p></a>


<a name="67"><p>
<table cellpadding="3" cellspacing="5" align="center" rules="rows" border="3"
       cols="3" title="Table 67">
<caption><h2>Table 67 --- Sequence Requirements</h2></caption>
Intro.3: Date tweak.
04b7c941
 
Phil Edwards committed
307 
<tr><th colspan="3">
TODO: Update.
8f94053d
 
Phil Edwards committed
308 
These are in addition to the requirements of <a href="#65">containers</a>.
Intro.3: Date tweak.
04b7c941
 
Phil Edwards committed
309 
Deque, list, and vector are such containers.
TODO: Update.
8f94053d
 
Phil Edwards committed
310 311 312 313 
</th></tr>
<tr>
<td><strong>expression</strong></td>
<td><strong>result type</strong></td>
Intro.3: Date tweak.
04b7c941
 
Phil Edwards committed
314 315 316 317 318 319 320 321 322 323 324 325 326 327 
<td><strong>notes, pre-/post-conditions, assertions</strong></td>
</tr>

<tr>
<td>X(n,t)<br />X a(n,t)</td>
<td>&nbsp;</td>
<td>constructs a sequence with n copies of t<br />post: size() == n</td>
</tr>

<tr>
<td>X(i,j)<br />X a(i,j)</td>
<td>&nbsp;</td>
<td>constructs a sequence equal to the range [i,j)<br />
    post: size() == distance(i,j)</td>
TODO: Update.
8f94053d
 
Phil Edwards committed
328 329 330 
</tr>

<tr>
Intro.3: Date tweak.
04b7c941
 
Phil Edwards committed
331 332 333 
<td>a.insert(p,t)</td>
<td>iterator (points to the inserted copy of t)</td>
<td>inserts a copy of t before p</td>
TODO: Update.
8f94053d
 
Phil Edwards committed
334 335 336 
</tr>

<tr>
Intro.3: Date tweak.
04b7c941
 
Phil Edwards committed
337 338 339 
<td>a.insert(p,n,t)</td>
<td>void</td>
<td>inserts n copies of t before p</td>
TODO: Update.
8f94053d
 
Phil Edwards committed
340 341 342 
</tr>

<tr>
Intro.3: Date tweak.
04b7c941
 
Phil Edwards committed
343 344 345 346 
<td>a.insert(p,i,j)</td>
<td>void</td>
<td>inserts copies of elements in [i,j) before p<br />
    pre: i, j are not iterators into a</td>
TODO: Update.
8f94053d
 
Phil Edwards committed
347 348 349 
</tr>

<tr>
Intro.3: Date tweak.
04b7c941
 
Phil Edwards committed
350 351 352 353 354 355 356 357 358 359 360 361 362 363 364 
<td>a.erase(q)</td>
<td>iterator (points to the element following q (prior to erasure))</td>
<td>erases the element pointed to by q</td>
</tr>

<tr>
<td>a.erase(q1,q1)</td>
<td>iterator (points to the element pointed to by q2 (prior to erasure))</td>
<td>erases the elements in the range [q1,q2)</td>
</tr>

<tr>
<td>a.clear()</td>
<td>void</td>
<td>erase(begin(),end())<br />post: size() == 0</td>
TODO: Update.
8f94053d
 
Phil Edwards committed
365 366 367 368 369 370 
</tr>
</table title="Table 67"></p></a>


<a name="68"><p>
<table cellpadding="3" cellspacing="5" align="center" rules="rows" border="3"
Intro.3: Date tweak.
04b7c941
 
Phil Edwards committed
371 
       cols="4" title="Table 68">
TODO: Update.
8f94053d
 
Phil Edwards committed
372 373 374 375 376 377 378 379 
<caption><h2>Table 68 --- Optional Sequence Operations</h2></caption>
<tr><th colspan="4">
These operations are only included in containers when the operation can be
done in constant time.
</th></tr>
<tr>
<td><strong>expression</strong></td>
<td><strong>result type</strong></td>
Intro.3: Date tweak.
04b7c941
 
Phil Edwards committed
380 381 382 383 384 385 386 387 388 389 390 391 392 393 394 395 396 397 398 399 400 401 402 403 404 405 406 407 408 409 
<td><strong>operational semantics</strong></td>
<td><strong>container</strong></td>
</tr>

<tr>
<td>a.front()</td>
<td>reference; const_reference for constant a</td>
<td>*a.begin()</td>
<td>vector, list, deque</td>
</tr>

<tr>
<td>a.back()</td>
<td>reference; const_reference for constant a</td>
<td>*--a.end()</td>
<td>vector, list, deque</td>
</tr>

<tr>
<td>a.push_front(x)</td>
<td>void</td>
<td>a.insert(a.begin(),x)</td>
<td>list, deque</td>
</tr>

<tr>
<td>a.push_back(x)</td>
<td>void</td>
<td>a.insert(a.end(),x)</td>
<td>vector, list, deque</td>
TODO: Update.
8f94053d
 
Phil Edwards committed
410 411 412 
</tr>

<tr>
Intro.3: Date tweak.
04b7c941
 
Phil Edwards committed
413 414 415 416 
<td>a.pop_front()</td>
<td>void</td>
<td>a.erase(a.begin())</td>
<td>list, deque</td>
TODO: Update.
8f94053d
 
Phil Edwards committed
417 418 419 
</tr>

<tr>
Intro.3: Date tweak.
04b7c941
 
Phil Edwards committed
420 421 422 423 
<td>a.pop_back()</td>
<td>void</td>
<td>a.erase(--a.end())</td>
<td>vector, list, deque</td>
TODO: Update.
8f94053d
 
Phil Edwards committed
424 425 426 
</tr>

<tr>
Intro.3: Date tweak.
04b7c941
 
Phil Edwards committed
427 428 429 430 
<td>a[n]</td>
<td>reference; const_reference for constant a</td>
<td>*(a.begin() + n)</td>
<td>vector, deque</td>
TODO: Update.
8f94053d
 
Phil Edwards committed
431 432 433 
</tr>

<tr>
Intro.3: Date tweak.
04b7c941
 
Phil Edwards committed
434 435 436 437 
<td>a.at(n)</td>
<td>reference; const_reference for constant a</td>
<td>*(a.begin() + n)<br />throws out_of_range if n&gt;=a.size()</td>
<td>vector, deque</td>
TODO: Update.
8f94053d
 
Phil Edwards committed
438 439 440 441 442 443 
</tr>
</table title="Table 68"></p></a>


<a name="69"><p>
<table cellpadding="3" cellspacing="5" align="center" rules="rows" border="3"
Intro.3: Date tweak.
04b7c941
 
Phil Edwards committed
444 
       cols="4" title="Table 69">
TODO: Update.
8f94053d
 
Phil Edwards committed
445 446 447 
<caption><h2>Table 69 --- Associative Container Requirements</h2></caption>
<tr><th colspan="4">
These are in addition to the requirements of <a href="#65">containers</a>.
Intro.3: Date tweak.
04b7c941
 
Phil Edwards committed
448 449 450 451 452 453 
Map, multimap, set, and multiset are such containers.  An associative
container supports <em>unique keys</em> (and is written as
<code>a_uniq</code> instead of <code>a</code>) if it may contain at most
one element for each key.  Otherwise it supports <em>equivalent keys</em>
(and is written <code>a_eq</code>).  Examples of the former are set and map,
examples of the latter are multiset and multimap.
TODO: Update.
8f94053d
 
Phil Edwards committed
454 455 456 457 
</th></tr>
<tr>
<td><strong>expression</strong></td>
<td><strong>result type</strong></td>
Intro.3: Date tweak.
04b7c941
 
Phil Edwards committed
458 
<td><strong>notes, pre-/post-conditions, assertions</strong></td>
TODO: Update.
8f94053d
 
Phil Edwards committed
459 460 461 462 
<td><strong>complexity</strong></td>
</tr>

<tr>
Intro.3: Date tweak.
04b7c941
 
Phil Edwards committed
463 464 465 466 467 468 469 470 471 472 473 474 475 476 477 478 479 480 481 482 483 484 485 486 487 488 489 490 491 492 493 494 495 496 497 498 499 500 501 502 503 504 505 506 507 508 509 510 511 512 513 514 515 516 517 518 519 520 521 522 523 524 525 526 527 528 529 530 531 532 533 534 535 536 537 538 539 540 541 542 543 544 545 546 547 548 549 550 551 552 553 554 555 556 557 558 559 560 561 562 563 564 565 566 567 568 569 570 571 572 573 574 575 576 577 578 579 580 581 582 583 584 585 586 587 588 589 590 591 592 593 594 595 596 597 598 599 600 601 602 603 604 605 606 607 608 
<td>X::key_type</td>
<td>Key</td>
<td>Key is Assignable</td>
<td>compile time</td>
</tr>

<tr>
<td>X::key_compare</td>
<td>Compare</td>
<td>defaults to less&lt;key_type&gt;</td>
<td>compile time</td>
</tr>

<tr>
<td>X::value_compare</td>
<td>a binary predicate type</td>
<td>same as key_compare for set and multiset; an ordering relation on
    pairs induced by the first component (Key) for map and multimap</td>
<td>compile time</td>
</tr>

<tr>
<td>X(c)<br />X a(c)</td>
<td>&nbsp;</td>
<td>constructs an empty container which uses c as a comparison object</td>
<td>constant</td>
</tr>

<tr>
<td>X()<br />X a</td>
<td>&nbsp;</td>
<td>constructs an empty container using Compare() as a comparison object</td>
<td>constant</td>
</tr>

<tr>
<td>X(i,j,c)<br />X a(i,j,c)</td>
<td>&nbsp;</td>
<td>constructs an empty container and inserts elements from the range [i,j)
    into it; uses c as a comparison object</td>
<td>NlogN in general where N is distance(i,j); linear if [i,j) is
    sorted with value_comp()</td>
</tr>

<tr>
<td>X(i,j)<br />X a(i,j)</td>
<td>&nbsp;</td>
<td>same as previous, but uses Compare() as a comparison object</td>
<td>same as previous</td>
</tr>

<tr>
<td>a.key_comp()</td>
<td>X::key_compare</td>
<td>returns the comparison object out of which a was constructed</td>
<td>constant</td>
</tr>

<tr>
<td>a.value_comp()</td>
<td>X::value_compare</td>
<td>returns an object constructed out of the comparison object</td>
<td>constant</td>
</tr>

<tr>
<td>a_uniq.insert(t)</td>
<td>pair&lt;iterator,bool&gt;</td>
<td>&quot;Inserts t if and only if there is no element in the container with
    key equivalent to the key of t. The bool component of the returned pair
    is true -iff- the insertion took place, and the iterator component of
    the pair points to the element with key equivalent to the key of
    t.&quot;</td> <!-- DR 316 -->
<td>logarithmic</td>
</tr>

<tr>
<td>a_eq.insert(t)</td>
<td>iterator</td>
<td>inserts t, returns the iterator pointing to the inserted element</td>
<td>logarithmic</td>
</tr>

<tr>
<td>a.insert(p,t)</td>
<td>iterator</td>
<td>possibly inserts t (depending on whether a_uniq or a_eq); returns iterator
    pointing to the element with key equivalent to the key of t; iterator p
    is a hint pointing to where the insert should start to search</td>
<td>logarithmic in general, amortized constant if t is inserted right
    after p<br />
    <strong>[but see DR 233 and <a href="
    http://gcc.gnu.org/onlinedocs/libstdc++/23_containers/howto.html#4">our
    specific notes</a>]</strong></td>
</tr>

<tr>
<td>a.insert(i,j)</td>
<td>void</td>
<td>pre: i, j are not iterators into a.  possibly inserts each element from
    the range [i,j) (depending on whether a_uniq or a_eq)</td>
<td>Nlog(size()+N) where N is distance(i,j) in general</td> <!-- DR 264 -->
</tr>

<tr>
<td>a.erase(k)</td>
<td>size_type</td>
<td>erases all elements with key equivalent to k; returns number of erased
    elements</td>
<td>log(size()) + count(k)</td>
</tr>

<tr>
<td>a.erase(q)</td>
<td>void</td>
<td>erases the element pointed to by q</td>
<td>amortized constant</td>
</tr>

<tr>
<td>a.erase(q1,q2)</td>
<td>void</td>
<td>erases all the elements in the range [q1,q2)</td>
<td>log(size()) + distance(q1,q2)</td>
</tr>

<tr>
<td>a.clear()</td>
<td>void</td>
<td>erases everthing; post: size() == 0</td>
<td>linear</td> <!-- DR 224 -->
</tr>

<tr>
<td>a.find(k)</td>
<td>iterator; const_iterator for constant a</td>
<td>returns iterator pointing to element with key equivalent to k, or
    a.end() if no such element found</td>
<td>logarithmic</td>
</tr>

<tr>
<td>a.count(k)</td>
<td>size_type</td>
<td>returns number of elements with key equivalent to k</td>
<td>log(size()) + count(k)</td>
TODO: Update.
8f94053d
 
Phil Edwards committed
609 610 611 
</tr>

<tr>
Intro.3: Date tweak.
04b7c941
 
Phil Edwards committed
612 613 614 615 
<td>a.lower_bound(k)</td>
<td>iterator; const_iterator for constant a</td>
<td>returns iterator pointing to the first element with key not less than k</td>
<td>logarithmic</td>
TODO: Update.
8f94053d
 
Phil Edwards committed
616 617 618 
</tr>

<tr>
Intro.3: Date tweak.
04b7c941
 
Phil Edwards committed
619 620 621 622 
<td>a.upper_bound(k)</td>
<td>iterator; const_iterator for constant a</td>
<td>returns iterator pointing to the first element with key greater than k</td>
<td>logarithmic</td>
TODO: Update.
8f94053d
 
Phil Edwards committed
623 624 625 
</tr>

<tr>
Intro.3: Date tweak.
04b7c941
 
Phil Edwards committed
626 627 628 629 630 
<td>a.equal_range(k)</td>
<td>pair&lt;iterator,iterator&gt;;
    pair&lt;const_iterator, const_iterator&gt; for constant a</td>
<td>equivalent to make_pair(a.lower_bound(k), a.upper_bound(k))</td>
<td>logarithmic</td>
TODO: Update.
8f94053d
 
Phil Edwards committed
631 632 633 634 635 636 637 
</tr>
</table title="Table 69"></p></a>


<hr />
<p class="smallertext"><em>
See <a href="mainpage.html">mainpage.html</a> for copying conditions.
Intro.3: Date tweak.
04b7c941
 
Phil Edwards committed
638 639 
See <a href="http://gcc.gnu.org/libstdc++/">the libstdc++-v3 homepage</a>
for more information.
TODO: Update.
8f94053d
 
Phil Edwards committed
640 641 642 643 644 645 
</em></p>


</body>
</html>