如何为boost::intrusive::rbtree实现stateful_value_traits？

我参考了Boost.Intrusive的doc_stateful_value_traits示例（代码如下），想要实现一个使用stateful_value_traits的自定义红黑树，但尝试后失败了——原因是rbtree_algorithms.hpp中用到的node_traits要求必须有NodeTraits::get_parent这类静态成员函数。请问该如何正确实现？

/////////////////////////////////////////////////////////////////////////////
//
// (C) Copyright Ion Gaztanaga  2007-2013
//
// Distributed under the Boost Software License, Version 1.0.
//    (See accompanying file LICENSE_1_0.txt or copy at
//          http://www.boost.org/LICENSE_1_0.txt)
//
// See http://www.boost.org/libs/intrusive for documentation.
//
/////////////////////////////////////////////////////////////////////////////
//[doc_stateful_value_traits
#include <boost/intrusive/list.hpp>

using namespace boost::intrusive;

//This type is not modifiable so we can't store hooks or custom nodes
typedef int identifier_t;

//This value traits will associate elements from an array of identifiers with
//elements of an array of nodes. The element i of the value array will use the
//node i of the node array:
struct stateful_value_traits
{
   typedef list_node_traits<void*>           node_traits;
   typedef node_traits::node                 node;
   typedef node *                            node_ptr;
   typedef const node *                      const_node_ptr;
   typedef identifier_t                      value_type;
   typedef identifier_t *                    pointer;
   typedef const identifier_t *              const_pointer;
   static const link_mode_type link_mode =   normal_link;

   stateful_value_traits(pointer ids, node_ptr node_array)
      :  ids_(ids),  nodes_(node_array)
   {}

   ///Note: non static functions!
   node_ptr to_node_ptr (value_type &value) const
      {  return this->nodes_ + (&value - this->ids_); }
   const_node_ptr to_node_ptr (const value_type &value) const
      {  return this->nodes_ + (&value - this->ids_); }
   pointer to_value_ptr(node_ptr n) const
      {  return this->ids_ + (n - this->nodes_); }
   const_pointer to_value_ptr(const_node_ptr n) const
      {  return this->ids_ + (n - this->nodes_); }

   private:
   pointer  ids_;
   node_ptr nodes_;
};

int main()
{
   const int NumElements = 100;

   //This is an array of ids that we want to "store"
   identifier_t                  ids   [NumElements];

   //This is an array of nodes that is necessary to form the linked list
   list_node_traits<void*>::node nodes [NumElements];

   //Initialize id objects, each one with a different number
   for(int i = 0; i != NumElements; ++i)   ids[i] = i;

   //Define a list that will "link" identifiers using external nodes
   typedef list<identifier_t, value_traits<stateful_value_traits> > List;

   //This list will store ids without modifying identifier_t instances
   //Stateful value traits must be explicitly passed in the constructor.
   List  my_list (stateful_value_traits (ids, nodes));

   //Insert ids in reverse order in the list
   for(identifier_t * it(&ids[0]), *itend(&ids[NumElements]); it != itend; ++it)
      my_list.push_front(*it);

   //Now test lists
   List::const_iterator   list_it (my_list.cbegin());
   identifier_t *it_val(&ids[NumElements]), *it_rbeg_val(&ids[0]);

   //Test the objects inserted in the base hook list
   for(; it_val != it_rbeg_val; --it_val, ++list_it)
      if(&*list_it  != &it_val[-1])   return 1;

   return 0;
}
//]

核心问题是误用了链表的节点特质list_node_traits，红黑树需要专门的rbtree_node_traits——它包含红黑树节点所需的父指针、颜色标记、左右子节点指针，以及对应的静态访问函数（比如get_parent、set_parent等），完全适配rbtree_algorithms的接口要求。

具体修改步骤：

1. 替换头文件：将<boost/intrusive/list.hpp>改为<boost/intrusive/rbtree.hpp>。
2. 替换节点特质类型：把list_node_traits<void*>改为rbtree_node_traits<void*>。
3. 调整节点数组类型：对应红黑树节点类型rbtree_node_traits<void*>::node。
4. 指定比较器：红黑树是有序容器，必须提供排序规则。

以下是完整可运行代码：

#include <boost/intrusive/rbtree.hpp>

using namespace boost::intrusive;

// 不可修改的目标类型，无法嵌入钩子
typedef int identifier_t;

// 自定义有状态值特质：关联标识符数组与红黑树节点数组
struct stateful_rbtree_value_traits
{
    // 替换为红黑树节点特质
    typedef rbtree_node_traits<void*>           node_traits;
    typedef node_traits::node                   node;
    typedef node*                               node_ptr;
    typedef const node*                         const_node_ptr;
    typedef identifier_t                        value_type;
    typedef identifier_t*                       pointer;
    typedef const identifier_t*                 const_pointer;
    static const link_mode_type link_mode =     normal_link;

    stateful_rbtree_value_traits(pointer ids, node_ptr node_array)
        : ids_(ids), nodes_(node_array)
    {}

    // 非静态的节点/值转换函数
    node_ptr to_node_ptr(value_type& value) const
    {
        return this->nodes_ + (&value - this->ids_);
    }

    const_node_ptr to_node_ptr(const value_type& value) const
    {
        return this->nodes_ + (&value - this->ids_);
    }

    pointer to_value_ptr(node_ptr n) const
    {
        return this->ids_ + (n - this->nodes_);
    }

    const_pointer to_value_ptr(const_node_ptr n) const
    {
        return this->ids_ + (n - this->nodes_);
    }

private:
    pointer  ids_;
    node_ptr nodes_;
};

// 为identifier_t定义比较器
struct IntCompare
{
    bool operator()(const identifier_t& a, const identifier_t& b) const
    {
        return a < b;
    }
};

int main()
{
    const int NumElements = 100;

    // 待关联的标识符数组
    identifier_t ids[NumElements];
    // 红黑树节点数组
    rbtree_node_traits<void*>::node nodes[NumElements];

    // 初始化标识符
    for(int i = 0; i != NumElements; ++i)
        ids[i] = i;

    // 定义红黑树类型：指定值特质和比较器
    typedef rbtree<
        identifier_t,
        value_traits<stateful_rbtree_value_traits>,
        compare<IntCompare>
    > RBTree;

    // 初始化红黑树，传入有状态值特质实例
    RBTree my_tree(stateful_rbtree_value_traits(ids, nodes));

    // 插入所有元素
    for(identifier_t* it = &ids[0], *itend = &ids[NumElements]; it != itend; ++it)
        my_tree.insert_unique(*it);

    // 验证红黑树的有序性
    RBTree::const_iterator tree_it = my_tree.cbegin();
    for(int i = 0; i < NumElements; ++i, ++tree_it)
    {
        if(*tree_it != i)
            return 1;
    }

    return 0;
}

• 红黑树作为有序容器，必须指定compare模板参数提供排序逻辑，这是和链表（无序容器）的核心区别。
• rbtree_node_traits自动提供了get_parent、set_parent等静态成员函数，完全满足rbtree_algorithms的接口要求。
• 保留了原示例中“外部节点关联不可修改值类型”的核心逻辑，仅将链表适配为红黑树。

内容的提问来源于stack exchange，提问作者JaydenFish