boost bimap with associated value

Question

Is there a way to construct a boost::bimap (or multi-index container) that has two keys, plus a value they both point to? In addition, you can query one key to get the other?

I can construct a boost multi-index container that has two keys for some element, but cannot figure out how to get the value of a key given the value of the other key?

I am trying to do something like:

struct s {};   
int main()    
{   
typedef std::map<int, std::shared_ptr<s>> left_map_type;  
typedef std::map<std::string, std::shared_ptr<s>> right_map_type;  
typedef boost::bimap<left_map_type, right_map_type> bi_map_type;  
typedef bi_map_type::value_type value_type;  
bi_map_type bim;  
std::shared_ptr<s> sp = std::make_shared<s>();  
std::shared_ptr<s> sp2 = std::make_shared<s>();  
left_map_type lm { {1, sp}, {2, sp2} };  
right_map_type rm { {"foo", sp}, {"bar", sp2} };  
bim.insert(lm, rm);  
/*   
  For instance, given the key "foo", search bim to obtain BOTH the shared pointer sp as well as the alternate key '1'.  
*/   
}  

Answer 1

I would use a multi-index container over records like:

struct Data { }; // your "s"

struct Record {
    int         id;
    std::string name;
    Data        data; // std::shared_ptr<Data>?
};

Now you could make a container that adds unique indexes by id and name:

using Table = boost::multi_index_container<Record,
      bmi::indexed_by<
        bmi::ordered_unique< bmi::tag<struct by_id>, bmi::member<Record, int, &Record::id>>,
        bmi::ordered_unique< bmi::tag<struct by_name>, bmi::member<Record, std::string, &Record::name>>
      > >;

Formatting more verbosely:

using Table = boost::multi_index_container<
    Record,
    bmi::indexed_by<
        bmi::ordered_unique<
            bmi::tag<struct by_id>,
            bmi::member<Record, int, &Record::id>>,
        bmi::ordered_unique<
            bmi::tag<struct by_name>,
            bmi::member<Record, std::string, &Record::name>>>>;

See below for a less verbose way;

Now you can make your table and access it using any of the indices:

Table table;
auto& left  = table.get<by_id>();   // or get<0>
auto& right = table.get<by_name>(); // or get<1>

Whatever interface you use, any changes will reflect in all other indexes, and uniqueness constraints are guaranteed. E.g.

table.emplace(1, "one", Data{"Sleepy", {1, 2, 3}});
table.emplace(2, "two", Data{"Grumpy", {2, 4, 6}});
table.emplace(3, "three", Data{"Sneezy", {3, 6, 9}});

Just printing them (using libfmt for demo):

// Simple enumeration:
fmt::print("Just the table:\n - {}\n", fmt::join(table, "\n - "));
fmt::print("By id:\n - {}\n", fmt::join(left, "\n - "));
fmt::print("By name:\n - {}\n", fmt::join(right, "\n - "));

Prints

Just the table:
 - Record{1, one, Data{Sleepy, {1, 2, 3}}}
 - Record{2, two, Data{Grumpy, {2, 4, 6}}}
 - Record{3, three, Data{Sneezy, {3, 6, 9}}}
By id:
 - Record{1, one, Data{Sleepy, {1, 2, 3}}}
 - Record{2, two, Data{Grumpy, {2, 4, 6}}}
 - Record{3, three, Data{Sneezy, {3, 6, 9}}}
By name:
 - Record{1, one, Data{Sleepy, {1, 2, 3}}}
 - Record{3, three, Data{Sneezy, {3, 6, 9}}}
 - Record{2, two, Data{Grumpy, {2, 4, 6}}}

This exemplifies that the default index is the first index declared (the "left view" here, or as I'd prefer to call it: by_id).

Searching is just like you'd expect from a standard container:

auto id2     = left.find(2);
auto nameTwo = right.find("two");

if (id2 != left.end())
    fmt::print("id2: {}\n", *id2);
if (nameTwo != right.end())
    fmt::print("nameTwo: {}\n", *nameTwo);

For non-unique indexes, equal_range is useful. There's lower_bound and upper_bound etc.

Live Demo

Live On Compiler Explorer

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

struct Data {
    std::string extra;
    std::vector<int> ints;
};

struct Record {
    int         id;
    std::string name;
    Data        data; // std::shared_ptr<Data>?
};

namespace bmi = boost::multi_index;

#define Index(name)                  \
    bmi::ordered_unique<             \
        bmi::tag<struct by_##name>,  \
        bmi::member<Record, decltype(Record::name), &Record::name>>

using Table = boost::multi_index_container<Record,
      bmi::indexed_by<
        Index(id),
        Index(name)
      > >;

#include <fmt/ranges.h>

template <>
struct fmt::formatter<Data, char> : fmt::formatter<std::string, char> {
    auto format(Data const& data, auto& ctx) {
        return fmt::format_to(ctx.out(), "Data{{{}, {}}}", data.extra,
                              data.ints);
    }
};

template <>
struct fmt::formatter<Record, char> : fmt::formatter<std::string, char> {
    auto format(Record const& rec, auto& ctx) {
        return fmt::format_to(ctx.out(), "Record{{{}, {}, {}}}", rec.id,
                              rec.name, rec.data);
    }
};

int main()
{
    Table table;
    auto& left  = table.get<by_id>();   // or get<0>
    auto& right = table.get<by_name>(); // or get<1>

    table.emplace(1, "one", Data{"Sleepy", {1, 2, 3}});
    table.emplace(2, "two", Data{"Grumpy", {2, 4, 6}});
    table.emplace(3, "three", Data{"Sneezy", {3, 6, 9}});

    // Simple enumeration:
    fmt::print("Just the table:\n - {}\n", fmt::join(table, "\n - "));
    fmt::print("By id:\n - {}\n", fmt::join(left, "\n - "));
    fmt::print("By name:\n - {}\n", fmt::join(right, "\n - "));

    // find:
    auto id2     = left.find(2);
    auto nameTwo = right.find("two");

    if (id2 != left.end())
        fmt::print("id2: {}\n", *id2);
    if (nameTwo != right.end())
        fmt::print("nameTwo: {}\n", *nameTwo);
}

Printing the outbove shown above.

Advanced Topics/Usages

A few things to keep in mind:

• if you really needed to share ownership of the data, you can, of course use shared_ptr<Data> instead
• you can also construct multi-index containers over references/pointers, so I'd advice against shared_ptr unless you know it's actually required
• more flexible key extraction mechanisms exist (e.g. you could have a non-unique ordered index on Record::data::ints::length())
• you can have composite keys, which support partial querying on ordered indexes. This enable "database like" queries, see e.g. Boost multi-index container vs a multi-level mapping container based on std::unordered_map (map of maps) or Using boost multi index like relational DB
• like with the standard containers, the key elements are const. In multi-index containers this implies that all accessors return const references. Refer to the document for modify, replace functions.
• there's a project function to convert iterators between indexes, should you ever require this

Bonus: Less Verbose?

Or, with a clever macro to reduce repetition¹

#define Index(name)                  \
    bmi::ordered_unique<             \
        bmi::tag<struct by_##name>,  \
        bmi::member<Record, decltype(Record::name), &Record::name>>

using Table = boost::multi_index_container<Record,
      bmi::indexed_by<
        Index(id),
        Index(name)
      > >;

---

¹ I was momentarily too lazy to make that template meta functions instead of the macro