Node algorithms with custom NodeTraits

Node algorithms with custom NodeTraits 定制化 NodeTraits 的節點算法

Intrusive singly linked list algorithms 介入式單鏈表算法
Intrusive doubly linked list algorithms 介入式雙鏈表算法
Intrusive red-black tree algorithms 介入式紅黑樹算法
Intrusive splay tree algorithms 介入式 splay 樹算法
Intrusive avl tree algorithms 介入式 avl 樹算法

As explained in the Concepts section, Boost.Intrusive containers are implemented using node algorithms that work on generic nodes.
正如在概念一節中所說的，Boost.Intrusive 容器是使用操作於普通節點上的節點算法來實現的。

Sometimes, the use of intrusive containers is expensive for some environments and the programmer might want to avoid all the template instantiations related to Boost.Intrusive containers. However, the user can still benefit from Boost.Intrusive using the node algorithms, because some of those algorithms, like red-black tree algorithms, are not trivial to write.
有時候，在某些環境下使用介入式容器是昂貴的，程序員也許想避免所有與 Boost.Intrusive 容器相關的模板實例化。不過，用戶還是可以通過使用節點算法從 Boost.Intrusive 獲得好處，因為其中的某些算法還是不容易編寫的，如紅黑樹算法。

All node algorithm classes are templatized by a NodeTraits class. This class encapsulates the needed internal type declarations and operations to make a node compatible with node algorithms. Each type of node algorithms has its own requirements:
所有節點算法類都是由一個 NodeTraits 類來模板化的。這個類封裝了所需的內部類型聲明和操作，以使得某種節點可以兼容於節點算法。每一種節點算法類型都有它自己的要求：

Intrusive singly linked list algorithms 介入式單鏈表算法

These algorithms are static members of the circular_slist_algorithms class:
這些算法是 circular_slist_algorithms 類的靜態成員：

template<class NodeTraits>
struct circular_slist_algorithms;

An empty list is formed by a node whose pointer to the next node points to itself. circular_slist_algorithms is configured with a NodeTraits class, which encapsulates the information about the node to be manipulated. NodeTraits must support the following interface:
空的鏈表由一個節點表示，它的下個節點指針指向它自己。circular_slist_algorithms 用一個 NodeTraits 類來配置，它封裝了被操縱的節點的信息。NodeTraits 必須支持以下接口：

Typedefs:

node: The type of the node that forms the circular list
node: 形成這個循環鏈表的節點的類型
node_ptr: The type of a pointer to a node (usually node*)
node_ptr: 節點指針的類型(通常為 node*)
const_node_ptr: The type of a pointer to a const node (usually const node*)
const_node_ptr: 常量節點指針的類型(通常為 const node*)

Static functions:
靜態函數：

static node_ptr get_next(const_node_ptr n);: Returns a pointer to the next node stored in "n".
static node_ptr get_next(const_node_ptr n);: 返回一個指針，指向保存在 "n" 中的下個節點指針。
static void set_next(node_ptr n, node_ptr next);: Sets the pointer to the next node stored in "n" to "next".
static void set_next(node_ptr n, node_ptr next);: 將 "n" 中的下個節點指針設置為 "next"。

Once we have a node traits configuration we can use Boost.Intrusive algorithms with our nodes:
只要我們有一個節點 traits 配置，我們就可以將 Boost.Intrusive 算法用於我們的節點：

#include <boost/intrusive/circular_slist_algorithms.hpp>
#include <cassert>

struct my_node
{
   my_node *next_;
   //other members... 其它成員...
};

//Define our own slist_node_traits 定義我們自己的 slist_node_traits
struct my_slist_node_traits
{
   typedef my_node                                 node;
   typedef my_node *                               node_ptr;
   typedef const my_node *                         const_node_ptr;
   static node_ptr get_next(const_node_ptr n)      {  return n->next_;  }  
   static void set_next(node_ptr n, node_ptr next) {  n->next_ = next;  }  
};

int main()
{
   typedef boost::intrusive::circular_slist_algorithms<my_slist_node_traits> algo;
   my_node one, two, three;

   //Create an empty singly linked list container:
   //"one" will be the first node of the container
   //創建一個空的單鏈表容器："one"為容器的第一個節點
   algo::init_header(&one);
   assert(algo::count(&one) == 1);

   //Now add a new node 現在加入一個新節點
   algo::link_after(&one, &two);
   assert(algo::count(&one) == 2);

   //Now add a new node after "one" 現在在"one"後面加入一個新節點
   algo::link_after(&one, &three);
   assert(algo::count(&one) == 3);

   //Now unlink the node after one 現在斷開"one"後面的節點
   algo::unlink_after(&one);
   assert(algo::count(&one) == 2);

   //Now unlink two 現在斷開 two
   algo::unlink(&two);
   assert(algo::count(&one) == 1);

   return 0;
}

For a complete list of functions see circular_slist_algorithms reference.
函數的完整列表，請見 circular_slist_algorithms 參考手冊。

Intrusive doubly linked list algorithms 介入式雙鏈表算法

These algorithms are static members of the circular_list_algorithms class:
這些算法是 circular_list_algorithms 類的靜態成員：

template<class NodeTraits>
struct circular_list_algorithms;

An empty list is formed by a node whose pointer to the next node points to itself. circular_list_algorithms is configured with a NodeTraits class, which encapsulates the information about the node to be manipulated. NodeTraits must support the following interface:
空的鏈表由一個節點表示，它的下個節點指針指向它自己。circular_list_algorithms 用一個 NodeTraits 類來配置，它封裝了被操縱的節點的信息。NodeTraits 必須支持以下接口：

Typedefs:

node: The type of the node that forms the circular list
node: 形成這個循環鏈表的節點的類型
node_ptr: The type of a pointer to a node (usually node*)
node_ptr: 節點指針的類型(通常為 node*)
const_node_ptr: The type of a pointer to a const node (usually const node*)
const_node_ptr: 常量節點指針的類型(通常為 const node*)

Static functions:
靜態函數：

static node_ptr get_next(const_node_ptr n);: Returns a pointer to the next node stored in "n".
static node_ptr get_next(const_node_ptr n);: 返回一個指針，指向保存在 "n" 中的下個節點指針。
static void set_next(node_ptr n, node_ptr next);: Sets the pointer to the next node stored in "n" to "next".
static void set_next(node_ptr n, node_ptr next);: 將 "n" 中的下個節點指針設置為 "next"。
static node_ptr get_previous(const_node_ptr n);: Returns a pointer to the previous node stored in "n".
static node_ptr get_previous(const_node_ptr n);: 返回一個指針，指向保存在 "n" 中的前個節點指針。
static void set_previous(node_ptr n, node_ptr prev);: Sets the pointer to the previous node stored in "n" to "prev".
static void set_previous(node_ptr n, node_ptr prev);: 將 "n" 中的前個節點指針設置為 "prev"。

#include <boost/intrusive/circular_list_algorithms.hpp>
#include <cassert>

struct my_node
{
   my_node *next_, *prev_;
   //other members...
};

//Define our own list_node_traits
struct my_list_node_traits
{
   typedef my_node                                    node;
   typedef my_node *                                  node_ptr;
   typedef const my_node *                            const_node_ptr;
   static node_ptr get_next(const_node_ptr n)         {  return n->next_;  }  
   static void set_next(node_ptr n, node_ptr next)    {  n->next_ = next;  }  
   static node *get_previous(const_node_ptr n)        {  return n->prev_;  }  
   static void set_previous(node_ptr n, node_ptr prev){  n->prev_ = prev;  }  
};

int main()
{
   typedef boost::intrusive::circular_list_algorithms<my_list_node_traits> algo;
   my_node one, two, three;

   //Create an empty doubly linked list container:
   //"one" will be the first node of the container
   algo::init_header(&one);
   assert(algo::count(&one) == 1);

   //Now add a new node before "one"
   algo::link_before(&one, &two);
   assert(algo::count(&one) == 2);

   //Now add a new node after "two"
   algo::link_after(&two, &three);
   assert(algo::count(&one) == 3);

   //Now unlink the node after one
   algo::unlink(&three);
   assert(algo::count(&one) == 2);

   //Now unlink two
   algo::unlink(&two);
   assert(algo::count(&one) == 1);

   //Now unlink one
   algo::unlink(&one);
   assert(algo::count(&one) == 1);

   return 0;
}

For a complete list of functions see circular_list_algorithms reference.
函數的完整列表，請見 circular_list_algorithms 參考手冊。

Intrusive red-black tree algorithms 介入式紅黑樹算法

These algorithms are static members of the rbtree_algorithms class:
這些算法是 rbtree_algorithms 類的靜態成員：

template<class NodeTraits>
struct rbtree_algorithms;

An empty tree is formed by a node whose pointer to the parent node is null, the left and right node pointers point to itself, and whose color is red. rbtree_algorithms is configured with a NodeTraits class, which encapsulates the information about the node to be manipulated. NodeTraits must support the following interface:
空的樹由一個節點表示，它的父節點指針為 null，它的左節點和右節點指針指向它自己，且顏色為紅色。rbtree_algorithms 用一個 NodeTraits 類來配置，它封裝了被操縱的節點的信息。NodeTraits 必須支持以下接口：

Typedefs:

node: The type of the node that forms the circular rbtree
node: 形成這個循環紅黑樹的節點的類型
node_ptr: The type of a pointer to a node (usually node*)
node_ptr: 節點指針的類型(通常為 node*)
const_node_ptr: The type of a pointer to a const node (usually const node*)
const_node_ptr: 常量節點指針的類型(通常為 const node*)
color: The type that can store the color of a node
color: 保存節點顏色的類型

Static functions:
靜態函數：

static node_ptr get_parent(const_node_ptr n);: Returns a pointer to the parent node stored in "n".
static node_ptr get_parent(const_node_ptr n);: 返回一個指針，指向保存在 "n" 中的父節點指針。
static void set_parent(node_ptr n, node_ptr p);: Sets the pointer to the parent node stored in "n" to "p".
static void set_parent(node_ptr n, node_ptr p);: 將 "n" 中的父節點指針設置為 "p"。
static node_ptr get_left(const_node_ptr n);: Returns a pointer to the left node stored in "n".
static node_ptr get_left(const_node_ptr n);: 返回一個指針，指向保存在 "n" 中的左節點指針。
static void set_left(node_ptr n, node_ptr l);: Sets the pointer to the left node stored in "n" to "l".
static void set_left(node_ptr n, node_ptr l);: 將 "n" 中的左節點指針設置為 "l"。
static node_ptr get_right(const_node_ptr n);: Returns a pointer to the right node stored in "n".
static node_ptr get_right(const_node_ptr n);: 返回一個指針，指向保存在 "n" 中的右節點指針。
static void set_right(node_ptr n, node_ptr r);: Sets the pointer to the right node stored in "n" to "r".
static void set_right(node_ptr n, node_ptr r);: 將 "n" 中的右節點指針設置為 "r"。
static color get_color(const_node_ptr n);: Returns the color stored in "n".
static color get_color(const_node_ptr n);: 返回保存在 "n" 中的顏色。
static void set_color(node_ptr n, color c);: Sets the color stored in "n" to "c".
static void set_color(node_ptr n, color c);: 將 "n" 中的顏色設置為 "c"。
static color black();: Returns a value representing the black color.
static color black();: 返回表示黑色的值。
static color red();: Returns a value representing the red color.
static color red();: 返回表示紅色的值。

#include <boost/intrusive/rbtree_algorithms.hpp>
#include <cassert>

struct my_node
{
   my_node(int i = 0)
      :  int_(i)
   {}
   my_node *parent_, *left_, *right_;
   int      color_;
   //other members
   int      int_;
};

//Define our own rbtree_node_traits
struct my_rbtree_node_traits
{
   typedef my_node                                    node;
   typedef my_node *                                  node_ptr;
   typedef const my_node *                            const_node_ptr;
   typedef int                                        color;
   static node_ptr get_parent(const_node_ptr n)       {  return n->parent_;   }  
   static void set_parent(node_ptr n, node_ptr parent){  n->parent_ = parent; }  
   static node_ptr get_left(const_node_ptr n)         {  return n->left_;     }  
   static void set_left(node_ptr n, node_ptr left)    {  n->left_ = left;     }  
   static node_ptr get_right(const_node_ptr n)        {  return n->right_;    }  
   static void set_right(node_ptr n, node_ptr right)  {  n->right_ = right;   }  
   static color get_color(const_node_ptr n)           {  return n->color_;    }  
   static void set_color(node_ptr n, color c)         {  n->color_ = c;       }
   static color black()                               {  return color(0);     }
   static color red()                                 {  return color(1);     }
};

struct node_ptr_compare
{
   bool operator()(my_node *a, my_node *b)
   {  return a->int_ < b->int_;  }
};

int main()
{
   typedef boost::intrusive::rbtree_algorithms<my_rbtree_node_traits> algo;
   my_node header, two(2), three(3);

   //Create an empty rbtree container:
   //"header" will be the header node of the tree
   algo::init_header(&header);

   //Now insert node "two" in the tree using the sorting functor
   algo::insert_equal_upper_bound(&header, &two, node_ptr_compare());

   //Now insert node "three" in the tree using the sorting functor
   algo::insert_equal_lower_bound(&header, &three, node_ptr_compare());

   //Now take the first node (the left node of the header)
   my_node *n = header.left_;
   assert(n == &two);

   //Now go to the next node
   n = algo::next_node(n);
   assert(n == &three);      

   //Erase a node just using a pointer to it
   algo::unlink(&two);

   //Erase a node using also the header (faster)
   algo::erase(&header, &three);
   return 0;
}

For a complete list of functions see rbtree_algorithms reference.
函數的完整列表，請見 rbtree_algorithms 參考手冊。

Intrusive splay tree algorithms 介入式 splay 樹算法

These algorithms are static members of the splaytree_algorithms class:
這些算法是 splaytree_algorithms 類的靜態成員：

template<class NodeTraits>
struct splaytree_algorithms;

An empty tree is formed by a node whose pointer to the parent node is null, and whose left and right nodes pointers point to itself. splaytree_algorithms is configured with a NodeTraits class, which encapsulates the information about the node to be manipulated. NodeTraits must support the following interface:
空的樹由一個節點表示，它的父節點指針為 null，它的左節點和右節點指針指向它自己。splaytree_algorithms 用一個 NodeTraits 類來配置，它封裝了被操縱的節點的信息。NodeTraits 必須支持以下接口：

Typedefs:

node: The type of the node that forms the circular splaytree
node: 形成這個循環splay樹的節點的類型
node_ptr: The type of a pointer to a node (usually node*)
node_ptr: 節點指針的類型(通常為 node*)
const_node_ptr: The type of a pointer to a const node (usually const node*)
const_node_ptr: 常量節點指針的類型(通常為 const node*)

Static functions:
靜態函數：

static node_ptr get_parent(const_node_ptr n);: Returns a pointer to the parent node stored in "n".
static node_ptr get_parent(const_node_ptr n);: 返回一個指針，指向保存在 "n" 中的父節點指針。
static void set_parent(node_ptr n, node_ptr p);: Sets the pointer to the parent node stored in "n" to "p".
static void set_parent(node_ptr n, node_ptr p);: 將 "n" 中的父節點指針設置為 "p"。
static node_ptr get_left(const_node_ptr n);: Returns a pointer to the left node stored in "n".
static node_ptr get_left(const_node_ptr n);: 返回一個指針，指向保存在 "n" 中的左節點指針。
static void set_left(node_ptr n, node_ptr l);: Sets the pointer to the left node stored in "n" to "l".
static void set_left(node_ptr n, node_ptr l);: 將 "n" 中的左節點指針設置為 "l"。
static node_ptr get_right(const_node_ptr n);: Returns a pointer to the right node stored in "n".
static node_ptr get_right(const_node_ptr n);: 返回一個指針，指向保存在 "n" 中的右節點指針。
static void set_right(node_ptr n, node_ptr r);: Sets the pointer to the right node stored in "n" to "r".
static void set_right(node_ptr n, node_ptr r);: 將 "n" 中的右節點指針設置為 "r"。

#include <boost/intrusive/splaytree_algorithms.hpp>
#include <cassert>

struct my_node
{
   my_node(int i = 0)
      :  int_(i)
   {}
   my_node *parent_, *left_, *right_;
   //other members
   int      int_;
};

//Define our own splaytree_node_traits
struct my_splaytree_node_traits
{
   typedef my_node                                    node;
   typedef my_node *                                  node_ptr;
   typedef const my_node *                            const_node_ptr;

   static node_ptr get_parent(const_node_ptr n)       {  return n->parent_;   }  
   static void set_parent(node_ptr n, node_ptr parent){  n->parent_ = parent; }  
   static node_ptr get_left(const_node_ptr n)         {  return n->left_;     }  
   static void set_left(node_ptr n, node_ptr left)    {  n->left_ = left;     }  
   static node_ptr get_right(const_node_ptr n)        {  return n->right_;    }  
   static void set_right(node_ptr n, node_ptr right)  {  n->right_ = right;   }  
};

struct node_ptr_compare
{
   bool operator()(my_node *a, my_node *b)
   {  return a->int_ < b->int_;  }
};

int main()
{
   typedef boost::intrusive::splaytree_algorithms<my_splaytree_node_traits> algo;
   my_node header, two(2), three(3);

   //Create an empty splaytree container:
   //"header" will be the header node of the tree
   algo::init_header(&header);

   //Now insert node "two" in the tree using the sorting functor
   algo::insert_equal_upper_bound(&header, &two, node_ptr_compare());

   //Now insert node "three" in the tree using the sorting functor
   algo::insert_equal_lower_bound(&header, &three, node_ptr_compare());

   //Now take the first node (the left node of the header)
   my_node *n = header.left_;
   assert(n == &two);

   //Now go to the next node
   n = algo::next_node(n);
   assert(n == &three);      

   //Erase a node just using a pointer to it
   algo::unlink(&two);

   //Erase a node using also the header (faster)
   algo::erase(&header, &three);
   return 0;
}

For a complete list of functions see splaytree_algorithms reference.
函數的完整列表，請見 splaytree_algorithms 參考手冊。

Intrusive avl tree algorithms 介入式 avl 樹算法

avltree_algorithms have the same interface as rbtree_algorithms.
avltree_algorithms 具有與 rbtree_algorithms 相同的接口。

template<class NodeTraits>
struct avltree_algorithms;

avltree_algorithms is configured with a NodeTraits class, which encapsulates the information about the node to be manipulated. NodeTraits must support the following interface:
avltree_algorithms 用一個 NodeTraits 類來配置，它封裝了被操縱的節點的信息。NodeTraits 必須支持以下接口：

Typedefs:

node: The type of the node that forms the circular avltree
node: 形成這個循環avl樹的節點的類型
node_ptr: The type of a pointer to a node (usually node*)
node_ptr: 節點指針的類型(通常為 node*)
const_node_ptr: The type of a pointer to a const node (usually const node*)
const_node_ptr: 常量節點指針的類型(通常為 const node*)
balance: A type that can represent 3 balance types (usually an integer)
balance: 表示3種平衡類型的類型(通常為整數)

Static functions:
靜態函數：

static node_ptr get_parent(const_node_ptr n);: Returns a pointer to the parent node stored in "n".
static node_ptr get_parent(const_node_ptr n);: 返回一個指針，指向保存在 "n" 中的父節點指針。
static void set_parent(node_ptr n, node_ptr p);: Sets the pointer to the parent node stored in "n" to "p".
static void set_parent(node_ptr n, node_ptr p);: 將 "n" 中的父節點指針設置為 "p"。
static node_ptr get_left(const_node_ptr n);: Returns a pointer to the left node stored in "n".
static node_ptr get_left(const_node_ptr n);: 返回一個指針，指向保存在 "n" 中的左節點指針。
static void set_left(node_ptr n, node_ptr l);: Sets the pointer to the left node stored in "n" to "l".
static void set_left(node_ptr n, node_ptr l);: 將 "n" 中的左節點指針設置為 "l"。
static node_ptr get_right(const_node_ptr n);: Returns a pointer to the right node stored in "n".
static node_ptr get_right(const_node_ptr n);: 返回一個指針，指向保存在 "n" 中的右節點指針。
static void set_right(node_ptr n, node_ptr r);: Sets the pointer to the right node stored in "n" to "r".
static void set_right(node_ptr n, node_ptr r);: 將 "n" 中的右節點指針設置為 "r"。
static balance get_balance(const_node_ptr n);: Returns the balance factor stored in "n".
static balance get_balance(const_node_ptr n);: 返回保存在 "n" 中的平衡因子。
static void set_balance(node_ptr n, balance b);: Sets the balance factor stored in "n" to "b".
static void set_balance(node_ptr n, balance b);: 將 "n" 中的平衡因子設置為 "b"。
static balance negative();: Returns a value representing a negative balance factor.
static balance negative();: 返回表示負平衡因子的值。
static balance zero();: Returns a value representing a zero balance factor.
static balance zero();: 返回表示零平衡因子的值。
static balance positive();: Returns a value representing a positive balance factor.
static balance positive();: 返回表示正平衡因子的值。

#include <boost/intrusive/avltree_algorithms.hpp>
#include <cassert>

struct my_node
{
   my_node(int i = 0)
      :  int_(i)
   {}
   my_node *parent_, *left_, *right_;
   int balance_;
   //other members
   int      int_;
};

//Define our own avltree_node_traits
struct my_avltree_node_traits
{
   typedef my_node                                    node;
   typedef my_node *                                  node_ptr;
   typedef const my_node *                            const_node_ptr;
   typedef int                                        balance;

   static node_ptr get_parent(const_node_ptr n)       {  return n->parent_;   }  
   static void set_parent(node_ptr n, node_ptr parent){  n->parent_ = parent; }  
   static node_ptr get_left(const_node_ptr n)         {  return n->left_;     }  
   static void set_left(node_ptr n, node_ptr left)    {  n->left_ = left;     }  
   static node_ptr get_right(const_node_ptr n)        {  return n->right_;    }  
   static void set_right(node_ptr n, node_ptr right)  {  n->right_ = right;   }  
   static balance get_balance(const_node_ptr n)       {  return n->balance_;  }  
   static void set_balance(node_ptr n, balance b)     {  n->balance_ = b;     }
   static balance negative()                          {  return -1; }
   static balance zero()                              {  return 0;  }
   static balance positive()                          {  return 1;  }
};

struct node_ptr_compare
{
   bool operator()(my_node *a, my_node *b)
   {  return a->int_ < b->int_;  }
};

int main()
{
   typedef boost::intrusive::avltree_algorithms<my_avltree_node_traits> algo;
   my_node header, two(2), three(3);

   //Create an empty avltree container:
   //"header" will be the header node of the tree
   algo::init_header(&header);

   //Now insert node "two" in the tree using the sorting functor
   algo::insert_equal_upper_bound(&header, &two, node_ptr_compare());

   //Now insert node "three" in the tree using the sorting functor
   algo::insert_equal_lower_bound(&header, &three, node_ptr_compare());

   //Now take the first node (the left node of the header)
   my_node *n = header.left_;
   assert(n == &two);

   //Now go to the next node
   n = algo::next_node(n);
   assert(n == &three);      

   //Erase a node just using a pointer to it
   algo::unlink(&two);

   //Erase a node using also the header (faster)
   algo::erase(&header, &three);
   return 0;
}

For a complete list of functions see avltree_algorithms reference.
函數的完整列表，請見 avltree_algorithms 參考手冊。