Subject: Re: [boost] [Review:Algorithms] all.hpp vs std::count
From: Stephan T. Lavavej (stl_at_[hidden])
Date: 2011-10-05 15:32:00
> Two-list partial-splice is now linear time. FDIS 18.104.22.168 [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 22.214.171.124 [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.)
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk