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

Subject: Re: [boost] [Review:Algorithms] all.hpp vs std::count
From: Simonson, Lucanus J (lucanus.j.simonson_at_[hidden])
Date: 2011-10-05 14:13:40

>> C++11 requires list::size() to be O(1), unless I'm misreading it.
>> 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."

I depend on the constant time splice in Polygon to achieve optimal runtime complexity of my polygon formation algorithm.  If not for that I would not have used a std::list.  Now I will be forced to implement my own linked list that has stable runtime complexity for splice so that performance doesn't degrade as people start using the new standard.  Constant time splice was just about the only reason that linked list was ever the right container to use for performance reasons.  I wish they had exposed it as an optional template parameter and made the default match the C++03 behavior.

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

Gnu did.

Regards,
Luke