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

Subject: [boost] [intrusive] constant/non-constant time size lists
From: Kevin Sopp (baraclese_at_[hidden])
Date: 2008-11-25 11:42:08

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

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 don't see an easy way to achieve that goal right now. As far as I
can tell I need to use the undocumented list_iterator::pointed_node()
function - which is okay, I'm only hesitant because it is
undocumented. I'm willing to change my code if that interface ever
changes though.

Kevin