Boost C++ Libraries

...one of the most highly regarded and expertly designed C++ library projects in the world. Herb Sutter and Andrei Alexandrescu, C++ Coding Standards

Click here to view the latest version of this page.
PrevUpHomeNext

Concepts explained

This section will expand the explanation of previously presented basic concepts before explaining the customization options of Boost.Intrusive.

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
   // ...
};

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

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
   // ...
};

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
   // ...
};

PrevUpHomeNext