Ассоциативные контейнеры STL имеют понятие ключа, хотя и в несколько начальной форме. Так, ключи таких контейнеров идентифицируются по вложенному типу.key_type; дляstd::setиstd::multisets,key_typeсовпадает сvalue_type, т.е. ключ является самим элементом.std::mapиstd::multimapУправление элементами типаstd::pair, где ключом является первый член. В любом случае процесс получения ключа от данного элемента неявно фиксируется и не может быть настроен пользователем.
Механизмы извлечения фиксированных ключей, подобные тем, которые выполняются ассоциативными контейнерами STL, плохо масштабируются в контексте Boost. MultiIndex, где несколько индексов разделяют их определениеvalue_type, но могут иметь совершенно другую семантику поиска. По этой причине Boost.MultiIndex формализует понятие а.Key Extractorдля того, чтобы сделать его явным и контролируемым в определении ключевых индексов.
Интуитивно говоря, экстрактор ключа является функциональным объектом, который принимает ссылку на элемент и возвращает связанный с ним ключ. Формальная концепция также накладывает некоторые разумные ограничения на стабильность процесса, в том смысле, что предполагается, что экстракторы возвращают один и тот же ключ при прохождении одного и того же элемента: это в соответствии с неформальным пониманием того, что ключи на самом деле являются некоторой «частью» элемента и не зависят от внешних данных.
Экстрактор ключа называетсяread/write, если он возвращает непостоянную ссылку на ключ при прохождении непостоянного элемента, и он называетсяread-onlyв противном случае. Повышаю. MultiIndex требует, чтобы экстрактор ключа был прочитан/записан при использованиимодифицируемой_ключафункции члена упорядоченных и хешированных индексов. Во всех других ситуациях достаточно только экстракторов для чтения.Ветхий Завет. Экстракторы ключей MultiIndexподробно описывают, какие из предопределенных экстракторов ключей читаются/записываются.
Идентификатор ключавозвращает весь базовый объект в качестве связанного ключа:
#include<boost/multi_index_container.hpp>#include<boost/multi_index/ordered_index.hpp>#include<boost/multi_index/identity.hpp>multi_index_container<int,indexed_by<ordered_unique<identity<int>// the key is the entire element>>>cont;
элементключевых экстракторов возвращает ссылку на заданное поле данных базового объекта. Например, в следующей версии нашего знакомого контейнера для сотрудников:
второй и третий индексы используютчленэкстракторы насотрудника::имяисотрудник::числосоответственно. Спецификация инстанциацииэлементапроста, но немного надумана:
member<(base type),(key type),(pointer to member)>
Может показаться, что первый и второй параметры излишни, поскольку тип базового объекта и связанного с ним поля данных уже подразумеваются в указателе на аргумент участника: к сожалению, извлечь эту информацию с помощью современных механизмов C++ невозможно, что делает синтаксисучастниканемного слишком многословным.
Иногда ключом индекса является не конкретный элемент данных элемента, а значение, возвращаемое конкретной функцией-членом. Это напоминает понятие 48 вычисленных индексов 49, поддерживаемых некоторыми реляционными базами данных. Boost.MultiIndex поддерживает этот вид извлечения ключей черезconst_mem_fun. Рассмотрим следующий контейнер, где сортировка по третьему индексу основана на длине поля имени:
#include<boost/multi_index_container.hpp>#include<boost/multi_index/ordered_index.hpp>#include<boost/multi_index/identity.hpp>#include<boost/multi_index/member.hpp>#include<boost/multi_index/mem_fun.hpp>structemployee{intid;std::stringname;employee(intid,conststd::string&name):id(id),name(name){}booloperator<(constemployee&e)const{returnid<e.id;}// returns the length of the name fieldstd::size_tname_length()const{returnname.size();}};typedefmulti_index_container<employee,indexed_by<// sort by employee::operator<ordered_unique<identity<employee>>,// sort by less<string> on nameordered_non_unique<member<employee,std::string,&employee::name>>,// sort by less<int> on name_length()ordered_non_unique<const_mem_fun<employee,std::size_t,&employee::name_length>>>>employee_set;
const_mem_fun<(base type),(key type),(pointer to member function)>
Упомянутая функция члена должна бытьconst, не принимать аргументов и возвращать значение указанного ключевого типа. Почти всегда вы захотите использовать функциюconst, поскольку элементы вmulti_index_containerрассматриваются как постоянные, так же как элементыstd::set. Однако для использования с непостоянными функциями-членами предусмотренmem_fun, применимость которого обсуждается в пунктерасширенных функций Boost. Ключевые экстракторы MultiIndex.
Пример 2в разделе примеров предоставляет полную программу, показывающую, как использоватьconst_mem_fun.
global_fun
В то время какconst_mem_funиmem_funоснованы на заданной членской функции базового типа, из которой извлекается ключ,global_funпринимает глобальную функцию (или статическую членскую функцию), принимая базовый тип в качестве своего параметра и возвращая ключ:
#include<boost/multi_index_container.hpp>#include<boost/multi_index/ordered_index.hpp>#include<boost/multi_index/global_fun.hpp>structrectangle{intx0,y0;intx1,y1;};unsignedlongarea(constrectangle&r){return(unsignedlong)(r.x1-r.x0)*(r.x1-r.x0)+(unsignedlong)(r.y1-r.y0)*(r.y1-r.y0);}typedefmulti_index_container<rectangle,indexed_by<// sort by increasing areaordered_non_unique<global_fun<constrectangle&,unsignedlong,&area>>>>rectangle_container;
global_fun<(argument type),(key type),(pointer to function)>
где тип аргумента и тип ключа должны соответствоватьточнотем, которые указаны в подписи используемой функции; например, в примере выше типа аргументаconst rectangle &, без опущения частей «const» и «&». Таким образом, хотя в большинстве случаев базовый тип будет принят путем постоянной ссылки,global_funтакже готов принять функции, принимающие их аргумент по значению или по непостоянной ссылке: этот последний случай обычно не может использоваться непосредственно в спецификацииmulti_index_containers, поскольку их элементы рассматриваются как постоянные, но раздел орасширенных функциях Boost. Экстракторы ключей MultiIndexописывают допустимые случаи использования извлечения ключей на основе таких функций с непостоянным эталонным аргументом.
Хотяпредопределенные ключевые экстракторыпредоставлены Boost. MultiIndex предназначен для обслуживания большинства случаев, пользователь также может предоставить свои собственные ключевые экстракторы в более экзотических ситуациях, если они соответствуют.Ключевой экстракторконцепция.
// some record classstructrecord{boost::gregorian::dated;std::stringstr;};// extracts a record's yearstructrecord_year{// result_type typedef required by Key Extractor concepttypedefboost::gregorian::greg_yearresult_type;result_typeoperator()(constrecord&r)const// operator() must be const{returnr.d.year();}};// example of use of the previous key extractortypedefmulti_index_container<record,indexed_by<ordered_non_unique<record_year>// sorted by record's year>>record_log;
Пример 6в разделе примеров применяет некоторые определяемые пользователем экстракторы ключей в сложном сценарии, где ключи доступны через указатели.
В реляционных базах данных составные ключи зависят от двух или более полей данной таблицы. Аналогичная концепция в Boost. MultiIndex моделируется с помощьюcomposite_key, как показано в примере:
#include<boost/multi_index_container.hpp>#include<boost/multi_index/ordered_index.hpp>#include<boost/multi_index/member.hpp>#include<boost/multi_index/composite_key.hpp>structphonebook_entry{std::stringfamily_name;std::stringgiven_name;std::stringphone_number;phonebook_entry(std::stringfamily_name,std::stringgiven_name,std::stringphone_number):family_name(family_name),given_name(given_name),phone_number(phone_number){}};// define a multi_index_container with a composite key on
// (family_name,given_name)typedefmulti_index_container<phonebook_entry,indexed_by<//non-unique as some subscribers might have more than one numberordered_non_unique<composite_key<phonebook_entry,member<phonebook_entry,std::string,&phonebook_entry::family_name>,member<phonebook_entry,std::string,&phonebook_entry::given_name>>>,ordered_unique<// unique as numbers belong to only one subscribermember<phonebook_entry,std::string,&phonebook_entry::phone_number>>>>phonebook;
Композитный_ключпринимает два или более ключевых экстракторов по одному и тому же значению (здесьphonebook_entry). Поисковые операции на композитном ключе выполняются путем передачи кортежей с искомыми значениями:
phonebookpb;...// search for Dorothea White's numberphonebook::iteratorit=pb.find(std::make_tuple("White","Dorothea"));std::stringnumber=it->phone_number;
Композитные ключи сортируются лексикографическим порядком, т.е. сортировка выполняется первым ключом, затем вторым ключом, если первый равен и т.д. Этот порядок позволяет осуществлять частичный поиск, где указаны только первые ключи:
phonebookpb;...// look for all Whitesstd::pair<phonebook::iterator,phonebook::iterator>p=pb.equal_range(std::make_tuple("White"));
В качестве удобства для обозначения, когда указан только первый ключ, можно передать аргумент напрямую, не включив его в кортеж:
phonebookpb;...// look for all Whitesstd::pair<phonebook::iterator,phonebook::iterator>p=pb.equal_range("White");
С другой стороны, не допускаются частичные поиски без указания первых ключей.
По умолчанию для каждого подключа композитного ключа используется соответствующийstd::lessпредикат. Альтернативные сравнительные предикаты могут быть определены сcomposite_key_compare:
// phonebook with given names in reverse ordertypedefmulti_index_container<phonebook_entry,indexed_by<ordered_non_unique<composite_key<phonebook_entry,member<phonebook_entry,std::string,&phonebook_entry::family_name>,member<phonebook_entry,std::string,&phonebook_entry::given_name>>,composite_key_compare<std::less<std::string>,// family names sorted as by defaultstd::greater<std::string>// given names reversed>>,ordered_unique<member<phonebook_entry,std::string,&phonebook_entry::phone_number>>>>phonebook;
См.пример 7в разделе примеров для примененияcomposite_key.
Композитные ключи также можно использовать с хешированными индексами простым способом:
structstreet_entry{// quadrant coordinatesintx;inty;std::stringname;street_entry(intx,inty,conststd::string&name):x(x),y(y),name(name){}};typedefmulti_index_container<street_entry,indexed_by<hashed_non_unique<// indexed by quadrant coordinatescomposite_key<street_entry,member<street_entry,int,&street_entry::x>,member<street_entry,int,&street_entry::y>>>,hashed_non_unique<// indexed by street namemember<street_entry,std::string,&street_entry::name>>>>street_locator;street_locatorsl;...voidstreets_in_quadrant(intx,inty){std::pair<street_locator::iterator,street_locator::iterator>p=sl.equal_range(std::make_tuple(x,y));while(p.first!=p.second){std::cout<<p.first->name<<std::endl;++p.first;}}
Обратите внимание, что хеширование автоматически обрабатывается:бустер::hashспециализируется на хешировании композитного ключа в качестве функции бустера::hashзначения его элементов. Если нам нужно указать различные хеш-функции для элементов композитного ключа, мы можем явно сделать это, используя утилитуcomposite_key_hash:
structtuned_int_hash{intoperator()(intx)const{// specially tuned hash for this application}};typedefmulti_index_container<street_entry,indexed_by<hashed_non_unique<// indexed by quadrant coordinatescomposite_key<street_entry,member<street_entry,int,&street_entry::x>,member<street_entry,int,&street_entry::y>>,composite_key_hash<tuned_int_hash,tuned_int_hash>>,hashed_non_unique<// indexed by street namemember<street_entry,std::string,&street_entry::name>>>>street_locator;
Кроме того, равенство композитных ключей можно настроить с помощьюcomposite_key_equal_to, хотя в большинстве случаев предикат равенства по умолчанию (исходя изstd::equal_toдля типов элементов) будет правильным выбором.
В отличие от упорядоченных индексов, мы не можем выполнять частичные поиски, определяющие только первые элементы составного ключа:
// try to locate streets in quadrants with x==0
// compile-time error: hashed indices do not allow such operationsstd::pair<street_locator::iterator,street_locator::iterator>p=sl.equal_range(std::make_tuple(0));
Причина этого ограничения вполне логична: поскольку хеш-значение композитного ключа зависит от всех его элементов, вычислить его из частичной информации невозможно.
КонцепцияKey Extractorпозволяет одному и тому же объекту извлекать ключи из нескольких различных типов, возможно, через соответствующим образом определенные перегрузки оператора:
// example of a name extractor from employee and employee *structname_extractor{typedefstd::stringresult_type;constresult_type&operator()(constemployee&e)const{returne.name;}result_type&operator()(employee*e)const{returne->name;}};// name_extractor can handle elements of type employee...typedefmulti_index_container<employee,indexed_by<ordered_unique<name_extractor>>>employee_set;// ...as well as elements of type employee *typedefmulti_index_container<employee*,indexed_by<ordered_unique<name_extractor>>>employee_ptr_set;
Эта возможность полностью используется предопределенными ключевыми экстракторами, предоставляемыми Boost. MultiIndex упрощает определениеmulti_index_containers, где элементы являются указателями или ссылками на фактические объекты. Далее указываетсяmulti_index_containerуказателей на сотрудников, отсортированных по их именам.
Обратите внимание, что это указано точно так же, какmulti_index_containerфактическогосотрудникаобъектов:члензаботится о дополнительной отсылке, необходимой для получения доступа ксотруднику::имя. Аналогичная функциональность предусмотрена для взаимодействия со справочными обертками отBoost.Ref:
На самом деле, поддержка указателей дополнительно расширена, чтобы принять то, что мы называемцепными указателями. Такой цепной указатель определяется индукцией как сырой или умный указатель или итератор к фактическому элементу, к обертке отсчета элемента илик другому цепному указателю; то есть, цепные указатели являются произвольными композициями указательных типов, в конечном счете относящимися к элементу, из которого должен быть извлечен ключ. Примерами цепных указателей насотрудникаявляются:
сотрудника *,
,
std::unique_ptr,
std::list>:::iterator,
сотрудника **,
boost::shared_ptr
. В общем, цепные указатели с расстоянием отсчета более 1 вряд ли будут использоваться в обычной программе, но они могут возникать в рамках, которые строят «просмотры» какmulti_index_containers из ранее существовавшегоmulti_index_containers.employee *,
In general, chained pointers with dereferencing distance greater than 1 are not
likely to be used in a normal program, but they can arise in frameworks
which construct "views" as multi_index_containers from preexisting
multi_index_containers.
[ORIG_END] -->
Для того, чтобы представить краткое изложение различных применений Boost. Ключевые экстракторы MultiIndex при наличии эталонных оберток и указателей учитывают следующий окончательный тип:
В таблице ниже перечислены соответствующие ключевые экстракторы, которые будут использоваться для различных типов указателей и эталонных оберток на основеTдля каждого из его членов.
Use cases for Boost.MultiIndex key extractors.
element type
key
key extractor
applicable to const elements?
read/write?
T
i
Member
yes
yes
j
Member
yes
no
f()
const_mem_fun
yes
no
g()
mem_fun
no
no
gf()
global_fun
yes
no
gg()
global_fun
no
no
reference_wrapper<T>
i
Member
yes
yes
j
Member
yes
no
f()
const_mem_fun
yes
no
g()
mem_fun
yes
no
gf()
global_fun
yes
no
gg()
global_fun
yes
no
reference_wrapper<const T>
i
Member
yes
no
j
Member
yes
no
f()
const_mem_fun
yes
no
g()
gf()
global_fun
yes
no
gg()
chained pointer to T
or to reference_wrapper<T>
i
Member
yes
yes
j
Member
yes
no
f()
const_mem_fun
yes
no
g()
mem_fun
yes
no
gf()
global_fun
yes
no
gg()
global_fun
yes
no
chained pointer to const T
or to reference_wrapper<const T>
i
Member
yes
no
j
Member
yes
no
f()
const_mem_fun
yes
no
g()
gf()
global_fun
yes
no
gg()
В колонке "применимо к элементамconst?" указывается, можно ли использовать соответствующий ключ-экстрактор при пропускании постоянных элементов (это относится к элементам, указанным в первой колонке, а не к упомянутым объектамT). Единственные отрицательные случаи относятся кT::gиT:gg, когда элементы являются сырымиTобъектами, которые имеют смысл, поскольку мы имеем дело с непостоянной функцией членаT::gи функцией, принимающейTнепостоянной ссылкой: это также подразумевает, чтоmulti_index_containers элементовT::gилиT::gg, поскольку элементы, содержащиеся вmulti_index_container, рассматриваются как постоянные.
Некоторая осторожность должна быть предпринята, чтобы сохранитьconst-правильность в спецификациичленаключевых экстракторов: в некотором смысле,constквалификатор переносится на членскую часть, даже если этот конкретный член не определен какconst. Например, если элементы имеют типconst T *, сортировка поT::iявляетсяне, указанным какчлен, а скорее какчлен.
Для практических демонстраций использования этих ключевых экстракторов обратитесь кпримеру 2ипримеру 6в разделе примеров.
Статья Boost.MultiIndex Documentation - Tutorial - Key extraction раздела Boost.MultiIndex Documentation - Tutorial может быть полезна для разработчиков на c++ и boost.
