Subject: Re: [boost] [Containers] How about a list with O(1) splice?
From: Dave Abrahams (dave_at_[hidden])
Date: 2011-10-05 16:29:27
on Wed Oct 05 2011, Ion GaztaÃ±aga <igaztanaga-AT-gmail.com> wrote:
> El 05/10/2011 20:28, Phil Endecott escribiÃ³:
>> In another thread, Stephan T. Lavavej wrote:
>>> 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."
>> Is there an opportunity here for Boost.Containers to provide a std::list
>> replacement that keeps the old O(1) splice and O(N) size? I can imagine
>> a lot of demand for this once people discover that their old splicing
>> code is trashed by a std library upgrade...
> IMHO this O(1) splice list should not have size() at all, just like
Exactly. There's room for a list with a cached size that's normally
O(1) except after a splice, but let's find out that someone needs it
before we go there.
-- Dave Abrahams BoostPro Computing http://www.boostpro.com
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk