Boost C++ Libraries

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 an element is searched. This disallows const versions of search functions like find(), lower_bound(), upper_bound(), equal_range(), count(), etc.

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

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 share the same hooks.

template <class ...Options>
class splay_set_base_hook;

template <class ...Options>
class splay_set_member_hook;

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

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:

And they also can receive an additional option:

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. A programmer might prefer using a binary search tree hook so that the same type can be inserted in some situations in a splay container but also inserted in other compatible containers when the hook is not being used in a splay container.

bs_set_base_hook and bs_set_member_hook admit the same options as splay_set_base_hook.

Now let's see a 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;
}