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

Subject: Re: [Boost-users] [MultiIndex] Indexing integers
From: Sensei (senseiwa_at_[hidden])
Date: 2014-07-31 03:59:30

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.

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?

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.

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

Thanks for your valuable help!

Cheers!

=== SOURCE ===

     typedef boost::multi_index::multi_index_container<
         __uint128_t,
         boost::multi_index::indexed_by<
 
boost::multi_index::ordered_non_unique<boost::multi_index::global_fun<__uint128_t, 
uint64_t, &Data::MSB>>,    // 0
 
boost::multi_index::ordered_non_unique<boost::multi_index::global_fun<__uint128_t, 
uint64_t, &Data::HSB>>,  // 1
 
boost::multi_index::ordered_non_unique<boost::multi_index::global_fun<__uint128_t, 
uint64_t, &Data::LSB>>,     // 2
 
boost::multi_index::hashed_non_unique<boost::multi_index::tag<byMSB>, 
boost::multi_index::global_fun<__uint128_t, uint64_t, &Data::MSB>>,     // 3
 
boost::multi_index::hashed_non_unique<boost::multi_index::tag<byHSB>, 
boost::multi_index::global_fun<__uint128_t, uint64_t, &Data::HSB>>,   // 4
 
boost::multi_index::hashed_non_unique<boost::multi_index::tag<byLSB>, 
boost::multi_index::global_fun<__uint128_t, uint64_t, &Data::LSB>> 
  // 5
         >
     > Storage;

     Storage storage_;

     void makelist(__uint128_t v, std::list<__uint128_t> &l)
     {

         std::cout << "TARGET IS " << MSB(v) << " | " << HSB(v) << " | " 
<< LSB(v) << std::endl;

         typedef typename Storage::template nth_index<3>::type 
byHashedIndex;

         byHashedIndex &p = storage_.template get<byMSB>();

         auto q = p.equal_range(v);

         while (q.first != q.second)
         {
             std::cout << " EQID " << MSB(*(q.first)) << " | " << 
HSB(*(q.first)) << " | " << LSB(*(q.first)) << std::endl;

             l.push_back(*(q.first));

             q.first++;
         }

         auto u = p.find(v);

         std::cout << " FIND " << MSB(*(u)) << " | " << HSB(*(u)) << " | 
" << LSB(*(u)) << std::endl;

         std::cout << "ALL ITEMS:" << std::endl;
         for (auto x : storage_.template get<byLSB>())
             std::cout << " +ALL " << MSB((x)) << " | " << HSB((x)) << " 
| " << LSB((x)) << std::endl;
     }

=== OUTPUT ===

TARGET IS 0 | 1 | 2
  FIND 0 | 0 | 0
ALL ITEMS:
  +ALL 14 | 13 | 2
  +ALL 0 | 1 | 2
  +ALL 0 | 3 | 4
  +ALL 0 | 5 | 6
  +ALL 0 | 7 | 8
  +ALL 14 | 9 | 10
  +ALL 0 | 9 | 10
  +ALL 14 | 11 | 12
  +ALL 2 | 11 | 12
  +ALL 0 | 11 | 12
  +ALL 2 | 13 | 14
  +ALL 2 | 3 | 15
  +ALL 2 | 7 | 16
  +ALL 14 | 3 | 17
  +ALL 14 | 5 | 18
  +ALL 14 | 7 | 19
  +ALL 14 | 5 | 20
Program ended with exit code: 0