l4/pkg/libstdc++-v3/contrib/libstdc++-v3-4.1.0/docs/html/23_containers/howto.html

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