Навязчивыеассоциативные контейнеры предлагают интерфейс, аналогичный ассоциативным контейнерам STL. Однако упорядоченные и неупорядоченные простые ассоциативные контейнеры STL (<std::set>,<std::multiset>,<std::unordered_set>и<std::unordered_multiset>) имеют некоторые недостатки, вызванные интерфейсом в нескольких функциях поиска, вставки или стирания (<equal_range>,<lower_bound>,<upper_bound>,<find>,<insert>,<erase>...): пользователь может работать только с<value_type>объектами или (начиная с C++11),гетерогенными поисками сравнения, которые недостаточно гибки, поскольку<key_compare>поддерживает сравнение между предоставленным ключом и<value_type>, что исключает использование определяемых пользователем объектов сравнения, которые могут разделять поиск совместимым, но продвинутым способом.

Для решения этих задачBoost.Intrusiveконтейнеры предлагают функции, в которых пользователь предоставляет ключевой тип, отличный от<key_type>, и объект сравнения. Это относится к: * equal_range * lower_bound * upper_bound * count * find * erase

Требованиями к таким функциям являются:

Подробнее см.Требуетоговорок о таких функциях в ссылке.

#include <boost/intrusive/set.hpp>
#include <boost/intrusive/unordered_set.hpp>
#include <cstring>
using namespace boost::intrusive;
// Hash function for strings
struct StrHasher
{
   std::size_t operator()(const char *str) const
   {
      std::size_t seed = 0;
      for(; *str; ++str)   boost::hash_combine(seed, *str);
      return seed;
   }
};
class Expensive : public set_base_hook<>, public unordered_set_base_hook<>
{
   std::string key_;
   // Other members...
   public:
   Expensive(const char *key)
      :  key_(key)
      {}  //other expensive initializations...
   const std::string & get_key() const
      {  return key_;   }
   friend bool operator <  (const Expensive &a, const Expensive &b)
      {  return a.key_ < b.key_;  }
   friend bool operator == (const Expensive &a, const Expensive &b)
      {  return a.key_ == b.key_;  }
   friend std::size_t hash_value(const Expensive &object)
      {  return StrHasher()(object.get_key().c_str());  }
};
// A set and unordered_set that store Expensive objects
typedef set<Expensive>           Set;
typedef unordered_set<Expensive> UnorderedSet;
// Search functions
Expensive *get_from_set(const char* key, Set &set_object)
{
   Set::iterator it = set_object.find(Expensive(key));
   if( it == set_object.end() )     return 0;
   return &*it;
}
Expensive *get_from_uset(const char* key, UnorderedSet &uset_object)
{
   UnorderedSet::iterator it = uset_object.find(Expensive (key));
   if( it == uset_object.end() )  return 0;
   return &*it;
}

// These compare Expensive and a c-string
struct StrExpComp
{
   bool operator()(const char *str, const Expensive &c) const
   {  return std::strcmp(str, c.get_key().c_str()) < 0;  }
   bool operator()(const Expensive &c, const char *str) const
   {  return std::strcmp(c.get_key().c_str(), str) < 0;  }
};
struct StrExpEqual
{
   bool operator()(const char *str, const Expensive &c) const
   {  return std::strcmp(str, c.get_key().c_str()) == 0;  }
   bool operator()(const Expensive &c, const char *str) const
   {  return std::strcmp(c.get_key().c_str(), str) == 0;  }
};
// Optimized search functions
Expensive *get_from_set_optimized(const char* key, Set &set_object)
{
   Set::iterator it = set_object.find(key, StrExpComp());
   if( it == set_object.end() )   return 0;
   return &*it;
}
Expensive *get_from_uset_optimized(const char* key, UnorderedSet &uset_object)
{
   UnorderedSet::iterator it = uset_object.find(key, StrHasher(), StrExpEqual());
   if( it == uset_object.end() )  return 0;
   return &*it;
}

Аналогичная проблема возникает с вставками в простые упорядоченные и неупорядоченные ассоциативные контейнеры с уникальными ключами<std::set>и<std::unordered_set>. В этих контейнерах, если значение уже присутствует, вставленное значение отбрасывается. С дорогими значениями, если стоимость уже присутствует, мы можем столкнуться с проблемами эффективности.

<set>и<unordered_set>-подобные контейнеры имеют функции вставки<insert_check>,<insert_unique_check>, ...) для эффективной проверки, без построения значения, если значение присутствует или нет, и если оно отсутствует, функция для его немедленной вставки (54) без какого-либо дальнейшего поиска. Требования к функциям, которые проверяют наличие такого значения:

В общем,<insert_check>похоже на нормальное<insert>, но:

Эти функции должны использоваться с осторожностью, никакая другая вставка или стирание не должны выполняться между<insert_check>и<insert_commit>парой. В противном случае поведение не определено.

См.<set>и<unordered_set>-подобные ссылки контейнеров для получения дополнительной информации о<insert_check>и<insert_commit>.

При множественных упорядоченных и неупорядоченных ассоциативных контейнерах<multiset>и<unordered_multiset>нет необходимости в этих расширенных функциях вставки, поскольку вставки всегда успешны.

// Insertion functions
bool insert_to_set(const char* key, Set &set_object)
{
   Expensive *pobject = new Expensive(key);
   bool success = set_object.insert(*pobject).second;
   if(!success)   delete pobject;
   return success;
}
bool insert_to_uset(const char* key, UnorderedSet &uset_object)
{
   Expensive *pobject = new Expensive(key);
   bool success = uset_object.insert(*pobject).second;
   if(!success)   delete pobject;
   return success;
}

// Optimized insertion functions
bool insert_to_set_optimized(const char* key, Set &set_object)
{
   Set::insert_commit_data insert_data;
   bool success = set_object.insert_check(key, StrExpComp(), insert_data).second;
   if(success) set_object.insert_commit(*new Expensive(key), insert_data);
   return success;
}
bool insert_to_uset_optimized(const char* key, UnorderedSet &uset_object)
{
   UnorderedSet::insert_commit_data insert_data;
   bool success = uset_object.insert_check
      (key, StrHasher(), StrExpEqual(), insert_data).second;
   if(success) uset_object.insert_commit(*new Expensive(key), insert_data);
   return success;
}

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

Примечание:Эти функциине проверяют предварительные условия, поэтому они должны использоваться с осторожностью. Это низкоуровневые операции, которыеразбивают инварианты контейнера, если предварительные условия заказа и уникальности не обеспечены абонентом.

Давайте посмотрим пример:

#include <boost/intrusive/set.hpp>
#include <vector>
#include <functional>
#include <cassert>
using namespace boost::intrusive;
//A simple class with a set hook
class MyClass : public set_base_hook<>
{
   public:
   int int_;
   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_;  }
};
int main()
{
   //Create some ORDERED elements
   std::vector<MyClass> values;
   for(int i = 0; i < 100; ++i)  values.push_back(MyClass(i));
   {  //Data is naturally ordered in the vector with the same criteria
      //as multiset's comparison predicate, so we can just push back
      //all elements, which is more efficient than normal insertion
      multiset<MyClass> mset;
      for(int i = 0; i < 100; ++i)  mset.push_back(values[i]);
      //Now check orderd invariant
      multiset<MyClass>::const_iterator next(mset.cbegin()), it(next++);
      for(int i = 0; i < 99; ++i, ++it, ++next) assert(*it < *next);
   }
   {  //Now the correct order for the set is the reverse order
      //so let's push front all elements
      multiset<MyClass, compare< std::greater<MyClass> > > mset;
      for(int i = 0; i < 100; ++i)  mset.push_front(values[i]);
      //Now check orderd invariant
      multiset<MyClass, compare< std::greater<MyClass> > >::
         const_iterator next(mset.cbegin()), it(next++);
      for(int i = 0; i < 99; ++i, ++it, ++next) assert(*it > *next);
   }
   {  //Now push the first and the last and insert the rest
      //before the last position using "insert_before"
      multiset<MyClass> mset;
      mset.insert_before(mset.begin(), values[0]);
      multiset<MyClass>::const_iterator pos =
         mset.insert_before(mset.end(), values[99]);
      for(int i = 1; i < 99; ++i)  mset.insert_before(pos, values[i]);
      //Now check orderd invariant
      multiset<MyClass>::const_iterator next(mset.cbegin()), it(next++);
      for(int i = 0; i < 99; ++i, ++it, ++next) assert(*it < *next);
   }
   return 0;
}