Combinations of a variadic list of arbitrary types

user_4555763 0
Viewed 97

I'd like to get a cartesian product of all the possible string-value pairs which are input in a variadic list of arguments and obtain a map M as,

using M = std::unordered_map<std::string, boost::any>;
template<typename ...Args>
std::vector<M> combinations(const std::pair<std::string, std::vector<Args>> &...args) {
// ... ??
}

A possible input is

std::pair<std::string, std::vector<std::string>> v1 = {"A", {"x","y","z"}};
std::pair<std::string, std::vector<int>> v2 = {"B", {1,2,3}};
std::pair<std::string, std::vector<double>> v3 = {"C", {0.1,0.2,0.3}};

auto m1 = combinations(v1,v2) // a vector consisting of 9 maps. E.g., m1[0] = {{"A","x"},{"B",1}} etc...
auto m2 = combinations(v1,v2,v3) // a vector consisting of 27 maps. E.g., m2[0] = {{"A","x"},{"B",1},{"C",0.1}} etc...

m1 (to be explicit)

m1[0] : {{"A","x"},{"B",1}}
m1[1] : {{"A","x"},{"B",2}}
m1[2] : {{"A","x"},{"B",3}}
m1[3] : {{"A","y"},{"B",1}}
m1[4] : {{"A","y"},{"B",2}}
m1[5] : {{"A","y"},{"B",3}}
m1[6] : {{"A","z"},{"B",1}}
m1[7] : {{"A","z"},{"B",2}}
m1[8] : {{"A","z"},{"B",3}}

How do I implement this?

variadic-templates template-meta-programming c++
1 Answers

I don't think it's necessary to use std::any/boost::any here since we can figure out the exact types.

For example, m1 will be a:

std::vector< std::tuple< std::pair<std::string, std::string>,
                         std::pair<std::string, int> > >;

Here's one way:

  • In combinations I deduce the tuple type to store in the resulting vector and call xprod passing all the pairs on with an index_sequence.
  • From these the cross product will be created in the function xprod. I create an array of pair<size_t, size_t> for the indices in each vector. idxlim[].first holds the current index, and idxlim[].second holds each vector's size(). To step the combined index value over all the vectors, I use this:
template <size_t N>
bool step_index(std::array<std::pair<size_t, size_t>, N>& idxlim) {    
    for (size_t i = N; i--;) {
        auto&[idx, lim] = idxlim[i];
        if (++idx != lim) return true;
        idx = 0;
    }
    return false; // reached the end
}

The xprod function receives the pairs and creates idxlim which contains the current index and the limit for each vector and just loops through all combinations, populating the resulting vector, rv, as it goes:

template <class T, size_t... I, class... P>
auto xprod(std::index_sequence<I...>, const P&... pairs) {
    std::vector<T> rv;
    std::array<std::pair<size_t, size_t>, sizeof...(P)> idxlim{
        {{0, pairs.second.size()}...}
    };

    do {
        rv.emplace_back(T{{pairs.first, pairs.second[ idxlim[I].first ]}...});
//                         ^^^^^^^^^^^  ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
//                         std::string        the "any" type
    } while(step_index(idxlim));

    return rv;
}

The "magic" in T{{pairs.first, pairs.second[ idxlim[I].first ]}...} is that it's a parameter expansion over I... (think horizontally) and I... is supplied by creating an index_sequence from the entry function (se below). It's not one pair. It's all of them (keep thinking horizontally):

It'll be expanded to these emplace_backs:

T{{"A", "x"}, {"B", 1}}
T{{"A", "x"}, {"B", 2}}
T{{"A", "x"}, {"B", 3}}
T{{"A", "y"}, {"B", 1}}
T{{"A", "y"}, {"B", 2}}
T{{"A", "y"}, {"B", 3}}
T{{"A", "z"}, {"B", 1}}
T{{"A", "z"}, {"B", 2}}
T{{"A", "z"}, {"B", 3}}

Entry function:

template <class... Ts>
auto combinations(const std::pair<std::string, std::vector<Ts>>&... args) {
    using tt = std::tuple<std::pair<std::string, Ts>...>;

    return xprod<tt>(std::make_index_sequence<sizeof...(Ts)>{}, args...);
}

Demo

user_75822470
Related