title: size() complexity of STL containers in G++: which containers are O(n)?
body: <p>I guess most people understand that the complexity of <code>size()</code> function is not guaranteed to be constant. Though in some implementations, it is constant. </p>
  
  <p>The G++ compiler is probably the most commonly used compiler. So, in G++'s implementation, what's the complexity of <code>size()</code>? If it varies by different containers, what containers have linear complexity? For the most commonly used ones (such as list, vector, deque, set, &amp; map), are they all constant?</p>