C++实现可变参数任意类型键值对的笛卡尔积组合函数

需求说明 #

需要实现可变参数模板函数combinations，对传入的多组「字符串键-同类型可选值列表」对计算笛卡尔积，最终返回存储映射类型M的向量，其中M定义为键为字符串、值为boost::any的哈希表。
预定义的类型与函数声明如下：

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) {
// 待实现
}

输入输出示例 #

测试输入代码：

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); // 返回包含9个M的vector
auto m2 = combinations(v1,v2,v3); // 返回包含27个M的vector

其中两参数调用返回的m1元素顺序如下：

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}}

实现代码 #

基于C++17折叠表达式与结构化绑定实现，逻辑简洁且性能可控：

#include <vector>
#include <unordered_map>
#include <string>
#include <utility>
#include <boost/any.hpp>

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) {
    std::vector<M> result{M{}};
    
    // 遍历所有传入的键值列表组，逐组做笛卡尔积扩展
    (
        [&result](const auto& kv_group) {
            const auto& [current_key, value_list] = kv_group;
            std::vector<M> tmp;
            tmp.reserve(result.size() * value_list.size());
            
            for (const auto& existed_map : result) {
                for (const auto& val : value_list) {
                    M new_map = existed_map;
                    new_map[current_key] = val;
                    tmp.push_back(std::move(new_map));
                }
            }
            
            result = std::move(tmp);
        }(args), ...
    );

    return result;
}

实现逻辑说明 #

• 初始状态下结果集仅包含1个空映射，对应0个输入参数时的唯一组合。
• 每处理一组键值列表时，创建临时存储容器，将当前结果集中的每一个映射，分别与当前组的所有可选值配对，生成包含当前键值对的新映射存入临时容器。
• 当前组所有组合生成完成后，通过移动语义将临时容器替换为新的结果集，避免深拷贝开销。
• 提前根据笛卡尔积的元素总数预分配内存，减少vector扩容带来的性能损耗。
• 由于映射值类型为boost::any，不同类型的可选值都可以直接存入，无需额外类型转换。

内容的提问来源于stack exchange，提问作者marital_weeping