Объявление контейнеров

Для объявления multi_index контейнера используется шаблон boost::multi_index_container, имеющий три аргумента:

• Тип элемента в контейнере
• (необязательно) Описание индексов контейнера
• (необязательно) Аллокатор, для элементов контейнера

Для описания индексов контейнера используется шаблон boost::multi_index::indexed_by, принимающий в качестве аргументов список индексов, необходимых контейнеру.

Таким образом, описание multi_index контейнера принимает следующую форму:

boost::multi_index_container < ElementType, boost::multi_index::indexed_by < > >

В библиотеке поддерживаются следующие типы индексов:

• Упорядоченные (ordered)
• Хэш (hashed)
• Последовательные (sequenced)

Упорядоченные индексы

Упорядоченные индексы используются для доступа к элементам, выстроенным в каком-то определенном порядке, аналогично контейнеру std::map. Они практически полностью повторяют его интерфейс, за исключением некоторых незначительных ограничений.

Упорядоченные индексы подразделяются на уникальные и неуникальные, разница между которыми состоит в возможности хранения в контейнере нескольких элементов с одинаковым значением ключа.

Упорядоченные индексы обьявляются одним из следующих вариантов:

• (ordered_unique | ordered_non_unique)

<[(tag)[,(key extractor)[,(comparison predicate)]]]>

• (ordered_unique | ordered_non_unique)

<[(key extractor)[,(comparison predicate)]]>

Необязательный параметр tag используется для более удобного доступа к индексам в контейнере. В качестве значения параметра должен выступать предикат boost::multi_index::tag, с одним параметром - именем типа.

Если параметр указан, то для получения индекса из контейнера можно использовать не только его порядковый номер, но также и имя типа, переданного в tag.

Значением параметра key extractor является предикат, специфицирующий получение значения ключа по значению элемента контейнера. Наиболее часто используемые предикаты это:

• identity<ElementType> - в качестве ключа используется весь элемент контейнера. Параметр – тип элемента в контейнере.
• member<ElementType,KeyType,MemberPtr> - в качестве ключа используется какой-либо член элемента контейнера. Параметры – тип элемента, тип ключа и указатель на значение ключа в структуре элемента.
• const_mem_fun<ElementType,KeyType,MemberFunPtr> - в качестве ключа используется значение какого-либо константного метода элемента. Параметры – тип элемента, тип ключа и указатель на метод получения ключа в элементе.

Значением параметра comparsion predicate является предикат сравнения ключей, который должен упорядочивать ключи, аналогично std::less или std::greater.

Примеры задания упорядоченных индексов:

ordered_unique<identity<employee> >
ordered_non_unique<member<employee,std::string,&employee::name>,std::greater<std::string> >

Хэш индексы

Хэш индексы, так же как и упорядоченные индексы реализуют доступ к элементу по ключу. Их основное отличие от упорядоченных индексов состоит в том, что они не хранят какой-либо информации о порядке, однако их использование для получения элементов по значению ключа может быть значительно эффективней.

Также, как и упорядоченные, хэш индексы подразделяются на уникальные и неуникальные и могут быть описаны следующим образом:

• (hashed_unique | hashed_non_unique)

<[(tag)[,(key extractor)[,(hash function)[,(equality predicate)]]]]>

• (hashed_unique | hashed_non_unique)

<[(key extractor)[,(hash function)[,(equality predicate)]]]>

Параметры tag и key extractor полностью аналогичны тем, что используются в упорядоченных индексах и были описаны выше. Хэш функция – основа возможностей быстрого поиска в хэш индексах. Это должен быть предикат, возвращающий значение std::size_t и принимающий один аргумент – значение ключа. В идеале, каждый ключ должен преобразовываться в уникальное значение, но в реальности ( в общем случае ) это невозможно. Поэтому, хорошая хэш функция должна обеспечивать быстрое преобразование ключа с максимально близкой к нулю вероятностью коллизии. Эта вероятность зависит от статистики ключей в конкретном приложении, поэтому невозможно предоставить такую функцию, которая давала бы оптимальные результаты всегда. Однако, значение параметра по умолчанию обеспечивает достаточно неплохие результаты работы в большинстве случаев. Последний параметр – предикат равенства для ключей. Он определяет какие ключи считать идентичными. В большинстве случаев, значение по умолчанию

std::equal_to<KeyFromValue::result_type>

обеспечивает именно то, что требуется.

Последовательные индексы

В отличие от упорядоченных и хэш индексов, элементы в последовательных индексах не предполагают какого-либо устойчивого порядка: элементы могут быть размещены в любой позиции, аналогично интерфейсу std::list.

Практически все операции, допустимые с std::list, допустимы и с последовательными индексами. Отличие состоит в том, что итераторы последовательных индексов не предоставляю возможности изменения значения элементов.

Последовательные индексы объявляются следующим образом:

sequenced<[(tag)]>

Необязательный параметр tag обозначает таг, используемый для доступа к индексам, и уже был описан выше.

Использование контейнеров

После обьявления контейнера, доступ к его индексам можно получить через метод get<Param>(), где шаблонный параметр это или порядковый номер индекса в контейнере, или имя типа, используемое в таге индекса.

Интерфейс, предоставляемый индексами практически полностью аналогичен интерфейсу соответствующих STL контейнеров.

Для доступа к типам индексов и их итераторов в контейнере используются следующие типы, вложенные в boost::multi_index_container:

template<int N>
struct nth_index {typedef implementation defined type;};

template<typename Tag>
struct index {typedef implementation defined type;};

template<int N>
struct nth_index_iterator {typedef implementation defined type;};

template<typename Tag>
struct index_iterator  {typedef implementation defined type;};

template<typename Tag>
struct index_const_iterator {typedef implementation defined type;};

Специальные операции поиска

Дополнительно к стандартным операциям поиска в соответствующих STL контейнерах, boost::multi_index предоставляет следующие операции в упорядоченных индексах:

• lower_bound – итератор на первый элемент, с переданным значением ключа
• upper_bound – итератор на следующий за последним элементом, с переданным значением ключа.
• range – пара итераторов, указывающих на начало и конец промежутка, определяемого предикатами, переданными в качестве параметров. Часто используется вместе с boost::lambda
• equal_range – пара итераторов, указывающих на начало и конец промежутка элементов, содержащих заданное значение ключа.

Примеры использования этих методов:

1. 
   using namespace boost::lambda;
   typedef multi_index_container<double>double_set;
   double_set s;
   
   ...
   
   double_set::iterator it0=s.upper_bound(100.0);
   double_set::iterator it1=s.lower_bound(200.0);
   // Промежуток [it0,it1) содержит элементы (100,200)
   

2. 
   std::pair<double_set::iterator,double_set::iterator> p=s.range(100.0<=_1,_1<=200); // 100<= x <=200
   ...
   p=s.range(100.0<_1,_1<200);   // 100 < x < 200
   ...
   p=s.range(100.0<=_1,_1<200);  // 100 <= x < 200
   

3. 
   p=s.range(100.0 <= _1,unbounded); // 100 ,= x
   p=s.range(unbounded,_1 < 200.0);  // x < 200
   p=s.range(unbounded,unbounded); // Эквиваленто std::make_pair(s.begin(),s.end())
   

Проекция итераторов

Для получения итераторов на один индекс по итераторам на другой индекс boost::multi_index предоставляет специальный метод итератора project, который принимает один шаблонный параметр – номер индекса к которому необходимо преобразовать итератор, или же его таг. Пример использования:

employee_set::iterator it2=es.project<0>( it1 ); // obtain an iterator of index #0 from it1

Записи на схожие темы

• Умные указатели в C++: boost::shared_ptr, boost::weak_ptr, boost::intrusive_ptr
• Использование контейнеров для указателей Boost Pointer Container Library

Ссылки

• http://www.boost.org/libs/multi_index/doc/index.html – родная документация на английском
• http://solarix.ru/for_developers/cpp/boost/multi_index/ru/an/multi_index.shtml – какая-то статья на русском
• Boost на русском [Ru]