Concepts explained . Boost , The Boost C++ Libraries BoostBook Documentation Subset , Chapter 17. Boost.Intrusive

Concepts explained

Этот раздел расширит объяснение ранее представленных основных концепций, прежде чем объяснить варианты настройки.

Алгоритмы узлов: Набор статических функций, реализующих основные операции на группе узлов: инициализация узла, link_mode_type узла на группу узлов, отсоединение узла от другой группы узлов и т.д. Например, круговой по отдельности связанный список представляет собой группу узлов, где каждый узел имеет указатель на следующий узел.Алгоритмы узловТребуется толькоУзелкипараметр шаблона, и они могут работать с любымУзелкикласс, удовлетворяющий требуемому интерфейсу. В качестве примера можно привести класс, реализующий операции по управлению группой узлов, образующих круговой по отдельности связанный список:

template<class NodeTraits>
struct my_slist_algorithms
{
   typedef typename NodeTraits::node_ptr       node_ptr;
   typedef typename NodeTraits::const_node_ptr const_node_ptr;
   //Get the previous node of "this_node"
   static node_ptr get_prev_node(node_ptr this_node)
   {
      node_ptr p = this_node;
      while (this_node != NodeTraits::get_next(p))
         p = NodeTraits::get_next(p);
      return p;
   }
   // number of elements in the group of nodes containing "this_node"
   static std::size_t count(const_node_ptr this_node)
   {
      std::size_t result = 0;
      const_node_ptr p = this_node;
      do{
         p = NodeTraits::get_next(p);
         ++result;
      } while (p != this_node);
      return result;
   }
   // More operations
   // ...
};

Черты узлов: Класс, который инкапсулирует основную информацию и операции на узле внутри группы узлов: тип узла, функцию получения указателя на следующий узел и т.д.Черты узловуказывают информацию о конфигурацииАлгоритмы узловнеобходимы. Каждый типАлгоритма узловожидает интерфейс, который должен реализовывать совместимыеклассы узлов. В качестве примера можно привести определение классаNode Traits, совместимого с ранее представленным<my_slist_algorithms>:

struct my_slist_node_traits
{
   //The type of the node
   struct node
   {
      node *next_;
   };
   typedef node *       node_ptr;
   typedef const node * const_node_ptr;
   //A function to obtain a pointer to the next node
   static node_ptr get_next(const_node_ptr n)
   {  return n->next_;  }
   //A function to set the pointer to the next node
   static void set_next(node_ptr n, node_ptr next)
   {  n->next_ = next;  }
};

Крюк: Класс, который пользователь должен добавить в качестве базового класса или в качестве члена в свой собственный класс, чтобы сделать этот класс вставленным в навязчивый контейнер. Обычно крючок содержит объект узла, который будет использоваться для формирования группы узлов: Например, следующий класс - этоКрюк, который пользователь может добавить в качестве базового класса, чтобы сделать класс пользователя совместимым с контейнером с единичным связанным списком:

class my_slist_base_hook
      //This hook contains a node, that will be used
      //to link the user object in the group of nodes
   : private my_slist_node_traits::node
{
   typedef my_slist_node_traits::node_ptr       node_ptr;
   typedef my_slist_node_traits::const_node_ptr const_node_ptr;
   //Converts the generic node to the hook
   static my_slist_base_hook *to_hook_ptr(node_ptr p)
   {  return static_cast<my_slist_base_hook*>(p); }
   //Returns the generic node stored by this hook
   node_ptr to_node_ptr()
   { return static_cast<node *const>(this); }
   // More operations
   // ...
};
//To make MyClass compatible with an intrusive singly linked list
//derive our class from the hook.
class MyClass
   :  public my_slist_base_hook
{
   void set(int value);
   int get() const;
   private:
   int value_;
};

Назойливый контейнер: Контейнер, который предлагает STL-подобный интерфейс для хранения пользовательских объектов. Интрузивный контейнер может быть шаблонизирован для хранения различных типов значений, которые используют разные крючки. Интрузивный контейнер также более сложный, чем группа узлов: он может хранить количество элементов для получения информации о постоянном размере, он может предлагать отладочные средства и т. Д. Например, контейнер<slist>(интрузивный по отдельности связанный список) должен иметь возможность удерживать<MyClass>объекты, которые, возможно, решили хранить крючок в качестве базового класса или в качестве члена. Внутреннее использование контейнераАлгоритмы узловдля реализации своих операций, а интрузивный контейнер настраивается с использованием параметра шаблона под названиемВалютные знакиValueTraitsбудет содержать информацию для преобразования классов пользователей в узлы, совместимые сАлгоритмы узлов. Например, это возможная реализация<slist>:

template<class ValueTraits, ...>
class slist
{
   public:
   typedef typename ValueTraits::value_type value_type;
   //More typedefs and functions
   // ...
   //Insert the value as the first element of the list
   void push_front (reference value)
   {
      node_ptr to_insert(ValueTraits::to_node_ptr(value));
      circular_list_algorithms::link_after(to_insert, get_root_node());
   }
   // More operations
   // ...
};

Полуинтрузивный контейнер: Полуинтрузивный контейнер похож на интрузивный контейнер, но помимо значений, которые должны быть вставлены в контейнер, ему нужна дополнительная память (например, вспомогательные массивы или индексы).
Признаки ценности: Как мы видим, чтобы сделать наши классы назойливыми, мы добавляем простой крючок в качестве члена или базового класса. Крючок содержит общий узел, который будет вставлен в группу узлов.Алгоритмы узловпросто работают с узлами и ничего не знают о классах пользователей. С другой стороны, интрузивный контейнер должен знать, как получить узел из класса пользователя, а также обратную операцию. Мы можем определить.ValueTraitsкак клей между классами пользователей и узлами, требуемыйАлгоритмы узлов. Давайте посмотрим на возможную реализацию класса признаков ценности, который склеивает MyClass и узел, хранящийся в крючке:

struct my_slist_derivation_value_traits
{
   public:
   typedef slist_node_traits           node_traits;
   typedef MyClass                     value_type;
   typedef node_traits::node_ptr       node_ptr;
   typedef value_type*                 pointer;
   //...
   //Converts user's value to a generic node
   static node_ptr to_node_ptr(reference value)
   { return static_cast<slist_base_hook &>(value).to_node_ptr(); }
   //Converts a generic node into user's value
   static value_type *to_value_ptr(node_traits::node *n)
   { static_cast<value_type*>(slist_base_hook::to_hook_ptr(n)); }
   // More operations
   // ...
};

Статья Concepts explained раздела The Boost C++ Libraries BoostBook Documentation Subset Chapter 17. Boost.Intrusive может быть полезна для разработчиков на c++ и boost.