Все типы Boost.MultiIndex объявлены в пространстве имен boost::multi_index. Дополнительно в пространство boost включены шаблонный класс multi_index_container и глобальные функции get и project. Для краткости большинство приводимых фрагментов кода предполагают предшествующее расширение области видимости:
using namespace ::boost; using namespace ::boost::multi_index;
Введение
Мы предлагаем ознакомится с основными концепциями Boost.MultiIndex на паре простых примеров.
Проведение различных сортировок одного множества
Шаблоны STL set и multiset являются массивами переменной длины, где элементы отсортированы согласно установленному сравнительному предикату (критерию). Эти контейнерные класс немногим способны помочь программисту, когда ему необходимо сортировать и искать элементы опираясь на несколько критериев. Взгляните на пример:
struct employee
{
int id;
std::string name;
employee(int id,const std::string& name):id(id),name(name){}
bool operator<(const employee& e)const{return id<e.id;}
};
Тот факт, что ID-ключ является уникальным для каждого служащего, определяет возможность перегрузки оператора «<», что в свою очередь позволяет держать такие переменные типа employee в контейнере std::set<employee>. Теперь, если мы хотим вывести список работников в алфавитном порядке, мы столкнемся с рядом трудностей и недостатков, начиная от неразумного расходования памяти, кончая громоздкостью и ненаглядностью кода. Вот, что первое приходит в голову:
Копировать переменную типа std::set<employee> в переменную типа vector и в качестве критерия сортировки определить функтор, работающий с полем структуры name.
Хранить кроме основного массива еще массив указателей на его элементы, соответственно отсортированный по полю name.
Их этих двух решений, пожалуй, второе принимается большинством программистов, заботящимся о быстродействии, однако оно предполагает постоянно в программе «тащить» вместо одной структуры – две. Если от такого кода потребовать еще и устойчивости к исключительным ситуациям, то поддерживать такую конструкцию становится невозможным.
Boost.MultiIndex отличает от других контейнеров наличие нескольких интерфейсов доступа (индексов упорядочения), каждый из которых сортирует элементы по определенному ключу. Этот шаблон разработан, чтобы помочь в решении задач на сортировку, поиск и др. элементов более чем по одному условному критерию. Определение индексов происходит при конкретизации шаблона multi_index_container; через каждый индекс доступ и сортировка будут происходить отдельно, тогда как сами элементы будут храниться в одном и том же контейнере. Задача, поставленная в примере при помощи Boost.MultiIndex решается следующим образом:
// определение бииндексированного множества с индексацией по полям name // и ID
typedef multi_index_container<
employee,
indexed_by<
// сортировка согласно перегруженному оператору “<”
ordered_unique<identity<employee> >,
// сортировка функтором less<string> по полю name
ordered_non_unique<member<employee,std::string,&employee::name> >
>
> employee_set;
void print_out_by_name(const employee_set& es)
{
// установка доступа к элементам по первому индексу
const employee_set::nth_index<1>::type& name_index=es.get<1>();
// используйте name_index просто как std::set
std::copy(
name_index.begin(),name_index.end(),
std::ostream_iterator<employee>(std::cout));
}
Вместо единственного условного критерия сравнения, как в ассоциативных контейнерах STL, multi_index_container имеет typelist (список типов), называемый indexed_by, где конкретизируются типы, вы устанавливаете соответствующие индексы. Доступ через соответствующий индекс получается через get<N>(), где N изменяется от 0 до количества условных критериев минус один. Доступ через 0-ой индекс может осуществляется по умолчанию прямо из объекта multi_index_container без использования функции get<0>(). Например, es.begin() – то же, что и es.get<0>().begin().
Отметим, что get() возвращает ссылку на индексированное множество (будем называть множество, имеющее доступ к элементам основного массива, через один из индексов просто ИНДЕКСом) , а не объект. Индекс не может быть сконструирован в самостоятельный объект, отдельный от основного контейнера. Поэтому следующий код
// неверно: мы забыли & после employee_set::nth_index<1>::type const employee_set::nth_index<1>::type name_index=es.get<1>();
будет вызывать ошибку, поскольку здесь осуществлена попытка сделать индекс-объект name_index. Это пример типичной ошибки среди пользователей этой библиотеки.
Двунаправленный список с быстрым поиском
На этом примере мы продемонстрируем работу так называемых последовательных индексов, узнаем, как можно их совместить с индексами упорядочения для построения более функциональных контейнеров. Допустим, мы имеем текст, разбитый на слова и хранящийся в списке, вреде этого:
typedef std::list<std::string> text_container;
std::string text=
"Alice was beginning to get very tired of sitting by her sister on the "
"bank, and of having nothing to do: once or twice she had peeped into the "
"book her sister was reading, but it had no pictures or conversations in "
"it, 'and what is the use of a book,' thought Alice 'without pictures or "
"conversation?'";
// внесение текста в список, используя шаблонный токенайзер из boost
text_container tc;
boost::tokenizer<boost::char_separator<char> > tok
(text,boost::char_separator<char>(" \t\n.,;:!?'\"-"));
std::copy(tok.begin(),tok.end(),std::back_inserter(tc));
//Если мы хотим посчитать, сколько раз слово включено в список, мы воспользуемся std::count:
std::size_t occurrences(const std::string& word)
{
return std::count(tc.begin(),tc.end(),word);
}
Однако исполнение такого алгоритма будет происходить за линейное время, что может быть неприемлемо в случае больших количеств текста. Аналогично, операция удаления слова из середины списка по времени также весьма затратна в std::list:
void delete_word(const std::string& word)
{
tc.remove(word); // scans the entire list looking for word
}
Если необходимо представление списка, к примеру, в алфавитном порядке, нам снова необходимо заводить отдельную структуру, индексирующую элементы в tc. Boost.MultiIndex делает это просто комбинируя последовательный и порядковый индексы:
// объявление multi_index_container со «списковым» индексом и порядковым
// индексом
typedef multi_index_container<
std::string,
indexed_by<
sequenced<>, // «списковый» индекс
ordered_non_unique<identity<std::string> > // слова в алфавит. Порядке
>
> text_container;
std::string text=...
// внесение текста в список
text_container tc;
boost::tokenizer<boost::char_separator<char> > tok
(text,boost::char_separator<char>(" \t\n.,;:!?'\"-"));
std::copy(tok.begin(),tok.end(),std::back_inserter(tc));
До сих пор, замена std::list на multi_index_container не давала особых преимуществ. Код для вставки текста в контейнер не изменился, поскольку последовательный индекс предоставляет интерфейс доступа, полностью аналогичный таковому у std::list (нет необходимости обращаться к этому индексу через get<0>(), поскольку, как было сказано выше, multi_index_container наследует весь интерфейс своего нулевого индекса.) Однако введение дополнительного порядкового индекса позволит нам выполнять процедуры подсчета слов и удаления слов более эффективно:
std::size_t occurrences(const std::string& word)
{
// устанавливаем доступ через №1 индекс
text_container::nth_index<1>::type& sorted_index=tc.get<1>();
// используем sorted_index просто как std::set
return sorted_index.count(word);
}
void delete_word(const std::string& word)
{
// устанавливаем доступ через №1 индекс
text_container::nth_index<1>::type& sorted_index=tc.get<1>();
// используем sorted_index просто как std::set
sorted_index.erase(word);
}
Теперь процедуры occurrences и delete_word выполняются за логарифмическое время. Программист может использовать №0 индекс для доступа к исходному тексту (как std::list) или использовать №1 индекс, когда необходим логарифмический поиск.
Определение индексов
Индексы в конкретизации multi_index_container объявляются внутри специальной конструкции indexed_by. Например, конкретизация:
typedef multi_index_container< employee, indexed_by< ordered_unique<identity<employee> >, ordered_non_unique<member<employee,std::string,&employee::name> > > > employee_set; включает уникальный порядковый индекс и неуникальный порядковый индекс, а, следующим кодом: typedef multi_index_container< std::string, indexed_by< sequenced<>, ordered_non_unique<identity<std::string> > > > text_container;
мы установили два индекса, первый последовательного типа, а второй – неуникальный порядковый индекс. В общем случае мы можем объявлять произвольное число индексов: каждый аргумент конструкции indexed_by называется спецификатором индекса. В зависимости от типа индекса, объявление соответствующего спецификатора будет требовать дополнительной информации: например, спецификаторы ordered_unique и ordered_non_unique требуют указания ключевого поля и (необязательно) сравнительного условного предиката; вместе они полностью определяют, как будет производиться сортировка.
конкретизация multi_index_container может быть объявлена без конструкции indexed_by: в таком случае индексация по умолчанию производится таким образом, что конкретизированный шаблон эквивалентен конкретизированному std::set. Если конкретно - конкретизация
multi_index_container<(element)> аналогична multi_index_container< (element), indexed_by< ordered_unique<identity<(element)> > > >
Метки
С целью получения доступа к индексу данного multi_index_container, программист должен помнить порядковый номер этого индекса в списке indexed_by. Однако такое обращение к индексу является неуклюжим и ненаглядным, поэтому в спецификатор индекса введен такой (необязательный) параметр, как метка (tag). Она всегда ставится первым параметром в соответствующем спецификаторе. Вот как будет выглядеть наш тип employee_set с использованием меток:
// метки
struct name{};
typedef multi_index_container<
employee,
indexed_by<
ordered_unique<identity<employee> >,
ordered_non_unique<tag<name>,member<employee,std::string,&employee::name> >
>
> employee_set;
Метка должна быть описана внутри конструкции tag. Любой тип может быть использован в качестве метки индекса, хотя, в основном, выбирают названия, которые так или иначе описывают индекс. Вызов соответствующего индекса по метке выглядит так:
typedef employee_set::index<name>::type employee_set_by_name; employee_set_by_name::iterator it=es.get<name>().begin();
Если метка для индекса не определена (как в случае №0 индекса в предыдущем примере), доступ к данному индексу предоставляется только по его номеру. Отметим, что typedef-конструкции для получения доступа к индексу через номер и через метку различны. Например:
// тип переменной доступа к индексу #1, employee_set::nth_index<1>::type // тип переменной доступа к индексу, меченному name (в данном случая эти два определения эквивалентны) employee_set::index<name>::type
Наоборот, метод get() перегружен и используется одинаково в обоих случаях:
employee_set::index<name>::type& name_index=es.get<name>(); employee_set::nth_index<1>::type& name_index2=es.get<1>(); // тот же индекс
К тому же шаблон класса tag может получать в качестве параметров несколько меток для одного индекса: например, спецификация №1 индекса в предыдущем примере может быть переписана с использованием двух различных меток name и by_name:
// метки
struct name{};
struct by_name{};
typedef multi_index_container<
...
ordered_non_unique<
tag<name,by_name>,
member<employee,std::string,&employee::name>
>
...
> employee_set;
Типы индексов
В настоящее время Boost.MultiIndex имеет следующие типы индексов:
Порядковые индексы сортируют элементы как std::set-ы и предоставляют аналогичный интерфейс. Они могут быть двух вариантов: уникальные и неуникальные; первые не позволяют хранить идентичные элементы, тогда как вторые – позволяют (как std::multiset)
Последовательные индексы разработаны по образу и подобию std::list : они хранят элементы аналогично двунаправленному списку.
Пример во введении демонстрирует использование всех видов индексов.
Порядковые индексы
Порядковые индексы сортируют элементы multi_index_container согласно заданному ключевому полю и заданному сравнительному предикату. Доступ через эти индексы аналогичен работе с контейнерами std::set, и более того – полностью копируют их интерфейс, хотя присутствуют некоторые небольшие отличия, диктуемые общими принципами Boost.MultiIndex.
Уникальный и неуникальный варианты
Последовательные индексы могут быть описаны как уникальные, тогда они запрещают наличие двух элементов с одинаковыми значениями ключевого поля, и неуникальные, которые это позволяют. Посмотрим снова на инсталляцию
typedef multi_index_container< employee, indexed_by< ordered_unique<identity<employee> >, ordered_non_unique<member<employee,std::string,&employee::name> > > > employee_set;
Первый индекс объявлен как уникальный (поскольку поле ID уникально для каждого рабочего) и поэтому описан как тип ordered_unique, тогда как второй индекс неуникален (поскольку два Джона Смита могут служить в одной компании) и соответственно описан как ordered_non_unique.
Разделение порядковых индексов на уникальный и неуникальные влияет на то, какие элементы можно вставлять в multi_index_container. Короче включение через уникальный порядковый индекс проходит аналогично включению в std::set, тогда как через неуникальный – аналогично std::multiset. Например, employee_set может содержать структуры employee(0, “George Brown”) и employee(1, “George Brown”), но добавить структуру с таким же ID, какой там уже имеется, нельзя.
В конкретизации multi_index_container может быть объявлено несколько уникальных индексов. Например, если мы собираем данные об ИНН работников, который также уникален, мы можем организовать контейнер таким образом:
struct employee
{
int id;
std::string name;
int ssnumber;
employee(int id,const std::string& name,int ssnumber):
id(id),name(name),ssnumber(ssnumber){}
bool operator<(const employee& e)const{return id<e.id;}
};
typedef multi_index_container<
employee,
indexed_by<
// сортировать по employee::operator<
ordered_unique<identity<employee> >,
// сортировать согласно less<string> по полю name
ordered_non_unique<member<employee,std::string,&employee::name> >,
// сортировать согласно less<int> по полю ssnumber
ordered_unique<member<employee,int,&employee::ssnumber> >
>
> employee_set;
Спецификация индексов
Синтаксис спецификатора порядкового индекса в поле шаблона indexed_by выглядит следующим образом:
(ordered_unique | ordered_non_unique) <[(tag)[,(key extractor)[,(comparison predicate)]]]> (ordered_unique | ordered_non_unique) <[(key extractor)[,(comparison predicate)]]>
Первый необязательный аргумент используется, когда индексу приписывается метка. Сейчас мы немного поговорим об остальных двух.
Ключевое поле
Первым параметром шаблона спецификации индекса (или второй, если есть метка) является ключевое поле. Этот параметр передает ссылку на элемент (в нашем примере на всю структуру employee) и частично информацию о способе сортировки таких элементов. Вот основные варианты определения ключевого поля:
Целый элемент служит ключом, как в случае первого индекса в employee_set. А для определения ключевого поля можно использовать; identity как раз используется, когда ключом является целый объект.
Сравнение осуществляется по отдельному полю структуры элемента – это очень напоминает работу с индексами отдельной колонки реляционной базы данных. Boost.MultiIndex имеет шаблон member, который возвращает ключ на поле структуры, определяемое указателем
В качестве примера снова рассмотри наш employee_set. Первый индекс:
ordered_unique<identity<employee> >
определяется при помощи identity, причем объект элемента выступает в качестве ключа. Теперь посмотрим на второй индекс:
ordered_non_unique<member<employee,std::string,&employee::name> >
Здесь мы используем шаблон member, чтобы определяем (извлекаем) ключ из поля структуры employee. Тип этого ключа – std::string.
Другой общий случай – когда сортировка производится по заданной функции-члену класса элемента. Это напоминает случай вычисляемого индекса в некоторых реляционных БД. В таких случаях ключ не является переменной-членом структуры элемента, а получает значение из заданной функции-члена. Boost.MultiIndex поддерживает такой механизм «извлечения» ключа посредством шаблона const_mem_fun. Рассмотрим расширение нашего примера, когда сортировка по третьему индексу проводится на основе длины поля name:
struct employee
{
int id;
std::string name;
employee(int id,const std::string& name):id(id),name(name){}
bool operator<(const employee& e)const{return id<e.id;}
// возвращает длину поля name
std::size_t name_length()const{return name.size();}
};
typedef multi_index_container<
employee,
indexed_by<
// сортировать согласно employee::operator<
ordered_unique<identity<employee> >,
// сортировать согласно less<string> по полю name
ordered_non_unique<member<employee,std::string,&employee::name> >,
// сортировать согласно less<int> по ключу name_length()
ordered_non_unique<
const_mem_fun<employee,std::size_t,&employee::name_length>
>
>
> employee_set;
Пример 2 в разделе примеров содержит законченную программу, демонстрирующую использование const_mem_fun. Почти всегда, используются именно константные функции-члены, поскольку в multi_index_container-е (как и в std::set-е) элементы предполагаются постоянными. Однако шаблон mem_fun предоставляет вам возможность использовать неконстантные функции-члены. Их использование и применение подробно обсуждено в параграфе о дополнительных характеристиках ключевых полей Boost MultiIndex в разделе дополнительной информации.
Более сложные типы контейнеров могут потребовать сложных ключей, собирающих информацию сразу от нескольких ключевых полей. Сложные ключи введены в Boost.MultiIndex при помощи конструкции composite_key.
identity, member и const_mem_fun (или их комбинации при помощи composite_key) наиболее часто используемые шаблоны, используемые для разработки multi_index_container-ов. Однако пользователь имеет возможность написать собственную процедуру «извлечения» ключа для более экзотических ситуаций, чем те, которые предполагает данная концепция. В примере №6 демонстрируется использование нескольких технологий «извлечения» ключа, которые необходимы когда доступ к элементам и/или ключам осуществляется через указатели.
Условные предикаты сравнения
И наконец, последнее поле спецификатора порядкового индекса – это предикат (критерий) сравнения, который представляет из себя оператор «меньше» (на деле – функтор), определенных для типа ключа. Этот критерий не отличается от таковых, использующихся в контейнерах STL, таких как std::set. По умолчанию (если поле предиката в спецификаторе не заполнено), индекс с ключом типа key_type сортирует элементы согласно функтору std::less<key_type>. Если требуется определить какой-то другой критерий сравнения, ссылка на него дается в конце объявления индекса:
// определяет полииндексированное множество с индексами по id и name // в обратном алфавитном порядке typedef multi_index_container< employee, indexed_by< ordered_unique<identity<employee> >, // обычный индекс ordered_non_unique< member<employee,std::string,&employee::name>, std::greater<std::string> //по умолчанию std::less<std::string> > > > employee_set;
Специальные функции поиска
Наличие порядкового индекса позволяет проводить поиск элементов согласно определенному для этого индекса ключу. Например, чтобы найти Веронику Круз в employee_set вы можете написать:
employee_set es;
...
typedef employee_set::index<name>::type employee_set_by_name;
employee_set_by_name::iterator it=es.get<name>().find("Veronica Cruz");
Кроме того, Boost.MultiIndex предоставляет специальные операции поиска, который ведется по ключу, отличному по типу от key_type-а нашего индекса. Это оказывается чрезвычайно полезным, когда затратно создавать переменные типа key_type. Последовательные контейнеры STL не имеют аналогичных возможностей, поэтому приходится прибегать к неэлегантным обходным путям. Например, рассмотрим задачу определения рабочих, чьи ID лежат в промежутке [0,100]. Принимая во внимание, что ключ индекса №0 это сам элемент employee, можем для начала написать следующее:
employee_set::iterator p0=es.lower_bound(employee(0,"")); employee_set::iterator p1=es.upper_bound(employee(100,""));
Однако помните, что std::less<employee> в действительности сравнивает ID рабочих, поэтому более уместно было бы запретить создание структуры employee целиком, а извлекать только их ID. Boost.MultiIndex предлагает для этой цели определить другой критерий-функтор:
struct comp_id
{
// compare an ID and an employee
bool operator()(int x,const employee& e2)const{return x<e2.id;}
// compare an employee and an ID
bool operator()(const employee& e1,int x)const{return e1.id<x;}
};
и написать теперь уже:
employee_set::iterator p0=es.lower_bound(0,comp_id()); employee_set::iterator p1=es.upper_bound(100,comp_id());
Здесь в ходе поиска мы не просто перебираем ID элементов вместо перебор целых employee-структур, мы создаем новый критерий поиска. В общем, если мы хотим перегрузить критерии поиска, мы должны позаботиться об их совместимости. Если не прибегать к строгим определениям (а их вы можете найти в главе «MultiIndex: Руководство»), то критерии называются совместимыми, когда любая последовательность, отсортированная по одному из них также отсортирована и по другому. Вот более интересный пример сортировки:
// сортировка по инициалам
struct comp_initial
{
bool operator()(char ch,const std::string& s)const{
if(s.empty())return false;
return ch<s[0];
}
bool operator()(const std::string& s,char ch)const{
if(s.empty())return true;
return s[0]<ch;
}
};
// получение первого рабочего с именем на 'J' (сортировка по имени)
typedef employee_set::index<name>::type employee_set_by_name;
employee_set_by_name& name_index=es.get<name>();
employee_set_by_name::const_iterator it=
name_index.lower_bound('J',comp_initial());
Получение диапазонов
Диапазонный поиск, то есть поиск всех элементов данного интервала – очень частая операция, для которой стандартные lower_bound и upper_bound могут быть использованы, разве что в простейших случаях. Например, этот код отбирает элементы multi_index_container<double>, расположенные в интервале [100; 200]:
typedef multi_index_container<double> double_set; // напомним, что параметры при конркретизации по умолчанию: // multi_index_container<double,indexed_by<unique<identity<double> > > >. double_set s; ... double_set::iterator it0=s.lower_bound(100.0); double_set::iterator it1=s.upper_bound(200.0); // диапазон [it0,it1) содержит элементы [100,200]
Небольшие изменения в код следует внести, если мы хотим сделать одну из границ интервала нестрогой. Если мы, к примеру, ищем элементы интервала (100, 200), то писать надо так:
double_set::iterator it0=s.upper_bound(100.0); double_set::iterator it1=s.lower_bound(200.0); // диапазон [it0,it1) содержит элементы (100;200)
Чтобы внести в код такое усложнение, аккуратный программист обязан принимать во внимание, что верхняя и нижняя границы интервала – вещи нестрогие. Если, к примеру, нижняя грань 200, а верхняя – 100, итераторы it0 и it1, определенные в порядке, обратном приведенному, не будут охватывать никакого диапазона. При попытке пройтись в цикле по элементам от it0 до it1 вы вполне можете проворонить исключение. Эти особенности делают поиск диапазона стандартными STL функциями ненаглядным и незащищенным.
Встроенная функция range, часто в сочетании с выражениями Boost.Lambda, может сильно облегчить программирование такого рода поисков. Взгляните:
using namespace boost::lambda; typedef multi_index_container<double> double_set; double_set s; ... 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 Одна или обе границы могут быть обозначены ключевым словом unbounded (неограничен): 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())
Обновление
Встроенная функция replace выполняет замену в месте, указанном итератором:
typedef index<employee_set,name>::type employee_set_by_name;
employee_set_by_name& name_index=es.get<name>();
employee_set_by_name::iterator it=name_index.find("Anna Jones");
employee anna=*it;
anna.name="Anna Smith"; // она уже вышла за муж за К. Смита
name_index.replace(it,anna); // обновляем запись
replace-процедура имеет в данном случае ряд особенности:
Выполнение ее происходит за постоянное время, если элемент после замены остается на то же месте, относительно всех индексов; в обратном случае она происходит за логарифмическое время.
Корректность итератора и ссылки проверяется.
Вся процедура выполнена защищенной от исключений, т.е. multi_index_container остается неизменными даже в том случае, если система или пользовательский тип данных возбуждает исключение в ходе выполнения процедуры.
replace – очень полезная функция, не объявленная в стандартах STL, очень удобна как раз когда требуется надежная защита от исключительных ситуаций.
Наблюдательный читатель может заметить, что удобство процедуры replace «влетает в копеечку»: элемент копируется целиком дважды. Первый раз при получении замещающего элемента, второй – при вставлении его в контейнер. Если структура громоздка для копирования, будет выгоднее модифицировать отдельные поля элемента. Для этого в Boost.MultiIndex введен альтернативный механизм обновления – функция modify:
struct change_name
{
change_name(const std::string& new_name):new_name(new_name){}
void operator()(employee& e)
{
e.name=new_name;
}
private:
std::string new_name;
};
...
typedef employee_set::index<name>::type employee_set_by_name;
employee_set_by_name& name_index=es.get<name>();
employee_set_by_name::iterator it=name_index.find("Anna Jones");
name_index.modify(it,change_name("Anna Smith"));
Функция Modify получает на вход функтор (или указатель на функцию), который модифицирует элемент, тем самым, избавляя программиста от необходимости создавать лишнюю структуру, как это нужно было бы в случае replace. Так же, как и replace, эта функция хорошо защищена и сохраняет информацию контейнера при сбоях. Однако механизм ее действия не полностью аналогичен механизму replace. Рассмотрим, что происходит, если в результате замены возникает повтор по уникальному индексу. В случае replace, исходное значение поля будет возвращено и функция завершится, никак не повлияв на контейнер. В случае modify, такой возможности у функции нет, поэтому ошибочный элемент, появившийся в результате модификации, будет немедленно удалее, а функция вернет false. Это различие необходимо должно учитываться программистом при выборе между функциями replace и modify.
Аналогично modify, объявлена функция для модификации ключевого поля -- modify_key. В таком случае модифицирующий функтор получает ссылку на поле key_value элемента контейнера, а не на весь элемент. Обратите внимание, что такие модификации возможны (разумеется, иначе никак), только в том случае, когда ключ не извлекается специальными процедурами (как const_mem_fun), а получается прямо из поля структуры элемента
struct change_str
{
change_str(const std::string& new_str):new_str(new_str){}
// работает со строкой, не со структурой employee
void operator()(std::string& str)
{
str=new_str;
}
private:
std::string new_str;
};
...
typedef employee_set::index<name>::type employee_set_by_name;
employee_set_by_name& name_index=es.get<name>();
employee_set_by_name::iterator it=name_index.find("Anna Jones");
name_index.modify_key(it,change_str("Anna Smith"));
Точно так же, как и modify, modify_key удаляет элемент, если результат модификации вызывает противоречие в каком-то из индексов. Modify и modify_key позволяют использование удобного синтаксиса Boost.Lambda в указании модификаторов:
using namespace boost::lambda;
typedef employee_set::index<name>::type employee_set_by_name;
employee_set_by_name& name_index=es.get<name>();
employee_set_by_name::iterator it=name_index.find("Anna Jones");
name_index.modify_key(it,_1="Anna Smith");
Последовательные индексы
В отличие от порядковых индексов, последовательные индексы не имеют фиксированного правила следования элементов – наоборот, элементы могут быть помещены в любую точку последовательности (как в std::list). Интерфейс последовательных индексов, соответственно задуман очень похожим на std::list, по крайней мере, все функции std::list здесь продублированы. Их реализация может быть слегка отличной по аргументам и/или семантике, дабы удовлетворять единой концепции Boost.MultiIndex. В частности, имеется существенное ограничение в доступе к элементам через последовательный индекс: изменение элементов multi_index_container через итератор запрещено:
multi_index_container< int, indexed_by<sequenced<> > > s; // контейнер-список s.push_front(0); *(s.begin()) = 1; // ERROR: элементы нельзя изменять ТАК
Получается, что итераторы последовательного индекса (в действительности, любого индекса) указывают на константные элементы. Это ограничение может показаться странным, однако оно продиктовано принципами работы multi_index_container-а. Если мы позволим изменять элементы таким образом, мы можем нарушить целостность других индексов контейнера. Изменение элементов может быть осуществлено только посредством функций обновления.
Если в нашем multi_index_container-е есть два или более индексов, один из которых последовательный, при вставлении элемента посредством любого непоследовательного индекса, элемент автоматически добавляется в конец последовательного. Пример поможет вам понять это:
multi_index_container< int, indexed_by< sequenced<>, // последовательный тип ordered_unique<identity<int> > // дополнительный день > > s; s.get<1>().insert(1); // вставка «1» посредством индекса #1 s.get<1>().insert(0); // вставка «0» посредством индекса #1 // список элементов, упорядоченных по индексу #0 std::copy(s.begin(),s.end(),std::ostream_iterator<int>(std::cout)); // результат: 1 0
Таким образом, последовательные индексы располагают элементы в порядке их вставления, даже если вставка производилась посредством непоследовательного индекса.
Спецификация
Последовательные индексы описываются при помощи шаблона sequenced:
sequenced<[(tag)]>
Параметр tag является необязательным.
Функции списка
Как было отмечено ранее, последовательные индексы довольно точно копируют интерфейс std::list (большинство функций практически идентичны). Однако семантика и внутренняя организация таких процедур совпадает далеко не всегда. Еще раз повторим, что эти отличия диктуются тем, что вставка элемента может повлечь за собой разрушение внутренней структуры других индексов multi_index_container. Для более подробной информации смотрите руководство.
Обновление
Так же, как и порядковые индексы, последовательные индексы предоставляют аналогичные функции modify и replace. Однако аналога modify_key нет, поскольку порядковые индексы не имеют ключа.
Проекция итераторов
Если в нашем multi_index_container-е определены два индекса i1 и i2, то при помощи функции project можно получить значение i1-итератора некоего элемента по известному i2-итератору того же элемента. Эта процедура позволяет программисту быстро перемещаться между различными индексами multi_index_container-а. Рассмотрим пример:
typedef employee_set::index<name>::type employee_set_by_name;
employee_set_by_name& name_index=es.get<name>();
// Список работников, упорядоченных по ID, начиная с ID Роберта Брауна
employee_set_by_name::iterator it1=name_index.find("Robert Brown");
// получение итератора по 0-индексу из it1
employee_set::iterator it2=es.project<0>(it1);
std::copy(it2,es.end(),std::ostream_iterator<employee>(std::cout));
Чуть более сложный пример:
text_container tc;
// доступ к элементам через #1 (индекс, упорядоченный по словам)
text_container::nth_index<1>::type& sorted_index=tc.get<1>();
// вставка "older" после каждой из "sister"
text_container::nth_index_iterator<1>::type it1=
sorted_index.lower_bound("sister");
while(it1!=sorted_index.end()&&*it1=="sister"){
// преобразование итератора в итератор последовательного индекса
text_container::iterator it2=tc.project<0>(it1);
tc.insert(it2,"older");
++it1;
}
При необходимости может быть использован в сочетании с tags.
Безопасность и дополнительные возможности
multi_index_container предосталяет дополнительные возможности и гарантирует определенный уровень безопасности, как это делает STL. Обращение к элементам через итераторы защищено в смысле операций вставки, замены и редактирования элементов.
Конкретизация multi_index_container может быть проведена абсолютно аналогично std::set, std::multiset и (с небольшими ограничениями) std::list, см. дополнительные вопросы. Эта аналогия продолжается не только на синтаксис, но и на эффективность выполнения операций. Для получения дополнительной информациии касательно дополнительных функций смотри руководство. Для получения данных о производительности multi_index_container - смотрите презентацию.
P.S.: ... Нагло утянуто отсюда: BOOST C++: Multi_Index
Ну ёлы-палы, разве так сложно в примерах кодов указывать хидеры?
ОтветитьУдалить