如何在C++中按特定模式遍历vector中不同set的元素？

你需要实现的其实就是计算多个集合的笛卡尔积——从每个集合中取出一个元素，生成所有可能的组合。下面是两种在C++中高效实现的方案，分别适配不同的使用场景：

一、递归实现（代码简洁，适合集合数量不多的场景） #

递归的思路非常直观：逐层处理每个std::set，把当前层的每个元素和之前生成的所有组合拼接，直到处理完所有集合。这种方式代码量少、逻辑清晰，适合集合层数较少的场景。

#include <vector>
#include <set>
#include <list>

void generateCartesianProduct(const std::vector<std::set<int>>& input, 
                              size_t currentIndex, 
                              std::list<int>& currentCombination, 
                              std::vector<std::list<int>>& result) {
    // 递归终止条件：处理完所有集合，保存当前组合
    if (currentIndex == input.size()) {
        result.push_back(currentCombination);
        return;
    }

    // 遍历当前集合的每个元素，递归拼接组合
    for (int num : input[currentIndex]) {
        currentCombination.push_back(num);
        generateCartesianProduct(input, currentIndex + 1, currentCombination, result);
        currentCombination.pop_back(); // 回溯，恢复当前组合状态
    }
}

std::vector<std::list<int>> getCartesianProduct(const std::vector<std::set<int>>& input) {
    std::vector<std::list<int>> result;
    if (input.empty()) return result;

    std::list<int> current;
    generateCartesianProduct(input, 0, current, result);
    return result;
}

使用示例 #

#include <iostream>

int main() {
    std::vector<std::set<int>> vec = {{2,4},{1,3,8},{7,5}};
    auto product = getCartesianProduct(vec);

    // 打印结果验证
    for (const auto& lst : product) {
        for (int num : lst) {
            std::cout << num << " ";
        }
        std::cout << "\n";
    }
    return 0;
}

二、迭代实现（性能更优，适合集合数量多、元素量大的场景） #

迭代方式避免了递归的函数调用栈开销，通过逐步构建结果集来实现。我们还可以利用std::move和容器交换来减少内存拷贝，进一步提升效率，适合处理大规模数据的场景。

#include <vector>
#include <set>
#include <list>

std::vector<std::list<int>> getCartesianProductIterative(const std::vector<std::set<int>>& input) {
    std::vector<std::list<int>> result;
    if (input.empty()) return result;

    // 初始化结果集：把第一个集合的每个元素作为独立组合
    for (int num : input[0]) {
        result.push_back({num});
    }

    // 依次处理后续每个集合
    for (size_t i = 1; i < input.size(); ++i) {
        std::vector<std::list<int>> temp;
        // 将已有组合与当前集合的每个元素拼接
        for (const auto& existing : result) {
            for (int num : input[i]) {
                std::list<int> newComb = existing;
                newComb.push_back(num);
                temp.push_back(std::move(newComb)); // 使用move避免不必要的拷贝
            }
        }
        result.swap(temp); // 交换容器，避免额外内存分配
    }

    return result;
}

效率说明 #

• 递归实现的优势是代码简洁、易于理解，但当输入的集合数量较多时，函数调用栈的开销会逐渐显现，递归深度也受限于编译器的栈大小（一般几十层以内都没问题）。
• 迭代实现通过减少拷贝和避免栈开销，性能更稳定，尤其是在处理大规模数据时，效率会明显高于递归。

另外，因为你的输入是有序的std::set<int>，两种实现生成的组合顺序都会和你示例中的顺序完全一致。

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