Boost logo

Boost Users :

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


Boost-users list run by williamkempf at hotmail.com, kalb at libertysoft.com, bjorn.karlsson at readsoft.com, gregod at cs.rpi.edu, wekempf at cox.net