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

From: JOAQUIN LOPEZ MU?Z (joaquin_at_[hidden])
Date: 2006-04-13 06:35:43

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

Joaquín wrote:

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

As I said, I'm reluctant to name sequenced indices as "orders",
since it is precisely the lack of any fixed order that defines
them. Besides, the differences between index interfaces are
huge, and referring to them collectively as orders tends to
blur (IMHO) these differences, as if the interfaces were
homogeneous, which they aren't.

Anyway, names were already chosen, published, and pretty much
cast in stone when the library was first released in 2004.
Back then, this conversation could have had more practical
implications, right now I can only concede/deny your points,
but no name change is likely to occur.

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

So, if your multi-index container is defined like this:

typedef multi_index_container<
  address,
  indexed_by<
    ordered_non_unique< // (last_name,first_name) index
      composite_key<
        address,
        member<address,std::string,&address::last_name>,
        member<address,std::string,&address::first_name>
      >
    >
    ... // other indices
  >
> address_book_t;

address_book_t b;

then you can write the following:

void list(const std::string& last_name)
{
  std::pair<address_book_t::iterator,address_book_t::iterator> p=
    b.equal_range(last_name);
  std::copy(
    p.first,p.second,
    std::ostream_iterator<address>(std::cout));
}

You require that all ops are constant complexity, which is
not entirely fulfilled by my example, since equal_range is
O(log n). On the other hand, I cannot see why your indexing
concept must guarantee constant complexity and not only fast
lookup. 

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

If the need for the kind of bookmarking (allow me to use this term
so as to not mix the different meanings we're giving to the
word "index") you describe is sufficiently general, such a facility
can be built separately from B.MI itself (like a standalone
view-like library) or integrated into B.MI as an index decorator:

typedef multi_index_container<
  element,
  indexed_by<
    bookmarked<
      ordered_unique<...>
    >
    ...
  >
>

So, the bookmarked<...> construct can embed any preexistent index
("order" in your terminology) type and supplement it with
bookmarking facilities, provided we had a precise definition of
what bookmarking boils down to. This kind of stuff can be done within
the current design, but then again I yet fail to see how what you
describe is a general need not sufficiently covered by current
facilities, like for instance compatible keys in ordered
indices --clarification here most welcome.

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