Intrusive avl tree based associative containers: avl_set, avl

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.
和紅黑樹相似，AVL 樹也是一種平衡二叉樹。AVL 樹通常會與紅黑樹相比較，因為它們都支持相同的操作集，且對於基本操作都具有 O(log n) 的時間複雜度。AVL 樹比紅黑樹更為嚴格地平衡，這導致了更慢的插入和刪除操作，但取出操作則要快一點，所以對於查找操作較多的應用來說，AVL 樹要比紅黑樹表現得好一些。

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.
Boost.Intrusive 提供了3種基於 splay 樹的容器：avl_set, avl_multiset 和 avltree。前兩種類似於 set 或 multiset，而最後一種則是一個提供了插入唯一鍵和重複鍵功能的泛型。

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).
這些帶有 Boost.Intrusive 鉤子的容器的空間開銷通常為3個指針加2個bits(由於要對齊，通常是3個指針加1個整數)。如果指針是4字節對齊的(在32位系統上通常都是如此)，則大小被壓縮為3個指針。

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).
一個空的、不帶常量時間 size 的 avl_set, avl_multiset 或 avltree 容器也具有3個指針加1個整數的大小(當按空間優化時為3個指針)。

avl_set, avl_multiset and avltree hooks

avl_set, avl_multiset 和 avltree 鉤子

avl_set, avl_multiset and avltree share the same hooks.
avl_set, avl_multiset 和 avltree 共享相同的鉤子。

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.
avl_set_base_hook: 用戶類公有派生自此類以兼容於基於 avl 樹的容器。

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.
set_member_hook: 用戶類包含一個此類的公有成員以兼容於基於 avl 樹的容器。

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:
avl_set_base_hook 和 avl_set_member_hook 接受在如何使用 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>.
tag<class Tag> (只用於基類鉤子)：該參數作為一個標記，你可以派生自多個 slist 鉤子。缺省值：tag<default_tag>.
link_mode<link_mode_type LinkMode>: The linking policy. Default: link_mode<safe_link>.
link_mode<link_mode_type LinkMode>: 鏈接策略。缺省值：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*>.
void_pointer<class VoidPointer>: 在鉤子內部使用並被傳遞給容器的指針類型。缺省值：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. Optimizing the size will reduce speed performance a bit since masking operations will be needed to access parent pointer and balance factor attributes. Default: optimize_size<false>.
optimize_size<bool Enable>: 鉤子將被按空間優化而不是按速度優化。如果指針是按4的倍數對齊的，鉤子會將 AVL 樹的平衡位嵌入到父節點中。空間優化會稍微降低速度性能，因為訪問父節點和平衡因子屬性的時候需要進行掩碼操作。缺省值：optimize_size<false>.

avl_set, avl_multiset and avltree containers

avl_set, avl_multiset 和 avltree 容器

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:
這些容器接受在如何使用 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.)
base_hook<class Hook> / member_hook<class T, class Hook, Hook T::* PtrToMember> / value_traits<class ValueTraits>: 指定用於配置容器的鉤子類型或 value traits。(要學習有關 value traits 的知識，請見帶定制化 ValueTraits 的容器)
constant_time_size<bool Enabled>: To activate the constant-time size() operation. Default: constant_time_size<true>
constant_time_size<bool Enabled>: 激活常量時間的 size() 操作。缺省值：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>
size_type<bool Enabled>: 指定用於保存容器大小的類型。缺省值：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> >
compare<class Compare>: 被插入到容器中的對象所用的比較函數。這個比較函數必須實現一個嚴格弱序。缺省值：compare< std::less<T> >

Example 例子

Now let's see a small example using both hooks and avl_set/ avl_multiset containers:
現在我們來看一個使用鉤和 avl_set/ avl_multiset 容器的小例子：

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