26

这个 SO 问题引发了关于标准的讨论std::generate和保证。特别是，您可以使用具有内部状态的函数对象并依赖于generate(it1, it2, gen)调用gen()、存储结果、再次*it调用、存储等，还是可以从后面开始，例如？gen()*(it + 1)

标准（n3337，§25.3.7/1）这样说：

效果：第一个算法调用函数对象gen并通过 range 中的所有迭代器分配 gen 的返回值[first,last)。第二种算法调用函数对象 gen 并通过范围内的所有迭代器分配 gen 的返回值，[first,first + n)如果n为正，则它不执行任何操作。

似乎没有顺序可以保证，特别是因为其他段落有更强的措辞，例如std::for_each（效果：适用f于取消引用范围内每个迭代器的结果[first,last)，从 first 开始并继续到last - 1。如果我们从字面上理解，它只是虽然保证开始first和结束last- 不保证两者之间的顺序）。

但是：Microsoft和Apache 的 C++ 标准库都在其文档页面上提供了要求按顺序进行评估的示例。libc++ (in algorithm) 和 libstdc++ (in bits/stl_algo.h) 都以这种方式实现它。generate此外，如果没有此保证，您将失去很多潜在的应用程序。

当前的措辞是否暗示顺序性？如果不是，这是委员会成员的疏忽还是故意的？

（我很清楚，没有多少人可以在不只是推测或讨论的情况下对这个问题提供有见地的答案，但以我的拙见，根据 SO 指南，这并不会使这个问题“不具建设性”。）

感谢@juanchopanza 指出这个问题并让我参考关于for_each.

4

2 回答 2

8

在LWG475的讨论中，std::for_each是比较的std::transform。需要注意的是“transform不保证调用其函数对象的顺序”。所以，是的，委员会意识到标准中缺乏顺序保证。

对非顺序行为也没有相反的要求，因此 Microsoft 和 Apache 可以自由使用顺序评估。

于 2013-02-12T10:55:19.847 回答
5

在标准没有指定算法排序的任何地方，您都应该假设实现可以利用它来实现并行性。论文n3408讨论了并行化的选项，并指出了Thrust库，它既是标准算法的可用并行重新实现，也是算法中并行性未来标准化的概念验证。

查看 Thrust 的实现，只要迭代器类别是随机访问，它就会在并行循环中generate调用。gen正如您所观察到的，这与标准一致，因此您不应假设它generate始终是顺序的。（例如，线程安全std::rand可以有效地用于generate并且不需要顺序调用。）

唯一保证顺序调用的算法是numeric; 如果您的代码依赖于顺序调用，您应该使用iota. generate调整现有的生成器：

template<typename F> struct iota_adapter {
   F f;
   operator typename std::result_of<F()>::type() { return f(); }
   void operator++() {}
};
template<typename F> iota_adapter<F> iota_adapt(F &&f) { return {f}; }

用于：

#include <numeric>
#include <iostream>

int main() {
   int v[5], i = 0;
   std::iota(std::begin(v), std::end(v), iota_adapt([&i]() { return ++i; }));
   for (auto i: v) std::cout << i << '\n';
}
于 2013-02-12T11:34:31.083 回答