Re: [boost] [multi_index]terminology/design concern

From: Gennadiy Rozental (gennadiy.rozental_at_[hidden])
Date: 2006-04-12 14:41:09

> > Hi,
> >
> > It possible that I just missing something and it was already
> > discussed. But
> > I find the terms used by the library misleading and/or incorrectly
> > used. The
> > library present different views on the same data. Each view is
> > defined by
> > notion of "Index". My understanding if term index is something
> > close to the
> > index at the end of the book. The thing is modeled here I would
> > rather
> > called an "Order".
> >   Even more importantly is that I feel the these concepts are
> > kind of mixed
> > into one in library design. I understand that we want multiple
> > Orders for
> > the same data. Each order define a view to the container. Each
> > view present
> > iterators to access this view. Different views have different
> > iterators,
> > which are not comparable in any way.
>
> From your description above, seems to me what you understand
> as an "order" is verily what the index concept (as used in
> Boost.MultiIndex) tries to model. Basically, an index is
> an access interface to a set of objects jointly owned
> by several other indices --in contrast with regular STL
> containers who own their elements in an exclusive fashion.
>

[...]

> "Order" would be a good candidate, except that it's generally
> tied to fixed-order containers (sets, maps), and
> Boost.MultiIndex also includes sequence-like constructs.

I do not see a problem with term "Order". You could have 
mulit_order_container. While STL present single order ones.

> > Now for any view (for any
> > order) I may
> > want to have one or more Indexes. Index is something that provides
> > direct(random) access based on some key into view. Index present
> > iterator
> > interface. All indexes for the same order present the same
> > iterator which is
> > a view iterator.
> >   Lets consider some example: an address book. We may have
> > different orders
> > defined:
> >   1. City, Last name, First Name order
> >   2. Last name, First Name order
> >   3. Phone number order
> >   4. Time registered order
> >
> > Now each order may have in addition following Indexes defined:
> >   1. City, Last name, First Name
> >       a) City Index: jump to the first record in the particular city
> >   2. Last name, First Name
> >      a) Last Name Index: jump to the first record with particular
> > last name
> >   3. Phone number order
> >      a) Area code Index: jump to the first record with particular
> > area code
> >   4. Time registered order
> >      a) Year Index: jump to the first record registered in
> > particular year
> >
> > I see Order and Index as two independent concepts and current
> > model seems to
> > mixing them in one.
>
> I'm afraid I'm not quite getting what you mean by "index"
> in this context. Certainly, the kind of operations you describe

Index is something that provided direct (constant-time) access somewhere 
within selected order.

> can be performed in Boost.MultiIndex by means of so-called
> "compatible keys" as described in http://tinyurl.com/rouet,

I am not sure how this is related.

> so that, for instance, given an ordered index sorted by
> (last name, first name) one can jump to the records
> beginning with some given last name. Is this what you're
> referring to?

Essencially. The same way as book index allows to jump to proper page based 
on keyword. Could you show some code example? What I want is to iterate 
through all persons with last name "Smith". All operations should have 
contant complexity.

> If so, the only thing I can say is I never
> thought of these operations as directly related to an
> index concept. If you could elaborate on your discussion
> maybe I'll be seeing your point more clearly.
>
> Thanks for discussing your concerns, I hope at least I've
> shed some light on them.

IMO we need another level of indirection that would support Index within an 
Order concept. I do not see how existing design could handle this.

Gennadiy