Re: [boost] [intrusive] constant/non-constant time size lists

Subject: Re: [boost] [intrusive] constant/non-constant time size lists
From: David Abrahams (dave_at_[hidden])
Date: 2008-11-25 13:21:19

on Tue Nov 25 2008, Ion Gaztañaga <igaztanaga-AT-gmail.com> wrote:

> Kevin Sopp wrote:
>> Hi Ion,
>>
>> have you thought about instantiating two different interfaces for
>> constant and non-constant time size() lists respectively? Instead of
>> instantiating one interface that has differing complexity guarantees
>> and is restricted by the lowest common denominator of what is possible
>> with constant-time size().
>
> I thought about it but I preferred a single class.
>
>> Non-constant time size() lists would allow to implement higher level
>> functionality as static member functions or as non-member functions,
>> and some functionality like splicing needs no additional list&
>> parameter. If I had such a list I could make my functions work on
>> iterator ranges without the need to pass the list object along. So
>> what I need is access to the nodes so that I can call
>> circular_list_algorithms directly on these.
>
> I can add new "optimized" functions that are only present for non
> constant-time size versions. Some of these optimizations don't depend
> only on the non-constant-time size but also in the node
> type,user-defined value-traits... so I could just activate them when
> such conditions are met. Could you give me any hint of the functions
> you think can be optimized so that I can add them quickly to my to-do
> list?

The best solution for many applications of std::list may be to manage
the size and invalidate it only upon splice() so it will take linear
time the next time it is requested.

FWIW'ly yr's

-- 
Dave Abrahams
BoostPro Computing
http://www.boostpro.com