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