libstdc++-v3/doc/html/manual/containers.html

   1 <html><head><meta http-equiv="Content-Type" content="text/html; charset=UTF-8"><title>Chapter 9.  Containers</title><meta name="generator" content="DocBook XSL-NS Stylesheets V1.76.1"><meta name="keywords" content="
   2       ISO C++
   3     ,
   4       library
   5     "><meta name="keywords" content="
   6       ISO C++
   7     ,
   8       runtime
   9     ,
  10       library
  11     "><link rel="home" href="../index.html" title="The GNU C++ Library"><link rel="up" href="bk01pt02.html" title="Part II.  Standard Contents"><link rel="prev" href="facets.html" title="Facets"><link rel="next" href="associative.html" title="Associative"></head><body bgcolor="white" text="black" link="#0000FF" vlink="#840084" alink="#0000FF"><div class="navheader"><table width="100%" summary="Navigation header"><tr><th colspan="3" align="center">Chapter 9.
  12   Containers
  13
  14 </th></tr><tr><td width="20%" align="left"><a accesskey="p" href="facets.html">Prev</a> </td><th width="60%" align="center">Part II.
  15     Standard Contents
  16   </th><td width="20%" align="right"> <a accesskey="n" href="associative.html">Next</a></td></tr></table><hr></div><div class="chapter" title="Chapter 9.  Containers"><div class="titlepage"><div><div><h2 class="title"><a name="std.containers"></a>Chapter 9.
  17   Containers
  18   <a class="indexterm" name="id627339"></a>
  19 </h2></div></div></div><div class="toc"><p><b>Table of Contents</b></p><dl><dt><span class="section"><a href="containers.html#std.containers.sequences">Sequences</a></span></dt><dd><dl><dt><span class="section"><a href="containers.html#containers.sequences.list">list</a></span></dt><dd><dl><dt><span class="section"><a href="containers.html#sequences.list.size">list::size() is O(n)</a></span></dt></dl></dd><dt><span class="section"><a href="containers.html#containers.sequences.vector">vector</a></span></dt><dd><dl><dt><span class="section"><a href="containers.html#sequences.vector.management">Space Overhead Management</a></span></dt></dl></dd></dl></dd><dt><span class="section"><a href="associative.html">Associative</a></span></dt><dd><dl><dt><span class="section"><a href="associative.html#containers.associative.insert_hints">Insertion Hints</a></span></dt><dt><span class="section"><a href="associative.html#containers.associative.bitset">bitset</a></span></dt><dd><dl><dt><span class="section"><a href="associative.html#associative.bitset.size_variable">Size Variable</a></span></dt><dt><span class="section"><a href="associative.html#associative.bitset.type_string">Type String</a></span></dt></dl></dd></dl></dd><dt><span class="section"><a href="containers_and_c.html">Interacting with C</a></span></dt><dd><dl><dt><span class="section"><a href="containers_and_c.html#containers.c.vs_array">Containers vs. Arrays</a></span></dt></dl></dd></dl></div><div class="section" title="Sequences"><div class="titlepage"><div><div><h2 class="title" style="clear: both"><a name="std.containers.sequences"></a>Sequences</h2></div></div></div><div class="section" title="list"><div class="titlepage"><div><div><h3 class="title"><a name="containers.sequences.list"></a>list</h3></div></div></div><div class="section" title="list::size() is O(n)"><div class="titlepage"><div><div><h4 class="title"><a name="sequences.list.size"></a>list::size() is O(n)</h4></div></div></div><p>
  20      Yes it is, and that's okay.  This is a decision that we preserved
  21      when we imported SGI's STL implementation.  The following is
  22      quoted from <a class="link" href="http://www.sgi.com/tech/stl/FAQ.html" target="_top">their FAQ</a>:
  23    </p><div class="blockquote"><blockquote class="blockquote"><p>
  24        The size() member function, for list and slist, takes time
  25        proportional to the number of elements in the list.  This was a
  26        deliberate tradeoff.  The only way to get a constant-time
  27        size() for linked lists would be to maintain an extra member
  28        variable containing the list's size.  This would require taking
  29        extra time to update that variable (it would make splice() a
  30        linear time operation, for example), and it would also make the
  31        list larger.  Many list algorithms don't require that extra
  32        word (algorithms that do require it might do better with
  33        vectors than with lists), and, when it is necessary to maintain
  34        an explicit size count, it's something that users can do
  35        themselves.
  36      </p><p>
  37        This choice is permitted by the C++ standard. The standard says
  38        that size() <span class="quote">“<span class="quote">should</span>”</span> be constant time, and
  39        <span class="quote">“<span class="quote">should</span>”</span> does not mean the same thing as
  40        <span class="quote">“<span class="quote">shall</span>”</span>.  This is the officially recommended ISO
  41        wording for saying that an implementation is supposed to do
  42        something unless there is a good reason not to.
  43       </p><p>
  44         One implication of linear time size(): you should never write
  45       </p><pre class="programlisting">
  46          if (L.size() == 0)
  47              ...
  48          </pre><p>
  49          Instead, you should write
  50          </p><pre class="programlisting">
  51          if (L.empty())
  52              ...
  53          </pre></blockquote></div></div></div><div class="section" title="vector"><div class="titlepage"><div><div><h3 class="title"><a name="containers.sequences.vector"></a>vector</h3></div></div></div><p>
  54   </p><div class="section" title="Space Overhead Management"><div class="titlepage"><div><div><h4 class="title"><a name="sequences.vector.management"></a>Space Overhead Management</h4></div></div></div><p>
  55      In <a class="link" href="http://gcc.gnu.org/ml/libstdc++/2002-04/msg00105.html" target="_top">this
  56      message to the list</a>, Daniel Kostecky announced work on an
  57      alternate form of <code class="code">std::vector</code> that would support
  58      hints on the number of elements to be over-allocated.  The design
  59      was also described, along with possible implementation choices.
  60    </p><p>
  61      The first two alpha releases were announced <a class="link" href="http://gcc.gnu.org/ml/libstdc++/2002-07/msg00048.html" target="_top">here</a>
  62      and <a class="link" href="http://gcc.gnu.org/ml/libstdc++/2002-07/msg00111.html" target="_top">here</a>.
  63    </p></div></div></div></div><div class="navfooter"><hr><table width="100%" summary="Navigation footer"><tr><td width="40%" align="left"><a accesskey="p" href="facets.html">Prev</a> </td><td width="20%" align="center"><a accesskey="u" href="bk01pt02.html">Up</a></td><td width="40%" align="right"> <a accesskey="n" href="associative.html">Next</a></td></tr><tr><td width="40%" align="left" valign="top">Facets </td><td width="20%" align="center"><a accesskey="h" href="../index.html">Home</a></td><td width="40%" align="right" valign="top"> Associative</td></tr></table></div></body></html>