Lookup on nested boost multi_index_container

Question

Consider following code

struct VersionData
{
    VersionData();
    VersionData(VersionData&& rhs);
    int     m_versionId;
    int     m_weight;
    int     m_pId;
    bool    m_hdi;
};

struct VersionId{};

typedef boost::multi_index_container<
    VersionData,
    bmi::indexed_by<
        bmi::ordered_non_unique<
            bmi::tag<VersionId>,
            bmi::member<VersionData, int, &VersionData::m_versionId>
        >
    >
> VersionDataContainer;

struct VersionsData
{
    VersionsData();
    VersionsData(VersionsData&& rhs);
    int m_sdGroupId;
    int m_retId;
    VersionDataContainer m_versionData;
};

struct mvKey{};

typedef boost::multi_index_container<
    VersionsData,
    bmi::indexed_by<
    bmi::ordered_unique<
            bmi::tag<mvKey>,
            bmi::composite_key<
                VersionsData,
                bmi::member<VersionsData,int, &VersionsData::m_subdeliveryGroupId>,
                bmi::member<VersionsData,int, &VersionsData::m_retargetingId>
            >
        >
    >
> mvDataContainer;

mvDataContainer m_data;

The intention is to lookup using the composite key in mvDataContainer but in some cases I need to lookup in VersionData across all VersionsData. Something like m_data.get<mvKey>.equal_range(make_tuple(ignore, ignore, ignore)).get<VersionId>.equal_range(123456);
First question, is it achievable?
Second, is this the right approach to use nested multi_index_containers? any performance impacts/gains?

Answer 1

It is not the exact answer which I originally asked but since the performance issue was mentioned and in light of discussion with @sehe this is what I found.
1) use flat structure, you can save wasting memory on the same keys using boost::flyweight
2) use MIC instead of tailored containers, MIC might be slightly slower (depends on test scenario) when searching on simple indexes, but once you use composite keys (and implement similar behavior for your tailored datastructure) it is from slightly to significantly faster than tailored DS
My previous statement that tailored one is faster is wrong, since I was using MIC from boost 1.52 and looks like there was a bug when using composite keys with strings (5 orders of magnitude slower than composite without string). When switched to 1.57 everything started to work as expected.

Tests on Coliru
Have a nice indexing, guys! :)

Answer 2

So indeed, instead of using nested containers, like that (live on Coliru)

You could/should implement it as a single /table/ (after all, this is a table with several indices):

Live On Coliru

#include <boost/multi_index_container.hpp>
#include <boost/multi_index/ordered_index.hpp>
#include <boost/multi_index/member.hpp>
#include <boost/multi_index/composite_key.hpp>

namespace bmi = boost::multi_index;

struct VersionRecord {
    int  m_subdeliveryGroupId;
    int  m_retargetingId;
    int  m_versionId;
    int  m_weight;
    int  m_pId;
    bool m_hdi;

    friend std::ostream& operator<<(std::ostream& os, VersionRecord const& record) {
        return os << "{ " << record.m_subdeliveryGroupId << " " << record.m_retargetingId << " "
            << record.m_versionId << " " << record.m_weight << " " << record.m_pId << " " << record.m_hdi << " }";
    }
};

typedef boost::multi_index_container<
    VersionRecord,
    bmi::indexed_by<
        bmi::ordered_unique<
            bmi::tag<struct mvKey>,
            bmi::composite_key<
                VersionRecord,
                bmi::member<VersionRecord,int, &VersionRecord::m_subdeliveryGroupId>,
                bmi::member<VersionRecord,int, &VersionRecord::m_retargetingId>
            >
        >,
        bmi::ordered_non_unique<
            bmi::tag<struct VersionId>,
            bmi::member<VersionRecord, int, &VersionRecord::m_versionId>
        >
    >
> VersionTable;

#include <iostream>
#include <boost/range/iterator_range.hpp>

int main() {

    auto table = VersionTable { 
        { 21, 10,                1,  100, 123, false },
        { 9,  27,                2,  90,  123, false },
        { 12, 25,                3,  110, 123, true  },
        { 10, 33, /*version 8:*/ 8,  80,  123, false },
        { 4,  38,                5,  101, 124, false },
        { 33, 7,                 6,  91,  124, false },
        { 34, 27,                7,  111, 124, true  },
        { 9,  11, /*version 8:*/ 8,  81,  124, false },
        { 0,  12,                9,  99,  125, false },
        { 35, 39, /*version 8:*/ 8,  89,  125, false },
        { 15, 15,                11, 109, 125, true  },
        { 25, 32, /*version 8:*/ 8,  79,  125, false },
    };

    // debug table output
    assert(table.size()==12);
    for (auto& record : table) std::cout << record << "\n";

    // so now you can do:
    auto& idx = table.get<VersionId>();

    std::cout << "---\nQuerying for version id 8:\n";
    for (auto& record : boost::make_iterator_range(idx.equal_range(8)))
        std::cout << record << "\n";
}

Which prints:

{ 0 12 9 99 125 0 }
{ 4 38 5 101 124 0 }
{ 9 11 8 81 124 0 }
{ 9 27 2 90 123 0 }
{ 10 33 8 80 123 0 }
{ 12 25 3 110 123 1 }
{ 15 15 11 109 125 1 }
{ 21 10 1 100 123 0 }
{ 25 32 8 79 125 0 }
{ 33 7 6 91 124 0 }
{ 34 27 7 111 124 1 }
{ 35 39 8 89 125 0 }
---
Querying for version id 8:
{ 25 32 8 79 125 0 }
{ 35 39 8 89 125 0 }
{ 10 33 8 80 123 0 }
{ 9 11 8 81 124 0 }

Alternatively, you can bolt an intrusive container on top of the VersionsData records. This however, complicates the design (you either have to use auto_unlink node hooks (sacrificing thread safety control) or you have to make sure the containers are in synch all the time.

Answer 3

In addition to the other answer suggesting a single container for the whole table, here's the idea based on Boost Intrusive multiset

See it Live On Coliru

#include <boost/multi_index_container.hpp>
#include <boost/multi_index/ordered_index.hpp>
#include <boost/multi_index/member.hpp>
#include <boost/multi_index/composite_key.hpp>

// for intrusive multiset
#include <boost/intrusive/set.hpp>
#include <boost/range/iterator_range.hpp>
#include <iostream>

namespace bmi = boost::multi_index;
namespace bi  = boost::intrusive;

struct VersionData : bi::set_base_hook<bi::link_mode<bi::auto_unlink> > {
    VersionData(int versionId, int weight=0, int pId=0, bool hdi=false) : 
        m_versionId(versionId), m_weight(weight), m_pId(pId), m_hdi(hdi) { }

    int     m_versionId;
    int     m_weight;
    int     m_pId;
    bool    m_hdi;

    friend std::ostream& operator<<(std::ostream& os, VersionData const& vd) {
        return os << "{ " << vd.m_versionId << " " << vd.m_weight << " " << vd.m_pId << " " << vd.m_hdi << " }";
    }

    struct ById {
        bool operator()(VersionData const& a, VersionData const& b) const  { return a.m_versionId < b.m_versionId; }
    };
};

typedef bi::multiset<VersionData, bi::constant_time_size<false>, bi::compare<VersionData::ById> > VersionIndex;

typedef boost::multi_index_container<
    VersionData,
    bmi::indexed_by<
        bmi::ordered_non_unique<
            bmi::tag<struct VersionId>,
            bmi::member<VersionData, int, &VersionData::m_versionId>
        >
    >
> VersionDataContainer;

struct VersionsData
{
    int m_subdeliveryGroupId;
    int m_retargetingId;

    VersionDataContainer m_versionData;
};

typedef boost::multi_index_container<
    VersionsData,
    bmi::indexed_by<
    bmi::ordered_unique<
            bmi::tag<struct mvKey>,
            bmi::composite_key<
                VersionsData,
                bmi::member<VersionsData,int, &VersionsData::m_subdeliveryGroupId>,
                bmi::member<VersionsData,int, &VersionsData::m_retargetingId>
            >
        >
    >
> mvDataContainer;

void insert(
        mvDataContainer& into, VersionIndex& global_version_index,
        int subdeliveryGroupId, int retargetingId, int
        versionId, int weight, int pId, bool hdi) 
{
    auto& mainIdx = into.get<mvKey>();
    auto insertion = mainIdx.insert(VersionsData { subdeliveryGroupId, retargetingId, VersionDataContainer {} });
    mainIdx.modify(insertion.first, [&](VersionsData& record) {
            auto insertion = record.m_versionData.insert(VersionData { versionId, weight, pId, hdi });
            global_version_index.insert(const_cast<VersionData&>(*insertion.first));
    });
}

int main() {

    VersionIndex global_version_index;
    mvDataContainer table;

    insert(table, global_version_index, 21, 10,                1,  100, 123, false);
    insert(table, global_version_index, 9,  27,                2,  90,  123, false);
    insert(table, global_version_index, 12, 25,                3,  110, 123, true);
    insert(table, global_version_index, 10, 33, /*version 8:*/ 8,  80,  123, false);
    insert(table, global_version_index, 4,  38,                5,  101, 124, false);
    insert(table, global_version_index, 33, 7,                 6,  91,  124, false);
    insert(table, global_version_index, 34, 27,                7,  111, 124, true);
    insert(table, global_version_index, 9,  11, /*version 8:*/ 8,  81,  124, false);
    insert(table, global_version_index, 0,  12,                9,  99,  125, false);
    insert(table, global_version_index, 35, 39, /*version 8:*/ 8,  89,  125, false);
    insert(table, global_version_index, 15, 15,                11, 109, 125, true);
    insert(table, global_version_index, 25, 32, /*version 8:*/ 8,  79,  125, false);

    // debug table output
    assert(table.size()==12);

    // so now you can do:
    std::cout << "---\nQuerying for version id 8:\n";
    for (auto& record : boost::make_iterator_range(global_version_index.equal_range(8)))
        std::cout << record << "\n";

    table.erase(table.find(boost::make_tuple(10,33))); // auto unlinks from global_version_index

    std::cout << "---\nQuerying for version id 8:\n";
    for (auto& record : boost::make_iterator_range(global_version_index.equal_range(8)))
        std::cout << record << "\n";
}

Prints:

---
Querying for version id 8:
{ 8 80 123 0 }
{ 8 81 124 0 }
{ 8 89 125 0 }
{ 8 79 125 0 }
---
Querying for version id 8:
{ 8 81 124 0 }
{ 8 89 125 0 }
{ 8 79 125 0 }