[multi_index] composite keys: request for advice

I'm working through the post review changes of multi_index and hope to have something released in one or two weeks. One of the issues raised in the review was the possibility to promote what was an example of composition of keys to be part of the library. I've come up with something more ambitious, but there's a design decision of which I'm not quite certain wich way to go, and I'd like to ask you for advice. Composite keys can be specified by a new construct called composite_key in the following manner: struct record { int first; int second int third; }; multi_index_container< record, indexed_by< composite_key< record, //base value member<record,int,&record::first>, // first key member<record,int,&record::second>, // 2nd member<record,int,&record::third> // 3rd >
mc;
In the example the composite key is composed of three key extractors, and the sorting is made in lexicographical order, for instance: 0,0,1 0,0,2 0,1,0 0,5,4 1,0,0 1,0,2 1,2,3 ... Given the lexicographical order, it is possible to efficiently search for incomplete keys where only the first values are given: mc.equal_range(make_tuple(1,0)) yields 1,0,0 1,0,2 mc.equal_range(make_tuple(0)) yields 0,0,1 0,0,2 0,1,0 0,5,4 and so on. Accordingly, comparison operators between composite_key results and tuples are overloaded so that the following holds: composite_key</* as before*> ck; ck(record(1,2,3))<=make_tuple(1,2); // yields true make_tuple(1,2)<=ck(record(1,2,3)); // yields true So far, this is all IMHO perfectly consistent, but the following design decision is not obvious to me: given the previous, what should be the result of ck(record(1,2,3))==make_tuple(1,2); // true or false? As these two objects are neither greater than the other, at least they are *equivalent*, but maybe allowing operator== to return true is too much. An argument against making them equal is that, with future hashed indices in mind, hashing has to be done on the whole tuple of values returned by the composite key so that: multi_index_container< record unordered_unique< //hashed composite_key< /* as before */ >
mc;
mc.find(make_tuple(1,2,3)); //OK mc.find(make_tuple(1,2)); //KO, we need the whole tuple If we make ck(record(1,2,3))==make_tuple(1,2) return true, the impossibility of having the last line to work is puzzling. If we make it return false, it is also puzling that neverthelss operator<= is true in both senses. What do I do? a. require operator== between composite_key results and tuples to work only on full tuples. b. define operator== in the same line operator<, <= etc. are defined. Thanks for your comments. Joaquín M López Muñoz Telefónica, Investigación y Desarrollo

Joaquin M Lopez Munoz <joaquin@tid.es> writes:
[snip: composite key system]
composite_key</* as before*> ck; ck(record(1,2,3))<=make_tuple(1,2); // yields true
This is not lexicographical order. According to lexicographical ordering: (1, 2) < (1, 2, 3) -- Jeremy Maitin-Shepard

On Sat, Apr 24, 2004 at 07:13:25PM +0000, Joaquin M Lopez Munoz wrote:
0,0,1 0,0,2 0,1,0 0,5,4 1,0,0 1,0,2 1,2,3 ...
Given the lexicographical order, it is possible to efficiently search for incomplete keys where only the first values are given:
mc.equal_range(make_tuple(1,0)) yields 1,0,0 1,0,2
mc.equal_range(make_tuple(0)) yields 0,0,1 0,0,2 0,1,0 0,5,4
and so on. Accordingly, comparison operators between composite_key results and tuples are overloaded so that the following holds:
composite_key</* as before*> ck; ck(record(1,2,3))<=make_tuple(1,2); // yields true make_tuple(1,2)<=ck(record(1,2,3)); // yields true
So far, this is all IMHO perfectly consistent, but the following design decision is not obvious to me: given the previous, what should be the result of
ck(record(1,2,3))==make_tuple(1,2); // true or false?
As these two objects are neither greater than the other, at least they are *equivalent*, but maybe allowing operator== to return true is too much.
It sounds to me like you have a partial ordering or a strict weak ordering, but not a total ordering. http://www.sgi.com/tech/stl/StrictWeakOrdering.html That is, these two objects: ck(record(1,2,3)) make_tuple(1,2) are in the same equivalence class, but they are not equal. My hunch is that if you call these two object "k" and "t" (key and tuple), then you should have k < t false t < k false t == k does not compile That's just my quick hunch based on what I've quoted above; I haven't considered what consequences it has for the library, but that's my intuitive notion of how tuples as "partial keys" ought to work. -- -Brian McNamara (lorgon@cc.gatech.edu)

"Joaquin M Lopez Munoz" <joaquin@tid.es> wrote:
Composite keys can be specified by a new construct called composite_key in the following manner:
OT question 1: will it be possible to specify calculated index as part of composite index? OT question 2 (I could had asked already): would it be somehow possible for calculated index to use user supplied functor and then sorting sequenced index according this index? This would create 'dynamic index', modifiable during runtime. /Pavel

From: Joaquin M Lopez Munoz <joaquin@tid.es>
Composite keys can be specified by a new construct called composite_key in the following manner:
struct record { int first; int second int third; };
multi_index_container< record, indexed_by< composite_key< record, //base value member<record,int,&record::first>, // first key
Would that you could make this work to avoid the duplication and chance for errors: member< &record::first > I know a function template can deduce the other types, but I can't think of how to make it work here. -- Rob Stewart stewart@sig.com Software Engineer http://www.sig.com Susquehanna International Group, LLP using std::disclaimer;
participants (5)
-
Brian McNamara
-
Jeremy Maitin-Shepard
-
Joaquin M Lopez Munoz
-
Pavel Vozenilek
-
Rob Stewart