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 188.8.131.52
>>> [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?
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk