Boost logo

Boost :

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

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

*An hybrid approach*

In a "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 list run by bdawes at, gregod at, cpdaniel at, john at