Эти алгоритмы являются статичными членами класса<circular_slist_algorithms>:

template<class NodeTraits>
struct circular_slist_algorithms;

Пустой список формируется узлом, указатель которого на следующий узел указывает на себя.<circular_slist_algorithms>сконфигурирован с классом NodeTraits, который инкапсулирует информацию о узле, которым нужно манипулировать. NodeTraits должен поддерживать следующий интерфейс:

Типдефы:

Статические функции:

Как только у нас есть конфигурация признаков узла, мы можем использоватьНавязчивыеалгоритмы с нашими узлами:

#include <boost/intrusive/circular_slist_algorithms.hpp>
#include <cassert>
struct my_node
{
   my_node *next_;
   //other members...
};
//Define our own 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
   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"
   algo::link_after(&one, &three);
   assert(algo::count(&one) == 3);
   //Now unlink the node after one
   algo::unlink_after(&one);
   assert(algo::count(&one) == 2);
   //Now unlink two
   algo::unlink(&two);
   assert(algo::count(&one) == 1);
   return 0;
}

Полный список функций см.<circular_slist_algorithms reference>.

Эти алгоритмы являются статическими членами класса<circular_list_algorithms>:

template<class NodeTraits>
struct circular_list_algorithms;

Пустой список формируется узлом, указатель которого на следующий узел указывает на себя.<circular_list_algorithms>сконфигурирован с классом NodeTraits, который инкапсулирует информацию о узле, которым нужно манипулировать. NodeTraits должен поддерживать следующий интерфейс:

Типдефы:

Статические функции:

Как только у нас есть конфигурация признаков узла, мы можем использоватьНавязчивыеалгоритмы с нашими узлами:

#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;
}

Полный список функций см.<circular_list_algorithms reference>.

Эти алгоритмы являются статическими членами класса<rbtree_algorithms>:

template<class NodeTraits>
struct rbtree_algorithms;

Пустое дерево образуется узлом, указатель которого на родительский узел нулевой, указатели левого и правого узлов указывают на себя, и чей цвет красный.<rbtree_algorithms>сконфигурирован с классом NodeTraits, который инкапсулирует информацию о узле, которым нужно манипулировать. NodeTraits должен поддерживать следующий интерфейс:

Типдефы:

Статические функции:

Как только у нас есть конфигурация признаков узла, мы можем использоватьНавязчивыеалгоритмы с нашими узлами:

#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()(const my_node *a, const 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;
}

Полный список функций см.<rbtree_algorithms reference>.

Эти алгоритмы являются статическими членами класса<splaytree_algorithms>:

template<class NodeTraits>
struct splaytree_algorithms;

Пустое дерево образуется узлом, указатель которого на родительский узел нулевой, а указатели левого и правого узлов указывают на себя.<splaytree_algorithms>сконфигурирован с классом NodeTraits, который инкапсулирует информацию о узле, которым нужно манипулировать. NodeTraits должен поддерживать следующий интерфейс:

Типдефы:

Статические функции:

Как только у нас есть конфигурация признаков узла, мы можем использоватьНавязчивыеалгоритмы с нашими узлами:

#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()(const my_node *a, const 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;
}

Полный список функций см.<splaytree_algorithms reference>.

<avltree_algorithms>имеют тот же интерфейс, что и<rbtree_algorithms>.

template<class NodeTraits>
struct avltree_algorithms;

<avltree_algorithms>сконфигурирован с классом NodeTraits, который инкапсулирует информацию о узле, которым нужно манипулировать. NodeTraits должен поддерживать следующий интерфейс:

Типдефы:

Статические функции:

Как только у нас есть конфигурация признаков узла, мы можем использоватьНавязчивыеалгоритмы с нашими узлами:

#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()(const my_node *a, const 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;
}

Полный список функций см.<avltree_algorithms reference>.

<treap_algorithms>имеют тот же интерфейс, что и<rbtree_algorithms>.

template<class NodeTraits>
struct treap_algorithms;

<treap_algorithms>сконфигурирован с классом NodeTraits, который инкапсулирует информацию о узле, которым нужно манипулировать. NodeTraits должен поддерживать следующий интерфейс:

Типдефы:

Статические функции:

Как только у нас есть конфигурация признаков узла, мы можем использоватьНавязчивыеалгоритмы с нашими узлами:

#include <boost/intrusive/treap_algorithms.hpp>
#include <cassert>
struct my_node
{
   my_node(int i = 0, unsigned int priority = 0)
      :  prio_(priority), int_(i)
   {}
   my_node *parent_, *left_, *right_;
   int prio_;
   //other members
   int      int_;
};
//Define our own treap_node_traits
struct my_treap_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()(const my_node *a, const my_node *b) {  return a->int_ < b->int_;  }  };
struct node_ptr_priority
{  bool operator()(const my_node *a, const my_node *b) {  return a->prio_ < b->prio_;}  };
int main()
{
   typedef boost::intrusive::treap_algorithms<my_treap_node_traits> algo;
   my_node header, two(2, 5), three(3, 1);
   //Create an empty treap 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(), node_ptr_priority());
   //Now insert node "three" in the tree using the sorting functor
   algo::insert_equal_lower_bound(&header, &three, node_ptr_compare(), node_ptr_priority());
   //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, node_ptr_priority());
   //Erase a node using also the header (faster)
   algo::erase(&header, &three, node_ptr_priority());
   return 0;
}

Полный список функций см.<treap_algorithms reference>.