Sensei
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