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

Subject: Re: [boost] [intrusive] constant/non-constant time size lists
From: Ion Gaztañaga (igaztanaga_at_[hidden])
Date: 2008-11-25 12:36:32

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?

Regards,

Ion