[Dave Abrahams]

Furthermore, the size() operation on std::list is not (necessarily) O(1).

FDIS 23.2.1 [container.requirements.general] requires a.size() to have constant complexity. 23.3.5 [list] doesn't specify any exceptions to this. 23.3.4.1 [forwardlist.overview]/2 does: "A forward_list satisfies all of the requirements of a container (Table 96), except that the size() member function is not provided." This was changed from C++03, which specified that size() "should have constant complexity". STL

[Dave Abrahams]

Furthermore, the size() operation on std::list is not (necessarily) O(1).

[STL]

FDIS 23.2.1 [container.requirements.general] requires a.size() to have constant complexity. 23.3.5 [list] doesn't specify any exceptions to this. 23.3.4.1 [forwardlist.overview]/2 does: "A forward_list satisfies all of the requirements of a container (Table 96), except that the size() member function is not provided." This was changed from C++03, which specified that size() "should have constant complexity".

[Marshall Clow]

That's fine - if you are talking about an entire container. However, for an arbitrary pair of iterators, it is not true.

Of course. list iterators are still bidirectional. (As a Standard Library maintainer, I am well aware of all_of/any_of/none_of()'s reasons for existing. I simply pounce on claims about the Standard like cats on yarn.) STL

[Dave Abrahams]

Furthermore, the size() operation on std::list is not (necessarily) O(1).

[STL]

I simply pounce on claims about the Standard like cats on yarn.

[Dave Abrahams]

I read everything you wrote but still find nothing much pounceable in what I wrote.

C++11 requires list::size() to be O(1), unless I'm misreading it. You've patiently corrected my confusion before, but in this case I think the requirement is clearly stated. :-> It's not a big deal - I just wanted to point it out. STL

[STL]

C++11 requires list::size() to be O(1), unless I'm misreading it.

[Dave Abrahams]

Even if that's so, Marshall's library is probably operating on C++03 lists most of the time.

This is just an aside - it doesn't have anything to do with the proposed Algorithms library.

And how does the standard propose that we implement O(1) splice in this case?

Two-list partial-splice is now linear time. FDIS 23.3.5.5 [list.ops]/14: "Complexity: Constant time if &x == this; otherwise, linear time."

Don't forget in the real world most of us have to work with the old standard too ;-)

Of course, although I'm not sure how many implementations actually had O(N) list::size(). STL

[STL]

Two-list partial-splice is now linear time. FDIS 23.3.5.5 [list.ops]/14: "Complexity: Constant time if &x == this; otherwise, linear time."

[Lucanus J. Simonson]

I depend on the constant time splice in Polygon to achieve optimal runtime complexity of my polygon formation algorithm.

C++03 didn't guarantee constant time for splice here. C++03 23.2.2.4 [lib.list.ops]/14: "Complexity: Constant time if &x == this; otherwise, linear time." Here's how the weird world of Standardese works. It's physically impossible for both size() and two-list partial-splice to be O(1). C++03 said that size() "should" be O(1), permitting both O(1) size() and O(1) splice implementations. C++11 requires size() to be O(1), banning O(1) splice implementations. (The splices other than two-list partial-splice are always O(1), that's easy to achieve.) I can confirm that VC's list::size() has been O(1) since VC8 (I believe since forever, but I'm absolutely certain about VC8+).

Constant time splice was just about the only reason that linked list was ever the right container to use for performance reasons.

Theoretically, there are other performance reasons. std::list (and std::forward_list) guarantee true O(1) insertion in wall-clock terms. std::vector::push_back() is amortized O(1), and std::deque ("the oddball") is true O(1) in element terms but amortized O(1) in wall-clock terms due to "map" reallocation (the Standardese is extremely subtle here). In practice I have never seen vector's amortized O(1) matter (vector is overwhelmingly the best container to use by default), but it is a theoretical concern. Other reasons to use std::list include the fact that it's capable of insertion without invalidating iterators/pointers/references.

I wish they had exposed it as an optional template parameter and made the default match the C++03 behavior.

Unfortunately, template parameters can't be added to containers - they would break partial/explicit specializations. (Otherwise, the first candidate would be deque's block size.) STL