summaryrefslogtreecommitdiff
path: root/libstdc++-v3/doc/html/manual/containers.html
blob: 1185af6a10b5ffca675ac2ed7799a252fce6679c (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
<?xml version="1.0" encoding="UTF-8" standalone="no"?>
<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.1//EN" "http://www.w3.org/TR/xhtml11/DTD/xhtml11.dtd">
<html xmlns="http://www.w3.org/1999/xhtml"><head><title>Chapter 9.  Containers</title><meta name="generator" content="DocBook XSL-NS Stylesheets V1.76.1"/><meta name="keywords" content="&#10;      ISO C++&#10;    , &#10;      library&#10;    "/><link rel="home" href="../spine.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><div class="navheader"><table width="100%" summary="Navigation header"><tr><th colspan="3" align="center">Chapter 9. 
  Containers
  
</th></tr><tr><td align="left"><a accesskey="p" href="facets.html">Prev</a> </td><th width="60%" align="center">Part II. 
    Standard Contents
  </th><td 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 id="std.containers"/>Chapter 9. 
  Containers
  <a id="id478750" class="indexterm"/>
</h2></div></div></div><div class="toc"><p><strong>Table of Contents</strong></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><dt><span class="section"><a href="containers.html#containers.sequences.vector">vector</a></span></dt></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></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"><a id="std.containers.sequences"/>Sequences</h2></div></div></div><div class="section" title="list"><div class="titlepage"><div><div><h3 class="title"><a id="containers.sequences.list"/>list</h3></div></div></div><div class="section" title="list::size() is O(n)"><div class="titlepage"><div><div><h4 class="title"><a id="sequences.list.size"/>list::size() is O(n)</h4></div></div></div><p>
     Yes it is, and that's okay.  This is a decision that we preserved
     when we imported SGI's STL implementation.  The following is
     quoted from <a class="link" href="http://www.sgi.com/tech/stl/FAQ.html">their FAQ</a>:
   </p><div class="blockquote"><blockquote class="blockquote"><p>
       The size() member function, for list and slist, takes time
       proportional to the number of elements in the list.  This was a
       deliberate tradeoff.  The only way to get a constant-time
       size() for linked lists would be to maintain an extra member
       variable containing the list's size.  This would require taking
       extra time to update that variable (it would make splice() a
       linear time operation, for example), and it would also make the
       list larger.  Many list algorithms don't require that extra
       word (algorithms that do require it might do better with
       vectors than with lists), and, when it is necessary to maintain
       an explicit size count, it's something that users can do
       themselves.
     </p><p>
       This choice is permitted by the C++ standard. The standard says
       that size() <span class="quote"><span class="quote">should</span></span> be constant time, and
       <span class="quote"><span class="quote">should</span></span> does not mean the same thing as
       <span class="quote"><span class="quote">shall</span></span>.  This is the officially recommended ISO
       wording for saying that an implementation is supposed to do
       something unless there is a good reason not to.
      </p><p>
	One implication of linear time size(): you should never write
      </p><pre class="programlisting">
	 if (L.size() == 0)
	     ...
	 </pre><p>
	 Instead, you should write
	 </p><pre class="programlisting">
	 if (L.empty())
	     ...
	 </pre></blockquote></div></div></div><div class="section" title="vector"><div class="titlepage"><div><div><h3 class="title"><a id="containers.sequences.vector"/>vector</h3></div></div></div><p>
  </p><div class="section" title="Space Overhead Management"><div class="titlepage"><div><div><h4 class="title"><a id="sequences.vector.management"/>Space Overhead Management</h4></div></div></div><p>
     In <a class="link" href="http://gcc.gnu.org/ml/libstdc++/2002-04/msg00105.html">this
     message to the list</a>, Daniel Kostecky announced work on an
     alternate form of <code class="code">std::vector</code> that would support
     hints on the number of elements to be over-allocated.  The design
     was also described, along with possible implementation choices.
   </p><p>
     The first two alpha releases were announced <a class="link" href="http://gcc.gnu.org/ml/libstdc++/2002-07/msg00048.html">here</a>
     and <a class="link" href="http://gcc.gnu.org/ml/libstdc++/2002-07/msg00111.html">here</a>.
   </p></div></div></div></div><div class="navfooter"><hr/><table width="100%" summary="Navigation footer"><tr><td align="left"><a accesskey="p" href="facets.html">Prev</a> </td><td align="center"><a accesskey="u" href="bk01pt02.html">Up</a></td><td align="right"> <a accesskey="n" href="associative.html">Next</a></td></tr><tr><td align="left" valign="top">Facets </td><td align="center"><a accesskey="h" href="../spine.html">Home</a></td><td align="right" valign="top"> Associative</td></tr></table></div></body></html>