如何在 C++ 中组合两个或多个任意类型的向量

Question

我有以下代码将任意类型的两个向量组合成一个组合，即 std::vector<std::tuple<A, B>>。

template<class A, class B>
std::vector<std::tuple<A, B>> combine(const std::vector<A>& a, const std::vector<B>& b) {

    const auto combine_parts_ = [](const A& x, const B& y) {
        auto result = std::tuple_cat(std::make_tuple(x), std::make_tuple(y));
        return result;
    };

    std::vector<std::tuple<A, B>> results;

    for (const auto& x : a) {
        for (const auto& y : b) {
            results.push_back(combine_parts_(x, y));
        }
    }

    return results;
}

但是，我不清楚如何将其扩展到任意数量的 types/vectors。我不关心重复类型；事实上，可能涉及两套或多套相同类型的设备。没关系。

一些示例用例，例如：

const auto combinations = combine(
    std::vector<int>({1,2,3})
    , std::vector<int>({1,2,3})
);
const auto combinations2 = combine(
    std::vector<int>({1,2,3})
    , std::vector<int>({1,2,3})
    , std::vector<bool>({true,false})
);
const auto combinations3 = combine(
    std::vector<int>({1,2,3})
    , std::vector<int>({1,2,3})
    , std::vector<bool>({true,false})
    , std::vector<char>({'a','b','c','d','e'})
);

主要是，我想做的是避免丑陋的嵌套 for 循环。同时，我想结合一些单元测试组合用例，以便将结果 std::tuple<...> 作为测试用例。

注意，我这里不是在谈论同构集合的排列。这是之前问题的一个混淆点。

我认为这可能与模板、可变参数、std::tuple_cat 相关，但我不知道。

想法？建议？

Answer 1

如果你想计算异构向量的笛卡尔积，你可以这样做：

template <std::size_t N>
bool increase(const std::array<std::size_t, N>& sizes, std::array<std::size_t, N>& it)
{
    for (std::size_t i = 0; i != N; ++i) {
        const std::size_t index = N - 1 - i;
        ++it[index];
        if (it[index] >= sizes[index]) {
            it[index] = 0;
        } else {
            return true;
        }
    }
    return false;
}

template <typename F, std::size_t ... Is, std::size_t N, typename Tuple>
void apply_impl(F&& f,
                std::index_sequence<Is...>,
                const std::array<std::size_t, N>& it,
                const Tuple& tuple)
{
    f(std::get<Is>(tuple)[it[Is]]...);
}

template <typename F, typename ... Ts>
void cartesian_product_apply(F&& f, const std::vector<Ts>&... vs)
{
    constexpr std::size_t N = sizeof...(Ts);
    std::array<std::size_t, N> sizes{{vs.size()...}};
    std::array<std::size_t, N> it{};

    do {
        apply_impl(f, std::index_sequence_for<Ts...>(), it, std::tie(vs...));
    } while (increase(sizes, it));
}

最后：

template <typename ... Ts>
std::vector<std::tuple<Ts...>> cartesian_product(const std::vector<Ts>&... vs)
{
    std::vector<std::tuple<Ts...>> res;

    cartesian_product_apply([&res](const auto&... args) { res.emplace_back(args...); },
                            vs...);
    return res;
}

用法类似于：

std::vector<int> v1 = {1, 2, 3};
std::vector<std::string> v2 = {" A "," B "};
std::vector<int> v3 = {4, 5};

const auto res = cartesian_product(v1, v2, v3);
for (const auto& t : res) {
    // ...
}

Demo

Answer 2

稍作调整，并禁用警告：

struct CartesianProduct {

    template<typename... Tys>
    std::vector<std::tuple<Tys...>> operator()(const std::vector<Tys>&... vectors) {
        std::vector<std::tuple<Tys...>> results;
        apply([&results](const auto&... args) {
            results.emplace_back(args...); }, vectors...);
        return results;
    }

private:

    template<std::size_t N>
    bool __increase(const std::array<std::size_t, N>& sizes, std::array<std::size_t, N>& it) {
        for (std::size_t i = 0; i < N; ++i) {
            const std::size_t index = N - 1 - i;
            ++it[index];
            if (it[index] >= sizes[index]) {
                it[index] = 0;
            }
            else {
                return true;
            }
        }
        return false;
    }

    template<typename Cb, std::size_t... Is, std::size_t N, typename Tup>
    void __apply_impl(Cb&& cb, std::index_sequence<Is...>
        , const std::array<std::size_t, N>& it, const Tup& tup) {
        cb(std::get<Is>(tup)[it[Is]]...);
    }

    template <typename Cb, typename... Tys>
    void apply(Cb&& cb, const std::vector<Tys>&... vectors) {
        constexpr std::size_t N = sizeof...(Tys);
        std::array<std::size_t, N> sizes{ {vectors.size()...} };
#pragma warning (disable: 4834)
        // TODO: TBD: warning C4834: discarding return value of function with 'nodiscard' attribute...
        std::array<std::size_t, N> it{ {(vectors.size(), 0u)...} };
#pragma warning (default: 4834)

        do {
            __apply_impl(cb, std::index_sequence_for<Tys...>(), it, std::tie(vectors...));
        } while (__increase(sizes, it));
    }
};

记得包括 tuple、vector 以及 array。

使用简单：

CartesianProduct prod;
// ...
const auto product_ = prod(ints_, doubles_, bools_);
CHECK(std::tuple_size<decltype(product_ )::value_type>::value == 3);

虽然不完全肯定警告的全部内容。

如何在 C++ 中组合两个或多个任意类型的向量

How to combine two or more vectors of arbitrary types in C++

c++

tuples

vector

cartesian-product