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
>Two-list partial-splice is now linear time. FDIS 22.214.171.124 [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().
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk