5

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

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

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

4

3 回答 3

6

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

您将从模板声明中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);

i1 效果：通过范围内的每个迭代器分配[result,result + (last1 - first1))一个新的对应值等于op(*(first1 + (i - result))or 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 备注：一元变换的结果可能等于first，二元变换的结果可能等于first1或first2。

于 2015-10-23T15:44:53.163 回答
3

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

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

于 2013-06-28T07:06:11.187 回答
3

尽管有一些较早的答案，但我认为可以以并行方式实现 std::transform 。例如像这样：

1）按顺序获取所有输入。

2）迭代OutputIterator，初始化虚拟对象并保持对每个输出的引用。

3) 将输入与相应的输出迭代器分配给不同的线程，每个线程独立地进行转换。

像这样，迭代器只在允许的情况下递增。

正如 clcto 所指出的，另一个实现可以先执行步骤 1)，然后为所有输出元素创建一个向量，然后使用给定的函数参数并行计算所有这些，然后将它们按顺序写入输出。

于 2016-09-20T15:42:31.817 回答