Boost :

henri.bavestrello_at_[hidden]

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