C++标准措辞:"通过范围内的所有迭代器"是否意味着顺序性？

Question

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

标准(n3337,§25.3.7/ 1)说明了这一点:

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

似乎没有保证排序,特别是因为其他段落具有更强的措辞,例如std::for_each(效果:适用f于取消引用范围中的每个迭代器的结果[first,last),从第一个开始并继续到last - 1.如果我们从字面上理解它,它只是保证从开始到first结束last- 不保证两者之间的排序.

但是:无论微软和Apache的C++标准库既给那些需要的评价是连续的文档页面的例子.libc ++(in algorithm)和libstdc ++(in bits/stl_algo.h)都以这种方式实现它.此外,如果generate没有这种保证,您将失去许多潜在的申请.

目前的措辞是否意味着顺序性？如果没有,这是委员会成员的监督还是故意的？

(我很清楚,没有很多人能够提供有关这个问题的深刻答案,而不仅仅是推测或讨论,但我认为,根据SO指南,这并不能使这个问题"没有建设性".)

---

感谢@juanchopanza指出这个问题,并引用了我关于的段落for_each.

Answer 1

在LWG475的讨论中,std::for_each进行了比较std::transform.注意到" transform不保证其函数对象被调用的顺序".所以,是的,委员会意识到标准中缺乏顺序保证.

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

Answer 2

在标准没有指定算法排序的任何地方,您应该假设一个实现可以利用它来实现并行性.论文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';
}