1*404b540aSrobert<?xml version="1.0" encoding="ISO-8859-1"?> 2*404b540aSrobert<!DOCTYPE html 3*404b540aSrobert PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" 4*404b540aSrobert "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd"> 5*404b540aSrobert 6*404b540aSrobert<html xmlns="http://www.w3.org/1999/xhtml" xml:lang="en" lang="en"> 7*404b540aSrobert<head> 8*404b540aSrobert <meta http-equiv="Content-Type" content="text/html; charset=iso-8859-1" /> 9*404b540aSrobert <meta name="AUTHOR" content="pme@gcc.gnu.org (Phil Edwards)" /> 10*404b540aSrobert <meta name="KEYWORDS" content="HOWTO, libstdc++, GCC, g++, libg++, STL" /> 11*404b540aSrobert <meta name="DESCRIPTION" content="HOWTO for the libstdc++ chapter 23." /> 12*404b540aSrobert <meta name="GENERATOR" content="vi and eight fingers" /> 13*404b540aSrobert <title>libstdc++-v3 HOWTO: Chapter 23: Containers</title> 14*404b540aSrobert<link rel="StyleSheet" href="../lib3styles.css" type="text/css" /> 15*404b540aSrobert<link rel="Start" href="../documentation.html" type="text/html" 16*404b540aSrobert title="GNU C++ Standard Library" /> 17*404b540aSrobert<link rel="Prev" href="../22_locale/howto.html" type="text/html" 18*404b540aSrobert title="Localization" /> 19*404b540aSrobert<link rel="Next" href="../24_iterators/howto.html" type="text/html" 20*404b540aSrobert title="Iterators" /> 21*404b540aSrobert<link rel="Copyright" href="../17_intro/license.html" type="text/html" /> 22*404b540aSrobert<link rel="Help" href="../faq/index.html" type="text/html" title="F.A.Q." /> 23*404b540aSrobert</head> 24*404b540aSrobert<body> 25*404b540aSrobert 26*404b540aSrobert<h1 class="centered"><a name="top">Chapter 23: Containers</a></h1> 27*404b540aSrobert 28*404b540aSrobert<p>Chapter 23 deals with container classes and what they offer. 29*404b540aSrobert</p> 30*404b540aSrobert 31*404b540aSrobert 32*404b540aSrobert<!-- ####################################################### --> 33*404b540aSrobert<hr /> 34*404b540aSrobert<h1>Contents</h1> 35*404b540aSrobert<ul> 36*404b540aSrobert <li><a href="#1">Making code unaware of the container/array difference</a></li> 37*404b540aSrobert <li><a href="#2">Variable-sized bitmasks</a></li> 38*404b540aSrobert <li><a href="#3">Containers and multithreading</a></li> 39*404b540aSrobert <li><a href="#4">"Hinting" during insertion</a></li> 40*404b540aSrobert <li><a href="#5">Bitmasks and string arguments</a></li> 41*404b540aSrobert <li><a href="#6"><code>std::list::size()</code> is O(n)!</a></li> 42*404b540aSrobert <li><a href="#7">Space overhead management for vectors</a></li> 43*404b540aSrobert</ul> 44*404b540aSrobert 45*404b540aSrobert<hr /> 46*404b540aSrobert 47*404b540aSrobert<!-- ####################################################### --> 48*404b540aSrobert 49*404b540aSrobert<h2><a name="1">Making code unaware of the container/array difference</a></h2> 50*404b540aSrobert <p>You're writing some code and can't decide whether to use builtin 51*404b540aSrobert arrays or some kind of container. There are compelling reasons 52*404b540aSrobert to use one of the container classes, but you're afraid that you'll 53*404b540aSrobert eventually run into difficulties, change everything back to arrays, 54*404b540aSrobert and then have to change all the code that uses those data types to 55*404b540aSrobert keep up with the change. 56*404b540aSrobert </p> 57*404b540aSrobert <p>If your code makes use of the standard algorithms, this isn't as 58*404b540aSrobert scary as it sounds. The algorithms don't know, nor care, about 59*404b540aSrobert the kind of "container" on which they work, since the 60*404b540aSrobert algorithms are only given endpoints to work with. For the container 61*404b540aSrobert classes, these are iterators (usually <code>begin()</code> and 62*404b540aSrobert <code>end()</code>, but not always). For builtin arrays, these are 63*404b540aSrobert the address of the first element and the 64*404b540aSrobert <a href="../24_iterators/howto.html#2">past-the-end</a> element. 65*404b540aSrobert </p> 66*404b540aSrobert <p>Some very simple wrapper functions can hide all of that from the 67*404b540aSrobert rest of the code. For example, a pair of functions called 68*404b540aSrobert <code>beginof</code> can be written, one that takes an array, another 69*404b540aSrobert that takes a vector. The first returns a pointer to the first 70*404b540aSrobert element, and the second returns the vector's <code>begin()</code> 71*404b540aSrobert iterator. 72*404b540aSrobert </p> 73*404b540aSrobert <p>The functions should be made template functions, and should also 74*404b540aSrobert be declared inline. As pointed out in the comments in the code 75*404b540aSrobert below, this can lead to <code>beginof</code> being optimized out of 76*404b540aSrobert existence, so you pay absolutely nothing in terms of increased 77*404b540aSrobert code size or execution time. 78*404b540aSrobert </p> 79*404b540aSrobert <p>The result is that if all your algorithm calls look like 80*404b540aSrobert </p> 81*404b540aSrobert <pre> 82*404b540aSrobert std::transform(beginof(foo), endof(foo), beginof(foo), SomeFunction);</pre> 83*404b540aSrobert <p>then the type of foo can change from an array of ints to a vector 84*404b540aSrobert of ints to a deque of ints and back again, without ever changing any 85*404b540aSrobert client code. 86*404b540aSrobert </p> 87*404b540aSrobert <p>This author has a collection of such functions, called "*of" 88*404b540aSrobert because they all extend the builtin "sizeof". It started 89*404b540aSrobert with some Usenet discussions on a transparent way to find the length 90*404b540aSrobert of an array. A simplified and much-reduced version for easier 91*404b540aSrobert reading is <a href="wrappers_h.txt">given here</a>. 92*404b540aSrobert </p> 93*404b540aSrobert <p>Astute readers will notice two things at once: first, that the 94*404b540aSrobert container class is still a <code>vector<T></code> instead of a 95*404b540aSrobert more general <code>Container<T></code>. This would mean that 96*404b540aSrobert three functions for <code>deque</code> would have to be added, another 97*404b540aSrobert three for <code>list</code>, and so on. This is due to problems with 98*404b540aSrobert getting template resolution correct; I find it easier just to 99*404b540aSrobert give the extra three lines and avoid confusion. 100*404b540aSrobert </p> 101*404b540aSrobert <p>Second, the line 102*404b540aSrobert </p> 103*404b540aSrobert <pre> 104*404b540aSrobert inline unsigned int lengthof (T (&)[sz]) { return sz; } </pre> 105*404b540aSrobert <p>looks just weird! Hint: unused parameters can be left nameless. 106*404b540aSrobert </p> 107*404b540aSrobert <p>Return <a href="#top">to top of page</a> or 108*404b540aSrobert <a href="../faq/index.html">to the FAQ</a>. 109*404b540aSrobert </p> 110*404b540aSrobert 111*404b540aSrobert<hr /> 112*404b540aSrobert<h2><a name="2">Variable-sized bitmasks</a></h2> 113*404b540aSrobert <p>No, you cannot write code of the form 114*404b540aSrobert </p> 115*404b540aSrobert <!-- Careful, the leading spaces in PRE show up directly. --> 116*404b540aSrobert <pre> 117*404b540aSrobert #include <bitset> 118*404b540aSrobert 119*404b540aSrobert void foo (size_t n) 120*404b540aSrobert { 121*404b540aSrobert std::bitset<n> bits; 122*404b540aSrobert .... 123*404b540aSrobert } </pre> 124*404b540aSrobert <p>because <code>n</code> must be known at compile time. Your compiler is 125*404b540aSrobert correct; it is not a bug. That's the way templates work. (Yes, it 126*404b540aSrobert <em>is</em> a feature.) 127*404b540aSrobert </p> 128*404b540aSrobert <p>There are a couple of ways to handle this kind of thing. Please 129*404b540aSrobert consider all of them before passing judgement. They include, in 130*404b540aSrobert no particular order: 131*404b540aSrobert </p> 132*404b540aSrobert <ul> 133*404b540aSrobert <li>A very large N in <code>bitset<N></code>.</li> 134*404b540aSrobert <li>A container<bool>.</li> 135*404b540aSrobert <li>Extremely weird solutions.</li> 136*404b540aSrobert </ul> 137*404b540aSrobert <p><strong>A very large N in 138*404b540aSrobert <code>bitset<N></code>. </strong> It has 139*404b540aSrobert been pointed out a few times in newsgroups that N bits only takes up 140*404b540aSrobert (N/8) bytes on most systems, and division by a factor of eight is pretty 141*404b540aSrobert impressive when speaking of memory. Half a megabyte given over to a 142*404b540aSrobert bitset (recall that there is zero space overhead for housekeeping info; 143*404b540aSrobert it is known at compile time exactly how large the set is) will hold over 144*404b540aSrobert four million bits. If you're using those bits as status flags (e.g., 145*404b540aSrobert "changed"/"unchanged" flags), that's a <em>lot</em> 146*404b540aSrobert of state. 147*404b540aSrobert </p> 148*404b540aSrobert <p>You can then keep track of the "maximum bit used" during some 149*404b540aSrobert testing runs on representative data, make note of how many of those bits 150*404b540aSrobert really need to be there, and then reduce N to a smaller number. Leave 151*404b540aSrobert some extra space, of course. (If you plan to write code like the 152*404b540aSrobert incorrect example above, where the bitset is a local variable, then you 153*404b540aSrobert may have to talk your compiler into allowing that much stack space; 154*404b540aSrobert there may be zero space overhead, but it's all allocated inside the 155*404b540aSrobert object.) 156*404b540aSrobert </p> 157*404b540aSrobert <p><strong>A container<bool>. </strong> The Committee 158*404b540aSrobert made provision 159*404b540aSrobert for the space savings possible with that (N/8) usage previously mentioned, 160*404b540aSrobert so that you don't have to do wasteful things like 161*404b540aSrobert <code>Container<char></code> or 162*404b540aSrobert <code>Container<short int></code>. 163*404b540aSrobert Specifically, <code>vector<bool></code> is required to be 164*404b540aSrobert specialized for that space savings. 165*404b540aSrobert </p> 166*404b540aSrobert <p>The problem is that <code>vector<bool></code> doesn't behave like a 167*404b540aSrobert normal vector anymore. There have been recent journal articles which 168*404b540aSrobert discuss the problems (the ones by Herb Sutter in the May and 169*404b540aSrobert July/August 1999 issues of 170*404b540aSrobert <u>C++ Report</u> cover it well). Future revisions of the ISO C++ 171*404b540aSrobert Standard will change the requirement for <code>vector<bool></code> 172*404b540aSrobert specialization. In the meantime, <code>deque<bool></code> is 173*404b540aSrobert recommended (although its behavior is sane, you probably will not get 174*404b540aSrobert the space savings, but the allocation scheme is different than that 175*404b540aSrobert of vector). 176*404b540aSrobert </p> 177*404b540aSrobert <p><strong>Extremely weird solutions. </strong> If you have 178*404b540aSrobert access to 179*404b540aSrobert the compiler and linker at runtime, you can do something insane, like 180*404b540aSrobert figuring out just how many bits you need, then writing a temporary 181*404b540aSrobert source code file. That file contains an instantiation of 182*404b540aSrobert <code>bitset</code> 183*404b540aSrobert for the required number of bits, inside some wrapper functions with 184*404b540aSrobert unchanging signatures. Have your program then call the 185*404b540aSrobert compiler on that file using Position Independent Code, then open the 186*404b540aSrobert newly-created object file and load those wrapper functions. You'll have 187*404b540aSrobert an instantiation of <code>bitset<N></code> for the exact 188*404b540aSrobert <code>N</code> 189*404b540aSrobert that you need at the time. Don't forget to delete the temporary files. 190*404b540aSrobert (Yes, this <em>can</em> be, and <em>has been</em>, done.) 191*404b540aSrobert </p> 192*404b540aSrobert <!-- I wonder if this next paragraph will get me in trouble... --> 193*404b540aSrobert <p>This would be the approach of either a visionary genius or a raving 194*404b540aSrobert lunatic, depending on your programming and management style. Probably 195*404b540aSrobert the latter. 196*404b540aSrobert </p> 197*404b540aSrobert <p>Which of the above techniques you use, if any, are up to you and your 198*404b540aSrobert intended application. Some time/space profiling is indicated if it 199*404b540aSrobert really matters (don't just guess). And, if you manage to do anything 200*404b540aSrobert along the lines of the third category, the author would love to hear 201*404b540aSrobert from you... 202*404b540aSrobert </p> 203*404b540aSrobert <p>Also note that the implementation of bitset used in libstdc++-v3 has 204*404b540aSrobert <a href="../ext/sgiexts.html#ch23">some extensions</a>. 205*404b540aSrobert </p> 206*404b540aSrobert <p>Return <a href="#top">to top of page</a> or 207*404b540aSrobert <a href="../faq/index.html">to the FAQ</a>. 208*404b540aSrobert </p> 209*404b540aSrobert 210*404b540aSrobert<hr /> 211*404b540aSrobert<h2><a name="3">Containers and multithreading</a></h2> 212*404b540aSrobert <p>This section discusses issues surrounding the design of 213*404b540aSrobert multithreaded applications which use Standard C++ containers. 214*404b540aSrobert All information in this section is current as of the gcc 3.0 215*404b540aSrobert release and all later point releases. Although earlier gcc 216*404b540aSrobert releases had a different approach to threading configuration and 217*404b540aSrobert proper compilation, the basic code design rules presented here 218*404b540aSrobert were similar. For information on all other aspects of 219*404b540aSrobert multithreading as it relates to libstdc++, including details on 220*404b540aSrobert the proper compilation of threaded code (and compatibility between 221*404b540aSrobert threaded and non-threaded code), see Chapter 17. 222*404b540aSrobert </p> 223*404b540aSrobert <p>Two excellent pages to read when working with the Standard C++ 224*404b540aSrobert containers and threads are 225*404b540aSrobert <a href="http://www.sgi.com/tech/stl/thread_safety.html">SGI's 226*404b540aSrobert http://www.sgi.com/tech/stl/thread_safety.html</a> and 227*404b540aSrobert <a href="http://www.sgi.com/tech/stl/Allocators.html">SGI's 228*404b540aSrobert http://www.sgi.com/tech/stl/Allocators.html</a>. 229*404b540aSrobert </p> 230*404b540aSrobert <p><em>However, please ignore all discussions about the user-level 231*404b540aSrobert configuration of the lock implementation inside the STL 232*404b540aSrobert container-memory allocator on those pages. For the sake of this 233*404b540aSrobert discussion, libstdc++-v3 configures the SGI STL implementation, 234*404b540aSrobert not you. This is quite different from how gcc pre-3.0 worked. 235*404b540aSrobert In particular, past advice was for people using g++ to 236*404b540aSrobert explicitly define _PTHREADS or other macros or port-specific 237*404b540aSrobert compilation options on the command line to get a thread-safe 238*404b540aSrobert STL. This is no longer required for any port and should no 239*404b540aSrobert longer be done unless you really know what you are doing and 240*404b540aSrobert assume all responsibility.</em> 241*404b540aSrobert </p> 242*404b540aSrobert <p>Since the container implementation of libstdc++-v3 uses the SGI 243*404b540aSrobert code, we use the same definition of thread safety as SGI when 244*404b540aSrobert discussing design. A key point that beginners may miss is the 245*404b540aSrobert fourth major paragraph of the first page mentioned above 246*404b540aSrobert ("For most clients,"...), which points out that 247*404b540aSrobert locking must nearly always be done outside the container, by 248*404b540aSrobert client code (that'd be you, not us). There is a notable 249*404b540aSrobert exceptions to this rule. Allocators called while a container or 250*404b540aSrobert element is constructed uses an internal lock obtained and 251*404b540aSrobert released solely within libstdc++-v3 code (in fact, this is the 252*404b540aSrobert reason STL requires any knowledge of the thread configuration). 253*404b540aSrobert </p> 254*404b540aSrobert <p>For implementing a container which does its own locking, it is 255*404b540aSrobert trivial to provide a wrapper class which obtains the lock (as 256*404b540aSrobert SGI suggests), performs the container operation, and then 257*404b540aSrobert releases the lock. This could be templatized <em>to a certain 258*404b540aSrobert extent</em>, on the underlying container and/or a locking 259*404b540aSrobert mechanism. Trying to provide a catch-all general template 260*404b540aSrobert solution would probably be more trouble than it's worth. 261*404b540aSrobert </p> 262*404b540aSrobert <p>The STL implementation is currently configured to use the 263*404b540aSrobert high-speed caching memory allocator. Some people like to 264*404b540aSrobert test and/or normally run threaded programs with a different 265*404b540aSrobert default. For all details about how to globally override this 266*404b540aSrobert at application run-time see <a href="../ext/howto.html#3">here</a>. 267*404b540aSrobert </p> 268*404b540aSrobert <p>There is a better way (not standardized yet): It is possible to 269*404b540aSrobert force the malloc-based allocator on a per-case-basis for some 270*404b540aSrobert application code. The library team generally believes that this 271*404b540aSrobert is a better way to tune an application for high-speed using this 272*404b540aSrobert implementation of the STL. There is 273*404b540aSrobert <a href="../ext/howto.html#3">more information on allocators here</a>. 274*404b540aSrobert </p> 275*404b540aSrobert <p>Return <a href="#top">to top of page</a> or 276*404b540aSrobert <a href="../faq/index.html">to the FAQ</a>. 277*404b540aSrobert </p> 278*404b540aSrobert 279*404b540aSrobert<hr /> 280*404b540aSrobert<h2><a name="4">"Hinting" during insertion</a></h2> 281*404b540aSrobert <p>Section [23.1.2], Table 69, of the C++ standard lists this function 282*404b540aSrobert for all of the associative containers (map, set, etc): 283*404b540aSrobert </p> 284*404b540aSrobert <pre> 285*404b540aSrobert a.insert(p,t);</pre> 286*404b540aSrobert <p>where 'p' is an iterator into the container 'a', and 't' is the item 287*404b540aSrobert to insert. The standard says that "iterator p is a hint 288*404b540aSrobert pointing to where the insert should start to search," but 289*404b540aSrobert specifies nothing more. (LWG Issue #233, currently in review, 290*404b540aSrobert addresses this topic, but I will ignore it here because it is not yet 291*404b540aSrobert finalized.) 292*404b540aSrobert </p> 293*404b540aSrobert <p>Here we'll describe how the hinting works in the libstdc++-v3 294*404b540aSrobert implementation, and what you need to do in order to take advantage of 295*404b540aSrobert it. (Insertions can change from logarithmic complexity to amortized 296*404b540aSrobert constant time, if the hint is properly used.) Also, since the current 297*404b540aSrobert implementation is based on the SGI STL one, these points may hold true 298*404b540aSrobert for other library implementations also, since the HP/SGI code is used 299*404b540aSrobert in a lot of places. 300*404b540aSrobert </p> 301*404b540aSrobert <p>In the following text, the phrases <em>greater than</em> and <em>less 302*404b540aSrobert than</em> refer to the results of the strict weak ordering imposed on 303*404b540aSrobert the container by its comparison object, which defaults to (basically) 304*404b540aSrobert "<". Using those phrases is semantically sloppy, but I 305*404b540aSrobert didn't want to get bogged down in syntax. I assume that if you are 306*404b540aSrobert intelligent enough to use your own comparison objects, you are also 307*404b540aSrobert intelligent enough to assign "greater" and "lesser" 308*404b540aSrobert their new meanings in the next paragraph. *grin* 309*404b540aSrobert </p> 310*404b540aSrobert <p>If the <code>hint</code> parameter ('p' above) is equivalent to: 311*404b540aSrobert </p> 312*404b540aSrobert <ul> 313*404b540aSrobert <li><code>begin()</code>, then the item being inserted should have a key 314*404b540aSrobert less than all the other keys in the container. The item will 315*404b540aSrobert be inserted at the beginning of the container, becoming the new 316*404b540aSrobert entry at <code>begin()</code>. 317*404b540aSrobert </li> 318*404b540aSrobert <li><code>end()</code>, then the item being inserted should have a key 319*404b540aSrobert greater than all the other keys in the container. The item will 320*404b540aSrobert be inserted at the end of the container, becoming the new entry 321*404b540aSrobert at <code>end()</code>. 322*404b540aSrobert </li> 323*404b540aSrobert <li>neither <code>begin()</code> nor <code>end()</code>, then: Let <code>h</code> 324*404b540aSrobert be the entry in the container pointed to by <code>hint</code>, that 325*404b540aSrobert is, <code>h = *hint</code>. Then the item being inserted should have 326*404b540aSrobert a key less than that of <code>h</code>, and greater than that of the 327*404b540aSrobert item preceding <code>h</code>. The new item will be inserted 328*404b540aSrobert between <code>h</code> and <code>h</code>'s predecessor. 329*404b540aSrobert </li> 330*404b540aSrobert </ul> 331*404b540aSrobert <p>For <code>multimap</code> and <code>multiset</code>, the restrictions are 332*404b540aSrobert slightly looser: "greater than" should be replaced by 333*404b540aSrobert "not less than" and "less than" should be replaced 334*404b540aSrobert by "not greater than." (Why not replace greater with 335*404b540aSrobert greater-than-or-equal-to? You probably could in your head, but the 336*404b540aSrobert mathematicians will tell you that it isn't the same thing.) 337*404b540aSrobert </p> 338*404b540aSrobert <p>If the conditions are not met, then the hint is not used, and the 339*404b540aSrobert insertion proceeds as if you had called <code> a.insert(t) </code> 340*404b540aSrobert instead. (<strong>Note </strong> that GCC releases prior to 3.0.2 341*404b540aSrobert had a bug in the case with <code>hint == begin()</code> for the 342*404b540aSrobert <code>map</code> and <code>set</code> classes. You should not use a hint 343*404b540aSrobert argument in those releases.) 344*404b540aSrobert </p> 345*404b540aSrobert <p>This behavior goes well with other container's <code>insert()</code> 346*404b540aSrobert functions which take an iterator: if used, the new item will be 347*404b540aSrobert inserted before the iterator passed as an argument, same as the other 348*404b540aSrobert containers. The exception 349*404b540aSrobert (in a sense) is with a hint of <code>end()</code>: the new item will 350*404b540aSrobert actually be inserted after <code>end()</code>, but it also becomes the 351*404b540aSrobert new <code>end()</code>. 352*404b540aSrobert </p> 353*404b540aSrobert <p><strong>Note </strong> also that the hint in this implementation is a 354*404b540aSrobert one-shot. The insertion-with-hint routines check the immediately 355*404b540aSrobert surrounding entries to ensure that the new item would in fact belong 356*404b540aSrobert there. If the hint does not point to the correct place, then no 357*404b540aSrobert further local searching is done; the search begins from scratch in 358*404b540aSrobert logarithmic time. (Further local searching would only increase the 359*404b540aSrobert time required when the hint is too far off.) 360*404b540aSrobert </p> 361*404b540aSrobert <p>Return <a href="#top">to top of page</a> or 362*404b540aSrobert <a href="../faq/index.html">to the FAQ</a>. 363*404b540aSrobert </p> 364*404b540aSrobert 365*404b540aSrobert<hr /> 366*404b540aSrobert<h2><a name="5">Bitmasks and string arguments</a></h2> 367*404b540aSrobert <p>Bitmasks do not take char* nor const char* arguments in their 368*404b540aSrobert constructors. This is something of an accident, but you can read 369*404b540aSrobert about the problem: follow the library's "Links" from the 370*404b540aSrobert homepage, and from the C++ information "defect reflector" 371*404b540aSrobert link, select the library issues list. Issue number 116 describes the 372*404b540aSrobert problem. 373*404b540aSrobert </p> 374*404b540aSrobert <p>For now you can simply make a temporary string object using the 375*404b540aSrobert constructor expression: 376*404b540aSrobert </p> 377*404b540aSrobert <pre> 378*404b540aSrobert std::bitset<5> b ( std::string("10110") ); 379*404b540aSrobert </pre> 380*404b540aSrobert instead of 381*404b540aSrobert <pre> 382*404b540aSrobert std::bitset<5> b ( "10110" ); // invalid 383*404b540aSrobert </pre> 384*404b540aSrobert <p>Return <a href="#top">to top of page</a> or 385*404b540aSrobert <a href="../faq/index.html">to the FAQ</a>. 386*404b540aSrobert </p> 387*404b540aSrobert 388*404b540aSrobert<hr /> 389*404b540aSrobert<h2><a name="6"><code>std::list::size()</code> is O(n)!</a></h2> 390*404b540aSrobert <p>Yes it is, and that's okay. This is a decision that we preserved when 391*404b540aSrobert we imported SGI's STL implementation. The following is quoted from 392*404b540aSrobert <a href="http://www.sgi.com/tech/stl/FAQ.html">their FAQ</a>: 393*404b540aSrobert </p> 394*404b540aSrobert <blockquote> 395*404b540aSrobert <p>The size() member function, for list and slist, takes time 396*404b540aSrobert proportional to the number of elements in the list. This was a 397*404b540aSrobert deliberate tradeoff. The only way to get a constant-time size() for 398*404b540aSrobert linked lists would be to maintain an extra member variable containing 399*404b540aSrobert the list's size. This would require taking extra time to update that 400*404b540aSrobert variable (it would make splice() a linear time operation, for example), 401*404b540aSrobert and it would also make the list larger. Many list algorithms don't 402*404b540aSrobert require that extra word (algorithms that do require it might do better 403*404b540aSrobert with vectors than with lists), and, when it is necessary to maintain 404*404b540aSrobert an explicit size count, it's something that users can do themselves. 405*404b540aSrobert </p> 406*404b540aSrobert <p>This choice is permitted by the C++ standard. The standard says that 407*404b540aSrobert size() "should" be constant time, and "should" 408*404b540aSrobert does not mean the same thing as "shall". This is the 409*404b540aSrobert officially recommended ISO wording for saying that an implementation 410*404b540aSrobert is supposed to do something unless there is a good reason not to. 411*404b540aSrobert </p> 412*404b540aSrobert <p>One implication of linear time size(): you should never write 413*404b540aSrobert </p> 414*404b540aSrobert <pre> 415*404b540aSrobert if (L.size() == 0) 416*404b540aSrobert ...</pre> 417*404b540aSrobert Instead, you should write 418*404b540aSrobert <pre> 419*404b540aSrobert if (L.empty()) 420*404b540aSrobert ...</pre> 421*404b540aSrobert </blockquote> 422*404b540aSrobert <p>Return <a href="#top">to top of page</a> or 423*404b540aSrobert <a href="../faq/index.html">to the FAQ</a>. 424*404b540aSrobert </p> 425*404b540aSrobert 426*404b540aSrobert<hr /> 427*404b540aSrobert<h2><a name="7">Space overhead management for vectors</a></h2> 428*404b540aSrobert <p>In 429*404b540aSrobert <a href="http://gcc.gnu.org/ml/libstdc++/2002-04/msg00105.html">this 430*404b540aSrobert message to the list</a>, Daniel Kostecky announced work on an 431*404b540aSrobert alternate form of <code>std::vector</code> that would support hints 432*404b540aSrobert on the number of elements to be over-allocated. The design was also 433*404b540aSrobert described, along with possible implementation choices. 434*404b540aSrobert </p> 435*404b540aSrobert <p>The first two alpha releases were announced 436*404b540aSrobert <a href="http://gcc.gnu.org/ml/libstdc++/2002-07/msg00048.html">here</a> 437*404b540aSrobert and 438*404b540aSrobert <a href="http://gcc.gnu.org/ml/libstdc++/2002-07/msg00111.html">here</a>. 439*404b540aSrobert The releases themselves are available at 440*404b540aSrobert <a href="http://www.kotelna.sk/dk/sw/caphint/"> 441*404b540aSrobert http://www.kotelna.sk/dk/sw/caphint/</a>. 442*404b540aSrobert </p> 443*404b540aSrobert <p>Return <a href="#top">to top of page</a> or 444*404b540aSrobert <a href="../faq/index.html">to the FAQ</a>. 445*404b540aSrobert </p> 446*404b540aSrobert 447*404b540aSrobert 448*404b540aSrobert<!-- ####################################################### --> 449*404b540aSrobert 450*404b540aSrobert<hr /> 451*404b540aSrobert<p class="fineprint"><em> 452*404b540aSrobertSee <a href="../17_intro/license.html">license.html</a> for copying conditions. 453*404b540aSrobertComments and suggestions are welcome, and may be sent to 454*404b540aSrobert<a href="mailto:libstdc++@gcc.gnu.org">the libstdc++ mailing list</a>. 455*404b540aSrobert</em></p> 456*404b540aSrobert 457*404b540aSrobert 458*404b540aSrobert</body> 459*404b540aSrobert</html> 460