Is list::size() really O(n)?

Pre-C++11 answer

You are correct that the standard does not state what the complexity of list::size() must be - however, it does recommend that it "should have constant complexity" (Note A in Table 65).

Here's an interesting article by Howard Hinnant that explains why some people think list::size() should have O(N) complexity (basically because they believe that O(1) list::size() makes list::splice() have O(N) complexity) and why an O(1) list::size() is be a good idea (in the author's opinion):

• http://howardhinnant.github.io/On_list_size.html

I think the main points in the paper are:

• there are few situations where maintaining an internal count so list::size() can be O(1) causes the splice operation to become linear
• there are probably many more situations where someone might be unaware of the negative effects that might happen because they call an O(N) size() (such as his one example where list::size() is called while holding a lock).
• that instead of permitting size() be O(N), in the interest of 'least surprise', the standard should require any container that implements size() to implement it in an O(1) fashion. If a container cannot do this, it should not implement size() at all. In this case, the user of the container will be made aware that size() is unavailable, and if they still want or need to get the number of elements in the container they can still use container::distance( begin(), end()) to get that value - but they will be completely aware that it's an O(N) operation.

I think I tend to agree with most of his reasoning. However, I do not like his proposed addition to the splice() overloads. Having to pass in an n that must be equal to distance( first, last) to get correct behavior seems like a recipe for hard to diagnose bugs.

I'm not sure what should or could be done moving forward, as any change would have a significant impact on existing code. But as it stands, I think that existing code is already impacted - behavior might be rather significantly different from one implementation to another for something that should have been well-defined. Maybe onebyone's comment about having the size 'cached' and marked known/unknown might work well - you get amortized O(1) behavior - the only time you get O(N) behavior is when the list is modified by some splice() operations. The nice thing about this is that it can be done by implementors today without a change to the standard (unless I'm missing something).

As far as I know, C++0x is not changing anything in this area.

I've had to look into gcc 3.4's list::size before, so I can say this:

1. It uses std::distance(head, tail).
2. std::distance has two implementations: for types that satisfy RandomAccessIterator, it uses "tail-head", and for types that merely satisfy InputIterator, it uses an O(n) algorithm relying on "iterator++", counting until it hits the given tail.
3. std::list does not satisfy RandomAccessIterator, so size is O(n).

As to the "why", I can only say that std::list is appropriate for problems that require sequential access. Storing the size as a class variable would introduce overhead on every insert, delete, etc., and that waste is a big no-no per the intent of the STL. If you really need a constant-time size(), use std::deque.

I personally don't see the issue with splice being O(N) as the only reason why size is permitted to be O(N). You don't pay for what you don't use is an important C++ motto. In this case, maintaining the list size requires an extra increment/decrement on every insert/erase whether you check the list's size or not. This is a small fixed overhead, but its still important to consider.

Checking the size of a list is rarely needed. Iterating from begin to end without caring the total size is infinitely more common.

I would go to the source (archive). SGI's STL page says that it is permitted to have a linear complexity. I believe that the design guideline they followed was to allow the list implementation to be as general as possible, and thus to allow more flexibility in using lists.

This can be clearly be shown in current GCC source code: size() is implement as below

  _GLIBCXX_NODISCARD
  size_type
  size() const _GLIBCXX_NOEXCEPT
  { return _M_node_count(); }

It called _M_node_count(), and _M_node_count is implemented as below:

    #if _GLIBCXX_USE_CXX11_ABI
      static size_t
      _S_distance(const_iterator __first, const_iterator __last)
      { return std::distance(__first, __last); }

      // return the stored size
      size_t
      _M_node_count() const
      { return this->_M_get_size(); }
#else
      // dummy implementations used when the size is not stored
      static size_t
      _S_distance(const_iterator, const_iterator)
      { return 0; }

      // count the number of nodes
      size_t
      _M_node_count() const
      { return std::distance(begin(), end()); }
#endif

if _GLIBCXX_USE_CXX11_ABI is set to 0, the size() is O(N), in other case is O(1). _GLIBCXX_USE_CXX11_ABI set to 0 will happen when you use a high version GCC compiled libraries and need link to a low version GCC compiled libraries, for example, your system have installed a GCC 4.8 compiled GTEST libraries, but your code now use GCC 7.3 and use C++11, and you need to link to that libraries, in this case you need to add following to your CMakeLists.txt, otherwise it will have link issue.

add_compile_definitions(_GLIBCXX_USE_CXX11_ABI=0)