boost Composite keys
http://www.boost.org/doc/libs/1_33_1/libs/multi_index/doc/advanced_topics.html#composite_keys
Composite keys
In relational databases, composite keys depend on two or more fields of a given table. The analogous concept in Boost.MultiIndex is modeled by means of composite_key
, as shown in the example:
struct phonebook_entry { std::string family_name; std::string given_name; std::string phone_number; phonebook_entry( std::string family_name, std::string given_name, std::string phone_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) typedef multi_index_container< phonebook_entry, indexed_by< //non-unique as some subscribers might have more than one number 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> > >, ordered_unique< // unique as numbers belong to only one subscriber member<phonebook_entry,std::string,&phonebook_entry::phone_number> > > > phonebook;
composite_key
accepts two or more key extractors on the same value (here, phonebook_entry
). Lookup operations on a composite key are accomplished by passing tuples with the values searched:
phonebook pb; ... // search for Dorothea White's number phonebook::iterator it=pb.find( boost::make_tuple(std::string("White"),std::string("Dorothea"))); std::string number=it->phone_number;
Composite keys are sorted by lexicographical order, i.e. sorting is performed by the first key, then the second key if the first one is equal, etc. This order allows for partial searches where only the first keys are specified:
phonebook pb; ... // look for all Whites std::pair<phonebook::iterator,phonebook::iterator> p= pb.equal_range(boost::make_tuple(std::string("White")));
On the other hand, partial searches without specifying the first keys are not allowed.
By default, the corresponding std::less
predicate is used for each subkey of a composite key. Alternate comparison predicates can be specified with composite_key_compare
:
// phonebook with given names in reverse order typedef multi_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 default std::greater<std::string> // given names reversed > >, ordered_unique< member<phonebook_entry,std::string,&phonebook_entry::phone_number> > > > phonebook;
See example 7 in the examples section for an application of composite_key
.
Composite keys and hashed indices
Composite keys can also be used with hashed indices in a straightforward manner:
struct street_entry { // quadrant coordinates int x; int y; std::string name; street_entry(int x,int y,const std::string& name):x(x),y(y),name(name){} }; typedef multi_index_container< street_entry, indexed_by< hashed_non_unique< // indexed by quadrant coordinates composite_key< street_entry, member<street_entry,int,&street_entry::x>, member<street_entry,int,&street_entry::y> > >, hashed_non_unique< // indexed by street name member<street_entry,std::string,&street_entry::name> > > > street_locator; street_locator sl; ... void streets_in_quadrant(int x,int y) { std::pair<street_locator::iterator,street_locator::iterator> p= sl.equal_range(boost::make_tuple(x,y)); while(p.first!=p.second){ std::cout<<p.first->name<<std::endl; ++p.first; } }
Note that hashing is automatically taken care of: boost::hash
is specialized to hash a composite key as a function of the boost::hash
values of its elements. Should we need to specify different hash functions for the elements of a composite key, we can explicitly do so by using the composite_key_hash
utility:
struct tuned_int_hash { int operator()(int x)const { // specially tuned hash for this application } }; typedef multi_index_container< street_entry, indexed_by< hashed_non_unique< // indexed by quadrant coordinates composite_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 name member<street_entry,std::string,&street_entry::name> > > > street_locator;
Also, equality of composite keys can be tuned with composite_key_equal_to
, though in most cases the default equality predicate (relying on the std::equal_to
instantiations for the element types) will be the right choice.
Unlike with ordered indices, we cannot perform partial searches specifying only the first elements of a composite key:
// try to locate streets in quadrants with x==0 // compile-time error: hashed indices do not allow such operations std::pair<street_locator::iterator,street_locator::iterator> p= sl.equal_range(boost::make_tuple(0));
The reason for this limitation is quite logical: as the hash value of a composite key depends on all of its elements, it is impossible to calculate it from partial information.
Advanced features of Boost.MultiIndex key extractors
The Key Extractor
concept allows the same object to extract keys from several different types, possibly through suitably defined overloads of operator()
:
// example of a name extractor from employee and employee * struct name_extractor { const std::string& operator()(const employee& e)const{return e.name;} std::string& operator()(employee& e)const{return e.name;} std::string& operator()(employee* e)const{return e->name;} };
This possibility is fully exploited by predefined key extractors provided by Boost.MultiIndex, making it simpler to define multi_index_container
s where elements are pointers or references to the actual objects. The following specifies a multi_index_container
of pointers to employees sorted by their names.
typedef multi_index_container< employee *, indexed_by< ordered_non_unique<member<employee,std::string,&employee::name> > > > employee_set;
Note that this is specified in exactly the same manner as a multi_index_container
of actual employee
objects: member
takes care of the extra dereferencing needed to gain access to employee::name
. A similar functionality is provided for interoperability with reference wrappers from Boost.Ref:
typedef multi_index_container< boost::reference_wrapper<const employee>, indexed_by< ordered_non_unique<member<employee,std::string,&employee::name> > > > employee_set;
In fact, support for pointers is further extended to accept what we call chained pointers. Such a chained pointer is defined by induction as a raw or smart pointer or iterator to the actual element, to a reference wrapper of the element or to another chained pointer; that is, chained pointers are arbitrary compositions of pointer-like types ultimately dereferencing to the element from where the key is to be extracted. Examples of chained pointers to employee
are:
employee *
,const employee *
,std::auto_ptr<employee>
,std::list<boost::reference_wrapper<employee> >::iterator
,employee **
,boost::shared_ptr<const employee *>
.
multi_index_container
s from preexisting multi_index_container
s.
In order to present a short summary of the different usages of Boost.MultiIndex key extractors in the presence of reference wrappers and pointers, consider the following final type:
struct T { int i; const int j; int f()const; int g(); };
The table below lists the appropriate key extractors to be used for different pointer and reference wrapper types based on T
, for each of its members.
element type | key | key extractor |
applicable toconst elements? |
read/write? |
---|---|---|---|---|
T |
i |
member<T,int,&T::i> |
yes | yes |
j |
member<T,const int,&T::j> |
yes | no | |
f() |
const_mem_fun<T,int,&T::f> |
yes | no | |
g() |
mem_fun<T,int,&T::g> |
no | no | |
reference_wrapper<T> |
i |
member<T,int,&T::i> |
yes | yes |
j |
member<T,const int,&T::j> |
yes | no | |
f() |
const_mem_fun<T,int,&T::f> |
yes | no | |
g() |
mem_fun<T,int,&T::g> |
yes | no | |
reference_wrapper<const T> |
i |
member<T,const int,&T::i> |
yes | no |
j |
member<T,const int,&T::j> |
yes | no | |
f() |
const_mem_fun<T,int,&T::f> |
yes | no | |
g() |
||||
chained pointer to T or to reference_wrapper<T> |
i |
member<T,int,&T::i> |
yes | yes |
j |
member<T,const int,&T::j> |
yes | no | |
f() |
const_mem_fun<T,int,&T::f> |
yes | no | |
g() |
mem_fun<T,int,&T::g> |
yes | no | |
chained pointer to const T or to reference_wrapper<const T> |
i |
member<T,const int,&T::i> |
yes | no |
j |
member<T,const int,&T::j> |
yes | no | |
f() |
const_mem_fun<T,int,&T::f> |
yes | no | |
g() |
The column "applicable to const
elements?" states whether the corresponding key extractor can be used when passed constant elements (this relates to the elements specified in the first column, not the referenced T
objects). The only negative case is for T::g
when the elements are raw T
objects, which make sense as we are dealing with a non-constant member function: this also implies that multi_index_container
s of elements of T
cannot be sorted by T::g
, because elements contained within amulti_index_container
are treated as constant.
A key extractor is called read/write if it returns a non-constant reference to the key when passed a non-constant element, and it is called read-only otherwise. In order to use multi_index_container::modify_key
, the associated key extractor must be read/write. The column "read/write?" shows that most combinations yield read-only extractors.
Some care has to be taken to preserve const
-correctness in the specification of the key extractors: in some sense, the const
qualifier is carried along to the member part, even if that particular member is not defined as const
. For instance, if the elements are of type const T *
, sorting by T::i
is not specified as member<const T,int,&T::i>
, but rather as member<T,const int,&T::i>
.
composite_key composite_key_compare
上一篇:boost自定义composite_key_compare比较函数
下一篇:CMFCTabCtrl的使用、颜色样式调整