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

Subject: Re: [boost] [Containers] How about a list with O(1) splice?
From: Vicente J. Botet Escriba (vicente.botet_at_[hidden])
Date: 2011-10-05 16:19:57

Le 05/10/11 21:42, Ion Gaztañaga a écrit :
> 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.
>
>
Hi,

long time ago I implemented a library Boost.ConstantTimeSize. Here 
follows an extract of the motivation.

*An hybrid approach*

In a http://www.thescripts.com/forum/thread720757.html "A solution for a 
fast std::list::size() *and* a fast std::list::splice()" - Juha Nieminen 
present an hybrid solution. " ... I was thinking: What if size() was an 
O(n) operation only *after* a splice() operation has been performed (and 
only the first time size() is called after that), but O(1) otherwise?

In other words, keep a size variable in the list class and update it as 
necessary, and additionally keep a flag which tells if this size 
variable is valid. As long as the flag tells that it's valid, 
list::size() can return the value of the variable. Only if the flag says 
it's invalid, then the O(n) counting will be performed, updating the 
variable, after which the flag can be set to valid.

A splice() operation would set the flag to invalid in both lists.

This way splice() will always be O(1), and size() will be O(n) only once 
after a splice(), but O(1) otherwise. You will get speed benefits in all 
cases except if you alternatively call splice() and size() repeatedly 
(in which case you just get the same behavior as in most current list 
implementations, so it's not like the result would be worse). "

This discusion will continue forever if we don't want a take in account 
all the requirements. There is not a best solution, there are bests 
solution each one on a different context. The question is, do we require 
only one solution that can not satisfy every body or should allow the 
user to ask for the better respect to its context.

I think that it is better to have the freedom to choose the 
implementation more adapted to each context.

  * linear_time: size has linear time complexity -> splice shall be
    implemented in constant time in the worst case
  * constant_time: size in constant time in the worst case -> splice has
    linear time complexity
  * quasy_constant_time: size in constant time in most of the cases ->
    splice can have constant time in most of the cases

Ion, does Boost.Containers provides these possibilities. If not, do you 
think it is worth including something like the quasy-constant-time  in 
Boost.Containers?

Best,
Vicente