Subject: Re: [boost] [Containers] How about a list with O(1) splice?
From: Ion Gaztañaga (igaztanaga_at_[hidden])
Date: 2011-10-05 15:42:40
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...
> [OT: does anyone know of a list of "C++1x nasties" like this? It's easy
> to find lists of new features, but harder to find lists of misfeatures...]
> Regards, Phil.
In Boost.Container you can avoid this problem if you know the distance
between the arguments of a range splice:
void splice(const_iterator p, ThisType &x, const_iterator first,
const_iterator last, size_type n)
This splice is constant-time and I've found many times you already know
the the distance between first and last.
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk