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

From: JOAQUIN LOPEZ MU?Z (joaquin_at_[hidden])
Date: 2006-04-14 05:57:24

Gennadiy, my computer time is too limited these
days to allow me to write an elaborate answer.
Let me return to you by the end of this week or
the beginning of the next one.

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

----- Mensaje original -----
De: Gennadiy Rozental <gennadiy.rozental_at_[hidden]>
Fecha: Jueves, Abril 13, 2006 5:35 pm
Asunto: Re: [boost] [multi_index]terminology/design concern

> > > 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 
> 
> 
> 
> _______________________________________________
> Unsubscribe & other changes: 
> http://lists.boost.org/mailman/listinfo.cgi/boost