Best way to associate 3 things in C++

Question

In my C++ application I have a problem where I need to associate 3 things and look them up or iterate over any one column.

Let's say I have 3 classes A, B, C, and an A may be two or three combinations of B/C pairs. I want to be able to find all As associated with Bs, all B-C pairs for each A, or each B for a given A and C.

This is not obvious to me other than having a vector of std::tuple and linearly iterating over the whole list, but I'd rather have hash-table like access. Another method I thought of is simply to make multiple hash tables of A -> vector<pair<B,C>>, B -> vector<pair<A,C>, that sort of thing, but it seems a headache to maintain.

Answer 1

I have written code to solve a potentially similar problem before and I did it like this which has worked out ok (so far).

In some class:

You could store a vector of tuples like:

vector<tuple<A, B, C>> tuple_array;

And maps for the hashed access that simply point to the tuple index like:

map<A, size_t> a_mapping;
map<B, size_t> b_mapping;
map<C, size_t> c_mapping;

In the constructor of the class you can derive the mappings fairly simply. This is assuming that As, Bs, and Cs can be sorted or hashed.

With this data structure you can write whatever query methods you need on that class and the implementation should always be decently simple and fast.

Adding a new element to the tuple array is simple. The mappings are essentially just caches allowing fast lookup. Things get a little more tricky if an instance A, B or C could be in multiple tuples, you might have to map to a vector of size_t.

Adding D is also fairly straight-forward in this design.

If you need some relationships to not have one of the classes you could replace tuple with variant potentially.

Answer 2

The Boost Multi-index Containers Library seems very close to what you want. From the introduction:

The Boost Multi-index Containers Library provides a class template named multi_index_container which enables the construction of containers maintaining one or more indices with different sorting and access semantics.

. . .

The versatile nature of Boost.MultiIndex allows for the specification of a wide spectrum of different data structures. The following are possible examples of use developed in the documentation:

• Sets with several iteration orders and search criteria.
• Lists with fast lookup and/or without duplicates.
• Bidirectional maps, i.e. maps searchable either for key or value. MRU (most recently used) lists, structures keeping the n last referenced items, beginning with the newest ones.
• Emulations of standard containers taking advantage of the extra functionalities provided by Boost.MultiIndex.