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

Question

假设

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

我知道可以使用嵌套的for循环来完成这个任务，但是否有一行优雅的代码使用C++ STL来完成呢？

- Abhishek Kumar

---

可能存在这种观点，但何必让一切变得更难理解呢？循环结构并非恶魔。 - deviantfan

可能是从两个向量的连接构建向量的重复问题。 - Jonathan Mee

@JonathanMee：不是这样的。这会创建一个长度为M*N的输出，而不是长度为N+M的输出。 - MSalters

for (auto i : a) for (auto j : b) output.push_back(i + ' ' + j); 真的吗？ - Nim

@Jonathan Mee，我认为这不是重复的问题。 OP想要两个向量的笛卡尔积的串联。 - Alessandro Teruzzi

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

演示样例

编辑：

我们已经初始化了 output，使其能够容纳每个 a 和 b 的组合。然后我们将遍历每个 output 元素并进行赋值。

我们将想要使用 a 的第一个元素来填充 output 的前 size(b) 个元素，并使用 a 的第二个元素来填充接下来的 size(b) 个元素，以此类推。因此，我们将使用 it / size(b) 进行索引。我们还需要通过迭代 b 的元素来完成这一操作。

it 将在每个 output 元素上移动到下一个索引，但索引需要进行循环，否则当 it == size(b) 时，它将越界，为了解决这个问题，我们使用 it % size(b)。

编辑2：

在这个问题中，通过基准测试我发现取模和除法是迭代的昂贵操作。我在这里进行了相同的测试。为了隔离算法，我只在一个 vector<int> 上执行笛卡尔求和，而不是 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中使用release模式和1000万个测试时，MSalters的算法完成时间大约是我的算法的2/3。

很明显，取模不是一个很好的索引方法 :(

- Jonathan Mee

---

这只将a的cend(a)-cbegin(a)个元素写入output。 - MSalters

@InnocentBystander 的确，Lambda 函数通常都是一行写完的。特别是在它们被嵌套在 STL 算法中时：for_each(begin(output), end(output), [&, it = 0U](auto& i) mutable { i = a[it / size(b)] + ' ' + b[it % size(b)]; ++it; }); - Jonathan Mee

@JonathanMee，没关系。 - Super-intelligent Shade

@JonathanMee，请注意你的程序输出采用尤达记法，即“apple good”而不是“good apple”。 - Super-intelligent Shade

并不意外 - 除法和取模相对于整数加法而言速度较慢。而且它们在内存访问的关键路径上；每次读取主内存都必须等待除法和取模完成。 - MSalters

Answer 2

这是一行代码（从Jonathan Mee的答案复制而来）：

for(size_t i = 0, s = a.size(); i < output.size(); ++i) output[i] = b[i/s] + ' ' + a[i%s];

Full example here.

- Super-intelligent Shade

---

@AbhishekKumar 你可以在我的回答中找到详细的解释...但是，正如我在评论中提到的那样，这并不是没有代价的。模运算可能需要几个周期才能完成。MSalter的回答没有产生这样的代价，因此，我认为他的回答是最好的。 - Jonathan Mee

@JonathanMee：重新阅读一下我说的话：当连接字符串时，所有这些都是废话，因为单个调用分配器比指数细节大得多。但是，我怀疑即使使用除法方法编写公平的基准测试也应该基本相同。在当前CPU上，对索引（=已经在寄存器中）进行除法比任何内存访问都要快得多（而在此循环中，您至少有三个内存访问）。可能确定获胜者的差异将取决于一个案例中的额外分支和另一个案例中的一个额外内存访问。 - Matteo Italia

@JonathanMee: 好的，所以：手动提升循环外的任何内容没有特别的优势，嵌套循环胜出；然而，我的主要观点仍然成立-当您对字符串执行此操作时，它们是无法区分的。 - Matteo Italia

@JonathanMee：更有趣的是，在我的机器上，MSalter版本在大向量上比我的版本快了一个数量级。原来，在64位机器上，g++能够对循环进行自动向量化，并发出'movdqa'/'paddd'/'movups'序列，实际上每次执行4个元素的求和。更好的是，使用'-march=native'，它使用AVX并直接转到'vpaddd'/'vmovup'。 - Matteo Italia

@JonathanMee：嗯，实际上并不是处理器在“隐藏”任何东西，更像是“分配一个新的std::string比循环中发生的其他任何事情都要昂贵得多，所以这种修改实际上只是噪音”。就像把一盒饼干放在你车子的后备箱里一样——它实际上并不会影响你的里程数 =)。 - Matteo Italia

Answer 3

目前没有直接的解决方案；我检查了整个<algorithm>，没有任何函数可以产生长度为M*N的输出。

您可以在第一个范围上调用std::for_each，使用一个lambda函数，在其中调用第二个范围上的std::for_each！

std::vector<std::string> a, b;
std::for_each(a.begin(), a.end(), 
  [&](std::string A) { std::for_each(b.begin(), b.end(),
      [A](std::string B) { std::cout << A << '/' << B << '\n';  }
);});

但那只是STL中的嵌套循环。

- MSalters

---

我认为你必须是一种特殊的受虐狂，才会用这个来代替两个简单的基于范围的for循环和一个push back操作... ;) - Nim

@InnocentBystander：我不知道他的显示器有多宽 ;) - MSalters

@MSalters 您的答案并不适合通过push_back以外的方式迭代地分配给vector，因为这种方式已知速度较慢。我已经修改了您的算法，用于基准测试。欢迎任何评论。 - Jonathan Mee

@JonathanMee：使用.reserve()并不会太糟糕。 - MSalters

@JonathanMee：这是STL未能将迭代器范围实现为一等对象所付出的代价。如果有一个“OutputRange”概念，它就可以有一个.reserve方法。 - MSalters