[boost] [multi_index] composite keys: request for advice

From: Joaquin M Lopez Munoz (joaquin_at_[hidden])
Date: 2004-04-24 14:13:25

>
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