Why is the size() method of std::list O(n) in GCC?

Question

In GCC the size() method of std::list is O(n). Why?

For C++11 the standard says size() of list should be O(1)

However in glibc we have the following:

/usr/include/c++/4.6.3/bits/stl_list.h

template<typename _Tp, typename _Alloc = std::allocator<_Tp> >
class list : protected _List_base<_Tp, _Alloc>
{
 ...
 size_type
  size() const
  { return std::distance(begin(), end()); }

The question is: How is it that the a three year old requirement is not yet implemented in GCC?

EDIT:

gcc 5 changes this: though at the cost of ABI change; this means that C++ code compiled with gcc 5.0 will not work with older versions of the C++ runtime library.

From https://gcc.gnu.org/gcc-5/changes.html

A new implementation of std::list is enabled by default, with an O(1) size() function

Answer 1

In C++98/03 it was unspecified as to whether std::list::size() is O(1) or O(N). There are tradeoffs for either decision.

In C++11, the committee specified that std::list::size() is O(1). This is an ABI-breaking change for implementations that have an O(N) std::list::size(), and gcc is such an implementation. Breaking ABI is a big deal for an implementor. It causes a lot of pain for its customers. So it is done only once in a big while, and with relatively big fanfare.