Why isn't std::list.size() constant-time? [duplicate]

Question

This code ran for 0.012 seconds:

 std::list<int> list;
 list.resize(100);
 int size;
 for(int i = 0 ; i < 10000; i++)
     size = list.size();

This one for 9.378 seconds:

 std::list<int> list;
 list.resize(100000);
 int size;
 for(int i = 0 ; i < 10000; i++)
     size = list.size();

In my opinion it would be possible to implement std::list in such way, that size would be stored in a private variable but according to this it is computed again each time I call size. Can anyone explain why?

Answer 1

There is a conflict between constant time size() and constant time list.splice. The committee chose to favour splice.

When you splice nodes between two lists, you would have to count the nodes moved to update the sizes of the two lists. That takes away a lot of the advantage of splicing nodes by just changing a few internal pointers.

---

As noted in the comments, C++11 has changed this by giving up O(1) for some rare(?) uses of splice:

void splice(const_iterator position, list& x, const_iterator first, const_iterator last);
void splice(const_iterator position, list&& x, const_iterator first, const_iterator last);

Complexity: Constant time if &x == this; otherwise, linear time.

Answer 2

In ISO/IEC 14882:2011, §C.2.12, Clause 23: "containers library":

Change: Complexity of size() member functions now constant

Rationale: Lack of specification of complexity of size() resulted in divergent implementations with inconsistent performance characteristics.

Effect on original feature: Some container implementations that conform to C++ 2003 may not conform to the specified size() requirements in this International Standard. Adjusting containers such as std::list to the stricter requirements may require incompatible changes.

---

For the comments:

In 23.3.5.5 - "list operations", again in ISO/IEC 14882:2011:

list provides three splice operations that destructively move elements from one list to another. The behavior of splice operations is undefined if get_allocator() != x.get_allocator().

void splice(const_iterator position, list& x);
void splice(const_iterator position, list&& x);
Requires: &x != this.
Effects: Inserts the contents of x before position and x becomes empty. Pointers and references to the moved elements of x now refer to those same elements but as members of *this. Iterators referringto the moved elements will continue to refer to their elements, but they now behave as iterators into *this, not into x.
Complexity: Constant time.

void splice(const_iterator position, list& x, const_iterator i);
void splice(const_iterator position, list&& x, const_iterator i);
Effects: Inserts an element pointed to by i from list x before position and removes the element from x. The result is unchanged if position == i or position == ++i. Pointers and references to *i continue to refer to this same element but as a member of *this. Iterators to *i (including i itself) continue to refer to the same element, but now behave as iterators into *this, not into x.
Requires: i is a valid dereferenceable iterator of x.
Complexity: Constant time.

void splice(const_iterator position, list& x, const_iterator first, const_iterator last);
void splice(const_iterator position, list&& x, const_iterator first, const_iterator last);
Effects: Inserts elements in the range [first,last) before position and removes the elements from x. Requires: [first, last) is a valid range in x. The result is undefined if position is an iterator in the range [first,last). Pointers and references to the moved elements of x now refer to those same elements but as members of *this. Iterators referring to the moved elements will continue to refer to their elements, but they now behave as iterators into *this, not into x.
Complexity: Constant time if &x == this; otherwise, linear time.