Назойливые контейнеры на основе дерева Splay имеют логарифмическую сложность во многих операциях, таких как поиски, вставки, стирания и т. Д., Но если некоторые элементы чаще доступны, чем другие, деревья Splay выполняют более быстрый поиск, чем эквивалентные сбалансированные бинарные деревья (например, красно-черные деревья).

Эффект кэширования, предлагаемый сплей-деревьями, имеет свою цену: дерево должно быть сбалансировано при поиске элемента. Для поддержания правильности и гарантии безопасности потока этот эффект кэширования не обновляется, когда называются конст-версии поисковых функций, таких как<find()>,<lower_bound()>,<upper_bound()>,<equal_range()>,<count()>. Это означает, что использование ассоциативных контейнеров на основе splay-tree в качестве замены<set>/<multiset>, специально для функций поиска const, может не привести к желаемым улучшениям производительности.

Если поиск элементов рандомизирован, дерево будет постоянно уравновешено, не воспользовавшись эффектом кэша, поэтому деревья сплея могут обеспечить худшую производительность, чем другие сбалансированные деревья, для нескольких шаблонов поиска.

Навязчивыеигровые ассоциативные контейнеры используют не свои собственные типы крючков, а простые древовидные крючки для двоичного поиска.Бинарные крючки деревьев поиска: bs_set_base_hook и bs_set_member_hookраздел для получения дополнительной информации об этих крючках.

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

Также они могут получить дополнительную опцию:

Теперь рассмотрим небольшой пример с использованием контейнеров<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;
}