C++ data structure to store multiple relationships between two unique sets of elements

I am working on a project where I have two unique sets of elements. Any of the elements in one set may be related to any of the elements in the other set.

Example:

Set 1: {A, B, C}

Set 2: {1, 2, 3, 4}

Allowed relationships:

(A, 1) (A, 3)

(B, 1) (B, 4)

(C, 1) (C, 3) (C, 4)

A single relationship is represented as two set elements inside one pair of parentheses.

In my particular project, the elements of both sets are objects, and I would like all references to all objects stored to resolve to one object (for example, all relationships containing A would all refer to the same object A, and the same goes for the references to other set on the other side of the relationship).

I was thinking of using a Boost bimap to solve for this problem. I was looking at the potential types of collections used for the left and right halves of the bimap and for the relationship between the two sets, and have been trying to decide which ones are correct.

For the left and right halves of the bimap, I was thinking that the set_of CollectionType would be correct, as my two sets of objects are, well, sets, and I do not want duplicate copies of any element in my bimap.

However, when I've tried this out in practice, I end up not being able to insert the relationship (B, 1) after I've inserted the relationship (A, 1), as the insertion must be valid in both the left and right views for it to occur. To correct for this problem, I've changed the CollectionType of both halves to be multiset_of. All values are properly inserted, however, does this mean that my bimap now has duplicate copies of the elements of my original sets?

To try and correct for this, I started looking at changing the collection type of the relationship between the two halves of the bimap. Since the collection type of the relationship type defaults to that of the left half of the bimap, I figured that multiset_of is incorrect, and specified it as set_of. However, I'm not sure that this fixes my original problem of having multiple copies of my objects from my original sets.

All I really need is to look at all objects from Set 2 that are related to an element from Set 1. Is a Boost bimap the correct route for me? Are the collection and relationship types I have selected the right ones? As an aside, I am trying to customize my map to have quick search times, with no concern for insertion times (deletion and modification will never happen, the map is initialized and then is just used for lookups after that). Should I just write a custom data structure instead?

Solution

I completely agree with Jerry's answer. If you're trying to model a graph, consider using an adjacency list, edge list or matrix representation, for example.

Paul's answer was a bit hand-wavy, so, here goes a sample using Boost Multi Index:

Live On Coliru

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

struct T1 {
    std::string name;
    bool operator<(T1 const& o) const { return name < o.name; }
};
struct T2 {
    int id;   
    bool operator<(T2 const& o) const { return id < o.id; }
};

namespace bmi = boost::multi_index;

struct Relation {
    T1 const* key1;
    T2 const* key2;

    std::string const& name() const { return key1->name; }
    int                id  () const { return key2->id;   }

    friend std::ostream& operator<<(std::ostream& os, Relation const& r) {
        return os << "(" << r.name() << ", " << r.id() << ")";
    }
};

using RelationTable = bmi::multi_index_container<Relation,
      bmi::indexed_by<
        bmi::ordered_unique<bmi::tag<struct by_composite>, 
            bmi::composite_key<Relation, 
                bmi::const_mem_fun<Relation, std::string const&, &Relation::name>,
                bmi::const_mem_fun<Relation, int, &Relation::id>
            >
        >
    > >;

#include <set>

int main() {
    using namespace std;
    set<T1> set1 { {"A"}, {"B"}, {"C"} };
    set<T2> set2 { {1}, {2}, {3}, {4} };

    // convenient data entry helpers
    auto lookup1 = [&set1](auto key) { return &*set1.find(T1{key}); }; // TODO error check?
    auto lookup2 = [&set2](auto key) { return &*set2.find(T2{key}); };
    auto relate  = [=](auto name, auto id) { return Relation { lookup1(name), lookup2(id) }; };
    // end helpers

    RelationTable relations {
        relate("A", 1), relate("A", 3),
        relate("B", 1), relate("B", 4),
        relate("C", 1), relate("C", 3), relate("C", 4),
    };

    for (auto& rel : relations)
        std::cout << rel << " ";
}

Prints

(A, 1) (A, 3) (B, 1) (B, 4) (C, 1) (C, 3) (C, 4)