Re: [boost] [Review:Algorithms] all.hpp vs std::count

Subject: Re: [boost] [Review:Algorithms] all.hpp vs std::count
From: Stephan T. Lavavej (stl_at_[hidden])
Date: 2011-10-05 15:32:00

[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