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

| Home | Libraries | People | FAQ | More

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

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 α-height-balanced tree is defined with defined with the following equation:

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

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

Scapegoat trees are loosely α-height-balanced so:

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

Scapegoat trees support any α between 0.5 and 1. If α is higher, the tree is rebalanced less often, obtaining quicker insertions but slower searches. Lower α values improve search times. Scapegoat-trees implemented in Boost.Intrusive offer the possibility of changing α 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/α. 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 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 plus an option to optimize the size of the node:

- `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 know about value traits go to the section titled 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 α 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 α factor that is used when this option is activated is 1/sqrt(2) ~ 0,70711. Default: `floating_point<true>`

### Example

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