[boost] Re: Interest in multiindex_set?(again)

From: Fernando Cacciola (fernando_cacciola_at_[hidden])
Date: 2003-07-11 18:22:18

Hi Joaquín,

Unfortunately, I douldn't compile the code with BCC because it extensively
uses non-type template parameters which are only partially supported on
Borland.

After having read the documentation and looked at the code again, I realize
now that your class is really a database-like table but not an associative
container. In fact, it is not even a container.
The problem is that you cannot traverse over _all_ the elements linerly.
(See 23.1, Table 65)
I previously took for granted that it was a container so I asked about the
_global_ arrangement of the elements.
I think that you shoud add iterators to traverse over the entire table as if
it were a Sequence. This is the basic requirement of a container.

Now, suppose that you can iterate over the all of the elements: what's the
order in which elements will appear w.r.t the insertion sequence and the
ordering implied by the indices? This is what I've asked you about the
"ordering and clustering invariants" of the data structure.

If, during a linear traversal (that is, iterating over all of the elements
as if it were a sequence), the elements will appear in an unspecified order,
then the data structure is not an associative container (much less a set),
so it should _definitely_ be called 'table' and not 'set'.

I think I understand now why the term 'index'. It reseambles the
filtering-key associated with the 'field' which designates a 'column' on a
database table. However, if I'm not mistaken, the filtered-column itself,
that is, the sequence of elements with such value in the corresponding
field, is not an 'index'. So the subsquence which is mapped to a given index
shouln't be called index, I think. I would call it a 'cluster' as I
suggested before.

Since I can't play with the code I couldn't see how much of a set is each
'cluster'. Make sure to check with the requirements and document this
clearly.

Another thing I couldn't figure out is how to compose indices hierachically.
That is, how to reproduce a typical SQL SELECT * ORDER BY X,Y,Z.
Since you're modeling an indexed table, this functionality should be
supported.

I vote for a separate KeyExtraction because:

(a) Key extraction and key comparison are conceptually orthogonal.

(b) The orthogonality will be important in practice when users want to
compare whith other predicates besides less_than and/or based on more than
just data members.
With your mixin approach, it would be more difficult to have an index based
on a runtime expression
(such as a hash value) combined with a comparison other than <.

Finally, I'm not entirely happy with the coallision response of 'modify' (or
maybe I don't understand it).
Is it ever possible to afford removing the colliding modified element?
Imagine I change the Social Security Number of Jhon, and by mistake, I
assign him
the same number as Carla... the modify() will return 'false', but there
won't be a
Jhon anymore in the table....

Best,

Fernando Cacciola