title: Is list::size() really O(n)?
body: <p>Recently, I noticed some people mentioning that <code>std::list::size()</code> has a linear complexity.<br>
  According to <a href="http://www.cplusplus.com/reference/stl/list/size.html" rel="noreferrer">some</a> <a href="http://bytes.com/forum/thread60248.html" rel="noreferrer">sources</a>, this is in fact implementation dependent as the standard doesn't say what the complexity has to be.<br>
  The comment <a href="http://ahlamnote.blogspot.com/2006/11/stl-list-size-method-is-slow.html" rel="noreferrer">in this blog entry</a> says:</p>
  
  <blockquote>
    <p>Actually, it depends on which STL you
    are using. Microsoft Visual Studio V6
    implements size() as {return (_Size);
    } whereas gcc (at least in versions
    3.3.2 and 4.1.0) do it as { return std::distance(begin(), end()); } The
    first has constant speed, the second
    has o(N) speed</p>
  </blockquote>
  
  <ol>
  <li>So my guess is that for the VC++ crowd <code>size()</code> has constant complexity as Dinkumware
  probably won't have changed that fact since VC6. Am I right there?<br></li>
  <li>What does it look like currently in <code>gcc</code>? If it is really O(n), why did the
  developers choose to do so?</li>
  </ol>