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 splaying (rebalancing): 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 thread-safe). 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 functions? Regards, Ion