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