136ac495dSmrg<?xml version="1.0" encoding="UTF-8" standalone="no"?> 236ac495dSmrg<!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 Stylesheets Vsnapshot" /><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. 336ac495dSmrg Containers 436ac495dSmrg 536ac495dSmrg</th></tr><tr><td width="20%" align="left"><a accesskey="p" href="facets.html">Prev</a> </td><th width="60%" align="center">Part II. 636ac495dSmrg Standard Contents 736ac495dSmrg </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. 836ac495dSmrg Containers 936ac495dSmrg <a id="id-1.3.4.7.1.1.1" class="indexterm"></a> 1036ac495dSmrg</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.insert_hints">Insertion Hints</a></span></dt><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*8feb0f0bSmrg Yes it is, at least using the <a class="link" href="using_dual_abi.html" title="Dual ABI">old 12*8feb0f0bSmrg ABI</a>, and that's okay. This is a decision that we preserved 1336ac495dSmrg when we imported SGI's STL implementation. The following is 14a2dc1f3fSmrg quoted from <a class="link" href="https://web.archive.org/web/20171225062613/http://www.sgi.com/tech/stl/FAQ.html" target="_top">their FAQ</a>: 1536ac495dSmrg </p><div class="blockquote"><blockquote class="blockquote"><p> 1636ac495dSmrg The size() member function, for list and slist, takes time 1736ac495dSmrg proportional to the number of elements in the list. This was a 1836ac495dSmrg deliberate tradeoff. The only way to get a constant-time 1936ac495dSmrg size() for linked lists would be to maintain an extra member 2036ac495dSmrg variable containing the list's size. This would require taking 2136ac495dSmrg extra time to update that variable (it would make splice() a 2236ac495dSmrg linear time operation, for example), and it would also make the 2336ac495dSmrg list larger. Many list algorithms don't require that extra 2436ac495dSmrg word (algorithms that do require it might do better with 2536ac495dSmrg vectors than with lists), and, when it is necessary to maintain 2636ac495dSmrg an explicit size count, it's something that users can do 2736ac495dSmrg themselves. 2836ac495dSmrg </p><p> 2936ac495dSmrg This choice is permitted by the C++ standard. The standard says 3036ac495dSmrg that size() <span class="quote">“<span class="quote">should</span>”</span> be constant time, and 3136ac495dSmrg <span class="quote">“<span class="quote">should</span>”</span> does not mean the same thing as 3236ac495dSmrg <span class="quote">“<span class="quote">shall</span>”</span>. This is the officially recommended ISO 3336ac495dSmrg wording for saying that an implementation is supposed to do 3436ac495dSmrg something unless there is a good reason not to. 3536ac495dSmrg </p><p> 3636ac495dSmrg One implication of linear time size(): you should never write 3736ac495dSmrg </p><pre class="programlisting"> 3836ac495dSmrg if (L.size() == 0) 3936ac495dSmrg ... 4036ac495dSmrg </pre><p> 4136ac495dSmrg Instead, you should write 4236ac495dSmrg </p><pre class="programlisting"> 4336ac495dSmrg if (L.empty()) 4436ac495dSmrg ... 4536ac495dSmrg </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>