Обычно ключи, присвоенные индексу, основаны на переменной элемента, но могут быть определены ключевые экстракторы, которые берут свое значение из функции члена или глобальной функции. Это имеет некоторое сходство с концепциейвычисленных ключей, поддерживаемой некоторыми реляционными движками баз данных. Пример показывает, как использовать предопределенные<const_mem_fun>и<global_fun>ключевые экстракторы для решения этой ситуации.
Ключи, основанные на функциях, обычно не являются фактическими ссылками, а скорее временными значениями, возникающими в результате вызова используемой функции-члена. Это означает, что<modify_key>не может быть применено к этому типу экстракторов, что в любом случае является совершенно логическим ограничением.
Мы показываем практический пример использования<multi_index_container::ctor_arg_list>, определение и цель которого объяснены вучебнике. Программа группирует отсортированный набор чисел, основанный на идентификации через арифметику модуля, с помощью которой<x>и<y>эквивалентны, если<(x%n)==(y%n)>, для некоторых фиксированных<n>.
Этот пример показывает, как построить двунаправленную карту<multi_index_container>. Поддвунаправленной картоймы подразумеваем контейнер из<(const FromType,const ToType)>пар, так что не существует двух элементов с одним и тем же первымиливторым компонентом<std::map>только гарантирует уникальность первого компонента. Для обоих ключей предусмотрен быстрый поиск. В программе есть крошечный испанско-английский словарь с онлайн-запросом слов на обоих языках.
Эта двунаправленная карта может рассматриваться как примитивный предшественник полноценного контейнера, предоставленногоBoost.Bimap.
Сочетание секвенированного индекса с индексом типа<ordered_non_unique>дает<list>-подобную структуру с возможностями быстрого поиска. Пример выполняет некоторые операции над данным текстом, такие как подсчет слов и выборочное удаление некоторых слов.
Эта программа иллюстрирует некоторые передовые методы, которые могут быть применены для сложных структур данных с использованием<multi_index_container>. Рассмотрим класс<car_model>для хранения информации об автомобилях. При первом подходе<car_model>можно определить как:
Это определение имеет недостаток дизайна, который любой читатель, знакомый с реляционными базами данных, может легко обнаружить: Модель<manufacturer>дублируется среди всех автомобилей, имеющих одного производителя. Это пустая трата пространства и создает трудности, когда, например, название производителя должно быть изменено. Следуя обычным принципам проектирования реляционных баз данных, соответствующий дизайн включает в себя хранение изделий в отдельном<multi_index_container>и указание на них в<car_model>:
Несмотря на предопределенный рост. Экстракторы ключей MultiIndex могут обрабатывать множество ситуаций, связанных с указателями (см.расширенные функции Boost). Ключевой экстрактор MultiIndexв учебнике достаточно сложен, чтобы определить подходящий ключ-экстрактор. Следующие полезные каскады двух ключевых экстракторов:
Программа запрашивает у пользователя автопроизводителя и диапазон цен и возвращает автомодели, удовлетворяющие этим требованиям. Это сложный поиск, который не может быть выполнен на одной операции. В общих чертах, одна процедура для выполнения выбора:
Выберите элементы с данным производителем с помощью<equal_range>,
подавайте эти элементы в<multi_index_container>, отсортированные по цене,
выберите по цене с использованием<lower_bound>и<upper_bound>;
или альтернативно:
Выберите элементы в ценовом диапазоне с<lower_bound>и<upper_bound>,
подавайте эти элементы в<multi_index_container>, отсортированный производителем,
найдите элементы с данным производителем с использованием<equal_range>.
Интересная техника, разработанная на примере, заключается в построении промежуточного<multi_index_container>. Чтобы избежать копирования объектов, соответствующиевидыопределяются с<multi_index_container>s, имеющими в качестве элементов указатели на<car_model>s вместо фактических объектов. Эти точки зрения должны быть дополнены соответствующими выжимателями ключей отмены ссылок.
Конструкция Boost.MultiIndex<composite_key>предоставляет гибкий инструмент для создания индексов с нетривиальными критериями сортировки. Программа имеет рудиментарное моделирование файловой системы вместе с интерактивной Unix-подобной оболочкой. Ввод файла представлен следующей структурой:
structfile_entry{std::stringname;unsignedsize;boolis_dir;// true if the entry is a directoryconstfile_entry*dir;// directory this entry belongs in};
Записи хранятся в<multi_index_container>с двумя индексами с композитными ключами:
Первичный индекс, упорядоченный по каталогу и имени,
.. . . . . . . . . . . . . . . . . . . .
Причина, по которой порядок выполняется в первую очередь каталогом, в котором расположены файлы, подчиняется локальному характеру команд оболочки, как, например,<ls>. Моделирование оболочки имеет только три команды:
< [26] >
< [28] >< [29] >[ударная стойка]
< [32] >
Программа выходит, когда пользователь нажимает клавишу Enter в командной строке.первичный индекс, упорядоченный по каталогу и имени,
Вторичный индекс, упорядоченный по каталогу и размеру.
The reason that the order is made firstly by the directory in which
the files are located obeys to the local nature of the shell commands,
like for instance ls. The shell simulation only has three
commands:
cd [.|..|<directory>]
ls [-s]-sзаказывает выход по размеру
mkdir<directory>
The program exits when the user presses the Enter key at the command prompt.
[ORIG_END] -->
Читателю предлагается добавить больше функциональности в программу, например:
Хешированные индексы могут использоваться в качестве альтернативы упорядоченным индексам, когда требуется быстрый поиск и сортировка информации не представляет интереса. Пример имеет счетчик слов, где дублирующие записи проверяются с помощью хешированного индекса. Сравните алгоритм подсчета слов с алгоритмомпримера 5.
Типичное применение возможностей сериализации позволяет программе восстанавливать пользовательский контекст между исполнениями. Примерная программа запрашивает у пользователя слова и ведет учет десяти последних введенных, в текущей или в предыдущих сессиях. Серийизованная структура данных, иногда называемаяMRU (самый недавно используемый) список, имеет некоторый интерес сама по себе: список MRU ведет себя как обычная очередь FIFO, за исключением того, что при вставке предсуществующей записи это не появляется дважды, но вместо этого запись перемещается в переднюю часть списка. Вы можете наблюдать это поведение во многих программах с командой меню «Недавние файлы». Эта структура данных реализована с помощью<multi_index_container>путем объединения секвенированного индекса и индекса типа<hashed_unique>.
Пример возобновляет текстовый контейнер, введенный впримере 5, и показывает, как замена индекса случайного доступа секвенированным индексом обеспечивает дополнительные возможности, такие как эффективный доступ по положению и расчет смещения данного элемента в контейнер.
Существует относительно распространенное городское предание, утверждающее, что колода карт должна быть перетасована семь раз подряд, чтобы быть идеально смешанной. Заявление вытекает из работ математика Перси Диакониса оперетасовке риффлей: Эта техника перетасовки включает в себя разделение колоды на два пакета примерно одинакового размера, а затем удаление карт из обоих пакетов, чтобы они стали переплетенными. Было показано, что при повторении этой процедуры в семь раз статистическое распределение карт достаточно близко к тому, которое связано с действительно случайной перестановкой. Меру «случайности» можно оценить, посчитаввосходящие последовательности: Рассмотрим перестановку последовательности 1,2, ...,n, восходящая последовательность представляет собой максимальную цепь последовательных элементовм,м+1, ...,м+р, так что они расположены в порядке возрастания. Например, перестановка 125364789 состоит из двух восходящих последовательностей 1234 и 56789, что становится очевидным при отображении такой последовательности125364789. Среднее число восходящих последовательностей в случайной перестановкеnэлементов составляетn+1/2: напротив, после одной рифлевой перетасовки первоначально сортированной колоды карт не может быть более двух восходящих последовательностей. Среднее число восходящих последовательностей приближается кn+1/2 по мере увеличения числа последовательных риффлевых перетасовок, при этом семь перетасовок дают близкий результат для колоды покера с 52 картами. Бумага Брэда Манна«Сколько раз вы должны перетасовать колоду карт?»обеспечивает строгий, но очень доступный подход к этому вопросу.
Примерная программа оценивает среднее число восходящих последовательностей в колоде из 52 карт после повторного перетасовки риффлей, а также применения совершенно случайной перестановки. Палуба смоделирована следующим контейнером:
, где первый индекс сохраняет текущее расположение палубы, а второй индекс используется для запоминания стартового положения. Это представление позволяет эффективно реализовать алгоритм подсчета восходящих последовательностей в линейном времени.<rearrange>используется для нанесения на палубу перетасовки, выполняемой внешне на вспомогательной структуре данных.
Повышаю. MultiIndex поддерживает специальные распределители, такие как те, которые предоставляютсяBoost.Interprocess, который позволяет размещать<multi_index_container>s в общей памяти. В примере показана передняя часть небольшой базы данных книг, реализованная с помощью<multi_index_container>, хранящейся в бусте. Межпроцессная память картографированного файла. Читатель может проверить, что несколько экземпляров программы работают правильно одновременно и сразу увидеть изменения в базе данных, выполненные любым другим экземпляром.
