Boost logo

Boost :

From: Ion Gaztañaga (igaztanaga_at_[hidden])
Date: 2007-08-24 17:10:39

Hi to all,

  First of all, thanks to all who participated in recent threads
about Boost.Intrusive options and extended configurability discussions.
These days I've been experimenting a bit with this option and also with
stateful value_traits (those who could allow non-intrusive hooks).

Passing policies to hooks and containers

As you know, one of my main concerns is that a container explicitly set
with some options, should have the same type as another container
defined with the same options in a different order. I meant:

  list<T, base_hook<my_base_hook>, constant_time_size<false> >

should have the same type as:

  list<T, constant_time_size<false>, base_hook<my_base_hook> > l;

My preferred alternative is the more verbose:

typedef list_options
  < base_hook<my_base_hook>
  , constant_time_size<false>
>::type options_t;

list<T, options_t> l;

that guarantees the same type for the same options.

1) Implemented interface:

I've implemented all current container options using this approach. I've
chosen a different options configurer "list_options", "slist_options"...
because otherwise, I couldn't set defaults that could lead to the
correct types.

The default hooks is the base hook so a user can just say:

class my_type
   : public list_base_hook<>

list<my_type> l;

Some options must not be set in the container *but in the hook*, since
options affect both the hook and the container. Examples: void pointer
definition, the linking policy. I think hook options can be unified so I

typedef hook_options
    < void_pointer<offset_ptr<void> >
    , link<normal_link>
    , tag<my_tag>
>::type hook_options_t;

class my_type
   : public list_base_hook<hook_options_t>
    typedef list_base_hook<hook_options_t> my_hook_t;

typedef list_options
  < base_hook<my_hook_t>
  , size_type<std::size_t>
>::type options_t;

list<T, options_t> l;

As you can see, specifying options can be quite verbose (comparing it to
the old way, but as new options are added (for example, custom buckets
definition in hash containers) users don't have put arguments in order
and can change only the options they want to change from the default.

2) Declaration of new classes:

template<class T, class ListOptions>
class list;

template<class T, class SlistOptions>
class slist;

template<class T, class Pred, class SetOptions>
class set;

template<class T, class Hash, class Equal, class UsetOptions>
class unordered_set;

So the declaration of intrusive containers would be exactly the same as
the STL containers plus an options argument.

3) Problem: Definition of member hooks is very long

class my_type
    list_member_hook member_hook_;

typedef list_options
   < member_hook<my_type, list_member_hook, &my_type::member_hook_>
>::type options;

list<my_type, options> l;

Why? Because I can't make C++ deduce a pointer to member value in a
single template parameter passed to a class. It would be nice that C++
could deduce my_type and list_member_hook from the value directly
yielding to:

typedef list_options
   //Deduce my_type and list_member_hook automatically
   < member_hook<&my_type::member_hook_>
>::type options;

If anyone can correct me, I would be *really* glad.

4) Custom value_traits

Current interface takes a value_traits class as the first parameter in

template<class ValueTraits, bool...>
class list;

ValueTraits concept is very powerful because allows separating the
concepts of a Node and a Value. The node is the minimal structure that
is need to form a group of nodes (group of pointers to form a list, a
tree...) and the Value is the whole user type that is somehow related to
the node (via inheritance, membership, or other).

Intrusive documentation offers examples of custom ValueTraits to reuse
nodes for different containers or to deal with non modifiable ABI of old
code. This is still possible specifying
the value_traits instead of the hook:

typedef list_options
   < value_traits<my_value_traits>
>::type options;

list<T, my_value_traits> l;

Stateful value_traits (aka allowing extrusive containers)

I've started experimenting with stateful value_traits, while trying to
keep zero overhead when ValueTraits is an empty class. There are some
problems though:

1) Iterators

Iterators containa pointer to node and they use ValueTraits to obtain
the user value from the node. If an stateful ValueTraits is used, we
also need to store a pointer to the value traits stored in the
container. If I want zero overhead when using hooks or just value traits
with static functions I have to avoid storing the pointer when the
iterator is stateless.

How do we know if an allocator is stateless? One possibility is to check
if the ValueTraits is empty, that is, has no members. However, this does
not guarantee that ValuetTraits will define static functions so that no
pointer to ValueTraits is needed to convert from a node to a container.
I think it's a good aproximation or I could also define a traits or
internal constant to say "this ValueTraits is stateless/stateful". For
the moment, my current option is to consider an empty ValueTratis
stateless, so it must define conversion functions as static members.

2) Losing static functions

Some member functions of intrusive containers are static, so that there
is no need to have a reference to the container. This sometimes is very
useful (e.g. list::iterator_to) but this can't be achieved if stateful
value traits are used. I can think 3 options:

-> Convert static functions in non-static (losing some advantages)
-> Offer static and non-static versions. Static versions won't compile
with stateful allocators (via BOOST_STATIC_ASSERT).
-> Someone knows have to make a function static or not depending on a
compile-time boolean.

3) Stateless, but taking advantage of composition

In a recent discussion about adding custom bucket traits to unordered
containers a booster wanted to have the bucket outside the class (for
example, to reuse that with other containers). With stateful allocators
this can be possible if bucket traits are stateful an contain a pointer
to the real bucket traits instance. But this increases the size of your
intrusive container.

However if the external bucket implementation is very near to the
container (said, it's a member of the same structure or whatever), it's
possible to obtain the address of the the external resource based on the
address of the container or the internal traits instance included in the

Rei Thiessen was requesting that when he explained the customized bucket
info structure.

template< unsigned n >
struct bucket_info_size_n
    /* appropriate constructors... */
    bucket_ptr buckets_;
    template<class T> bucket_ptr buckets( T* container ) const { return
buckets_; }
    size_type buckets_len() const { return 1<<n; }

So based on the address of the container, the user can find the resource
(in this case, the bucket array) obtaining zero size overhead (the
internal traits is empty). This logic can be extended to every traits
class of the container, but specially to ValueTraits.

But this would require passing the address of the container to every
function the traits class implements. Users not wanting this composition
hack surely don't want to change their signatures to just support this
extremely advance practice:


class my_value_traits
    node_ptr to_node_ptr(value_type &val)


class my_value_traits
    template<class Container>
    node_ptr to_node_ptr(value_type &val, const Container& cont)

So if there is any metaprogramming hack (if increases compilation time
too much, forget it ;-) ) I would like to receive suggestions.
Otherwise, a member static const bool saying "pass container address" in
value traits might be useful, so that the container changes the calls to
the traits with another equivalent one passing the address of the container.

I haven't still experimented this composition hack so I'm really open to
all suggestions from advanced users. My point is that this should be
really optional and should not affect users not using these advanced

As Rei said (inflating my ego): "These intrusive containers are so close
to perfect that it's painful to have to modify them."

So let's make them perfect ;-)



Boost list run by bdawes at, gregod at, cpdaniel at, john at