Containers with custom ValueTraits

| Home | Libraries | People | FAQ | More

## Containers with custom ValueTraits

As explained in the Concepts section, Boost.Intrusive containers need a `ValueTraits` class to perform transformations between nodes and user values. `ValueTraits` can be explicitly configured (using the `value_traits<>` option) or implicitly configured (using hooks and their `base_hook<>`/`member_hook<>` options). `ValueTraits` contains all the information to glue the `value_type` of the containers and the node to be used in node algorithms, since these types can be different. Apart from this, `ValueTraits` also stores information about the link policy of the values to be inserted.

Instead of using Boost.Intrusive predefined hooks a user might want to develop customized containers, for example, using nodes that are optimized for a specific application or that are compatible with a legacy ABI. A user might want to have only two additional pointers in his class and insert the class in a doubly linked list sometimes and in a singly linked list in other situations. You can't achieve this using Boost.Intrusive predefined hooks. Now, instead of using `base_hook<...>` or `member_hook<...>` options the user will specify the `value_traits<...>` options. Let's see how we can do this:

### ValueTraits interface

`ValueTraits` has the following interface:

    #include <boost/intrusive/pointer_traits.hpp>
    #include <boost/intrusive/link_mode.hpp>

    struct my_value_traits
    {
       typedef implementation_defined                                    node_traits;
       typedef implementation_defined                                    value_type;
       typedef node_traits::node_ptr                                     node_ptr;
       typedef node_traits::const_node_ptr                               const_node_ptr;
       typedef boost::intrusive::pointer_traits<node_ptr>::rebind_traits
          <value_type>::type::pointer                                    pointer;
       typedef boost::intrusive::pointer_traits<node_ptr>::rebind_traits
          <const value_type>::type::pointer                              const_pointer;

       static const link_mode_type link_mode = some_linking_policy;

       static node_ptr       to_node_ptr    (value_type &value);
       static const_node_ptr to_node_ptr    (const value_type &value);
       static pointer        to_value_ptr   (node_ptr n);
       static const_pointer  to_value_ptr   (const_node_ptr n);
    };

Let's explain each type and function:

- node_traits: The node configuration that is needed by node algorithms. These node traits and algorithms are described in the previous chapter: Node Algorithms.
  - If my_value_traits is meant to be used with `slist`, `node_traits` should follow the interface needed by `circular_slist_algorithms`.
  - If my_value_traits is meant to be used with `list`, `node_traits` should follow the interface needed by `circular_list_algorithms`.
  - If my_value_traits is meant to be used with `set`/`multiset`, `node_traits` should follow the interface needed by `rbtree_algorithms`.
  - If my_value_traits is meant to be used with `unordered_set`/ `unordered_multiset`, `node_traits` should follow the interface needed by `circular_slist_algorithms`.
- node_ptr: A typedef for `node_traits::node_ptr`.
- const_node_ptr: A typedef for `node_traits::const_node_ptr`.
- value_type: The type that the user wants to insert in the container. This type can be the same as `node_traits::node` but it can be different (for example, `node_traits::node` can be a member type of `value_type`). If `value_type` and `node_traits::node` are the same type, the `to_node_ptr` and `to_value_ptr` functions are trivial.
- pointer: The type of a pointer to a `value_type`. It must be the same pointer type as `node_ptr`: If `node_ptr` is `node*`, `pointer` must be `value_type*`. If `node_ptr` is `smart_ptr<node_traits::node>`, `pointer` must be `smart_ptr<value_type>`. This can be generically achieved using `boost::intrusive::pointer_traits` (portable implementation of C++11 `std::pointer_traits`).
- const_pointer: The type of a pointer to a `const value_type`. It must be the same pointer type as `node_ptr`: If `node_ptr` is `node*`, `const_pointer` must be `const value_type*`. If `node_ptr` is `smart_ptr<node_traits::node>`, `const_pointer` must be `smart_ptr<const value_type>`.
- link_mode: Indicates that `value_traits` needs some additional work or checks from the container. The types are enumerations defined in the `link_mode.hpp` header. These are the possible types:
  - `normal_link`: If this linking policy is specified in a `ValueTraits` class as the link mode, containers configured with such `ValueTraits` won't set the hooks of the erased values to a default state. Containers also won't check that the hooks of the new values are default initialized.
  - `safe_link`: If this linking policy is specified as the link mode in a `ValueTraits` class, containers configured with this `ValueTraits` will set the hooks of the erased values to a default state. Containers also will check that the hooks of the new values are default initialized.
  - `auto_unlink`: Same as "safe_link" but containers with constant-time size features won't be compatible with `ValueTraits` configured with this policy. Containers also know that a value can be silently erased from the container without using any function provided by the containers.
- static node_ptr to_node_ptr (value_type &value) and static const_node_ptr to_node_ptr (const value_type &value): These functions take a reference to a value_type and return a pointer to the node to be used with node algorithms.
- static pointer to_value_ptr (node_ptr n) and static const_pointer to_value_ptr (const_node_ptr n): These functions take a pointer to a node and return a pointer to the value that contains the node.

### Custom ValueTraits example

Let's define our own `value_traits` class to be able to use Boost.Intrusive containers with an old C structure whose definition can't be changed. That legacy type has two pointers that can be used to build singly and doubly linked lists: in singly linked lists we only need a pointer, whereas in doubly linked lists, we need two pointers. Since we only have two pointers, we can't insert the object in both a singly and a doubly linked list at the same time. This is the definition of the old node:

    #include <boost/intrusive/link_mode.hpp>
    #include <boost/intrusive/list.hpp>
    #include <boost/intrusive/slist.hpp>
    #include <vector>

    //This node is the legacy type we can't modify and we want to insert in
    //intrusive list and slist containers using only two pointers, since
    //we know the object will never be at the same time in both lists.
    struct legacy_value
    {
       legacy_value *prev_;
       legacy_value *next_;
       int id_;
    };

Now we have to define a NodeTraits class that will implement the functions/typedefs that will make the legacy node compatible with Boost.Intrusive algorithms. After that, we'll define a ValueTraits class that will configure Boost.Intrusive containers:

    //Define our own NodeTraits that will configure singly and doubly linked
    //list algorithms. Note that this node traits is compatible with
    //circular_slist_algorithms and circular_list_algorithms.

    namespace bi = boost::intrusive;

    struct legacy_node_traits
    {
       typedef legacy_value                            node;
       typedef legacy_value *                          node_ptr;
       typedef const legacy_value *                    const_node_ptr;

       static node *get_next(const node *n)            {  return n->next_;  }
       static void set_next(node *n, node *next)       {  n->next_ = next;  }
       static node *get_previous(const node *n)        {  return n->prev_;  }
       static void set_previous(node *n, node *prev)   {  n->prev_ = prev;  }
    };

    //This ValueTraits will configure list and slist. In this case,
    //legacy_node_traits::node is the same as the
    //legacy_value_traits::value_type so to_node_ptr/to_value_ptr
    //functions are trivial.
    struct legacy_value_traits
    {
       typedef legacy_node_traits                                  node_traits;
       typedef node_traits::node_ptr                               node_ptr;
       typedef node_traits::const_node_ptr                         const_node_ptr;
       typedef legacy_value                                        value_type;
       typedef legacy_value *                                      pointer;
       typedef const legacy_value *                                const_pointer;
       static const bi::link_mode_type link_mode = bi::normal_link;
       static node_ptr to_node_ptr (value_type &value)             {  return node_ptr(&value); }
       static const_node_ptr to_node_ptr (const value_type &value) {  return const_node_ptr(&value); }
       static pointer to_value_ptr(node_ptr n)                     {  return pointer(n); }
       static const_pointer to_value_ptr(const_node_ptr n)         {  return const_pointer(n); }
    };

Defining a value traits class that simply defines `value_type` as `legacy_node_traits::node` is a common approach when defining customized intrusive containers, so Boost.Intrusive offers a templatized `trivial_value_traits` class that does exactly what we want:

    typedef bi::trivial_value_traits<legacy_node_traits, bi::normal_link> trivial_legacy_value_traits;

Now we can just define the containers that will store the legacy abi objects and write a little test:

    //Now define an intrusive list and slist that will store legacy_value objects
    typedef bi::value_traits<legacy_value_traits>         ValueTraitsOption;
    typedef bi::value_traits<trivial_legacy_value_traits> TrivialValueTraitsOption;

    typedef bi::list<legacy_value,  ValueTraitsOption>          LegacyAbiList;
    typedef bi::slist<legacy_value, ValueTraitsOption>          LegacyAbiSlist;
    typedef bi::list<legacy_value,  TrivialValueTraitsOption>   TrivialLegacyAbiList;
    typedef bi::slist<legacy_value, TrivialValueTraitsOption>   TrivialLegacyAbiSlist;

    template<class List>
    bool test_list()
    {
       typedef std::vector<legacy_value> Vect;

       //Create legacy_value objects, with a different internal number
       Vect legacy_vector;
       for(int i = 0; i < 100; ++i){
          legacy_value value;     value.id_ = i;    legacy_vector.push_back(value);
       }

       //Create the list with the objects
       List mylist(legacy_vector.begin(), legacy_vector.end());

       //Now test both lists
       typename List::const_iterator bit(mylist.begin()), bitend(mylist.end());
       typename Vect::const_iterator it(legacy_vector.begin()), itend(legacy_vector.end());

       //Test the objects inserted in our list
       for(; it != itend; ++it, ++bit)
          if(&*bit != &*it) return false;
       return true;
    }

    int main()
    {
       return test_list<LegacyAbiList>()        && test_list<LegacyAbiSlist>() &&
              test_list<TrivialLegacyAbiList>() && test_list<TrivialLegacyAbiSlist>()
              ? 0 : 1;
    }

As seen, several key elements of Boost.Intrusive can be reused with custom user types, if the user does not want to use the provided Boost.Intrusive facilities.

### Reusing node algorithms for different values

In the previous example, `legacy_node_traits::node` type and `legacy_value_traits::value_type` are the same type, but this is not necessary. It's possible to have several `ValueTraits` defining the same `node_traits` type (and thus, the same `node_traits::node`). This reduces the number of node algorithm instantiations, but now `ValueTraits::to_node_ptr` and `ValueTraits::to_value_ptr` functions need to offer conversions between both types. Let's see a small example:

First, we'll define the node to be used in the algorithms. For a linked list, we just need a node that stores two pointers:

    #include <boost/intrusive/link_mode.hpp>
    #include <boost/intrusive/list.hpp>
    #include <vector>

    //This is the node that will be used with algorithms.
    struct simple_node
    {
       simple_node *prev_;
       simple_node *next_;
    };

Now we'll define two different types that will be inserted in intrusive lists and a templatized `ValueTraits` that will work for both types:

    class base_1{};
    class base_2{};

    struct value_1 :  public base_1, public simple_node
    {  int   id_;  };

    struct value_2 :  public base_1, public base_2, public simple_node
    {  float id_;  };

    //Define the node traits. A single node_traits will be enough.
    struct simple_node_traits
    {
       typedef simple_node                             node;
       typedef node *                                  node_ptr;
       typedef const node *                            const_node_ptr;
       static node *get_next(const node *n)            {  return n->next_;  }
       static void set_next(node *n, node *next)       {  n->next_ = next;  }
       static node *get_previous(const node *n)        {  return n->prev_;  }
       static void set_previous(node *n, node *prev)   {  n->prev_ = prev;  }
    };

    //A templatized value traits for value_1 and value_2
    template<class ValueType>
    struct simple_value_traits
    {
       typedef simple_node_traits                                  node_traits;
       typedef node_traits::node_ptr                               node_ptr;
       typedef node_traits::const_node_ptr                         const_node_ptr;
       typedef ValueType                                           value_type;
       typedef ValueType *                                         pointer;
       typedef const ValueType *                                   const_pointer;
       static const boost::intrusive::link_mode_type link_mode = boost::intrusive::normal_link;
       static node_ptr to_node_ptr (value_type &value)             {  return node_ptr(&value); }
       static const_node_ptr to_node_ptr (const value_type &value) {  return const_node_ptr(&value); }
       static pointer to_value_ptr(node_ptr n)                     {  return static_cast<value_type*>(n); }
       static const_pointer to_value_ptr(const_node_ptr n)         {  return static_cast<const value_type*>(n); }
    };

Now define two containers. Both containers will instantiate the same list algorithms (`circular_list_algorithms<simple_node_traits>`), due to the fact that the value traits used to define the containers provide the same `node_traits` type:

    //Now define two intrusive lists. Both lists will use the same algorithms:
    // circular_list_algorithms<simple_node_traits>

    using namespace boost::intrusive;
    typedef list <value_1, value_traits<simple_value_traits<value_1> > > Value1List;
    typedef list <value_2, value_traits<simple_value_traits<value_2> > > Value2List;

All Boost.Intrusive containers using predefined hooks use this technique to minimize code size: all possible `list` containers created with predefined hooks that define the same `VoidPointer` type share the same list algorithms.

### Simplifying value traits definition

The previous example can be further simplified using the `derivation_value_traits` class to define a value traits class with a value that stores the `simple_node` as a base class:

    class base_1{};
    class base_2{};

    struct value_1 :  public base_1, public simple_node
    {
       int   id_;
       simple_node node_;
    };

    struct value_2 :  public base_1, public base_2, public simple_node
    {
       simple_node node_;
       float id_;
    };

    using namespace boost::intrusive;

    //Now define the needed value traits using derivation_value_traits
    typedef derivation_value_traits<value_1, simple_node_traits, normal_link> ValueTraits1;
    typedef derivation_value_traits<value_2, simple_node_traits, normal_link> ValueTraits2;

    //Now define two intrusive lists. Both lists will use the same algorithms:
    // circular_list_algorithms<simple_node_traits>
    typedef list <value_1, value_traits<ValueTraits1> > Value1List;
    typedef list <value_2, value_traits<ValueTraits2> > Value2List;

We can even choose to store `simple_node` as a member of `value_1` and `value_2` classes and use `member_value_traits` to define the needed value traits classes:

    class base_1{};
    class base_2{};

    struct value_1 :  public base_1, public simple_node
    {
       int   id_;
       simple_node node_;
    };

    struct value_2 :  public base_1, public base_2, public simple_node
    {
       simple_node node_;
       float id_;
    };

    using namespace boost::intrusive;

    typedef member_value_traits
       <value_1, simple_node_traits, &value_1::node_, normal_link> ValueTraits1;
    typedef member_value_traits
    <value_2, simple_node_traits, &value_2::node_, normal_link> ValueTraits2;

    //Now define two intrusive lists. Both lists will use the same algorithms:
    // circular_list_algorithms<simple_node_traits>
    typedef list <value_1, value_traits<ValueTraits1> > Value1List;
    typedef list <value_2, value_traits<ValueTraits2> > Value2List;

### Stateful value traits

Until now all shown custom value traits are stateless, that is, the transformation between nodes and values is implemented in terms of static functions. It's possible to use stateful value traits so that we can separate nodes and values and avoid modifying types to insert nodes. Boost.Intrusive differentiates between stateful and stateless value traits by checking if all Node <-> Value transformation functions are static or not (except for Visual 7.1, since overloaded static function detection is not possible, in this case the implementation checks if the class is empty):

- If all Node <-> Value transformation functions are static , a stateless value traits is assumed. transformations must be static functions.
- Otherwise a stateful value traits is assumed.

Using stateful value traits it's possible to create containers of non-copyable/movable objects without modifying the definition of the class to be inserted. This interesting property is achieved without using global variables (stateless value traits could use global variables to achieve the same goal), so:

- Thread-safety guarantees: Better thread-safety guarantees can be achieved with stateful value traits, since accessing global resources might require synchronization primitives that can be avoided when using internal state.
- Flexibility: A stateful value traits type can be configured at run-time.
- Run-time polymorphism: A value traits might implement node <-> value transformations as virtual functions. A single container type could be configured at run-time to use different node <-> value relationships.

Stateful value traits have many advantages but also some downsides:

- Performance: Value traits operations should be very efficient since they are basic operations used by containers. A heavy node <-> value transformation will hurt intrusive containers' performance.
- Exception guarantees: The stateful ValueTraits must maintain no-throw guarantees, otherwise, the container invariants won't be preserved.
- Static functions: Some static functions offered by intrusive containers are not available because node <-> value transformations are not static.
- Bigger iterators: The size of some iterators is increased because the iterator needs to store a pointer to the stateful value traits to implement node to value transformations (e.g. `operator*()` and `operator->()`).

An easy and useful example of stateful value traits is when an array of values can be indirectly introduced in a list guaranteeing no additional allocation apart from the initial resource reservation:

    #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-1]), *it_rbeg_val(&ids[0]-1);

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

       return 0;
    }