...

...

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

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@thomson.com> Fecha: Jueves, Abril 13, 2006 5:35 pm Asunto: Re: [boost] [multi_index]terminology/design concern 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