Boost logo

Boost :

From: Gennadiy Rozental (gennadiy.rozental_at_[hidden])
Date: 2006-05-21 11:01:28

"Joaquin M Lopez Munoz" <joaquin_at_[hidden]> wrote in message
> >
> Hello Gennadiy, I'm returning to this discussion. Excuse
> the big delay.
> By the end of your post, you wrote:
>> 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.
> Well, let me use Index/Bookmark if only during this
> discussion so as to not introduce further confusion,
> since I think you agree with me it is concepts we're
> most interested now, rather than words.
> I'm not in love with "bookmark" either, it is just a
> hack word I came by with some resonance to the
> concept it is being used to refer to here.
> Now, returning to the original flow of your post:
> Gennadiy Rozental <gennadiy.rozental <at>> writes:
>> 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.
> Well, if we concentrate now on the kind of data structures
> we'd need in order to achieve what you request, I come up with the
> following conclusions:
> 1. If the index to be sped up is of the ordered kind, then
> the only way to have faster lookups for clusters of elements
> (which, according to my terminology, are groups of elements
> equivalent under some sorting criterion compatible to that
> used by the index, see, we'd probably
> have to resort to hashing (which improves rb-tree O(log n)
> lookup) and have some inner structures like
> hash_map<key_type,oredered_index_type::iterator>
> storing pointers to the first element of each cluster. This
> has to be properly synchronized with the ordered index on
> insertion/deletion.

It could be hash, it could be random access or it could be any other custom
faster lookup. This is essencially is just a way to jump particulat position
in the Order based on some conditions. I may have records ordered by
creation time for last week and index that allows me to jump to start of
todays and yestadays entries.

> 2. If the index to be sped up is of the sequenced kind, we've
> got a problem: you require that the bookmark refer
> to clusters by using iterators from the index itself, as
> implied in your example:
> std::pair<full_name_order::iterator,full_name_order::iterator>
> p = fno.get_index<LastName>::equal_range( "Smith" );
> and explicitly stated by you in a previous post:
> "All indexes for the same order present the same
> iterator which is a view iterator."
> This is AFAICS impossible if the index is sequenced,

I may misunderstand what sequenced order is. I understand it as just a
"natural" order entries where added into collection with. Why couldn't I
have an Index that would allow me to jump directly to the every 10000th

> since the elements can be freely rearranged and thus
> a cluster need not be adjacent (from the point of view
> of the sequenced index iterator).

What do you mean by rearanged and cluster here?


Boost list run by bdawes at, gregod at, cpdaniel at, john at