Re: [boost] Re: Re: [In response to Fernando Cacciola] Re: Interestinmultiindex_set?(again)

From: Joaquín Mª López Muñoz (joaquin_at_[hidden])
Date: 2003-07-02 11:37:58

Hi Fernando,

Fernando Cacciola ha escrito:

[...]

> I understand the current design but I'm not sure if it defines the concepts
> correctly, which is IMO the first important thing to get right.
> So let's see:
>
> >From a C++ user perspective, your class is an Associative Container.
> An associative container associates contained elements with a key.
> The 'key' _identifies_ the element by means of some 'relation' (or association).
> Since the key is the element identifier, keys are used to look up elements.
>
> In a std 'set', the relation which associates keys and elements is the
> 'identity'.  It means that to identify (look up) an element of type 'E'
> with value 'e', the user needs to use the value 'e' itself, of the same type,
> as a key.
>
> In a std 'map', the relation is the explicit bijection expressed by a
> 'pair<Key,Data>. It means that to identify an element of type 'Data'
> whith value  'd', the user needs to use a value 'k' of type 'Key' as the key.
>
> Hence, the 'key' of an associative container is the (typed) value which is
> used to identify elements in the container.
>
> In your class, the elements look like keys simply because you choose
> to model the predicates as black-boxes which extract keys in some
> indeterminate way.
> That is,  an _entire_ element value does not identify a contained element.
> It is a 'part' of the element value which acts as a key, but not the element
> (not the whole of it).
>
> It is not really necessary to melt the concepts of key and value using
> a black-box predicate over an entire element. You can use separate
> KeyExtractor and KeyCompare.
> This would better reflect the fact that your container stores values
> (elements) along with mutiple keys, which by default just happen
> to be different parts of the stored values.

This can certainly be done but
* It complicates the instantiation of a multiindex_set type (you've got
to provide more info).
* I cannot see its usefulnes.
Maybe you've got in mind something different to me. Please read below.

[...]

> >> One last concern: keys are related hierarchycally?
> >>
> >Only for implementation purposes: derivation from one key
> >(or index) to another is protected. From the user's point of
> >view, keys/indices are structurally unrelated types obtained via
> >get() from the source multiindex_set object.
> >
> I see.
> Depending on the application, this independece might
> not be a good property.
> How do I 'cluster' (that is, get all of) elements which
> share some primary key and some secondary key, and so on?
>
> BTW: I figure that there is some clustering and ordering invariant.
> That is, elements sharing some key-related property are placed
> together (clustered), and clusters are ordered in some way.
> But I can't tell how is this exactly and which operations maintain
> these invariants.
> For example: can I expect a specific arrangement with a lineal
> traversal (as with set/map), or only via 'get()'?
>

Now I'm totally missing your point. Each index (or cluster if you prefer)
defines an independent set-like interface by which you can access all
the elements contained (though in different orders depending on the index).
When you insert an element through an index say i1, it becomes visible from all
other indices. Indices behave as views, if you want to see it that way.
There's some kind of facility for "horizontal traversal", i.e, for getting
an iterator of index M given an iterator of index N. It is called project() and
can be used like this:

typedef multiindex_set<...> mx_set;
mx_set ms;
mx_set::index_type<1>::type::iterator it1=...;
mx_set::index_type<3>::type::iterator it3=project<3>(ms,it1);

This obtains an index-3 iterator from an index-1 iterator so that both
iterators point to the same element. project() has been recently
added, check last version on http://groups.yahoo.com/group/boost/files/multiindex.zip
I don't know if this answer your "lineal traversal" question.
An interesting question is whether project() or similar stuff can be used
to allow for searches based on different indices, à la SQL. On this point
I haven't thought out anything yet.

I really value your contributions, but I think withouth some minimal
docs we'll keep going round and round just defining the basic concepts.
If I have time, I'll try to write something down by next week, please stay
tuned.
Besides, no one except you seems to be interested in multiindex_type :(
If only some boosters jump into this discussion I'm sure many interesting
insights would be provided.

Regards,

Joaquín M López Muñoz
Telefónica, Investigación y Desarrollo