Subject: Re: [boost] [Containers] How about a list with O(1) splice?
From: Ion Gaztañaga (igaztanaga_at_[hidden])
Date: 2011-10-05 15:43:28
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 188.8.131.52
>> [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
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk