Boost C++ Libraries of the most highly regarded and expertly designed C++ library projects in the world. Herb Sutter and Andrei Alexandrescu, C++ Coding Standards


Intrusive scapegoat tree based associative containers: sg_set, sg_multiset and sgtree

sg_set, sg_multiset and sgtree containers

A scapegoat tree is a self-balancing binary search tree, that provides worst-case O(log n) lookup time, and O(log n) amortized insertion and deletion time. Unlike other self-balancing binary search trees that provide worst case O(log n) lookup time, scapegoat trees have no additional per-node overhead compared to a regular binary search tree.

A binary search tree is said to be weight balanced if half the nodes are on the left of the root, and half on the right. An a-height-balanced tree is defined with defined with the following equation:

height(tree) <= log1/a(tree.size())

Scapegoat trees are loosely a-height-balanced so:

height(tree) <= log1/a(tree.size()) + 1

Scapegoat trees support any a between 0.5 and 1. If a is higher, the tree is rebalanced less often, obtaining quicker insertions but slower searches. Lower a values improve search times. Scapegoat-trees implemented in Boost.Intrusive offer the possibility of changing a at run-time taking advantage of the flexibility of scapegoat trees. For more information on scapegoat trees see Wikipedia entry.

Scapegoat trees also have downsides:

Boost.Intrusive offers 3 containers based on scapegoat trees: sg_set, sg_multiset and sgtree. 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 3 pointers.

An empty, sg_set, sg_multiset or sgtree has also the size of 3 pointers, two integers and two floating point values (equivalent to the size of 7 pointers on most systems).

Boost.Intrusive scapegoat associative containers don't use their own hook types but plain Binary search tree hooks. See Binary search tree hooks: bs_set_base_hook and bs_set_member_hook section for more information about these hooks.

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

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

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

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 learn about value traits go to the section Containers with custom ValueTraits.)
  • 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 additional options:

  • 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> >
  • floating_point<bool Enable>: When this option is deactivated, the scapegoat tree loses the ability to change the balance factor a at run-time, but the size of an empty container is reduced and no floating point operations are performed, normally increasing container performance. The fixed a factor that is used when this option is activated is 1/sqrt(2) ~ 0,70711. Default: floating_point<true>

Now let's see a small example using binary search tree hooks and sg_set/ sg_multiset containers:

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

using namespace boost::intrusive;

class MyClass : public bs_set_base_hook<>
   int int_;

   //This is a member hook
   bs_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 an sg_set using the base hook that will store values in reverse order
//and won't execute floating point operations.
typedef sg_set
   < MyClass, compare<std::greater<MyClass> >, floating_point<false> >   BaseSet;

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

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

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

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

   //Change balance factor

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

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

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