size() complexity of STL containers in G++: which containers are O(n)?

Question

I guess most people understand that the complexity of size() function is not guaranteed to be constant. Though in some implementations, it is constant.

The G++ compiler is probably the most commonly used compiler. So, in G++'s implementation, what's the complexity of size()? If it varies by different containers, what containers have linear complexity? For the most commonly used ones (such as list, vector, deque, set, & map), are they all constant?

Answer 1

For C++11, the standard (23.2.1) specifies that size is O(1) for all containers in conformant implementations of the standard library (unfortunately this doesn't mean that all implementations are conformant; e.g. gcc has this issue).

For C++03, the standard (23.1) says that size "should have constant complexity", which as it turns out (thank you, commenters) is a strong but non-binding suggestion; that means you have to read the documentation for the implementation provided with each compiler.

Answer 2

It may change depending on the version of the standard library.

For GCC recent versions (atleast up to 4.6.2) List and ones based off of List are not constant time, but implemented as { return std::distance(begin(), end()); }.

MSVC standard library keeps track of size as it changes and just returns its value (which makes splice() O(n) because it has to count when it splices).

From my /usr/include/c++/4.6.2/bits/stl_list.h :

/**  Returns the number of elements in the %list.  */
      size_type
      size() const
      { return std::distance(begin(), end()); }

vector, set, deque, and map are constant time. ,

this is std::deque's

  size_type
  size() const
  { return this->_M_impl._M_finish - this->_M_impl._M_start; }

queue and stack are actually container adapters and depend on the underlying container, which can be specified. However the default is deque, which is constant.