Boost multi-index container vs a multi-level mapping container based on std::unordered_map (map of maps)

Question

I recently found boost::multi_index_container and I'm curious about his performance compared to my own implementation of a similar container based on multi-level mapping and defined as:

typedef int      Data;
typedef uint64_t MainKey;
typedef uint64_t SecondaryKey;

typedef std::unordered_map<SecondaryKey, Data>       SecondaryMap;
typedef std::unordered_map<PrimaryKey, SecondaryMap> PrimaryMap;

The key ordering is not important. The fast lookup is important and for this I'm using something like:

// find primaryKey=10 and secondaryKey=30
PrimaryMap m;
....
auto i1 = m.find( 10);
if ( i1 != m.end())
{
    auto& secondary = i1->second;
    auto i2 = secondary.find( 30);
    if ( i2 != secondary.end())
    {
        found = true;
        ....
    }
}

I would like to know what would be

• the most closest configuration of boost::multi_index_container to match my implementation
• the fastest way to search by primary key and secondary key.

I have tried to configure the template but I'm not sure if this is the best solution:

struct RecordKey
{
    MainKey         mainKey;
    SecondaryKey    secondaryKey;

    RecordKey( const MainKey mainKey, SecondaryKey secondaryKey):
        mainKey( mainKey),
        secondaryKey( secondaryKey)
    {}
};

struct Record: public RecordKey
{
    Data data;

    Record( const MainKey mainKey = 0, const SecondaryKey secondaryKey = 0, const Data& data = 0):
        RecordKey( mainKey, secondaryKey),
        data( data)
    {}
};


struct MainKeyTag {};
struct SecondaryKeyTag {};
struct CompositeKeyTag {};

using boost::multi_index_container;
using namespace boost::multi_index;

typedef boost::multi_index_container<Record,
    indexed_by  <   /*random_access<>,*/
                    hashed_non_unique<tag<MainKeyTag>,      BOOST_MULTI_INDEX_MEMBER( RecordKey, MainKey, mainKey) >,
                    hashed_non_unique<tag<SecondaryKeyTag>, BOOST_MULTI_INDEX_MEMBER( RecordKey, SecondaryKey, secondaryKey) >,
                    hashed_unique<tag<CompositeKeyTag>,     composite_key<Record,   member<RecordKey, MainKey, &RecordKey::mainKey>,
                                                                                    member<RecordKey, SecondaryKey, &RecordKey::secondaryKey> > > > > RecordContainer;

Answer 1

You can have your cake and eat it too, by choosing ordered (instead of hashed) indexes in BMI.

There is a nice property of ordered composite indexes that allows you to query by partial keys, so you need only define the composite index to be able to query by main index too:

typedef boost::multi_index_container<
    Record,
    indexed_by<
        ordered_non_unique< tag<CompositeKeyTag>, 
        composite_key<Record, 
                    member<RecordKey, MainKey, &RecordKey::mainKey>,
                    member<RecordKey, SecondaryKey, &RecordKey::secondaryKey>
    > > > > RecordContainer;

Now you can either query by mainKey:

range = index.equal_range(10);

Or by composite:

range = index.equal_range(boost::make_tuple(10,30));

Background:

• boost::multi_index composite keys efficiency
• http://www.boost.org/doc/libs/1_56_0/libs/multi_index/doc/tutorial/key_extraction.html#composite_keys

Here's a full demo Live On Coliru:

#include <boost/multi_index_container.hpp>
#include <boost/multi_index/composite_key.hpp>
#include <boost/multi_index/hashed_index.hpp>
#include <boost/multi_index/ordered_index.hpp>
#include <boost/multi_index/member.hpp>
#include <boost/range/iterator_range.hpp>
#include <iostream>

using MainKey      = uint64_t;
using SecondaryKey = uint64_t;
using Data         = std::string;

struct RecordKey
{
    MainKey         mainKey;
    SecondaryKey    secondaryKey;

    RecordKey( const MainKey mainKey, SecondaryKey secondaryKey):
        mainKey( mainKey),
        secondaryKey( secondaryKey)
    {}
};

struct Record: public RecordKey
{
    Data data;

    Record( const MainKey mainKey = 0, const SecondaryKey secondaryKey = 0, const Data& data = 0):
        RecordKey( mainKey, secondaryKey),
        data( data)
    {}

    friend std::ostream& operator<<(std::ostream& os, Record const& r) {
        return os << " Record[" << r.mainKey << ", " << r.secondaryKey << ", " << r.data << "]";
    }
};

struct MainKeyTag {};
struct SecondaryKeyTag {};
struct CompositeKeyTag {};

using boost::multi_index_container;
using namespace boost::multi_index;

typedef boost::multi_index_container<
    Record,
    indexed_by<
        ordered_non_unique< tag<CompositeKeyTag>, 
        composite_key<Record, 
                    member<RecordKey, MainKey, &RecordKey::mainKey>,
                    member<RecordKey, SecondaryKey, &RecordKey::secondaryKey>
    > > > > RecordContainer;


int main()
{
    RecordContainer records;
    records.insert(Record(10, 20, "12"));
    records.insert(Record(10, 30, "13"));
    records.insert(Record(10, 30, "13 - need not be unique!"));
    records.insert(Record(30, 40, "34"));
    records.insert(Record(30, 50, "35"));
    records.insert(Record(50, 60, "56"));
    records.insert(Record(50, 70, "57"));
    records.insert(Record(70, 80, "78"));

    std::cout << "\nAll records:\n----------------------------------------------------------------------\n";
    for (auto const& r : records)
        std::cout << r << "\n";

    {
        std::cout << "\nAll records with (main) == (10):\n----------------------------------------------------------------------\n";
        auto& index = records.get<0>();
        auto range = index.equal_range(10);
        for (auto const& r : boost::make_iterator_range(range.first, range.second))
            std::cout << r << "\n";
    }

    {
        std::cout << "\nAll records with (main,secondary) == (10,30):\n----------------------------------------------------------------------\n";
        auto& index = records.get<0>();
        auto range = index.equal_range(boost::make_tuple(10,30));
        for (auto const& r : boost::make_iterator_range(range.first, range.second))
            std::cout << r << "\n";
    }
}

Output:

All records:
----------------------------------------------------------------------
 Record[10, 20, 12]
 Record[10, 30, 13]
 Record[10, 30, 13 - need not be unique!]
 Record[30, 40, 34]
 Record[30, 50, 35]
 Record[50, 60, 56]
 Record[50, 70, 57]
 Record[70, 80, 78]

All records with (main) == (10):
----------------------------------------------------------------------
 Record[10, 20, 12]
 Record[10, 30, 13]
 Record[10, 30, 13 - need not be unique!]

All records with (main,secondary) == (10,30):
----------------------------------------------------------------------
 Record[10, 30, 13]
 Record[10, 30, 13 - need not be unique!]