Intrusive avl tree based associative containers: avl_set, avl_multiset and avltree

avl_set, avl_multiset and avltree hooks
avl_set, avl_multiset and avltree containers
Example

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 hooks

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

avl_set, avl_multiset and avltree containers

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

Example

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

Boost C++ Libraries