Dear all, this being my a first post/review, I hope that it is not too "stupid" ;-). I have been using this library since last October (actually the latest version of Olaf Krzikalla that wast uploaded by Ion Gaztañaga in the Vault around that time) in our Finite Element code. I mainly used the iset/imultiset containers of that version to somehow emulate an intrusive map: unfortunately as during looking-up phases I had to create a whole dummy ojbect initialized with the key searched for to be able to use the imultiset::find method; I decided to implement an intrusive map (imap) modifying the red-black tree implementation that comes with the library, something like: template<typename Key, typename Access, typename KeyExtractor, typename Compare = std::less<Key>, bool clear_on_dtor = true> class imap : boost::noncopyable { public: // typedef private: // select the type of the tree (red-black or avl) // depending on the type of the tree hook (i.e. rb_node, avl_node) // for instance, a user class UserClass to be used into 2 imap (one using // a rb_tree, the other an avl_tree) is defined as // class UserClass : public imap_node_d<Tag, unlink_dtor, rbtree_node>, public imap_node_d<Tag, unlink_dtor, avltree_node> typedef typename itree_dispatcher<Key, Access, KeyExtractor, Compare, typename Access::itree_node >::value_type tree_type; tree_type m_tree; // the actual tree structure // etc ... }; borrowing the keyExtractor concept from the Boost.MultiIndex library. (being a "baby" in the library/template world, I kind of follow existing boost libraries design). I am happy to see that with this new version of the library, I can directly use the iset container taking advantage of the find(key, comp) method ;-). Also, the iset container instantiation is simpler as the Compare operator actually combines the comparison operator and the key extractor. It may be help full in the example about the iset/imultiset container that the two container uses different type (currently they both use MyClass int_ data member as key), and make use of the iset/imultiset::find(key, comp) method. - What is your evaluation of the design? I am not qualified enough to say much about it, except that it was easy to use: creating a container was easy, even with legacy classes. The use of node and value traits really make customization easy. As for performance oriented code, I like the presence of insert_check and insert_commit methods of the associative intrusive containers. I always feel that similar methods were missing from the STL associative containers. - What is your evaluation of the implementation? It is well above my standard ;-). It is well documented and it was quite easy to navigate through the code. - What is your evaluation of the potential usefulness of the library? I find it useful. I agree that this is a kind of "low-level" library and you have to be aware of what you are doing with it, but it may be worth it in some cases. - Did you try to use the library? With what compiler? Did you have any problems? Yes. I used the library with gcc 4.1 and intel icc 9.1 under linux. I didn't have any problems with the library. - How much effort did you put into your evaluation? A glance? A quick reading? In-depth study? I have been using the previous version of this library for a couple of months now. Even though, this new version have been quite upgraded, it was quite easy to plug it into our code (creating an intrusive map as a wrapper around iset went smoothly). - Are you knowledgeable about the problem domain? I am no expert on containers, but as a user in the HPC community, I well aware of problems like data locality and cache trashing. - Do you think the library should be accepted as a Boost library? Yes. I will definitively use it; and as an other review wrote, I will maintained my own copy, it is not ... I really would like to thank very much the authors for their great work. Best regards, Henri. -- Institute for Computational & Mathematical Engineering Stanford University http://icme.stanford.edu P.S.: when I implemented the tree methods, I also ran into the problem of having a constant time size method and allowing the node to unlink itself from the tree (by calling either node::unlink() or the destructor operator). Looking at the original unlink_and_rebalance() method in the rb_node class of Olaf Krzikalla's implementation: void rbtree_node::unlink_and_rebalance() { rbtree_node* h = this->parent(); if (h != 0) { // this node is linked // go up the tree until the header node while (!is_header (h)) h = h->parent(); this->remove (*h); // h is the header node } } I figured that the node that unlinks itself knows "implicitly" from which tree it actually unlinks itself: rbtree_node::unlink_and_rebalance() starts from the node and goes up the tree until it reaches the tree's header node. So to allow both nodes to unlink themselves with a constant time map/tree size() method, the tree nodes counter can be actually be embeded into the tree's header node which is derived from the rb_node class; and uses a cast in the rbtree_node::unlink_and_rebalance() method. More precisely, something likes that: class rbtree_node { public: void unlink_and_rebalance(); // see below // other needed methods private: //All needed data member: parent pointer, color, etc ... }; class rb_header : public rbtree_node { #ifdef DISABLE_INTRUSIVE_RBTREE_CST_TIME_SIZE public: rb_header() : rbtree_node(0) { } // rbtree_node(0) makes a header node size_t node_count() const { } void incr_node_count(ssize_t n) { } #else public: rb_header() : rbtree_node(0), m_node_count(0) { } size_t node_count() const { return m_node_count; } void incr_node_count(ssize_t n) { m_node_count += n; } private: size_t m_node_count; #endif }; inline void rbtree_node::unlink_and_rebalance() { rbtree_node* h = this->parent(); if (h != 0) { // this node is linked // go up the tree until the header node while (!is_header (h)) h = h->parent(); this->remove (*h); // h is the header node static_cast<rb_header*>(h)->incr_node_count(-1); } } template<typename Key, typename Access, typename KeyExtractor, typename Compare> class iRb_tree { public: // typedef ... private: // private typedef // data member rb_header m_header; // node counter embeded into it if DISABLE_INTRUSIVE_RBTREE_CST_TIME_SIZE is not defined key_compare m_key_compare; key_extractor m_key_extractor; // some methods that use the nodes'count embeded into the header node iterator insert(link_ptr y, const_value_ref val, bool link_left) { link_ptr z(node(val)); tree_node::link_and_balance(z, y, link_left, m_header); m_header.incr_node_count(+1); return iterator(z); } public: size_type size() const { #ifndef DISABLE_INTRUSIVE_RBTREE_CST_TIME_SIZE return m_header.node_count(); #else return std::distance(begin(), end()); #endif } // etc ... }; I am not sure if this applicable with the new intrusive library that uses "generalized pointer"; but if it is, it may allow to have both constant time size method and auto-unlink node in intrusive containers that use an rb tree (or avl tree) as underlaying implementation.