是否有一些STL函数可以获得两个C++向量的笛卡尔积？

Question

假设

b =  ["good ", "bad "]
a  = ["apple","mango"]
then output = ["good apple","good mango","bad apple","bad mango"]

我知道这可以用嵌套的for循环来完成,但是使用C++ STL是否有一些优雅的衬里呢？

Answer 1

鉴于vector<string> a您vector<string> b可以使用for_each：

vector<string> output(size(a) * size(b));

for_each(begin(output), end(output), [&, it = 0U](auto& i) mutable {
    i = a[it / size(b)] + ' ' + b[it % size(b)];
    ++it;
});

Live Example

编辑：

我们已经初始化了足够的空间来包含和output的每个组合。然后我们将逐步遍历 的每个元素并对其进行分配。aboutput

我们将使用 的第一个元素作为的第^一个元素，使用 的第二^个元素作为第二个元素，依此类推。因此，我们将通过使用 进行索引来完成此操作。我们希望通过迭代s 元素来组合它。asize(b)outputasize(b)it / size(b)b

it将移动到 的每个元素的下一个索引，output但索引需要换行，否则当 时，索引将超出范围it == size(b)，为此我们使用it % size(b)。

编辑2：

在这个问题中，通过基准测试，我发现了一个现象，即求模和除法对于迭代来说是昂贵的操作。我在这里做了同样的测试。为了隔离算法，我只是对vector<int>not进行笛卡尔求和vector<string>。

首先，我们可以看到两种算法产生不同的汇编结果。我上面写的算法需要 585 行汇编。我对MSalter 代码的解释需要 588 行

vector<string> output(size(testValues1) * size(testValues2));
auto i = begin(output);

std::for_each(cbegin(a), cend(a), [&](const auto& A) { std::for_each(cbegin(b), cend(b), [&](const auto& B) { *i++ = A + ' ' + B; }); });

我在这里进行了相当可靠的基准测试：http://ideone.com/1YpzIO在测试中，我只将其设置为进行 100 次测试，但 MSalters 的算法总是获胜。在本地使用已发布的 Visual Studio 2015 进行 10,000,000 次测试，MSalters 算法的完成时间约为我的时间的 2/3。

显然模数并不是一个很好的索引方法:(