Thanks Joaquin, I've played with your example and I find it very useful! Now the appetite grew and combining your example with the custom key extractor docs you provided, I am trying to move to a single class with a multi index member. However, I cannot compile it. My attempt is now to use a 128bit integers, and extract MSB/LSB as before. The difference is using a const member function. Of course, I've specialized std::less for my type. The errors are puzzling to me. Here they are: == LOG == In file included from Data.h:15: /usr/local/include/boost/multi_index/mem_fun.hpp:42:50: error: member pointer refers into non-class type 'unsigned __int128' template Data.h:42:32: note: while substituting prior template arguments into non-type template parameter 'PtrToMemberFunction' [with Class = unsigned __int128, Type = unsigned long long] ordered_non_unique>, ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ Data.h:42:83: error: expected a type ordered_non_unique>, ^ /Users/sensei/Documents/Projects/sparql/Sparql/Sparqlo/soData.h:45:5: error: expected a type > soDataStorage; ^ == END == I must confess I cannot understand what type it expects. From the documentation I see that I need in const_mem_fun<> in order, the input type, the output type, and the address of a member function, a const member in my case. // sort by less<int> on name_length() ordered_non_unique< const_mem_fun > I believe less<> isn't a problem, since it should work on 128bit integers with my specilization... I think! Can anyone help me? Thanks & Cheers! #include #include #include #include <functional> using namespace boost::multi_index; namespace std { template<> struct less<__uint128_t> { bool operator()(const __uint128_t& x, const __uint128_t& y) const { return x < y; } }; }; using namespace boost::multi_index; class Data { public: Data(); uint64_t msb(__uint128_t storage) const { return static_cast(storage >> 64); }; uint64_t lsb(__uint128_t storage) const { return static_cast(storage & 0xFFFFFFFFFFFFFFFF); }; private: typedef multi_index_container< __uint128_t, indexed_by< ordered_non_unique>, ordered_non_unique> > > DataStorage; };

On 7/20/14, 12:55pm, Joaquin M Lopez Munoz wrote:

This is off-topic, but you don't need to specialize std::less for __uint128_t because the default implementation does exactly the same as your specialization (both use operator<). [...]

Thanks Joaquin, and sorry for the OT. I thought it was a problem regarding std::less. Thanks again!

Sensei writes:

As Joaquín helped me out, I'm currently using his solution to test multi index containers.

[...]

Following the example [1], I proceeded in defining the index type, but here my compiler throws me two errors:

error: missing 'typename' prior to dependent type name 'DataWithIndices::nth_index' ^

and

error: expected unqualified-id typedef DataWithIndices::nth_index<3>::type byHashedIndex; ^

So I followed the suggestion and used typename, but an error is there:

error: use 'template' keyword to treat 'nth_index' as a dependent template name typedef typename DataWithIndices::nth_index<3>::type byHashedIndex; ^

Again, I follow the suggestion, use template and it works. Adding the following line from the example gives me an error:

error: expected expression byHashedIndex &p = multiIndex_.get<3>(); ^

error: declaration of reference variable 'p' requires an initializer byHashedIndex &p = multiIndex_.get<3>();

I think you need to write byHashedIndex &p = multiIndex_.template get<3>(); (note the extra "template"). You might want to check the excellent explanation on templates and dependent names given at http://tinyurl.com/cmlqhcr . Best, Joaquín M López Muñoz Telefónica

Sensei writes:

On 7/29/14, 5:53 PM, Joaquin M Lopez Munoz wrote:

...

I think you need to write

byHashedIndex &p = multiIndex_.template get<3>();

(note the extra "template"). You might want to check the excellent explanation on templates and dependent names given at http://tinyurl.com/cmlqhcr .

Thanks as always Joaquin, this solves the compilation error.

I might have misunderstood how hashed indices work, because I don't know if multi index is suitable for fast retrieval of, for instance, all 128-bit integers that have MSB equal to 3? Something akin to a simple std::unordered_multimap with better storage?

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. Joaquín M López Muñoz Telefonica

Sensei 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

On 7/31/14, 11:49am, Joaquin M Lopez Munoz wrote:

Ok, never mind, the problem is this: lookup functions take *keys*, not whole values, so instead of

auto q = p.equal_range(v);

you have to write

auto q = p.equal_range(MSB(v));

The bug goes undetected at compile time because there's a default conversion from __uint128_t to uint64_t, but this conversion of course does not extract the MSB part, hence the run-time problems. In more usual scenarios where the key is a member of the element, the error would have been more apparent and the code wouldn't have compiled.

Thanks Joaquin, you're very clear and helpful! Cheers!