From: Ion Gaztañaga (igaztanaga_at_[hidden])
Date: 2007-10-18 15:07:24
Hi to all,
Lately I've been trying to implement splay trees for Intrusive.
Excerpt taken from en.wikipedia.org/wiki/Splay_tree:
"A splay tree is a self-balancing binary search tree with the additional
unusual property that recently accessed elements are quick to access
again. It performs basic operations such as insertion, look-up and
removal in O(log(n)) amortized time. For many non-uniform sequences of
operations, splay trees perform better than other search trees, even
when the specific pattern of the sequence is unknown. The splay tree was
invented by Daniel Sleator and Robert Tarjan."
As most of you know, splay trees splay (rebalance) the tree also on
searches, so that the target node is placed as root, yielding to better
search times for frequently searched nodes (cache effect).
The implementation I've taken as model is taken from the article written
by Ralf Mattethat for C++ Users Journal (September 2005) titled
"Implementing Splay Trees in C++" (http://www.ddj.com/architect/184402007).
Following usual STL-like implementations I've used left and right
pointers of the header to point to the leftmost and rightmost node
respectively. Several intrusive rbtree implementation tricks and
optimizations can be easily reused for splay trees so I think we can
have a useful intrusive splay tree.
My main issue is related to constness and thread-safety. I would like to
offer a STL-like interface (that is, the interface actually implemented
for other Intrusive containers like set, multiset and rbtree), but take
in care that the tree will rebalance in each
find/lower_bound/upper_bound operation so those operations couldn't be
const members unless we declare the header as mutable. I plan to add
optional (runtime) rebalancing for each operation (for example, the user
could call find() without rebalancing if he doesn't want to alter the
cache effect, or just needs more predictable search times).
iterator it = splay_tree.find(a);//Splay operation performed
iterator it = splay_tree.find(a, dont_splay);//No splay
Allowing const overloads (casting the constness away internally) with
const_iterator it = const_splay_tree.find(a); //Splaying performed
would break usual de-facto thread-safety guarantees for STL and
Intrusive containers (read-only access from different threads is
So the main question is: what approach do you think would be better?
¿Just splay in const operations and put a thread-safety warning? ¿Make
const versions non-splaying? ¿Don't offer const versions of search
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk