[intrusive] constant/non-constant time size lists
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
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
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
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) ;
Kevin Sopp wrote:
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:
Ok. Thanks. I could add new static splice functions that do that and that only compile when appropriate conditions (non-constant-time size, etc...) are activated. Regards, Ion
participants (3)
-
David Abrahams -
Ion Gaztañaga -
Kevin Sopp