Is std::list::size() Truly O(n) in Modern Implementations?

Recently, some developers have suggested that std::list::size() has a linear time complexity (O(n)). However, according to the C standard, the complexity is not defined and may vary depending on the implementation.

In earlier versions of the C standard (C 03), the size() operation was recommended to have constant complexity (O(1)). However, with the introduction of C 11, it became a requirement for all standard containers. Table 96 of the C 11 standard explicitly states that .size() should have constant complexity for all containers.

Historically, GCC's libstdc library implemented size() with complexity O(n) using std::distance(begin(), end()), as described in the blog entry you cited. However, in C 11 mode, this behavior has changed:

size_type
size() const _GLIBCXX_NOEXCEPT
{ return __size_alloc_.first(); }

_LIBCPP_INLINE_VISIBILITY
const size_type& __sz() const _NOEXCEPT
    {return __size_alloc_.first();}

In GCC 5.0 and above, the size() function uses an internal data structure to keep track of the number of elements, effectively making the operation O(1). This aligns with the C 11 requirement for all standard containers.

It's important to note that some niche use cases might still lead to O(n) complexity for size(), but for the vast majority of users, the operation should be constant time.