Intrusive scapegoat tree based associative containers: sg_set, sg

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

Using binary search tree hooks: bs_set_base_hook and bs_set_member_hook
sg_set, sg_multiset and sgtree containers
Example

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

a == 1: A tree forming a linked list is considered balanced.
a == 0.5: Only a perfectly balanced binary is considered balanced.

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:

They need additional storage of data on the root (the size of the tree, for example) to achieve logarithmic complexity operations so it's not possible to offer auto_unlink hooks. The size of an empty scapegoat tree is also considerably increased.
The operations needed to determine if the tree is unbalanced require floating-point operations like log1/a. If the system has no floating point operations (like some embedded systems), scapegoat tree operations might become slow.

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

Using binary search tree hooks: bs_set_base_hook and bs_set_member_hook

sg_set, sg_multiset and sgtree don't use their own hooks but plain binary search tree hooks. This has many advantages since binary search tree hooks can also be used to insert values in splay and treap containers.

template <class ...Options>
class bs_set_base_hook;

bs_set_base_hook: the user class derives publicly from this class to make it compatible with scapegoat tree based containers.

template <class ...Options>
class bs_set_member_hook;

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

bs_set_base_hook and bs_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*>.

sg_set, sg_multiset and sgtree containers

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>

Example

Now let's see a small example using both 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_;

   public:
   //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;
   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;
   
   //Now insert them in the reverse order in the base hook sg_set
   for(VectIt it(values.begin()), itend(values.end()); it != itend; ++it){
      baseset.insert(*it);
      membermultiset.insert(*it);
   }

   //Change balance factor
   membermultiset.balance_factor(0.9f);

   //Now test sg_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 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;
}