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

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 
(http://svn.boost.org/svn/boost/trunk/boost/container/list.hpp) 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 
invalidated.
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:

http://home.roadrunner.com/~hinnant/On_list_size.html

> 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 ;-)

Ion