[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