将 std::transform 与 std::back_inserter 一起使用是否有效？

Question

Cppreference 有以下示例代码std::transform：

std::vector<std::size_t> ordinals;
std::transform(s.begin(), s.end(), std::back_inserter(ordinals),
               [](unsigned char c) -> std::size_t { return c; });

但它也说：

std::transform不保证unary_op或的有序应用binary_op。要将函数按顺序应用于序列或应用修改序列元素的函数，请使用std::for_each。

这大概是为了允许并行实现。但是，的第三个参数std::transform是 a LegacyOutputIterator，它具有以下后置条件++r：

在此操作之后r不需要是可递增的，并且r不再需要可取消引用或可递增的先前值的任何副本。

所以在我看来，输出的分配必须按顺序进行。它们是否只是意味着应用程序unary_op可能会乱序，并存储到临时位置，但按顺序复制到输出？这听起来不像你想做的事情。

大多数 C++ 库还没有真正实现并行执行器，但微软已经实现了。我很确定这是相关的代码，我认为它调用这个populate()函数来将迭代器记录到输出的块中，这肯定不是一件有效的事情，因为 LegacyOutputIterator可以通过增加它的副本来失效。

我错过了什么？

Answer 1

1）标准中的输出迭代器要求完全被打破。参见LWG2035。

2）如果您使用纯输出迭代器和纯输入源范围，那么该算法在实践中几乎无能为力；它别无选择，只能按顺序写。（但是，假设的实现可以选择特殊情况下它自己的类型，例如std::back_insert_iterator<std::vector<size_t>>; 我不明白为什么任何实现都想在这里这样做，但允许这样做。）

3) 标准中没有任何内容保证transform按顺序应用转换。我们正在查看实现细节。

这std::transform仅需要输出迭代器并不意味着它不能在这种情况下，检测更高的迭代器的优势和重新排序操作。事实上，调度算法对迭代器强度所有的时间，他们有特殊的迭代器类型进行特殊处理（如指针或矢量迭代器）所有的时间。

当标准想要保证特定的顺序时，它知道如何表达（参见std::copy“开始first和继续到last”）。

Answer 2

来自n4385：

§25.6.4变换：

template<class InputIterator, class OutputIterator, class UnaryOperation>
constexpr OutputIterator
transform(InputIterator first1, InputIterator last1, OutputIterator result, UnaryOperation op);

template<class ExecutionPolicy, class ForwardIterator1, class ForwardIterator2, class UnaryOperation>
ForwardIterator2
transform(ExecutionPolicy&& exec, ForwardIterator1 first1, ForwardIterator1 last1, ForwardIterator2 result, UnaryOperation op);

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

template<class ExecutionPolicy, class ForwardIterator1, class ForwardIterator2, class ForwardIterator, class BinaryOperation>
ForwardIterator
transform(ExecutionPolicy&& exec, ForwardIterator1 first1, ForwardIterator1 last1, ForwardIterator2 first2, ForwardIterator result, BinaryOperation binary_op);

§23.5.2.1.2 back_inserter

template<class Container>
constexpr back_insert_iterator<Container> back_inserter(Container& x);

返回：back_insert_iterator(x)。

§23.5.2.1类模板 back_insert_iterator

using iterator_category = output_iterator_tag;

因此std::back_inserter不能与std::transform. 支持输出迭代器的版本使用输入迭代器从其源中读取。由于输入迭代器只能在前和后自增（第 23.3.5.2 节输入迭代器）并且只有顺序（即非并行）执行，因此必须在它们和输出迭代器之间保持顺序。