为什么 std::transform 不保证顺序(但for_each保证顺序)?这不允许为性能实施技巧吗?



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

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

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

直接从标准报价(最后复制):

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

InputIterator是c++中限制性最强的迭代器概念之一。它不支持任何类型的随机访问。它只能前进。

因此,任何要求迭代器执行除取消引用或前进之外的任何操作的std::transform实现都是不正确的。请记住,通过指定InputIterator,标准明确允许使用std::istream_iterator(例如),并且std::transform的实现需要遵守其中的限制。它必须仅根据InputIterator概念上可用的方法编写。

因此,通过暗示,此函数的实现必须按顺序访问元素(因此按顺序转换值),因为不这样做会破坏接口中隐含的契约。

因此,标准确实(隐式且安静地)保证std::transform按顺序初始化其元素。编写一个格式良好的std::transform实现是不可能的。

25.3.4变换[代数变换]

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效果:通过范围[result,result + (last1 - first1))中的每个迭代器i分配一个新的对应值,该值等于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-irst1)]中的元素。

3返回:result+(last1-first1)。

4复杂性:恰好是op或binary_op的last1-first1应用程序。

5备注:在一元变换的情况下,结果可以等于first,在二元变换的情形下,结果可能等于first1或first2。

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

可以把它看作是算法中的语义差异(也就是说,它代表了程序员的意图,而不仅仅是另一个工具)。使用for_each,您表示需要进行顺序扫描。使用transform,您可以声明只需要为容器中的每个项应用一个函数,但不关心如何实现。

尽管前面有一些答案,但我认为以并行方式实现std::transform是可能的。例如:

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

2) 在OutputIterator上迭代,初始化虚拟对象并保留对每个输出的引用。

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

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

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

最新更新