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

Question

In GCC, the size() method for std :: list is O (n). What for?

For C ++ 11, the standard says that the size() 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()); } 

Question: how is it that the three-year requirement has not yet been implemented in the GCC?

EDIT:

gcc 5 changes this: although by changing the ABI; 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

The new std::list implementation is enabled by default with the O (1) size() function

Answer 1

C ++ 98/03 does not indicate whether std::list::size() O (1) or O (N). There are tradeoffs for any solution.

In C ++ 11, the committee pointed out that std::list::size() is O (1). This is an ABI change for implementations that have O (N) std::list::size() , and gcc is such an implementation. Breaking ABI is a big task for the developer. This causes a lot of pain for their customers. So this is done only once for a long time and with relatively large fanfare.