Intrusive associative containers: set, multiset, rbtree

| Home | Libraries | People | FAQ | More

## Intrusive associative containers: set, multiset, rbtree

Boost.Intrusive also offers associative containers that can be very useful when creating more complex associative containers, like containers maintaining one or more indices with different sorting semantics. Boost.Intrusive associative containers, like most STL associative container implemenatations are based on red-black trees.

The memory overhead of these containers is usually 3 pointers and a bit (with alignment issues, this means 3 pointers and an integer). This size can be reduced to 3 pointers if pointers have even alignment (which is usually true in most systems).

An empty, non constant-time size `set`, `multiset` or `rbtree` has also the size of 3 pointers and an integer (3 pointers when optimized for size). These containers have logarithmic complexity in many operations like searches, insertions, erasures, etc... `set` and `multiset` are the intrusive equivalents of standard `std::set` and `std::multiset` containers.

`rbtree` is a superset of `set` and `multiset` containers that offers functions to insert unique and multiple keys.

### set, multiset and rbtree hooks

`set`, `multiset` and `rbtree` share the same hooks. This is an advantage, because the same user type can be inserted first in a `multiset` and after that in `set` without changing the definition of the user class.

    template <class ...Options>
    class set_base_hook;

- `set_base_hook`: the user class derives publicly from `set_base_hook` to make it `set`/`multiset`-compatible.

    template <class ...Options>
    class set_member_hook;

- `set_member_hook`: the user class contains a public `set_member_hook` to make it `set`/`multiset`-compatible.

`set_base_hook` and `set_member_hook` receive the same options explained in the section How to use Boost.Intrusive plus a size optimization option:

- `tag<class Tag>` (for base hooks only): This argument serves as a tag, so you can derive from more than one base hook. Default: `tag<default_tag>`.
- `link_mode<link_mode_type LinkMode>`: The linking policy. Default: `link_mode<safe_link>`.
- `void_pointer<class VoidPointer>`: The pointer type to be used internally in the hook and propagated to the container. Default: `void_pointer<void*>`.
- `optimize_size<bool Enable>`: The hook will be optimized for size instead of speed. The hook will embed the color bit of the red-black tree node in the parent pointer if pointer alignment is even. Optimizing the size will reduce speed performance a bit since masking operations will be needed to access parent pointer and color attributes. Default: `optimize_size<false>`.

### set, multiset and rbtree containers

    template <class T, class ...Options>
    class set;

    template <class T, class ...Options>
    class multiset;

    template <class T, class ...Options>
    class rbtree;

These containers receive the same options explained in the section How to use Boost.Intrusive:

- `base_hook<class Hook>` / `member_hook<class T, class Hook, Hook T::* PtrToMember>` / `value_traits<class ValueTraits>`: To specify the hook type or value traits used to configure the container (to know about value traits go to the section titled Containers with custom ValueTraits.
- `constant_time_size<bool Enabled>`: To activate the constant-time `size()` operation. Default: `constant_time_size<true>`
- `size_type<bool Enabled>`: To specify the type that will be used to store the size of the container. Default: `size_type<std::size_t>`

And they also can receive an additional option:

- `compare<class Compare>`: Comparison function for the objects to be inserted in containers. The comparison functor must induce a strict weak ordering. Default: `compare< std::less<T> >`

### Example

Now let's see an small example using both hooks and both containers:

    #include <boost/intrusive/set.hpp>
    #include <vector>
    #include <algorithm>
    #include <cassert>

    using namespace boost::intrusive;

                      //This is a base hook optimized for size
    class MyClass : public set_base_hook<optimize_size<true> >
    {
       int int_;

       public:
       //This is a member hook
       set_member_hook<> member_hook_;

       MyClass(int i)
          :  int_(i)
          {}
       friend bool operator< (const MyClass &a, const MyClass &b)
          {  return a.int_ < b.int_;  }
       friend bool operator> (const MyClass &a, const MyClass &b)
          {  return a.int_ > b.int_;  }
       friend bool operator== (const MyClass &a, const MyClass &b)
          {  return a.int_ < b.int_;  }
    };

    //Define a set using the base hook that will store values in reverse order
    typedef set< MyClass, compare<std::greater<MyClass> > >     BaseSet;

    //Define an multiset using the member hook
    typedef member_hook<MyClass, set_member_hook<>, &MyClass::member_hook_> MemberOption;
    typedef multiset< MyClass, MemberOption>   MemberMultiset;

    int main()
    {
       typedef std::vector<MyClass>::iterator VectIt;
       typedef std::vector<MyClass>::reverse_iterator VectRit;

       //Create several MyClass objects, each one with a different value
       std::vector<MyClass> values;
       for(int i = 0; i < 100; ++i)  values.push_back(MyClass(i));

       BaseSet baseset;
       MemberMultiset membermultiset;

       //Check that size optimization is activated in the base hook
       assert(sizeof(set_base_hook<optimize_size<true> >) == 3*sizeof(void*));
       //Check that size optimization is deactivated in the member hook
       assert(sizeof(set_member_hook<>) > 3*sizeof(void*));

       //Now insert them in the reverse order in the base hook set
       for(VectIt it(values.begin()), itend(values.end()); it != itend; ++it){
          baseset.insert(*it);
          membermultiset.insert(*it);
       }

       //Now test sets
       {
          BaseSet::reverse_iterator rbit(baseset.rbegin()), rbitend(baseset.rend());
          MemberMultiset::iterator mit(membermultiset.begin()), mitend(membermultiset.end());
          VectIt it(values.begin()), itend(values.end());

          //Test the objects inserted in the base hook set
          for(; it != itend; ++it, ++rbit)
             if(&*rbit != &*it)   return 1;

          //Test the objects inserted in the member hook set
          for(it = values.begin(); it != itend; ++it, ++mit)
             if(&*mit != &*it) return 1;
       }
       return 0;
    }