StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>At present, time complexity of <code>size()</code> for <em>all</em> STL containers is underspecified. There's an <a href="http://www.open-std.org/jtc1/sc22/wg21/docs/lwg-active.html#632" rel="nofollow noreferrer">open C++ defect report</a> for that.</p> <p>The present ISO C++ standard says that STL containers <em>should</em> have <code>size()</code> of constant complexity:</p> <blockquote> <h3>21.3[lib.basic.string]/2</h3> <p>The class template basic_string conforms to the requirements of a Sequence, as specified in (23.1.1). Additionally, because the iterators supported by basic_string are random access iterators (24.1.5), basic_string conforms to the the requirements of a Reversible Container, as specified in (23.1).</p> <h3>23.1[lib.container.requirements]/5</h3> <ul> <li>Expression: <code>a.size()</code></li> <li>Complexity: (Note A)</li> </ul> <p>Those entries marked ‘‘(Note A)’’ <strong>should have constant complexity</strong></p> </blockquote> <p>However, "should" is not a binding requirement in the Standard parlance; indeed, the above applies to <code>std::list</code> as well, but in practice some implementations (notably g++) have O(N) <code>std::list::size()</code>.</p> <p>The only thing that can be guaranteed is that <code>(end() - begin())</code> for a string is (possibly amortized) O(1). This is because string iterators are guaranteed to be random-access, and random-access iterators are guaranteed to have constant time <code>operator-</code>.</p> <p>As a more practical issue, for all existing C++ implementations out there, the following holds:</p> <ul> <li><code>std::string::size()</code> is O(1)</li> <li><code>std::vector::size()</code> is O(1)</li> </ul> <p>They are fairly obvious, as both strings and vectors are most efficiently implemented as contiguous arrays with separately stored size: contiguous because it gives fastest element access while satisfying all other complexity requirements, and storing size is because Container requirements demand that <code>end()</code> be constant-time.</p>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload