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

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

> 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?

I am not sure if we're on the same page here, but given a
list::iterator without a list object I need to be able to splice nodes
before it, unlink and link before/after, basically the same
functionality of circular_list_algorithms, only that it is accessible
from the list class. Or equivalently there exists a documented way of
using circular_list_algorithms with such an iterator.

I am specifically thinking of this functionality as static member functions:

  void splice(const_iterator, const_iterator) ;
  void splice(const_iterator, const_iterator, const_iterator) ;

  iterator erase(const_iterator) ;
  iterator erase(const_iterator, const_iterator) ;
  template<typename Disposer>
    iterator erase_and_dispose(const_iterator, Disposer) ;
  template<typename Disposer>
    iterator erase_and_dispose(const_iterator, const_iterator, Disposer) ;

  iterator insert(const_iterator, reference) ;
  template<typename Iterator> void insert(const_iterator, Iterator, Iterator) ;