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

From: JOAQUIN LOPEZ MU?Z (joaquin_at_[hidden])
Date: 2006-04-12 14:04:06

Hello Gennadiy,

----- Mensaje original -----
De: Gennadiy Rozental <gennadiy.rozental_at_[hidden]>
Fecha: Miércoles, Abril 12, 2006 7:09 pm
Asunto: [boost] [mulit_index]terminology/design concern

> 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.

The problem with the words "view", "order", "index", etc.
is that they are badly overloaded. David Abrahams recently
objected to the current use of "index" since, for him, this
word is customarily used to refer to the distance between
an element and the beginning of the container it belongs
in (as for instance the argument of std::vector::operator[]).
I would have happily used "view" instead of "index" but
refrained myself because the term "view" was already used by
some view libraries (e.g. Maciej Sobczak's view library at
http://www.msobczak.com/prog/publications.html or Gary
Powell and Martin Weiser's VTL at
http://www.zib.de/weiser/vtl/) with a somewhat different
meaning: these views are detached from the elements
they're constructed from (so that further changes to the
elements may not be reflected back to the view) and may
list only some of the elements (filtering views.)
At the end I decided on "index" to avoid semantic clashing
with preexisting definitions of "view" and because the concept
is more or less related to indices as used in relational
databases --in fact, the definition of a
multi_index_container is kind of reminiscent of the way
one declares indices for a relational DB table.
"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.

> 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
can be performed in Boost.MultiIndex by means of so-called
"compatible keys" as described in http://tinyurl.com/rouet,
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? 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.

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