基于侵入式伸展树的关联容器：splay_set, splay_multiset 和 splay_tree

基于伸展树的容器的优点和缺点
splay_set, splay_multiset 和 splaytree 容器
示例

C++ 关联容器通常基于红黑树实现（例如：STL、Boost.Intrusive 关联容器）。然而，还有其他有趣的数据结构提供了一些优点（以及缺点）。

伸展树是自调整二叉搜索树，通常用于缓存、内存分配器和其他应用，因为伸展树具有“缓存效应”：最近访问的元素比访问频率较低的元素具有更好的访问时间。有关伸展树的更多信息，请参阅相应的维基百科条目。

Boost.Intrusive 提供了 3 个基于伸展树的容器：splay_set, splay_multiset 和 splaytree。前两个类似于 set 或 multiset，而后者是一个泛化，提供了插入唯一和多个键的功能。

这些容器使用 Boost.Intrusive 钩子的内存开销通常为 3 个指针。一个空的、非常量时间大小的伸展树容器也具有 3 个指针的大小。

基于伸展树的容器的优点和缺点

基于伸展树的侵入式容器在许多操作（如搜索、插入、删除等）中具有对数复杂度，但如果某些元素比其他元素更频繁地访问，则伸展树执行搜索的速度比等效的平衡二叉树（如红黑树）更快。

伸展树提供的缓存效应是有代价的：当搜索元素时，必须重新平衡树。为了保持 const 正确性和线程安全保证，当调用 const 版本的搜索函数（如 find(), lower_bound(), upper_bound(), equal_range(), count()...）时，不会更新此缓存效应。这意味着使用基于伸展树的关联容器作为 set/ multiset 的直接替代品，特别是对于 const 搜索函数，可能不会带来期望的性能提升。

如果元素搜索是随机的，树将不断地重新平衡，而无法利用缓存效应，因此对于某些搜索模式，伸展树可能比其他平衡树提供更差的性能。

Boost.Intrusive 伸展树关联容器不使用它们自己的钩子类型，而是使用普通的二叉搜索树钩子。有关这些钩子的更多信息，请参阅二叉搜索树钩子：bs_set_base_hook 和 bs_set_member_hook 部分。

splay_set, splay_multiset 和 splaytree 容器

template <class T, class ...Options>
class splay_set;

template <class T, class ...Options>
class splay_multiset;

template <class T, class ...Options>
class splaytree;

这些容器接收与如何使用 Boost.Intrusive 部分中解释的相同选项

base_hook<class Hook> / member_hook<class T, class Hook, Hook T::* PtrToMember> / value_traits<class ValueTraits>：用于指定用于配置容器的钩子类型或值特征。（要了解有关值特征的信息，请转到具有自定义 ValueTraits 的容器部分。）
constant_time_size<bool Enabled>：用于激活常量时间 size() 操作。默认值：constant_time_size<true>
size_type<typename SizeType>：用于指定将用于存储容器大小的类型。默认值：size_type<std::size_t>

并且它们还可以接收一个额外的选项

compare<class Compare>：用于容器中要插入的对象的比较函数。比较仿函数必须引起严格弱排序。默认值：compare< std::less<key_type> >
key_of_value<class KeyOfValueFunctionObject>：一个函数对象，它将定义要存储的值类型的 key_type。此类型将允许类似 map 的接口。有关详细信息，请参阅集合和多重集合的 Map 和 multimap 类接口。默认值：key_type 等于 value_type（类似集合的接口）。

示例

现在让我们看一个使用 splay_set/ splay_multiset 容器的小例子

#include <boost/intrusive/splay_set.hpp>
#include <vector>
#include <functional>

using namespace boost::intrusive;

class mytag;

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 a set using the base hook that will store values in reverse order
typedef splay_set< MyClass, compare<std::greater<MyClass> > >     BaseSplaySet;

//Define an multiset using the member hook
typedef member_hook<MyClass, bs_set_member_hook<>, &MyClass::member_hook_> MemberOption;
typedef splay_multiset< MyClass, MemberOption>   MemberSplayMultiset;

int main()
{
   typedef std::vector<MyClass>::iterator VectIt;

   //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));

   BaseSplaySet   baseset;
   MemberSplayMultiset membermultiset;


   //Insert values in the container
   for(VectIt it(values.begin()), itend(values.end()); it != itend; ++it){
      baseset.insert(*it);
      membermultiset.insert(*it);
   }

   //Now test sets
   {
      BaseSplaySet::reverse_iterator rbit(baseset.rbegin());
      MemberSplayMultiset::iterator mit(membermultiset.begin());
      VectIt it(values.begin()), itend(values.end());

      //Test the objects inserted in the base hook set
      for(; it != itend; ++it, ++rbit){
         if(&*rbit != &*it)   return 1;
      }

      //Test the objects inserted in member and binary search hook sets
      for(it = values.begin(); it != itend; ++it, ++mit){
         if(&*mit != &*it)    return 1;
      }
   }
   return 0;
}

Boost C++ 库