1*404b540aSrobert<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN"> 2*404b540aSrobert<html> 3*404b540aSrobert<head><meta http-equiv="Content-Type" content="text/html;charset=iso-8859-1"> 4*404b540aSrobert<title>Tables</title> 5*404b540aSrobert<link href="style.css" rel="stylesheet" type="text/css"> 6*404b540aSrobert</head> 7*404b540aSrobert 8*404b540aSrobert<body bgcolor="#ffffff"> 9*404b540aSrobert 10*404b540aSrobert<h1>Tables</h1> 11*404b540aSrobert 12*404b540aSrobert<p>Most of the requirements on containers are presented in the ISO standard 13*404b540aSrobert in the form of tables. In order to avoid massive duplication of effort 14*404b540aSrobert while documenting all the classes, we follow the standard's lead and 15*404b540aSrobert present the base information here. Individual classes will only document 16*404b540aSrobert their departures from these tables (removed functions, additional functions, 17*404b540aSrobert changes, etc). 18*404b540aSrobert</p> 19*404b540aSrobert 20*404b540aSrobert<p>We will not try to duplicate all of the surrounding text (footnotes, 21*404b540aSrobert explanations, etc.) from the standard, because that would also entail a 22*404b540aSrobert duplication of effort. Some of the surrounding text has been paraphrased 23*404b540aSrobert here for clarity. If you are uncertain about the meaning or interpretation 24*404b540aSrobert of these notes, consult a good textbook, and/or purchase your own copy of 25*404b540aSrobert the standard (it's cheap, see our FAQ). 26*404b540aSrobert</p> 27*404b540aSrobert 28*404b540aSrobert<p>The table numbers are the same as those used in the standard. Tables can 29*404b540aSrobert be jumped to using their number, e.g., "tables.html#67". Only 30*404b540aSrobert Tables 65 through 69 are presented. Some of the active Defect Reports 31*404b540aSrobert are also noted or incorporated. 32*404b540aSrobert</p> 33*404b540aSrobert 34*404b540aSrobert<hr /> 35*404b540aSrobert 36*404b540aSrobert<a name="65"><p> 37*404b540aSrobert<table cellpadding="3" cellspacing="5" align="center" rules="rows" border="3" 38*404b540aSrobert cols="5" title="Table 65"> 39*404b540aSrobert<caption><h2>Table 65 --- Container Requirements</h2></caption> 40*404b540aSrobert<tr><th colspan="5"> 41*404b540aSrobertAnything calling itself a container must meet these minimum requirements. 42*404b540aSrobert</th></tr> 43*404b540aSrobert<tr> 44*404b540aSrobert<td><strong>expression</strong></td> 45*404b540aSrobert<td><strong>result type</strong></td> 46*404b540aSrobert<td><strong>operational semantics</strong></td> 47*404b540aSrobert<td><strong>notes, pre-/post-conditions, assertions</strong></td> 48*404b540aSrobert<td><strong>complexity</strong></td> 49*404b540aSrobert</tr> 50*404b540aSrobert 51*404b540aSrobert<tr> 52*404b540aSrobert<td>X::value_type</td> 53*404b540aSrobert<td>T</td> 54*404b540aSrobert<td> </td> 55*404b540aSrobert<td>T is Assignable</td> 56*404b540aSrobert<td>compile time</td> 57*404b540aSrobert</tr> 58*404b540aSrobert 59*404b540aSrobert<tr> 60*404b540aSrobert<td>X::reference</td> 61*404b540aSrobert<td>lvalue of T</td> 62*404b540aSrobert<td> </td> 63*404b540aSrobert<td> </td> 64*404b540aSrobert<td>compile time</td> 65*404b540aSrobert</tr> 66*404b540aSrobert 67*404b540aSrobert<tr> 68*404b540aSrobert<td>X::const_reference</td> 69*404b540aSrobert<td>const lvalue of T</td> 70*404b540aSrobert<td> </td> 71*404b540aSrobert<td> </td> 72*404b540aSrobert<td>compile time</td> 73*404b540aSrobert</tr> 74*404b540aSrobert 75*404b540aSrobert<tr> 76*404b540aSrobert<td>X::iterator</td> 77*404b540aSrobert<td>iterator type pointing to T</td> 78*404b540aSrobert<td> </td> 79*404b540aSrobert<td>Any iterator category except output iterator. 80*404b540aSrobert Convertible to X::const_iterator.</td> 81*404b540aSrobert<td>compile time</td> 82*404b540aSrobert</tr> 83*404b540aSrobert 84*404b540aSrobert<tr> 85*404b540aSrobert<td>X::const_iterator</td> 86*404b540aSrobert<td>iterator type pointing to const T</td> 87*404b540aSrobert<td> </td> 88*404b540aSrobert<td>Any iterator category except output iterator.</td> 89*404b540aSrobert<td>compile time</td> 90*404b540aSrobert</tr> 91*404b540aSrobert 92*404b540aSrobert<tr> 93*404b540aSrobert<td>X::difference_type</td> 94*404b540aSrobert<td>signed integral type</td> 95*404b540aSrobert<td> </td> 96*404b540aSrobert<td>identical to the difference type of X::iterator and X::const_iterator</td> 97*404b540aSrobert<td>compile time</td> 98*404b540aSrobert</tr> 99*404b540aSrobert 100*404b540aSrobert<tr> 101*404b540aSrobert<td>X::size_type</td> 102*404b540aSrobert<td>unsigned integral type</td> 103*404b540aSrobert<td> </td> 104*404b540aSrobert<td>size_type can represent any non-negative value of difference_type</td> 105*404b540aSrobert<td>compile time</td> 106*404b540aSrobert</tr> 107*404b540aSrobert 108*404b540aSrobert<tr> 109*404b540aSrobert<td>X u;</td> 110*404b540aSrobert<td> </td> 111*404b540aSrobert<td> </td> 112*404b540aSrobert<td>post: u.size() == 0</td> 113*404b540aSrobert<td>constant</td> 114*404b540aSrobert</tr> 115*404b540aSrobert 116*404b540aSrobert<tr> 117*404b540aSrobert<td>X();</td> 118*404b540aSrobert<td> </td> 119*404b540aSrobert<td> </td> 120*404b540aSrobert<td>X().size == 0</td> 121*404b540aSrobert<td>constant</td> 122*404b540aSrobert</tr> 123*404b540aSrobert 124*404b540aSrobert<tr> 125*404b540aSrobert<td>X(a);</td> 126*404b540aSrobert<td> </td> 127*404b540aSrobert<td> </td> 128*404b540aSrobert<td>a == X(a)</td> 129*404b540aSrobert<td>linear</td> 130*404b540aSrobert</tr> 131*404b540aSrobert 132*404b540aSrobert<tr> 133*404b540aSrobert<td>X u(a);<br />X u = a;</td> 134*404b540aSrobert<td> </td> 135*404b540aSrobert<td> </td> 136*404b540aSrobert<td>post: u == a. Equivalent to: X u; u = a;</td> 137*404b540aSrobert<td>linear</td> 138*404b540aSrobert</tr> 139*404b540aSrobert 140*404b540aSrobert<tr> 141*404b540aSrobert<td>(&a)->~X();</td> 142*404b540aSrobert<td>void</td> 143*404b540aSrobert<td> </td> 144*404b540aSrobert<td>dtor is applied to every element of a; all the memory is deallocated</td> 145*404b540aSrobert<td>linear</td> 146*404b540aSrobert</tr> 147*404b540aSrobert 148*404b540aSrobert<tr> 149*404b540aSrobert<td>a.begin()</td> 150*404b540aSrobert<td>iterator; const_iterator for constant a</td> 151*404b540aSrobert<td> </td> 152*404b540aSrobert<td> </td> 153*404b540aSrobert<td>constant</td> 154*404b540aSrobert</tr> 155*404b540aSrobert 156*404b540aSrobert<tr> 157*404b540aSrobert<td>a.end()</td> 158*404b540aSrobert<td>iterator; const_iterator for constant a</td> 159*404b540aSrobert<td> </td> 160*404b540aSrobert<td> </td> 161*404b540aSrobert<td>constant</td> 162*404b540aSrobert</tr> 163*404b540aSrobert 164*404b540aSrobert<tr> 165*404b540aSrobert<td>a == b</td> 166*404b540aSrobert<td>convertible to bool</td> 167*404b540aSrobert<td> </td> 168*404b540aSrobert<td>== is an equivalence relation. a.size()==b.size() && 169*404b540aSrobert equal(a.begin(),a.end(),b.begin())</td> 170*404b540aSrobert<td>linear</td> 171*404b540aSrobert</tr> 172*404b540aSrobert 173*404b540aSrobert<tr> 174*404b540aSrobert<td>a != b</td> 175*404b540aSrobert<td>convertible to bool</td> 176*404b540aSrobert<td> </td> 177*404b540aSrobert<td>equivalent to !(a==b)</td> 178*404b540aSrobert<td>linear</td> 179*404b540aSrobert</tr> 180*404b540aSrobert 181*404b540aSrobert<tr> 182*404b540aSrobert<td>a.swap(b)</td> 183*404b540aSrobert<td>void</td> 184*404b540aSrobert<td> </td> 185*404b540aSrobert<td>swap(a,b)</td> 186*404b540aSrobert<td>may or may not have constant complexity</td> 187*404b540aSrobert</tr> 188*404b540aSrobert 189*404b540aSrobert<tr> 190*404b540aSrobert<td>r = a</td> 191*404b540aSrobert<td>X&</td> 192*404b540aSrobert<td> </td> 193*404b540aSrobert<td>r == a</td> 194*404b540aSrobert<td>linear</td> 195*404b540aSrobert</tr> 196*404b540aSrobert 197*404b540aSrobert<!-- a fifth column, "operation semantics," magically appears in the table 198*404b540aSrobert at this point... wtf? --> 199*404b540aSrobert<tr> 200*404b540aSrobert<td>a.size()</td> 201*404b540aSrobert<td>size_type</td> 202*404b540aSrobert<td>a.end() - a.begin()</td> 203*404b540aSrobert<td> </td> 204*404b540aSrobert<td>may or may not have constant complexity</td> 205*404b540aSrobert</tr> 206*404b540aSrobert 207*404b540aSrobert<tr> 208*404b540aSrobert<td>a.max_size()</td> 209*404b540aSrobert<td>size_type</td> 210*404b540aSrobert<td>size() of the largest possible container</td> 211*404b540aSrobert<td> </td> 212*404b540aSrobert<td>may or may not have constant complexity</td> 213*404b540aSrobert</tr> 214*404b540aSrobert 215*404b540aSrobert<tr> 216*404b540aSrobert<td>a.empty()</td> 217*404b540aSrobert<td>convertible to bool</td> 218*404b540aSrobert<td>a.size() == 0</td> 219*404b540aSrobert<td> </td> 220*404b540aSrobert<td>constant</td> 221*404b540aSrobert</tr> 222*404b540aSrobert 223*404b540aSrobert<tr> 224*404b540aSrobert<td>a < b</td> 225*404b540aSrobert<td>convertible to bool</td> 226*404b540aSrobert<td>lexographical_compare( a.begin, a.end(), b.begin(), b.end())</td> 227*404b540aSrobert<td>pre: < is defined for T and is a total ordering relation</td> 228*404b540aSrobert<td>linear</td> 229*404b540aSrobert</tr> 230*404b540aSrobert 231*404b540aSrobert<tr> 232*404b540aSrobert<td>a > b</td> 233*404b540aSrobert<td>convertible to bool</td> 234*404b540aSrobert<td>b < a</td> 235*404b540aSrobert<td> </td> 236*404b540aSrobert<td>linear</td> 237*404b540aSrobert</tr> 238*404b540aSrobert 239*404b540aSrobert<tr> 240*404b540aSrobert<td>a <= b</td> 241*404b540aSrobert<td>convertible to bool</td> 242*404b540aSrobert<td>!(a > b)</td> 243*404b540aSrobert<td> </td> 244*404b540aSrobert<td>linear</td> 245*404b540aSrobert</tr> 246*404b540aSrobert 247*404b540aSrobert<tr> 248*404b540aSrobert<td>a >= b</td> 249*404b540aSrobert<td>convertible to bool</td> 250*404b540aSrobert<td>!(a < b)</td> 251*404b540aSrobert<td> </td> 252*404b540aSrobert<td>linear</td> 253*404b540aSrobert</tr> 254*404b540aSrobert</table title="Table 65"></p></a> 255*404b540aSrobert 256*404b540aSrobert 257*404b540aSrobert<a name="66"><p> 258*404b540aSrobert<table cellpadding="3" cellspacing="5" align="center" rules="rows" border="3" 259*404b540aSrobert cols="4" title="Table 66"> 260*404b540aSrobert<caption><h2>Table 66 --- Reversible Container Requirements</h2></caption> 261*404b540aSrobert<tr><th colspan="4"> 262*404b540aSrobertIf a container's iterator is bidirectional or random-access, then the 263*404b540aSrobertcontainer also meets these requirements. 264*404b540aSrobertDeque, list, vector, map, multimap, set, and multiset are such containers. 265*404b540aSrobert</th></tr> 266*404b540aSrobert<tr> 267*404b540aSrobert<td><strong>expression</strong></td> 268*404b540aSrobert<td><strong>result type</strong></td> 269*404b540aSrobert<td><strong>notes, pre-/post-conditions, assertions</strong></td> 270*404b540aSrobert<td><strong>complexity</strong></td> 271*404b540aSrobert</tr> 272*404b540aSrobert 273*404b540aSrobert<tr> 274*404b540aSrobert<td>X::reverse_iterator</td> 275*404b540aSrobert<td>iterator type pointing to T</td> 276*404b540aSrobert<td>reverse_iterator<iterator></td> 277*404b540aSrobert<td>compile time</td> 278*404b540aSrobert</tr> 279*404b540aSrobert 280*404b540aSrobert<tr> 281*404b540aSrobert<td>X::const_reverse_iterator</td> 282*404b540aSrobert<td>iterator type pointing to const T</td> 283*404b540aSrobert<td>reverse_iterator<const_iterator></td> 284*404b540aSrobert<td>compile time</td> 285*404b540aSrobert</tr> 286*404b540aSrobert 287*404b540aSrobert<tr> 288*404b540aSrobert<td>a.rbegin()</td> 289*404b540aSrobert<td>reverse_iterator; const_reverse_iterator for constant a</td> 290*404b540aSrobert<td>reverse_iterator(end())</td> 291*404b540aSrobert<td>constant</td> 292*404b540aSrobert</tr> 293*404b540aSrobert 294*404b540aSrobert<tr> 295*404b540aSrobert<td>a.rend()</td> 296*404b540aSrobert<td>reverse_iterator; const_reverse_iterator for constant a</td> 297*404b540aSrobert<td>reverse_iterator(begin())</td> 298*404b540aSrobert<td>constant</td> 299*404b540aSrobert</tr> 300*404b540aSrobert</table title="Table 66"></p></a> 301*404b540aSrobert 302*404b540aSrobert 303*404b540aSrobert<a name="67"><p> 304*404b540aSrobert<table cellpadding="3" cellspacing="5" align="center" rules="rows" border="3" 305*404b540aSrobert cols="3" title="Table 67"> 306*404b540aSrobert<caption><h2>Table 67 --- Sequence Requirements</h2></caption> 307*404b540aSrobert<tr><th colspan="3"> 308*404b540aSrobertThese are in addition to the requirements of <a href="#65">containers</a>. 309*404b540aSrobertDeque, list, and vector are such containers. 310*404b540aSrobert</th></tr> 311*404b540aSrobert<tr> 312*404b540aSrobert<td><strong>expression</strong></td> 313*404b540aSrobert<td><strong>result type</strong></td> 314*404b540aSrobert<td><strong>notes, pre-/post-conditions, assertions</strong></td> 315*404b540aSrobert</tr> 316*404b540aSrobert 317*404b540aSrobert<tr> 318*404b540aSrobert<td>X(n,t)<br />X a(n,t)</td> 319*404b540aSrobert<td> </td> 320*404b540aSrobert<td>constructs a sequence with n copies of t<br />post: size() == n</td> 321*404b540aSrobert</tr> 322*404b540aSrobert 323*404b540aSrobert<tr> 324*404b540aSrobert<td>X(i,j)<br />X a(i,j)</td> 325*404b540aSrobert<td> </td> 326*404b540aSrobert<td>constructs a sequence equal to the range [i,j)<br /> 327*404b540aSrobert post: size() == distance(i,j)</td> 328*404b540aSrobert</tr> 329*404b540aSrobert 330*404b540aSrobert<tr> 331*404b540aSrobert<td>a.insert(p,t)</td> 332*404b540aSrobert<td>iterator (points to the inserted copy of t)</td> 333*404b540aSrobert<td>inserts a copy of t before p</td> 334*404b540aSrobert</tr> 335*404b540aSrobert 336*404b540aSrobert<tr> 337*404b540aSrobert<td>a.insert(p,n,t)</td> 338*404b540aSrobert<td>void</td> 339*404b540aSrobert<td>inserts n copies of t before p</td> 340*404b540aSrobert</tr> 341*404b540aSrobert 342*404b540aSrobert<tr> 343*404b540aSrobert<td>a.insert(p,i,j)</td> 344*404b540aSrobert<td>void</td> 345*404b540aSrobert<td>inserts copies of elements in [i,j) before p<br /> 346*404b540aSrobert pre: i, j are not iterators into a</td> 347*404b540aSrobert</tr> 348*404b540aSrobert 349*404b540aSrobert<tr> 350*404b540aSrobert<td>a.erase(q)</td> 351*404b540aSrobert<td>iterator (points to the element following q (prior to erasure))</td> 352*404b540aSrobert<td>erases the element pointed to by q</td> 353*404b540aSrobert</tr> 354*404b540aSrobert 355*404b540aSrobert<tr> 356*404b540aSrobert<td>a.erase(q1,q1)</td> 357*404b540aSrobert<td>iterator (points to the element pointed to by q2 (prior to erasure))</td> 358*404b540aSrobert<td>erases the elements in the range [q1,q2)</td> 359*404b540aSrobert</tr> 360*404b540aSrobert 361*404b540aSrobert<tr> 362*404b540aSrobert<td>a.clear()</td> 363*404b540aSrobert<td>void</td> 364*404b540aSrobert<td>erase(begin(),end())<br />post: size() == 0</td> 365*404b540aSrobert</tr> 366*404b540aSrobert</table title="Table 67"></p></a> 367*404b540aSrobert 368*404b540aSrobert 369*404b540aSrobert<a name="68"><p> 370*404b540aSrobert<table cellpadding="3" cellspacing="5" align="center" rules="rows" border="3" 371*404b540aSrobert cols="4" title="Table 68"> 372*404b540aSrobert<caption><h2>Table 68 --- Optional Sequence Operations</h2></caption> 373*404b540aSrobert<tr><th colspan="4"> 374*404b540aSrobertThese operations are only included in containers when the operation can be 375*404b540aSrobertdone in constant time. 376*404b540aSrobert</th></tr> 377*404b540aSrobert<tr> 378*404b540aSrobert<td><strong>expression</strong></td> 379*404b540aSrobert<td><strong>result type</strong></td> 380*404b540aSrobert<td><strong>operational semantics</strong></td> 381*404b540aSrobert<td><strong>container</strong></td> 382*404b540aSrobert</tr> 383*404b540aSrobert 384*404b540aSrobert<tr> 385*404b540aSrobert<td>a.front()</td> 386*404b540aSrobert<td>reference; const_reference for constant a</td> 387*404b540aSrobert<td>*a.begin()</td> 388*404b540aSrobert<td>vector, list, deque</td> 389*404b540aSrobert</tr> 390*404b540aSrobert 391*404b540aSrobert<tr> 392*404b540aSrobert<td>a.back()</td> 393*404b540aSrobert<td>reference; const_reference for constant a</td> 394*404b540aSrobert<td>*--a.end()</td> 395*404b540aSrobert<td>vector, list, deque</td> 396*404b540aSrobert</tr> 397*404b540aSrobert 398*404b540aSrobert<tr> 399*404b540aSrobert<td>a.push_front(x)</td> 400*404b540aSrobert<td>void</td> 401*404b540aSrobert<td>a.insert(a.begin(),x)</td> 402*404b540aSrobert<td>list, deque</td> 403*404b540aSrobert</tr> 404*404b540aSrobert 405*404b540aSrobert<tr> 406*404b540aSrobert<td>a.push_back(x)</td> 407*404b540aSrobert<td>void</td> 408*404b540aSrobert<td>a.insert(a.end(),x)</td> 409*404b540aSrobert<td>vector, list, deque</td> 410*404b540aSrobert</tr> 411*404b540aSrobert 412*404b540aSrobert<tr> 413*404b540aSrobert<td>a.pop_front()</td> 414*404b540aSrobert<td>void</td> 415*404b540aSrobert<td>a.erase(a.begin())</td> 416*404b540aSrobert<td>list, deque</td> 417*404b540aSrobert</tr> 418*404b540aSrobert 419*404b540aSrobert<tr> 420*404b540aSrobert<td>a.pop_back()</td> 421*404b540aSrobert<td>void</td> 422*404b540aSrobert<td>a.erase(--a.end())</td> 423*404b540aSrobert<td>vector, list, deque</td> 424*404b540aSrobert</tr> 425*404b540aSrobert 426*404b540aSrobert<tr> 427*404b540aSrobert<td>a[n]</td> 428*404b540aSrobert<td>reference; const_reference for constant a</td> 429*404b540aSrobert<td>*(a.begin() + n)</td> 430*404b540aSrobert<td>vector, deque</td> 431*404b540aSrobert</tr> 432*404b540aSrobert 433*404b540aSrobert<tr> 434*404b540aSrobert<td>a.at(n)</td> 435*404b540aSrobert<td>reference; const_reference for constant a</td> 436*404b540aSrobert<td>*(a.begin() + n)<br />throws out_of_range if n>=a.size()</td> 437*404b540aSrobert<td>vector, deque</td> 438*404b540aSrobert</tr> 439*404b540aSrobert</table title="Table 68"></p></a> 440*404b540aSrobert 441*404b540aSrobert 442*404b540aSrobert<a name="69"><p> 443*404b540aSrobert<table cellpadding="3" cellspacing="5" align="center" rules="rows" border="3" 444*404b540aSrobert cols="4" title="Table 69"> 445*404b540aSrobert<caption><h2>Table 69 --- Associative Container Requirements</h2></caption> 446*404b540aSrobert<tr><th colspan="4"> 447*404b540aSrobertThese are in addition to the requirements of <a href="#65">containers</a>. 448*404b540aSrobertMap, multimap, set, and multiset are such containers. An associative 449*404b540aSrobertcontainer supports <em>unique keys</em> (and is written as 450*404b540aSrobert<code>a_uniq</code> instead of <code>a</code>) if it may contain at most 451*404b540aSrobertone element for each key. Otherwise it supports <em>equivalent keys</em> 452*404b540aSrobert(and is written <code>a_eq</code>). Examples of the former are set and map, 453*404b540aSrobertexamples of the latter are multiset and multimap. 454*404b540aSrobert</th></tr> 455*404b540aSrobert<tr> 456*404b540aSrobert<td><strong>expression</strong></td> 457*404b540aSrobert<td><strong>result type</strong></td> 458*404b540aSrobert<td><strong>notes, pre-/post-conditions, assertions</strong></td> 459*404b540aSrobert<td><strong>complexity</strong></td> 460*404b540aSrobert</tr> 461*404b540aSrobert 462*404b540aSrobert<tr> 463*404b540aSrobert<td>X::key_type</td> 464*404b540aSrobert<td>Key</td> 465*404b540aSrobert<td>Key is Assignable</td> 466*404b540aSrobert<td>compile time</td> 467*404b540aSrobert</tr> 468*404b540aSrobert 469*404b540aSrobert<tr> 470*404b540aSrobert<td>X::key_compare</td> 471*404b540aSrobert<td>Compare</td> 472*404b540aSrobert<td>defaults to less<key_type></td> 473*404b540aSrobert<td>compile time</td> 474*404b540aSrobert</tr> 475*404b540aSrobert 476*404b540aSrobert<tr> 477*404b540aSrobert<td>X::value_compare</td> 478*404b540aSrobert<td>a binary predicate type</td> 479*404b540aSrobert<td>same as key_compare for set and multiset; an ordering relation on 480*404b540aSrobert pairs induced by the first component (Key) for map and multimap</td> 481*404b540aSrobert<td>compile time</td> 482*404b540aSrobert</tr> 483*404b540aSrobert 484*404b540aSrobert<tr> 485*404b540aSrobert<td>X(c)<br />X a(c)</td> 486*404b540aSrobert<td> </td> 487*404b540aSrobert<td>constructs an empty container which uses c as a comparison object</td> 488*404b540aSrobert<td>constant</td> 489*404b540aSrobert</tr> 490*404b540aSrobert 491*404b540aSrobert<tr> 492*404b540aSrobert<td>X()<br />X a</td> 493*404b540aSrobert<td> </td> 494*404b540aSrobert<td>constructs an empty container using Compare() as a comparison object</td> 495*404b540aSrobert<td>constant</td> 496*404b540aSrobert</tr> 497*404b540aSrobert 498*404b540aSrobert<tr> 499*404b540aSrobert<td>X(i,j,c)<br />X a(i,j,c)</td> 500*404b540aSrobert<td> </td> 501*404b540aSrobert<td>constructs an empty container and inserts elements from the range [i,j) 502*404b540aSrobert into it; uses c as a comparison object</td> 503*404b540aSrobert<td>NlogN in general where N is distance(i,j); linear if [i,j) is 504*404b540aSrobert sorted with value_comp()</td> 505*404b540aSrobert</tr> 506*404b540aSrobert 507*404b540aSrobert<tr> 508*404b540aSrobert<td>X(i,j)<br />X a(i,j)</td> 509*404b540aSrobert<td> </td> 510*404b540aSrobert<td>same as previous, but uses Compare() as a comparison object</td> 511*404b540aSrobert<td>same as previous</td> 512*404b540aSrobert</tr> 513*404b540aSrobert 514*404b540aSrobert<tr> 515*404b540aSrobert<td>a.key_comp()</td> 516*404b540aSrobert<td>X::key_compare</td> 517*404b540aSrobert<td>returns the comparison object out of which a was constructed</td> 518*404b540aSrobert<td>constant</td> 519*404b540aSrobert</tr> 520*404b540aSrobert 521*404b540aSrobert<tr> 522*404b540aSrobert<td>a.value_comp()</td> 523*404b540aSrobert<td>X::value_compare</td> 524*404b540aSrobert<td>returns an object constructed out of the comparison object</td> 525*404b540aSrobert<td>constant</td> 526*404b540aSrobert</tr> 527*404b540aSrobert 528*404b540aSrobert<tr> 529*404b540aSrobert<td>a_uniq.insert(t)</td> 530*404b540aSrobert<td>pair<iterator,bool></td> 531*404b540aSrobert<td>"Inserts t if and only if there is no element in the container with 532*404b540aSrobert key equivalent to the key of t. The bool component of the returned pair 533*404b540aSrobert is true -iff- the insertion took place, and the iterator component of 534*404b540aSrobert the pair points to the element with key equivalent to the key of 535*404b540aSrobert t."</td> <!-- DR 316 --> 536*404b540aSrobert<td>logarithmic</td> 537*404b540aSrobert</tr> 538*404b540aSrobert 539*404b540aSrobert<tr> 540*404b540aSrobert<td>a_eq.insert(t)</td> 541*404b540aSrobert<td>iterator</td> 542*404b540aSrobert<td>inserts t, returns the iterator pointing to the inserted element</td> 543*404b540aSrobert<td>logarithmic</td> 544*404b540aSrobert</tr> 545*404b540aSrobert 546*404b540aSrobert<tr> 547*404b540aSrobert<td>a.insert(p,t)</td> 548*404b540aSrobert<td>iterator</td> 549*404b540aSrobert<td>possibly inserts t (depending on whether a_uniq or a_eq); returns iterator 550*404b540aSrobert pointing to the element with key equivalent to the key of t; iterator p 551*404b540aSrobert is a hint pointing to where the insert should start to search</td> 552*404b540aSrobert<td>logarithmic in general, amortized constant if t is inserted right 553*404b540aSrobert after p<br /> 554*404b540aSrobert <strong>[but see DR 233 and <a href=" 555*404b540aSrobert http://gcc.gnu.org/onlinedocs/libstdc++/23_containers/howto.html#4">our 556*404b540aSrobert specific notes</a>]</strong></td> 557*404b540aSrobert</tr> 558*404b540aSrobert 559*404b540aSrobert<tr> 560*404b540aSrobert<td>a.insert(i,j)</td> 561*404b540aSrobert<td>void</td> 562*404b540aSrobert<td>pre: i, j are not iterators into a. possibly inserts each element from 563*404b540aSrobert the range [i,j) (depending on whether a_uniq or a_eq)</td> 564*404b540aSrobert<td>Nlog(size()+N) where N is distance(i,j) in general</td> <!-- DR 264 --> 565*404b540aSrobert</tr> 566*404b540aSrobert 567*404b540aSrobert<tr> 568*404b540aSrobert<td>a.erase(k)</td> 569*404b540aSrobert<td>size_type</td> 570*404b540aSrobert<td>erases all elements with key equivalent to k; returns number of erased 571*404b540aSrobert elements</td> 572*404b540aSrobert<td>log(size()) + count(k)</td> 573*404b540aSrobert</tr> 574*404b540aSrobert 575*404b540aSrobert<tr> 576*404b540aSrobert<td>a.erase(q)</td> 577*404b540aSrobert<td>void</td> 578*404b540aSrobert<td>erases the element pointed to by q</td> 579*404b540aSrobert<td>amortized constant</td> 580*404b540aSrobert</tr> 581*404b540aSrobert 582*404b540aSrobert<tr> 583*404b540aSrobert<td>a.erase(q1,q2)</td> 584*404b540aSrobert<td>void</td> 585*404b540aSrobert<td>erases all the elements in the range [q1,q2)</td> 586*404b540aSrobert<td>log(size()) + distance(q1,q2)</td> 587*404b540aSrobert</tr> 588*404b540aSrobert 589*404b540aSrobert<tr> 590*404b540aSrobert<td>a.clear()</td> 591*404b540aSrobert<td>void</td> 592*404b540aSrobert<td>erases everything; post: size() == 0</td> 593*404b540aSrobert<td>linear</td> <!-- DR 224 --> 594*404b540aSrobert</tr> 595*404b540aSrobert 596*404b540aSrobert<tr> 597*404b540aSrobert<td>a.find(k)</td> 598*404b540aSrobert<td>iterator; const_iterator for constant a</td> 599*404b540aSrobert<td>returns iterator pointing to element with key equivalent to k, or 600*404b540aSrobert a.end() if no such element found</td> 601*404b540aSrobert<td>logarithmic</td> 602*404b540aSrobert</tr> 603*404b540aSrobert 604*404b540aSrobert<tr> 605*404b540aSrobert<td>a.count(k)</td> 606*404b540aSrobert<td>size_type</td> 607*404b540aSrobert<td>returns number of elements with key equivalent to k</td> 608*404b540aSrobert<td>log(size()) + count(k)</td> 609*404b540aSrobert</tr> 610*404b540aSrobert 611*404b540aSrobert<tr> 612*404b540aSrobert<td>a.lower_bound(k)</td> 613*404b540aSrobert<td>iterator; const_iterator for constant a</td> 614*404b540aSrobert<td>returns iterator pointing to the first element with key not less than k</td> 615*404b540aSrobert<td>logarithmic</td> 616*404b540aSrobert</tr> 617*404b540aSrobert 618*404b540aSrobert<tr> 619*404b540aSrobert<td>a.upper_bound(k)</td> 620*404b540aSrobert<td>iterator; const_iterator for constant a</td> 621*404b540aSrobert<td>returns iterator pointing to the first element with key greater than k</td> 622*404b540aSrobert<td>logarithmic</td> 623*404b540aSrobert</tr> 624*404b540aSrobert 625*404b540aSrobert<tr> 626*404b540aSrobert<td>a.equal_range(k)</td> 627*404b540aSrobert<td>pair<iterator,iterator>; 628*404b540aSrobert pair<const_iterator, const_iterator> for constant a</td> 629*404b540aSrobert<td>equivalent to make_pair(a.lower_bound(k), a.upper_bound(k))</td> 630*404b540aSrobert<td>logarithmic</td> 631*404b540aSrobert</tr> 632*404b540aSrobert</table title="Table 69"></p></a> 633*404b540aSrobert 634*404b540aSrobert 635*404b540aSrobert<hr /> 636*404b540aSrobert<p class="smallertext"><em> 637*404b540aSrobertSee <a href="mainpage.html">mainpage.html</a> for copying conditions. 638*404b540aSrobertSee <a href="http://gcc.gnu.org/libstdc++/">the libstdc++ homepage</a> 639*404b540aSrobertfor more information. 640*404b540aSrobert</em></p> 641*404b540aSrobert 642*404b540aSrobert 643*404b540aSrobert</body> 644*404b540aSrobert</html> 645*404b540aSrobert 646