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

   1 <?xml version="1.0" encoding="UTF-8" standalone="no"?>
   2 <!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">
   3 <html xmlns="http://www.w3.org/1999/xhtml"><head><meta http-equiv="Content-Type" content="text/html; charset=UTF-8" /><title>Chapter 16. Sequences</title><meta name="generator" content="DocBook XSL Stylesheets V1.74.0" /><meta name="keywords" content="&#10;      ISO C++&#10;    , &#10;      library&#10;    " /><link rel="home" href="../spine.html" title="The GNU C++ Library Documentation" /><link rel="up" href="containers.html" title="Part VII.  Containers" /><link rel="prev" href="containers.html" title="Part VII.  Containers" /><link rel="next" href="vector.html" title="vector" /></head><body><div class="navheader"><table width="100%" summary="Navigation header"><tr><th colspan="3" align="center">Chapter 16. Sequences</th></tr><tr><td width="20%" align="left"><a accesskey="p" href="containers.html">Prev</a> </td><th width="60%" align="center">Part VII.
   4   Containers
   5
   6 </th><td width="20%" align="right"> <a accesskey="n" href="vector.html">Next</a></td></tr></table><hr /></div><div class="chapter" lang="en" xml:lang="en"><div class="titlepage"><div><div><h2 class="title"><a id="manual.containers.sequences"></a>Chapter 16. Sequences</h2></div></div></div><div class="toc"><p><b>Table of Contents</b></p><dl><dt><span class="sect1"><a href="sequences.html#containers.sequences.list">list</a></span></dt><dd><dl><dt><span class="sect2"><a href="sequences.html#sequences.list.size">list::size() is O(n)</a></span></dt></dl></dd><dt><span class="sect1"><a href="vector.html">vector</a></span></dt><dd><dl><dt><span class="sect2"><a href="vector.html#sequences.vector.management">Space Overhead Management</a></span></dt></dl></dd></dl></div><div class="sect1" lang="en" xml:lang="en"><div class="titlepage"><div><div><h2 class="title" style="clear: both"><a id="containers.sequences.list"></a>list</h2></div></div></div><div class="sect2" lang="en" xml:lang="en"><div class="titlepage"><div><div><h3 class="title"><a id="sequences.list.size"></a>list::size() is O(n)</h3></div></div></div><p>
   7      Yes it is, and that's okay.  This is a decision that we preserved
   8      when we imported SGI's STL implementation.  The following is
   9      quoted from <a class="ulink" href="http://www.sgi.com/tech/stl/FAQ.html" target="_top">their FAQ</a>:
  10    </p><div class="blockquote"><blockquote class="blockquote"><p>
  11        The size() member function, for list and slist, takes time
  12        proportional to the number of elements in the list.  This was a
  13        deliberate tradeoff.  The only way to get a constant-time
  14        size() for linked lists would be to maintain an extra member
  15        variable containing the list's size.  This would require taking
  16        extra time to update that variable (it would make splice() a
  17        linear time operation, for example), and it would also make the
  18        list larger.  Many list algorithms don't require that extra
  19        word (algorithms that do require it might do better with
  20        vectors than with lists), and, when it is necessary to maintain
  21        an explicit size count, it's something that users can do
  22        themselves.
  23      </p><p>
  24        This choice is permitted by the C++ standard. The standard says
  25        that size() “<span class="quote">should</span>” be constant time, and
  26        “<span class="quote">should</span>” does not mean the same thing as
  27        “<span class="quote">shall</span>”.  This is the officially recommended ISO
  28        wording for saying that an implementation is supposed to do
  29        something unless there is a good reason not to.
  30       </p><p>
  31         One implication of linear time size(): you should never write
  32       </p><pre class="programlisting">
  33          if (L.size() == 0)
  34              ...
  35          </pre><p>
  36          Instead, you should write
  37          </p><pre class="programlisting">
  38          if (L.empty())
  39              ...
  40          </pre></blockquote></div></div></div></div><div class="navfooter"><hr /><table width="100%" summary="Navigation footer"><tr><td width="40%" align="left"><a accesskey="p" href="containers.html">Prev</a> </td><td width="20%" align="center"><a accesskey="u" href="containers.html">Up</a></td><td width="40%" align="right"> <a accesskey="n" href="vector.html">Next</a></td></tr><tr><td width="40%" align="left" valign="top">Part VII.
  41   Containers
  42
  43  </td><td width="20%" align="center"><a accesskey="h" href="../spine.html">Home</a></td><td width="40%" align="right" valign="top"> vector</td></tr></table></div></body></html>