Re: [Boost-users] Multi-Index: custom iterator

Subject: Re: [Boost-users] Multi-Index: custom iterator
From: Sensei (senseiwa_at_[hidden])
Date: 2014-08-26 04:00:58

On 8/25/14, 9:14pm, Joaquin M Lopez Munoz wrote:
> One easy way to get something roughly equivalent in many situations
> to what you want is (warning, uncompiled):
>
> template<typename Tag>
> typename boost::multi_index::index<DataStorage,Tag>::index::const_iterator
> myfind(const DataStorage& s,unsigned int v)
> {
>    return s.template get<Tag>().find(v);
> }
>
> ...
>
> auto it=myfind<byMSB>(storage,MSB(value128bits));
>
> myfind returns a different iterator type depending on the tag you
> specify when calling it.

Hi Joaquin, and thanks as usual!

I am trying your solution with a member function, but I get the 
following error:

/Users/sensei/Documents/Projects/scratch/indexed/indexed/main.cpp:145:16: error: 
no matching member function for call to 'myfind'
     auto q = d.myfind<byMSB>(Data::storage(1, 30, 30));
              ~~^~~~~~~~~~~~~
/Users/sensei/Documents/Projects/scratch/indexed/indexed/main.cpp:125:5: 
note: candidate template ignored: substitution failure [with Index = 
byMSB]: no type named 'const_iterator' in 
'boost::multi_index::index<boost::multi_index::multi_index_container<unsigned 
__int128, 
boost::multi_index::indexed_by<boost::multi_index::hashed_non_unique<boost::multi_index::tag<byMSB, 
mpl_::na, mpl_::na, mpl_::na, mpl_::na, mpl_::na, mpl_::na, mpl_::na, 
mpl_::na, mpl_::na, mpl_::na, mpl_::na, mpl_::na, mpl_::na, mpl_::na, 
mpl_::na, mpl_::na, mpl_::na, mpl_::na, mpl_::na>, 
boost::multi_index::global_fun<unsigned __int128, unsigned long long, 
&Data::msb>, mpl_::na, mpl_::na>, 
boost::multi_index::hashed_non_unique<boost::multi_index::tag<byHSB, 
mpl_::na, mpl_::na, mpl_::na, mpl_::na, mpl_::na, mpl_::na, mpl_::na, 
mpl_::na, mpl_::na, mpl_::na, mpl_::na, mpl_::na, mpl_::na, mpl_::na, 
mpl_::na, mpl_::na, mpl_::na, mpl_::na, mpl_::na>, 
boost::multi_index::global_fun<unsigned __int128, unsigned short, 
&Data::hsb>, mpl_::na, mpl_::na>, 
boost::multi_index::hashed_non_unique<boost::multi_index::tag<byLSB, 
mpl_::na, mpl_::na, mpl_::na, mpl_::na, mpl_::na, mpl_::na, mpl_::na, 
mpl_::na, mpl_::na, mpl_::na, mpl_::na, mpl_::na, mpl_::na, mpl_::na, 
mpl_::na, mpl_::na, mpl_::na, mpl_::na, mpl_::na>, 
boost::multi_index::global_fun<unsigned __int128, unsigned long long, 
&Data::lsb>, mpl_::na, mpl_::na>, mpl_::na, mpl_::na, mpl_::na, 
mpl_::na, mpl_::na, mpl_::na, mpl_::na, mpl_::na, mpl_::na, mpl_::na, 
mpl_::na, mpl_::na, mpl_::na, mpl_::na, mpl_::na, mpl_::na, mpl_::na>, 
std::__1::allocator<unsigned __int128> >, byMSB>'
     myfind(unsigned int v) //const DataStorage& s, unsigned int v)
     ^
1 error generated.

I changed your definition to this, I think the modifications are really 
trivial, but I doubt my code makes sense now:

     template<typename Index>
     typename boost::multi_index::index<DataStorage, 
Index>::index::const_iterator
     myfind(unsigned int v)
     {
         return storage_.template get<Index>().find(v);
     }

The entire code is below.

As I gave up on writing an iterator (see below), I am trying to do the 
best I can do with some cosmetic code.

The part in #if 0 / #endif is my failed attempt to use equal_range with 
something more palatable, but it fails again.

> Note that this is *not* the same as returning a custom iterator type
> that is able to traverse the different indices DataStorage is
> comprised of: in order to do that you need to implement an iterator
> class with *type erasure*, which has a run-time penalty and is not
> entirely trivial to write. If you want to know more about
> type-erasing iterators, take a look at, for instance,
> adobe::any_iterator:

I guess I won't be writing a type-erasure-based custom iterator: I don't 
like run-time overhead if I can avoid this :)

Thanks!

=== SOURCE CODE ===

#include <boost/multi_index_container.hpp>
#include <boost/multi_index/global_fun.hpp>
#include <boost/multi_index/ordered_index.hpp>
#include <boost/multi_index/hashed_index.hpp>

#include <functional>
#include <iomanip>
#include <iosfwd>
#include <tuple>
#include <list>
#include <utility>
#include <iterator>
#include <type_traits>

typedef __uint128_t Storage;

struct byMSB { };
struct byHSB { };
struct byLSB { };

const int MSBbits = 60;
const int HSBbits =  8;
const int LSBbits = 60;

template <unsigned int N>
struct Mask
{
     static Storage const value = (static_cast<Storage>(1) << N) - 1;
};

template <>
struct Mask<0>
{
     static Storage const value = 0;
};

// Dump to stream
std::ostream &operator<<(std::ostream &os, const Storage &s)
{
     uint64_t msb = (s >> 64), lsb = (s & 0xFFFFFFFFFFFFFFFF);

     os << "0x";
     os << std::hex << std::setfill('0') << std::setw(16) << msb;
     os << " ";
     os << std::hex << std::setfill('0') << std::setw(16) << lsb;
     return os;
}

class Data
{
public:

     Data()
     {};

     // Get the msb
     static uint64_t msb(Storage v)
     {
         return static_cast<uint64_t>((v >> (HSBbits + LSBbits)));
     }

     // Get the hsb
     static uint16_t hsb(Storage v)
     {
         return static_cast<uint16_t>((v >> (LSBbits)) & 
Mask<HSBbits>::value);
     }

     // Get the lsb
     static uint64_t lsb(Storage v)
     {
         return static_cast<uint64_t>(v & Mask<LSBbits>::value);
     }

     // Returns a storage type
     static Storage storage(uint64_t msbv, uint16_t hsbv, uint64_t lsbv)
     {
         return static_cast<Storage>((static_cast<Storage>(msbv) & 
Mask<MSBbits>::value) << (HSBbits + LSBbits) |
                                     (static_cast<Storage>(hsbv) & 
Mask<HSBbits>::value) << (LSBbits) |
                                     (static_cast<Storage>(lsbv) & 
Mask<LSBbits>::value));
     }

     // Insert a new item
     void insert(uint64_t msbv, uint16_t hsbv, uint64_t lsbv)
     {
         storage_.insert(storage(msbv, hsbv, lsbv));
     }

private:

     // Storage type with indexing
     typedef boost::multi_index::multi_index_container<
         Storage,
         boost::multi_index::indexed_by<
             // Hashed by msb/hsb/lsb
 
boost::multi_index::hashed_non_unique<boost::multi_index::tag<byMSB>, 
boost::multi_index::global_fun<Storage, uint64_t, &Data::msb>>,   // 0
 
boost::multi_index::hashed_non_unique<boost::multi_index::tag<byHSB>, 
boost::multi_index::global_fun<Storage, uint16_t, &Data::hsb>>,   // 1
 
boost::multi_index::hashed_non_unique<boost::multi_index::tag<byLSB>, 
boost::multi_index::global_fun<Storage, uint64_t, &Data::lsb>>    // 2
         >
     > DataStorage;

     DataStorage storage_;

public:

#if 0
     template <class Index>
     using const_iterator = typename DataStorage::hashed_index;

     template <class Index>
     using iterator = std::pair<const_iterator<Index>, 
const_iterator<Index>>;

     template <class Index>
     iterator<Index> use(Storage v)
     {
         auto &p = storage_.template get<Index>();

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

         return iterator<Index>(q);
     };
#endif

     template<typename Index>
     typename boost::multi_index::index<DataStorage, 
Index>::index::const_iterator
     myfind(unsigned int v)
     {
         return storage_.template get<Index>().find(v);
     }

};

int main(int argc, const char * argv[])
{
     Data d;

     d.insert(1, 0, 0);
     d.insert(2, 1, 0);
     d.insert(3, 0, 0);
     d.insert(1, 1, 1);
     d.insert(4, 0, 4);
     d.insert(5, 4, 3);
     d.insert(1, 9, 9);

     auto q = d.myfind<byMSB>(Data::storage(1, 30, 30));

     return 0;
}