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

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?

You don't need list::size, it is not a random-access container. The only way to count the number of elements is to iterate the whole list. Private variable would increase the memory overhead, which is still an issue - if not for you personally, then for many other people. — Viktor Latypov, Oct 31 '12 at 11:47
Did you actually isolate the list.size() loop in your measurement? Or is the line list.resize(...) also included in it, as a strict reading of your question suggests? — Daniel Daranas, Oct 31 '12 at 11:49
Sorry if I didn't make it clear. Only list.size() is inside the loop. — Pavel Madaj, Oct 31 '12 at 11:53
What are you measuring exactly? The entire program, or the loop? A good compiler would remove the 'loop' part of your code since it's just doing the same operation over and over. — PhonicUK, Oct 31 '12 at 12:02
I am measuring the entire program but creating the list and resizing it are really fast operations (when I removed the loop running time of the second program was 0.019 seconds). I am using g++ and I didn't use optimization options (even when I tried using -O2 it didn't remove the loop). — Pavel Madaj, Oct 31 '12 at 12:10
@ViktorLatypov Let me see if I understand you correctly... you are asserting that people who would take exception at an additional 4 (or 8 or, hell, even 16 *bytes*) per std::list would actually use std::list to begin with? Are you serious? I mean *really*? — Nik Bougalis, Oct 31 '12 at 16:25

Bo Persson · Accepted Answer · 2012-10-31T12:05:54.727

16

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.

edited Oct 31 '12 at 12:05

answered Oct 31 '12 at 11:47

Bo Persson

90,663
31
146
203

7

commitee actually said that it's up to implementation. It's GNU that chose to implement it as O(n). In MS STL it's O(1). In C++11 it guaranteed to be O(1) – Oct 31 '12 at 11:53
Size *can* be cached, but that is not very useful is you don't know *when* that happens. Otherwise you get "sometimes O(1), sometimes O(n)". Not very helpful. – Bo Persson Oct 31 '12 at 11:54
1

What aleguna says. C++03 doesn't choose (it says that `size()` "should" be `O(1)` but not "must"). C++11 chooses to favour `size()`, and this brings `list` in line with all other standard containers, which have obvious ways to implement O(1) `size()`. In both C++03 and C++11, `splice` is only required to have constant complexity in the cases where sizes (if cached) could be updated without counting nodes. – Steve Jessop Oct 31 '12 at 12:04
Instead of mandating a predictable behaviour the committee left everyone with the worst of both worlds. Of course they should of specifed that size is O(1). I'm glad to learn that the C++11 committee has seen sense. – john Oct 31 '12 at 12:52
@john: the problem is that O(1) splicing of lists *or parts of lists* is well known from everyone's data structures lectures, and was present in SGI's STL. But I agree that it wasn't good for the standard Container requirements, for there to be one (and only one) standard container that can't track its size efficiently. Now that the standard rejects the original STL `list` as non-conforming, it's easy to see that it should have done so sooner rather than later :-) – Steve Jessop Oct 31 '12 at 13:49
3

@john: well, I disagree, I'd rather have `list` demoted from being a `container` and have O(N) size and O(1) splice. If you do not use `splice`, there is little point using a `list` in the first place. – Matthieu M. Oct 31 '12 at 14:42
@MatthieuM: if there were a lot of template functions that took containers generically, then we could have container categories similar to the way we have iterator categories. Even then I suppose it's dubious whether it's worth it to define separate "container" and "quicklycountablecontainer" concepts just for the sake of `list` being a container. Whereas it is reasonably often worth distinguishing between iterators with O(1) `std::distance` and those without. – Steve Jessop Oct 31 '12 at 16:09
@SteveJessop: My point is, it would be simpler to just drop the `size` member of list altogether => you'd get a compiler error. And no loss of generality either, `std::distance(list.begin(), list.end())` would provide the size in O(N). – Matthieu M. Oct 31 '12 at 16:13
@MatthieuM: I guess it depends whether you think "container" is generally a useful concept (for linked lists). If it is, then you'd want to maintain your quick-splice `list` satisfying some slightly relaxed set of requirements. If "container" isn't all that useful to start with, then there's no use "list" trying to look like one, in which case by all means drop `size()`. Or of course do both, and define a concept "almostcontainer", which is "container" minus `size()`, so every container is an almostcontainer and so is `list` :-) – Steve Jessop Oct 31 '12 at 16:17
@SteveJessop: the problem with lists is that they are the first data structure taught in CS and the O(1) for many operations make people think they are fast and should be used by default whereas in fact they are one of the last resort containers. – Matthieu M. Oct 31 '12 at 16:43
@MatthieuM. that is *a* problem, but not one that I'd expect the standard committee to suffer from. At least, not directly, it might be that they've decided that `std::list` should support that bad decision by being a container. But I suspect they have more sophisticated reasons, which haven't yet collapsed in the face of linked lists being mostly rubbish... – Steve Jessop Oct 31 '12 at 17:57
@SteveJessop: They are not mostly rubbish. They are the only sequence type with node-based representation, which guarantees that an element address is immutable once inserted (something that neither `vector` nor `deque` guarantees). They support very specific operations (such as `splice`) due their unique representation. However, by requiring `size` to be constant the committee chose to save newbies and cut off the usefulness of linked lists a bit. That's not a decision I expected in the C++ language. – Matthieu M. Oct 31 '12 at 18:32
@MatthieuM: Sure, I know how non-SGI-like implementations including C++11 change what they're good for. By "mostly rubbish" I just meant "typically not the right container". – Steve Jessop Nov 01 '12 at 08:50

Kiril Kirov · Answer 2 · 2012-10-31T12:16:26.137

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.

Does that mean that splice is now O(N) or did they find a way to avoid that? — jcoder, Oct 31 '12 at 11:59
@J99: In C++11, the version of splice that takes 4 arguments is now O(N), except in the case where the source and destination lists are the same. The other two forms, and moving elements within the same list (which is the other case for the 4 argument version) are all O(1). — Dave S, Oct 31 '12 at 12:07

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

2 Answers2