为什么 std::transform 不保证顺序（但 for_each 保证顺序）？这不是允许实现性能的技巧吗？

Question

我只是意识到标准并不能保证在std::transform. 并且它不允许回调函数或函子有副作用。但同时std::for_each实际上保证了顺序。

一种猜测是转换可以使用不保证顺序的高性能算法，但是 O(N) 已经是最好的算法。

那么为什么标准没有使从应用回调函数顺序的角度来看transform具有行为for_each？用户将从该保证中受益。

Answer 1

直接从标准中引用（最后复制）：

您将从模板声明中std::transform<>看到输入迭代器参数必须符合InputIterator.

AnInputIterator是 C++ 中最严格的迭代器概念之一。它不支持任何类型的随机访问。它只能前进。

因此，任何需要迭代器执行除取消引用或提前之外的任何操作的 std::transform 实现都是格式错误的。请记住，通过指定InputIterator，标准明确允许使用 a std::istream_iterator（例如），并且std::transform需要实现以遵守其中的限制。它必须仅根据InputIterator概念上可用的方法来编写。

因此，隐含地，此函数的实现必须按顺序访问元素（并因此按顺序转换值），因为不这样做会破坏接口中隐含的约定。

因此，标准确实（隐式和安静地）保证std::transform按顺序初始化其元素。如果没有，就不可能编写一个格式良好的实现std::transform。

25.3.4 变换 [alg.transform]

template<class InputIterator, class OutputIterator, class UnaryOperation>
OutputIterator
transform(InputIterator first, InputIterator last, OutputIterator result, UnaryOperation op);

template<class InputIterator1, class InputIterator2, class OutputIterator, class BinaryOperation>
OutputIterator
transform(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, OutputIterator result, BinaryOperation binary_op);

1 效果：通过i范围内[result,result + (last1 - first1))的每个迭代器分配一个新的对应值，等于op(*(first1 + (i - result))或binary_op(*(first1 + (i - result)), *(first2 + (i - result)))。

2 要求：op 和 binary_op 不得使迭代器或子范围无效，或修改范围 [first1,last1]、[first2,first2 + (last1 - first1)] 和 [result,result + (last1 - first1)] 中的元素。

3 返回：结果 + (last1 - first1)。

4 复杂性：正好是 op 或 binary_op 的 last1 - first1 应用。

5 备注：一元变换时result可能等于first，二元变换时result可能等于first1或first2。

Answer 2

这种非限制性定义允许并行计算。实现可以选择使用多个线程来应用变换函数。另请参阅相关问题：STL算法和并发编程

将其视为算法中的语义差异（即，代表程序员的意图而不仅仅是另一种工具）。您声明for_each您需要顺序扫描。你声明transform你只需要对容器中的每个项目应用一个函数，但你不关心它是如何完成的。