Boost logo

Boost :

Subject: Re: [boost] [Review:Algorithms] all.hpp vs std::count
From: Stephan T. Lavavej (stl_at_[hidden])
Date: 2011-10-04 23:09:29


[STL]
> C++11 requires list::size() to be O(1), unless I'm misreading it.

[Dave Abrahams]
> Even if that's so, Marshall's library is probably operating on C++03
> lists most of the time.

This is just an aside - it doesn't have anything to do with the proposed Algorithms library.

> 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."

> Don't forget in the real world most of us have to work with the old standard too ;-)

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

STL


Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk