Re: [Boost-users] [MultiIndex] Indexing integers

Subject: Re: [Boost-users] [MultiIndex] Indexing integers
From: Joaquin M Lopez Munoz (joaquin_at_[hidden])
Date: 2014-07-31 04:51:37

Sensei <senseiwa <at> gmail.com> writes:

> 
> On 7/30/14, 5:17pm, Joaquin M Lopez Munoz wrote:
> > Absolutely. The interface of hashed indices is modelled upon that of
> > C++ unordered associative containers. equal_range(3) (on the MSB index)
> > will get you the elements you're after.
> 
> Perfect! So I am doing something wrong with a library that does what I'd 
> like!
> 
> The following is a simple dump & append to list. The objective is 
> simple, append to a list all 128-bit integers that have a common MSB. To 
> debug I've also dumped the whole container, just to be sure.
> 
> My code, actually, won't find anything with equal_range, and find will 
> return 0, although my call works in some sense, or better, the element I 
> am passing DOES exist in the container. Source and output in the
> following.

OK, some weird things are happening here, though I can only guess as
the code you're showing is not complete. Seemingly p.equal_range(v) is
returning an empty result (since the output does not emit any EQID). As
for p.find(v) returning something, what's actually hapenning is that
it is returning an iterator to end --this is why FIND outputs 0|0|0 when
there's no such element in the container, judging from the ALL dump. This
you can easily check by comparing u with p.end().

So... my wild guess is that Data::MSB is not working properly. Could
you please show the code for that function? (even better, could you
post a complete compilable snippet for me to play with?)

> Apart from feeling shame over my flawed code, I'd like to know some 
> underlying facts, if possible.
> 
> The complexity of equal_range is constant with respect to the key I'm 
> finding, in other words, linear wrt the number of matched keys. Is this 
> always the average case regardless of the number of elements in the 
> container?

In Boost 1.55 and prior, the complexity of equal_range(k) is linear
wrt matched keys. Starting with Boost 1.56, the complexity is in fact
constant, i.e, the same regardless of the number of matched keys, you
can check this at:

http://www.boost.org/doc/libs/1_56_0_b1/
libs/multi_index/doc/reference/hash_indices.html#lookup

(All of this assuming a reasonably well-behaved hashing function.)

> If I need to find, for instance, all items matching MSB, and within 
> them, all matching HSB, will I need an additional key (composite key, if 
> I understand)? It seems quite expensive from the memory point of view, 
> so in case I have may items I could just iterate over them.

You can do it in either of two ways:

* By having a composite key
* By retrieving on MSB and linearly scanning for HSB matches.

As it happens, I recently answered a question on this very topic:

http://stackoverflow.com/a/24872210/213114

> Instead of copying matched items, is it possible to have a 
> "sub-container" akin to a view, without copying anything? Probably not...

Not sure what you mean... Could you elaborate? If your view happens
to be the result of some equal_range query, then you could
use the resulting iterator pair as a range for most postprocessing
purposes.

Joaquín M López Muñoz
Telefónica