Re: [boost] [Containers] How about a list with O(1) splice?

Subject: Re: [boost] [Containers] How about a list with O(1) splice?
From: Phil Endecott (spam_from_boost_dev_at_[hidden])
Date: 2011-10-06 06:42:00

Ion Gazta?aga 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 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...
>
> 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.

Well that's another interesting possibility.  But to be clear, the 
current boost::containter::list has O(1) size and O(N) splice.  (In 
fact, the docs don't even mention constant splice when splicing to 
itself - is that a doc issue?)

Fundamentally, if you have a list that doesn't store its own size you 
can have O(N) size and O(1) splice.  Given such an implementation it's 
straightforward to add a wrapper that tracks the size, changing the 
complexities to O(1) size and O(N) splice.  In contrast, if you start 
with an implementation that stores the size it is impossible to write a 
wrapper that will give you back O(1) splice.  This is why I believe the 
default implementation should have been the O(N) size one.

As Vicente mentions, it is also possible to write a wrapper that keeps 
a flag and gives you either O(1) size OR O(1) splice but not both at 
runtime.  Personally I don't much like that idea, but it also requires 
an underlying implementation that has O(N) size and O(1) splice.

Or, as Ion suggests, it could not have size() at all - that would work.

Ion, is there any chance of adding something like this to Boost.Container?

Regards,  Phil.