Boost logo

Boost :

Subject: Re: [boost] [Containers] How about a list with O(1) splice?
From: Ion Gaztañaga (igaztanaga_at_[hidden])
Date: 2011-10-06 12:22:55

El 06/10/2011 12:42, Phil Endecott escribió:
> Ion Gazta?aga wrote:
> 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?)

Trunk container::list
( contains
this code:

//! <b>Requires</b>: p must point to an element contained
//! by this list. first and last must point to elements contained in
list x.
//! n == std::distance(first, last)
//! <b>Effects</b>: Transfers the range pointed by first and last from
list x to this list,
//! before the the element pointed by p. No destructors or copy
constructors are called.
//! <b>Throws</b>: std::runtime_error if this' allocator and x's allocator
//! are not equal.
//! <b>Complexity</b>: Constant.
//! <b>Note</b>: Iterators of values obtained from list x now point to
elements of this
//! list. Iterators of this list and all the references are not
void splice(const_iterator p, ThisType &x, const_iterator first,
const_iterator last, size_type n);

This was inspired in Howard Hinnant's "on list size" paper:

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

Yes, but you need a mutable member or non-const size() function and that
might conflict with multithreading read-only (usually const) accesses,
say in shared memory.

My choice would be to write a new class without any size() member. It is
not a top priority addition to Boost.Container, but patches are welcome ;-)


Boost list run by bdawes at, gregod at, cpdaniel at, john at