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 23.3.5.5
>> [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.