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

From: Gennadiy Rozental (gennadiy.rozental_at_[hidden])
Date: 2006-04-13 11:35:13

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

That's the primary reason I would need an Index. Aa Order may have have 
different complexity guarantees. But in some cases I need partucular search 
to be performed much faster then it is guaranted by order search complexity. 
Essentially I am looking for an ability to do something like this:

address_book_t ab;
typedef address_book_t::order<2>::type full_name_order;

// this operation is compile time
full_name_order fno = ab.get_order<FullName>();

// this operation has constant complexity, since Last name Index provide 
direct access
std::pair<full_name_order::iterator,full_name_order::iterator>
  p =  fno.get_index<LastName>::equal_range( "Smith" );

...

In some cases Index could have non-constant complexity, but still could be 
used to significantly speedup orderred collection search. Lets say I have 
Input messages log ordered sequencially (meaning that the order is just 
natuaral order messages where comming in). And I have int64 number of theses 
comming in every day. Now for this order I want to define Time index to 
speedup lookup for messages in partucilar time interval. This operation most 
probably wont be constant (due to continues nature of time) but still could 
be implemented much faster then global serach through messages collection. 
In addition for the same collection I may want to define Symbol (some 
attribute in a messages) order. And for that order I need first letter 
index.
  My primary point in above examples is that both Order and Index are first 
class citizents and current desing doesn't account for the latter.

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

I am not really crazy about the term Bookmark. IMO Order/Index is much 
better reflect the nature of the concepts we are trying to model. But above 
is step in right direction IMO.

Gennadiy