Boost :: multi_index compound key performance

Question

The long-awaited reader for the first time poster! I play with the boost :: multi_index container and ask a rather detailed question that the container expert with add-in or C ++ may hopefully know (my knowledge in C ++ containers is pretty simple). For reference, additional documentation on compound keys can be found here: boost :: multi_index compound keys.

When using a composite key, the documentation states that "composite keys are sorted in lexicographic order, that is, sorting is performed using the first key, then the second key, if the first is equal, etc." Does this mean that the structure is stored in such a way that the search for a specific composite key of 2 parts will take O time (n = 1), i.e. Is the container sorted in such a way that there is a pointer directly to each element, or is there an increase? Does the container retrieve a list that matches the first part of the composite key, and then you need to search for elements matching the second part of the key, and therefore slower?

For example, if I were to maintain two containers manually using two different indexes and want to find elements that match a particular two-part query, I would probably filter the first container for all elements matching the first part of the query, and then filter the result for elements corresponding to the second part of the request. Thus, this manual method will effectively include two searches. Does this increase efficiency, or does it improve efficiency in some way with the compound keys?

I hope I explained myself here, but please ask questions and I will try my best to clarify what I mean!

Answer 1

Compound key searches do not go through any two-step process as you describe. composite_key -induced orderings are normal orders, the only feature is that it depends on two or more element keys, not one.

Perhaps an example will explain. Consider this use of composite_key :

 struct element { int x,y,z; }; typedef multi_index_container< element, indexed_by< ordered_unique< composite_key< element, member<element,int,&element::x>, member<element,int,&element::y>, member<element,int,&element::z> > > > > multi_t; 

The resulting container is in a sense equivalent to this:

 struct element_cmp { bool operator()(const element& v1, const element& v2)const { if(v1.x<v2.x)return true; if(v2.x<v1.x)return false; if(v1.y<v2.y)return true; if(v2.y<v1.y)return false; return v1.z<v2.z; } }; typedef std::set<element,element_cmp> set_t; 

composite_key automatically generates the equivalent code in element_cmp::operator() and additionally allows you to search only the first n keys, but the basic data structure does not change with respect to the case using std::set .