Intrusive splay tree based associative containers: splay_set, splay_multiset and , splay_tree

| Home | Libraries | People | FAQ | More

## Intrusive splay tree based associative containers: splay_set, splay_multiset and , splay_tree

C++ associative containers are usually based on red-black tree implementations (e.g.: STL, Boost.Intrusive associative containers). However, there are other interesting data structures that offer some advantages (and also disadvantages).

Splay trees are self-adjusting binary search trees used tipically in caches, memory allocators and other applications, because splay trees have a "caching effect": recently accessed elements have better access times that elements accessed less frequently. For more information on splay trees see Wikipedia entry.

Boost.Intrusive offers 3 containers based on splay trees: `splay_set`, `splay_multiset` and `splaytree`. The first two are similar to `set` or `multiset` and the latter is a generalization that offers functions both to insert unique and multiple keys.

The memory overhead of these containers with Boost.Intrusive hooks is usually 3 pointers. An empty, non constant-time size splay container has also the size of 3 pointers.

### Advantages and disadvantages of splay tree based containers

Splay tree based intrusive containers have logarithmic complexity in many operations like searches, insertions, erasures, etc... but if some elements are more frequently accessed than others, splay trees perform faster searches than equivalent balanced binary trees (such as red-black trees).

The caching effect offered by splay trees comes with a cost: the tree must be rebalanced when a element is searched. This disallows const versions of search functions like `find()`, `lower_bound()`, `upper_bound()`, `equal_range()`, `count()`...

Because of this, splay-tree based associative containers are not drop-in replacements of `set`/ `splay_set`.

Apart from this, if element searches are randomized, the tree will be rebalanced without taking advantage of the cache effect, so splay trees can offer worse performance than other balanced trees for some search patterns.

### splay_set, splay_multiset and splaytree hooks

`splay_set`, `splay_multiset` and `splaytree` share the same hooks.

    template <class ...Options>
    class splay_set_base_hook;

- `splay_set_base_hook`: the user class derives publicly from this class to make it compatible with splay tree based containers.

    template <class ...Options>
    class splay_set_member_hook;

- `set_member_hook`: the user class contains a public member of this class to make it compatible with splay tree based containers.

`splay_set_base_hook` and `splay_set_member_hook` receive the same options explained in the section How to use Boost.Intrusive:

- `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*>`.

### splay_set, splay_multiset and splaytree containers

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

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

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

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> >`

### Splay trees with BST hooks

Intrusive splay containers can also use plain binary search tree hooks `bs_set_base_hook` and `bs_set_base_hook`. These hooks can be used by other intrusive containers like intrusive scapegoat containers `sg_set` and `sg_multiset` so a programmer might prefer using a binary search tree hook so that the same type can be introduced in some situations in an splay container but that can also be introduced in other compatible containers as well when the hook is not being used in an splay container.

`bs_set_base_hook` and `bs_set_member_hook` admit the same options as `splay_set_base_hook`.

### Example

Now let's see an small example using both splay hooks, binary search tree hooks and `splay_set`/ `splay_multiset` containers:

    #include <boost/intrusive/splay_set.hpp>
    #include <boost/intrusive/bs_set_hook.hpp>
    #include <vector>
    #include <algorithm>

    using namespace boost::intrusive;

    class MyClass
       : public splay_set_base_hook<>   //This is an splay tree base hook
       , public bs_set_base_hook<>      //This is a binary search tree base hook

    {
       int int_;

       public:
       //This is a member hook
       splay_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 splay_set< MyClass, compare<std::greater<MyClass> > >     BaseSplaySet;

    //Define a set using the binary search tree hook
    typedef splay_set< MyClass, base_hook<bs_set_base_hook<> > >      BaseBsSplaySet;

    //Define an multiset using the member hook
    typedef member_hook<MyClass, splay_set_member_hook<>, &MyClass::member_hook_> MemberOption;
    typedef splay_multiset< MyClass, MemberOption>   MemberSplayMultiset;

    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));

       BaseSplaySet   baseset;
       BaseBsSplaySet bsbaseset;
       MemberSplayMultiset membermultiset;

       //Insert values in the container
       for(VectIt it(values.begin()), itend(values.end()); it != itend; ++it){
          baseset.insert(*it);
          bsbaseset.insert(*it);
          membermultiset.insert(*it);
       }

       //Now test sets
       {
          BaseSplaySet::reverse_iterator rbit(baseset.rbegin()), rbitend(baseset.rend());
          BaseBsSplaySet::iterator bsit(bsbaseset.begin()), bsitend(bsbaseset.end());
          MemberSplayMultiset::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 member and binary search hook sets
          for(it = values.begin(); it != itend; ++it, ++bsit, ++mit){
             if(&*bsit != &*it)   return 1;
             if(&*mit != &*it)    return 1;
          }
       }
       return 0;
    }