|
|
|
Boost.MultiIndex Documentation - Tutorial - Index typesBoost , , Boost.MultiIndex Documentation - Tutorial
|
||||||||||||||||||||
| type | specifier | |
|---|---|---|
| key-based | ordered | ordered_unique |
ordered_non_unique |
||
ranked_unique |
||
ranked_non_unique |
||
| hashed | hashed_unique |
|
hashed_non_unique |
||
| non key-based | sequenced |
|
random_access |
||
Ключевые индексы, в которых упорядоченные индексы являются обычным примером, обеспечивают эффективный поиск элементов на основе некоторой информации, называемой ключом элемента: Существует обширный наборклассов утилиты извлечения ключей, позволяющий спецификацию таких ключей. Быстрый поиск накладывает внутренний управляемый порядок на эти индексы, которые пользователю не разрешается изменять; неключевые индексы, с другой стороны, могут быть свободно перестроены за счет отсутствия средств поиска. Последовательные индексы, смоделированные по интерфейсу<std::list>, являются обычным примером неключевого индекса.
Предположим, что мы имеем<std::multiset>чисел и хотим вывести значения выше 75hпроцентиля:
typedef std::multiset<int> int_multiset; void output_above_75th_percentile(const int_multiset& s) { int_multiset::const_iterator it=s.begin(); std::advance(it,s.size()*3/4); // linear on s.size(); std::copy(it,s.end(),std::ostream_iterator<int>(std::cout,"\n")); }
Проблема с этим кодом заключается в том, что попадание в начало нужной последовательности предполагает линейное прохождение контейнера. Ранжированные индексы обеспечивают механизмы, чтобы сделать это намного быстрее:
typedef multi_index_container< int, indexed_by< ranked_non_unique<identity<int> > > > int_multiset; void output_above_75th_percentile(const int_multiset& s) { int_multiset::const_iterator it=s.nth(s.size()*3/4); // logarithmic std::copy(it,s.end(),std::ostream_iterator<int>(std::cout,"\n")); }
<nth(n)>возвращает итератор к элементу, чейранг, то есть его расстояние от начала индекса, составляет<n>, и делает это эффективно в логарифмическое время. И наоборот,<rank(it)>вычисляет в логарифмическое время ранг элемента, на который указывает<it>, или<size()>, если<it==end()>.
int_multiset::iterator it=s.insert(10).first; int_multiset::size_type r=s.rank(it); // rank of 10;
Ранжированные индексы обеспечивают тот же интерфейс, что и упорядоченные индексы, а также несколько операций, связанных с рангом. Стоимость этой дополнительной функциональности - более высокое потребление памяти из-за некоторых внутренних дополнительных данных (одно слово на элемент) и несколько более длительное время выполнения во вставке и стирании — в частности, стирание элемента занимает время, пропорциональное<log(n)>, где<n>- количество элементов в индексе, тогда как для упорядоченных индексов это время постоянно. Ссылкаподробно описывает эти показатели.
Спецификация ранжированных индексов выполняется точно так же, как супорядоченными индексами, за исключением того, что вместо них используются<ranked_unique>и<ranked_non_unique>.
(ranked_unique | ranked_non_unique) <[(tag)[,(key extractor)[,(comparison predicate)]]]> (ranked_unique | ranked_non_unique) <[(key extractor)[,(comparison predicate)]]>
Кроме<nth>и<rank>, ранжированные индексы обеспечивают функции членов
find>,<lower_bound>и т.д.), но возвращают ранги, а не итераторы.find_rank,
lower_bound_rank,upper_bound_rank,equal_range_rankиrange_rankfind, lower_bound etc.) but return ranks rather than iterators.
[ORIG_END] -->
void percentile(int n,const int_multiset& s) { std::cout<<n<<" lies in the "<< s.upper_bound_rank(n)*100.0/s.size()<<" percentile\n"; }
Вы можете подумать, что<upper_bound_rank(n)>это просто сокращение<rank(upper_bound(n))>: В действительности, однако, вы должны предпочесть использовать операции<*_rank>напрямую, поскольку они работают быстрее, чем альтернативные формулировки.
Индексы хеширования представляют собой компромисс в отношении упорядоченных индексов: при правильном использовании они обеспечивают гораздо более быстрый поиск элементов за счет потери сортировочной информации. Давайте вернемся к нашему<employee_set>примеру: предположим, что поле для хранения номера социального страхования добавлено, и необходимо, чтобы поиск по этому номеру был как можно быстрее. Вместо обычного упорядоченного индекса к хешированному индексу можно прибегнуть:
#include <boost/multi_index_container.hpp> #include <boost/multi_index/hashed_index.hpp> #include <boost/multi_index/ordered_index.hpp> #include <boost/multi_index/identity.hpp> #include <boost/multi_index/member.hpp> 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< // sort by employee::operator< ordered_unique<identity<employee> >, // sort by less<string> on name ordered_non_unique<member<employee,std::string,&employee::name> >, // hashed on ssnumber hashed_unique<member<employee,int,&employee::ssnumber> > > > employee_set
Обратите внимание, что хешированный индекс не гарантирует какого-либо конкретного заказа элементов: так, например, мы не можем эффективно запрашивать сотрудников, SSN которых больше заданного числа. Обычно вы должны учитывать эти ограничения при определении того, является ли хешированный индекс предпочтительным по сравнению с упорядоченным.
Индексы хеширования воспроизводят интерфейс как<std::unordered_set>и<std::unordered_multiset>, с незначительными различиями, когда это требуется общими ограничениями<multi_index_container>, и обеспечивают дополнительные полезные возможности, такие как обновление элементов на месте. Проверьте ссылкудля полной спецификации интерфейса хешированных индексов ипример 8ипример 9для практических применений.
Как и упорядоченные индексы, хешированные индексы имеют уникальные и неуникальные варианты, выбранные с помощью спецификаторов<hashed_unique>и<hashed_non_unique>соответственно. В последнем случае элементы с эквивалентными ключами сохраняются вместе и могут быть совместно извлечены с помощью функции<equal_range>члена.
У хешированных индексов есть два альтернативных синтаксиса, в зависимости от того, предоставляются ли теги:
(hashed_unique | hashed_non_unique) <[(tag)[,(key extractor)[,(hash function)[,(equality predicate)]]]]> (hashed_unique | hashed_non_unique) <[(key extractor)[,(hash function)[,(equality predicate)]]]>
Параметр извлечения ключа работает точно так же, как дляупорядоченных индексов; поиск, вставка и т. д. основаны на ключе, возвращенном экстрактором, а не на всем элементе.
Хэш-функция является ядром возможностей быстрого поиска этого типа индексов: хэшер — это просто унарный функциональный объект, возвращающий значение<std::size_t>для любого заданного ключа. В общем, невозможно, чтобы каждая карта ключей имела разное хеш-значение, ибо пространство ключей может быть больше, чем количество допустимых хеш-кодов: то, что делает хороший хеш-код хорошим, заключается в том, что вероятность столкновения (два разных ключа с одинаковым хеш-значением) максимально близка к нулю. Это статистическое свойство, зависящее от типичного распределения ключей в заданном приложении, поэтому невозможно иметь универсальную хеш-функцию с отличными результатами вкаждомвозможном сценарии; значение по умолчанию для этого параметра используетBoost.Hash, который часто обеспечивает достаточно хорошие результаты.
Предикат равенства используется для определения того, следует ли считать два ключа одинаковыми. Значение по умолчанию<std::equal_to<KeyFromValue::result_type>>в большинстве случаев именно то, что нужно, поэтому очень редко вам придется предоставлять свой собственный предикат. Обратите внимание, что хешированные индексы требуют, чтобы два эквивалентных ключа имели одинаковое хеш-значение, что на практике значительно снижает свободу выбора предиката равенства.
Интерфейс поиска хешированных индексов состоит из функций-членов<find>,<count>и<equal_range>. Обратите внимание, что<lower_bound>и<upper_bound>не предусмотрены, поскольку в этом типе индексов отсутствует внутреннее упорядочивание ключей.
Как и в случае с упорядоченными индексами, эти функции-члены принимают ключи в качестве аргументов поиска, а не целые объекты. Помните, что операции поиска упорядоченных индексов дополнительно увеличиваются, чтобы приниматьсовместимые ключи, которые можно примерно рассматривать как «подключи». Для хешированных индексов также поддерживается концепциясовместимого ключа, хотя его полезность гораздо более ограничена: в основном совместимый ключ является объектом, который полностью эквивалентен нативному объекту<key_type>значения, хотя, возможно, с другим внутренним представлением:
// US SSN numbering scheme struct ssn { ssn(int area_no,int group_no,int serial_no): area_no(area_no),group_no(group_no),serial_no(serial_no) {} int to_int()const { return serial_no+10000*group_no+1000000*area_no; } private: int area_no; int group_no; int serial_no; }; // interoperability with SSNs in raw int form struct ssn_equal { bool operator()(const ssn& x,int y)const { return x.to_int()==y; } bool operator()(int x,const ssn& y)const { return x==y.to_int(); } }; struct ssn_hash { std::size_t operator()(const ssn& x)const { return boost::hash<int>()(x.to_int()); } std::size_t operator()(int x)const { return boost::hash<int>()(x); } }; typedef employee_set::nth_index<2>::type employee_set_by_ssn; employee_set es; employee_set_by_ssn& ssn_index=es.get<2>(); ... // find an employee by ssn employee e=*(ssn_index.find(ssn(12,1005,20678),ssn_hash(),ssn_equal()));
В примере мы предоставили хеш-функтор<ssn_hash>и предикат равенства<ssn_equal>, позволяющий взаимодействовать между<ssn>объектами и сырыми<int>, хранящимися в<employee_set>.
Безусловно, наиболее полезное применение совместимых ключей в контексте хешированных индексов заключается в том, что они позволяют беспрепятственно использоватьсоставные ключи.
<replace>,<modify>и<modify_key>функции-члены, с той же функциональностью, что и в упорядоченных индексах.
Из-за внутренних ограничений, наложенных Ростом. Структура MultiIndex, хешированные индексы обеспечивают гарантии валидности и безопасности итератора, которые на самом деле сильнее, чем требуется стандартом C++ в отношении неупорядоченных ассоциативных контейнеров:
rehashобеспечивает безусловную гарантию безопасности. Стандарт гарантирует его только для неупорядоченных ассоциативных контейнеров, если внутренняя хеш-функция и равенство предикатов объектов не выбрасываются. Несколько удивительным последствием является то, что стандартно совместимыйstd::unordered_setможет стереть элементы, если во время перетасовки выбрасывается исключение!Индексы случайного доступа предлагают ту же функциональность, что исеквенированные индексы, с дополнительными преимуществами, что их итераторы являются случайным доступом, и<operator[]>и<at()>предоставляются для доступа к элементам на основе их положения в индексе. Давайте перепишем контейнер, используемый в предыдущем примере, используя случайный доступ вместо секвенированных индексов:
#include <boost/multi_index_container.hpp> #include <boost/multi_index/random_access_index.hpp> #include <boost/multi_index/ordered_index.hpp> #include <boost/multi_index/identity.hpp> // text container with fast lookup based on a random access index typedef multi_index_container< std::string, indexed_by< random_access<>, ordered_non_unique<identity<std::string> > > > text_container; // global text container object text_container tc;
Возможности случайного доступа позволяют нам эффективно писать код:
void print_page(std::size_t page_num) { static const std::size_t words_per_page=50; std::size_t pos0=std::min(tc.size(),page_num*words_per_page); std::size_t pos1=std::min(tc.size(),pos0+words_per_page); // note random access iterators can be added offsets std::copy( tc.begin()+pos0,tc.begin()+pos1, std::ostream_iterator<std::string>(std::cout)); } void print_random_word() { std::cout<<tc[rand()%tc.size()]; }
Эта дополнительная гибкость достигается ценой: вставки и удаления в позициях, отличных от конца индекса, имеют линейную сложность, тогда как эти операции являются постоянным временем для секвенированных индексов. Эта ситуация напоминает различия в поведении сложности между<std::list>и<std::vector>: Однако в случае индексов случайного доступа вставка и удаление никогда не сопряжены с копированием элементов, поэтому фактическое выполнение этих операций может быть приемлемым, несмотря на теоретический недостаток в отношении секвенированных индексов.
Пример 10ипример 11в разделе примеров ставят индексы случайного доступа на практике.
Индексы случайного доступа определяются конструкцией<random_access>, где параметртега, как обычно, необязателен:
random_access<[(tag)]>
Все публичные функции, предлагаемые секвенированными индексами, также обеспечиваются индексами случайного доступа, так что последние могут выступать в качестве замены первых (за исключением пределов их сложности, как объяснено выше). Кроме того, индексы случайного доступа имеют<operator[]>и<at()>для позиционного доступа к элементам, а функции-члены<capacity>и<reserve>контролируют внутреннее перераспределение таким же образом, как и омонимные средства в<std::vector>. Проверьте ссылкудля деталей.
std::vectorЗаманчиво рассматривать индексы случайного доступа как аналог<std::vector>для использования в Boost. MultiIndex, но эта метафора может вводить в заблуждение, поскольку обе конструкции, хотя и похожи во многих отношениях, показывают важные семантические различия. Преимуществом индексов случайного доступа является то, что их итераторы, а также ссылки на их элементы являютсястабильными, то есть они остаются действительными после любых вставок или удалений. С другой стороны, индексы случайного доступа имеют несколько недостатков по отношению к<std::vector>с:
std::vectorс, посредством которого элементы хранятся рядом друг с другом в одном блоке памяти.
replaceиmodify. Это исключает использование многих мутирующих алгоритмов, которые, тем не менее, применимы кstd::vector.В целом, более поучительно рассматривать индексы случайного доступа как вариацию секвенированных индексов, обеспечивающих семантику случайного доступа, вместо того, чтобы настаивать на аналогии<std::vector>.
По конструкции индексные элементы являются неизменяемыми, т.е. итераторы только предоставляют<const>доступ к ним, и только через предоставленный интерфейс обновления<replace>,<modify>и<modify_key>могут быть изменены элементы. Это ограничение устанавливается таким образом, чтобы не нарушались внутренние инварианты ключевых индексов (например, в упорядоченных индексах происходит прохождение по восходящему порядку), а вызывались важные ограничения в неключевых индексах:
typedef multi_index_container< int, indexed_by< random_access<>, ordered_unique<identity<int> > > > container; container c; std::mt19937 rng; ... // compiler error: assignment to read-only objects std::shuffle(c.begin(),c.end(),rng);
К сожалению, в предыдущем примере операция, выполняемая<std::shuffle>, потенциально совместима с<multi_index_container>инвариантами, поскольку ее результат может быть описан перестановкой элементов в индексе случайного доступа без фактических модификаций самих элементов. Есть еще много примеров таких совместимых алгоритмов в стандартной библиотеке C++, например, все функции сортировки и раздела.
Индексы последовательного и случайного доступа обеспечивают возможность использования таких внешних алгоритмов. Для того, чтобы ввести это средство, нам нужна предварительная концепция: видиндекса определяется как некоторый диапазон итераторов<first>,<last>по элементам индекса таким образом, что все его элементы содержатся в диапазоне ровно один раз. Продолжая наш пример, мы можем применить<std::random_suffle>на специальном представлении, полученном из контейнера:
// note that the elements of the view are not copies of the elements // in c, but references to them std::vector<boost::reference_wrapper<const int> > v; BOOST_FOREACH(const int& i,c)v.push_back(boost::cref(i)); // this compiles OK, as reference_wrappers are swappable std::shuffle(v.begin(),v.end(),rng);
Элементы<v>составляют<reference_wrapper>с (отBoost.Ref) до фактических элементов в многоиндексном контейнере. Эти объекты до сих пор не допускают модификации упоминаемых объектов, но они являются сменными, что является единственным требованием<std::shuffle>. После того, как у нас есть желаемая перегруппировка, сохраненная в виде, мы можем перенести ее в контейнер.
c.rearrange(v.begin());
<rearrange>принимает входной итератор, сигнализирующий о начале внешнего вида (и конечный итератор не нужен, поскольку длина вида совпадает с длиной индекса), и внутренне перемещает элементы индекса так, чтобы их порядок прохождения соответствовал виду. Хотя и с некоторыми обходами,<rearrange>позволяет применять разнообразный спектр алгоритмов к неключевым индексам. Обратите внимание, что концепция представления является очень общей и никоим образом не связана с конкретным примером реализации, показанным выше. Например, индексы<multi_index_container>действительно представляют собой мнения в отношении его неключевых индексов:
// rearrange as index #1 (ascending order) c.rearrange(c.get<1>().begin()); // rearrange in descending order c.rearrange(c.get<1>().rbegin());
Единственное важное требование, предъявляемое к взглядам, заключается в том, что они должны бытьсвободными, то есть на них не влияют перемещения по базовому индексу: таким образом,<rearrange>не принимает следующее:
// undefined behavior: [rbegin(),rend()) is not free with respect // to the base index c.rearrange(c.rbegin());
Понятие представления подробно определено в ссылке. См.пример 11в разделе примеров для демонстрации использования<rearrange>.
iterator_toВсе индексы Boost. MultiIndex обеспечивает функцию члена, называемую<iterator_to>, которая возвращает итератор к заданному элементу контейнера:
multi_index_container< int, indexed_by<sequenced<> > > c; ... // convoluted way to do c.pop_back() c.erase(c.iterator_to(c.back())); // The following, though similar to the previous code, // does not work: iterator_to accepts a reference to // the element in the container, not a copy. int x=c.back(); c.erase(c.iterator_to(x)); // run-time failure ensues
<iterator_to>обеспечивает способ извлечения итератора к элементу из указателя к элементу, таким образом делая итераторы и указатели взаимозаменяемыми для целей указания элемента (не так для обхода) во многих ситуациях. Несмотря на это, целью<iterator_to>не является содействие использованию указателей в качестве заменителей реальных итераторов: последние специально разработаны для обработки элементов контейнера и не только извлекают выгоду из ориентации итератора интерфейсов контейнера, но также способны выявлять гораздо больше ошибок программирования, чем необработанные указатели, как при компиляции, так и во время выполнения.<iterator_to>, таким образом, предназначен для использования в сценариях, где доступ через итераторы не подходит или желателен:
Упорядоченные и ранжированные индексы реализуются с помощью структуры данных, известной каккрасно-черное дерево. Узлы красного дерева содержат указатели на родительский и два детских узла, плюс 1-битное поле, называемое цветом узла(отсюда и название структуры). Из-за проблем с выравниванием на большинстве архитектур цветовое поле занимает одно целое слово, то есть 4 байта в 32-битных системах и 8 байтов в 64-битных средах. Этой пустой траты пространства можно избежать, встраивая бит цвета в один из указателей узла, при условии, что не все биты представления указателя содержат полезную информацию: это именно тот случай во многих архитектурах, где такие узлы выровнены с четными адресами, что подразумевает, что наименее значимый бит адреса всегда должен быть равен нулю.
Повышаю. Упорядоченные и ранжированные индексы MultiIndex реализуют этот тип сжатия узлов, когда это применимо. По сравнению с обычными реализациями контейнера STL<std::set>сжатие узла может привести к уменьшению перегрузки заголовка на 25% (от 16 до 12 байт на типичных 32-битных архитектурах и от 32 до 24 байт на 64-битных системах). Влияние на производительность этой оптимизации было оценено как незначительное для контейнеров среднего размера, в то время как контейнеры со многими элементами (сотни тысяч или более) работают быстрее с этой оптимизацией, скорее всего, из-за эффектов кэша L1 и L2.
Сжатие узлов может быть отключено путем глобальной настройки макроса<BOOST_MULTI_INDEX_DISABLE_COMPRESSED_ORDERED_INDEX_NODES>.
Пересмотрено 19 августа 2015
© Copyright 2003-2015 Joaquín M López Muñoz. Распространяется под лицензией Boost Software License, версия 1.0. (См. сопроводительный файлLICENSE_1_0.txtили копию на) http://www.boost.org/LICENSE_1_0.txt
Статья Boost.MultiIndex Documentation - Tutorial - Index types раздела Boost.MultiIndex Documentation - Tutorial может быть полезна для разработчиков на c++ и boost.
:: Главная :: Boost.MultiIndex Documentation - Tutorial ::
реклама |