|
Home | Libraries | People | FAQ | More |
Similar to red-black trees, AVL trees are balanced binary trees. AVL trees are often compared with red-black trees because they support the same set of operations and because both take O(log n) time for basic operations. AVL trees are more rigidly balanced than Red-Black trees, leading to slower insertion and removal but faster retrieval, so AVL trees perform better than red-black trees for lookup-intensive applications.
Boost.Intrusive offers 3 containers based
on avl trees: avl_set,
avl_multiset and
avltree. 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 usually 3 pointers and 2 bits (due to alignment, this usually means 3 pointers plus an integer). This size can be reduced to 3 pointers if pointers have 4 byte alignment (which is usually true in 32 bit systems).
An empty, non constant-time size avl_set,
avl_multiset or
avltree also has a size
of 3 pointers and an integer (3 pointers when optimized for size).
avl_set, avl_multiset and avltree share the same hooks.
template <class ...Options> class avl_set_base_hook;
avl_set_base_hook:
the user class derives publicly from this class to make it compatible
with avl tree based containers.
template <class ...Options> class avl_set_member_hook;
set_member_hook:
the user class contains a public member of this class to make it compatible
with avl tree based containers.
avl_set_base_hook
and avl_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*>.
optimize_size<bool Enable>:
The hook will be optimized for size instead of speed. The hook will embed
the balance bits of the AVL tree node in the parent pointer if pointer
alignment is multiple of 4. In some platforms, optimizing the size might
reduce speed performance a bit since masking operations will be needed
to access parent pointer and balance factor attributes, in other platforms
this option improves performance due to improved memory locality. Default:
optimize_size<false>.
template <class T, class ...Options> class avl_set; template <class T, class ...Options> class avl_multiset; template <class T, class ...Options> class avltree;
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.)
constant_time_size<bool Enabled>:
To activate the constant-time size() operation. Default: constant_time_size<true>
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 an additional option:
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> >
Now let's see a small example using both hooks and avl_set/
avl_multiset
containers:
#include <boost/intrusive/avl_set.hpp> #include <vector> #include <algorithm> #include <cassert> using namespace boost::intrusive; //This is a base hook optimized for size class MyClass : public avl_set_base_hook<optimize_size<true> > { int int_; public: //This is a member hook avl_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 avl_set using the base hook that will store values in reverse order typedef avl_set< MyClass, compare<std::greater<MyClass> > > BaseSet; //Define an multiset using the member hook typedef member_hook<MyClass, avl_set_member_hook<>, &MyClass::member_hook_> MemberOption; typedef avl_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; //Check that size optimization is activated in the base hook assert(sizeof(avl_set_base_hook<optimize_size<true> >) == 3*sizeof(void*)); //Check that size optimization is deactivated in the member hook assert(sizeof(avl_set_member_hook<>) > 3*sizeof(void*)); //Now insert them in the sets for(VectIt it(values.begin()), itend(values.end()); it != itend; ++it){ baseset.insert(*it); membermultiset.insert(*it); } //Now test avl_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 avl_set for(; it != itend; ++it, ++rbit) if(&*rbit != &*it) return 1; //Test the objects inserted in the member hook avl_set for(it = values.begin(); it != itend; ++it, ++mit) if(&*mit != &*it) return 1; } return 0; }