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"><html xmlns=
"http://www.w3.org/1999/xhtml"><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.78.1" /><meta name=
"keywords" content=
"ISO C++, library" /><meta name=
"keywords" content=
"ISO C++, runtime, library" /><link rel=
"home" href=
"../index.html" title=
"The GNU C++ Library" /><link rel=
"up" href=
"std_contents.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.
5 </th></tr><tr><td width=
"20%" align=
"left"><a accesskey=
"p" href=
"facets.html">Prev
</a> </td><th width=
"60%" align=
"center">Part II.
7 </th><td width=
"20%" align=
"right"> <a accesskey=
"n" href=
"associative.html">Next
</a></td></tr></table><hr /></div><div class=
"chapter"><div class=
"titlepage"><div><div><h2 class=
"title"><a id=
"std.containers"></a>Chapter
9.
9 <a id=
"idm269999493408" class=
"indexterm"></a>
10 </h2></div></div></div><div class=
"toc"><p><strong>Table of Contents
</strong></p><dl class=
"toc"><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></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=
"unordered_associative.html">Unordered Associative
</a></span></dt><dd><dl><dt><span class=
"section"><a href=
"unordered_associative.html#containers.unordered.hash">Hash Code
</a></span></dt><dd><dl><dt><span class=
"section"><a href=
"unordered_associative.html#containers.unordered.cache">Hash Code Caching Policy
</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"><div class=
"titlepage"><div><div><h2 class=
"title" style=
"clear: both"><a id=
"std.containers.sequences"></a>Sequences
</h2></div></div></div><div class=
"section"><div class=
"titlepage"><div><div><h3 class=
"title"><a id=
"containers.sequences.list"></a>list
</h3></div></div></div><div class=
"section"><div class=
"titlepage"><div><div><h4 class=
"title"><a id=
"sequences.list.size"></a>list::size() is O(n)
</h4></div></div></div><p>
11 Yes it is, and that was okay until the
2011 edition of the C++ standard.
12 In future GCC will change it to O(
1) but O(N) was a decision that we
13 preserved when we imported SGI's STL implementation. The following is
14 quoted from
<a class=
"link" href=
"http://www.sgi.com/tech/stl/FAQ.html" target=
"_top">their FAQ
</a>:
15 </p><div class=
"blockquote"><blockquote class=
"blockquote"><p>
16 The size() member function, for list and slist, takes time
17 proportional to the number of elements in the list. This was a
18 deliberate tradeoff. The only way to get a constant-time
19 size() for linked lists would be to maintain an extra member
20 variable containing the list's size. This would require taking
21 extra time to update that variable (it would make splice() a
22 linear time operation, for example), and it would also make the
23 list larger. Many list algorithms don't require that extra
24 word (algorithms that do require it might do better with
25 vectors than with lists), and, when it is necessary to maintain
26 an explicit size count, it's something that users can do
29 This choice is permitted by the C++ standard. The standard says
30 that size()
<span class=
"quote">“
<span class=
"quote">should
</span>”
</span> be constant time, and
31 <span class=
"quote">“
<span class=
"quote">should
</span>”
</span> does not mean the same thing as
32 <span class=
"quote">“
<span class=
"quote">shall
</span>”
</span>. This is the officially recommended ISO
33 wording for saying that an implementation is supposed to do
34 something unless there is a good reason not to.
36 One implication of linear time size(): you should never write
37 </p><pre class=
"programlisting">
41 Instead, you should write
42 </p><pre class=
"programlisting">
45 </pre></blockquote></div></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=
"std_contents.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>