...one of the most highly
regarded and expertly designed C++ library projects in the
world.
— Herb Sutter and Andrei
Alexandrescu, C++
Coding Standards
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:
auto_unlink
hooks.
The size of an empty scapegoat tree is also considerably increased.
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).
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*>
.
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 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; }