libstdc++-v3/docs/html/23_containers/howto.html

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