使用std::back_inserter和std::transform是否有效？

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的第三个参数是一个LegacyOutputIterator，它对于++r有以下后置条件：

此操作之后，不需要再递增r，并且任何先前值的副本都不需要再进行引用或递增。

所以我认为输出的赋值必须按顺序进行。他们是否仅仅意味着unary_op的应用可能是无序的，并且存储到临时位置，但按顺序复制到输出中？那听起来不像是你想做的事情。

大多数C++库实际上还没有实现并行执行器，但是微软已经实现了。我相当确定这就是相关代码，而且我认为它调用这个populate()函数来记录输出块的迭代器，这肯定不是有效的操作，因为通过增加副本可以使LegacyOutputIterator无效。

我错过了什么？

- Timmmm

---

在godbolt上进行的一个简单测试显示这是一个问题。使用C++20和transform版本来决定是否使用并行处理。对于大向量，transform会失败。 - Croolman

你的代码有误，因为你在向s进行反向插入，这会使迭代器失效。 - Daniel Langr

@DanielsaysreinstateMonica 哦，你说得对。我在调整它，但是没有将其设置为有效状态。我收回我的评论。 - Croolman

有时候人们会突然回想起旧问题，这是怎么发生的呢？无论如何，@DanielLangr指出了我的第一条评论中的代码错误。当你在godbolt中将back_inserter更改为插入到ordinals时，它可以编译并且似乎可以工作。 - Croolman

@alfC godbolt 代码存在问题，即在 std::back_inserter 中传递了 s 而不是 ordinals。 - Croolman

Answer 1

1) 标准中输出迭代器的要求完全有问题。请参见LWG2035。

2) 如果你使用纯输出迭代器和纯输入源范围，那么实际上算法可以做的事情很少; 它别无选择，只能按顺序写入。(但是，一个假设的实现可以选择特殊处理自己的类型，比如std::back_insert_iterator<std::vector<size_t>>;我不知道为什么任何实现会在这里想要这样做，但允许这样做。)

3) 标准中没有保证transform按顺序应用变换。我们正在看实现细节。

std::transform仅需要输出迭代器并不意味着它不能检测到更高的迭代器强度，并在这种情况下重新排序操作。实际上，算法可以一直根据迭代器强度进行分派，他们对特殊的迭代器类型（如指针或矢量迭代器）有特殊处理。

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

- T.C.

---

我发现相当令人惊讶的是，std::copy不能作为std::transform的特殊情况实现。 - alfC

我不理解你关于专门化 std::back_insert_iterator 的观点。你是在说这种情况可以通过使用 operator+= 实现吗？这将使它有效地具有随机访问的能力？因此允许 std::transform 无序执行操作。这可能相当疯狂，但我无法确定原因所在。我认为这是因为如果未交错应用 ++ 和 *，输出迭代器就会出现未定义行为。这本身就应该阻止尝试实现 +=（并具有多次应用 ++ 的语义）。 - alfC

我认为“交错”要求在以下短语中得到了体现：“在此操作（*）之后，r不需要再被解引用，并且先前的r值的任何副本也不再需要被解引用或递增。”和“在此操作（++）之后，r不需要再递增，并且先前的r值的任何副本也不再需要被解引用或递增。”。链接在这里：https://en.cppreference.com/w/cpp/named_req/OutputIterator。我认为这使得不同的乱序实现和`back_insert_iterator`的专门化变得不可能。 - alfC

Answer 2

来自n4385:

§25.6.4 Transform：

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 输入迭代器），并且只有顺序（即非并行）执行，因此必须在它们之间保留顺序，并保留输出迭代器。

- Paul Evans

---

请注意，C++标准中的这些定义并不排除实现提供专门针对其他类型迭代器选择的算法特殊版本。例如，std::advance只有一个接受输入迭代器的定义，但是libstdc++提供了额外的版本用于双向迭代器和随机访问迭代器。然后根据传递的迭代器类型执行特定版本。 - Daniel Langr

@Timmmm 我认为如果 first1/last1 参数是 输入迭代器 类型，或者 result 是 输出迭代器 类型，则元素必须按顺序处理。因为实现除了使用 ++ 操作移动到下一个迭代之外没有其他选择。由于 std::back_inserter_iterator 是 _输出迭代器_，所以这个条件成立。 - Daniel Langr

它可以使用 ++ 来移动到下一个迭代，而不实际执行转换 - 它只需要保存迭代器的副本。对于 LegacyOutputIterator 的问题在于您无法保存迭代器的副本。对于 LegacyForwardIterator，您可以这样做。 - Timmmm

这个回答可能会受益于添加一些词语来解释它的实际含义。 - Barry

@Barry 添加了一些词，非常感谢任何反馈。 - Paul Evans

Answer 3

所以我错过的是并行版本需要使用LegacyForwardIterator，而不是LegacyOutputIterator。 LegacyForwardIterator可以被递增而不会使其副本无效，因此很容易使用它来实现无序并行std::transform。

我认为std::transform的非并行版本必须按顺序执行。cppreference可能是错误的，或者标准可能只是隐含地留下了这个要求，因为没有其他方法来实现它。（懒得翻阅标准！）

- Timmmm

---

如果所有的迭代器都足够强，则变换的非并行版本可能会乱序执行。在问题的示例中，它们不是，因此“transform”的那个特定实现必须是有序的。 - Caleth

不行，因为LegacyOutputIterator强制你必须按顺序使用它。 - Timmmm

它可以针对 std::back_insert_iterator<std::vector<T>> 和 std::vector<T>::iterator 进行不同的特化。第一个必须有序，而第二个没有此限制。 - Caleth

啊，等等我明白你的意思了 - 如果你碰巧将一个 LegacyForwardIterator 传递到非并行 transform 中，它可能会有一个专门针对此类情况的特化实现，从而使其无序。说得好。 - Timmmm

Answer 4

我相信转换保证按顺序处理。std::back_inserter_iterator是一个输出迭代器（它的iterator_category成员类型是std::output_iterator_tag的别名）参考[back.insert.iterator]。

因此，std::transform没有其他选择，只能调用result参数的成员operator ++以继续下一次迭代。

当然，这仅适用于没有执行策略的重载，其中无法使用std::back_inserter_iterator（它不是转发迭代器）。

---

顺便说一句，我不会使用cppreference上的引用来争论。那里的陈述经常不够精确或简化了。在这种情况下，最好查看C++标准。关于std::transform，标准中没有关于操作顺序的任何引用。

- Daniel Langr

---

“C++标准。在std::transform方面，没有关于操作顺序的引用。”由于未提及顺序，那么它不是未指定的吗？ - HolyBlackCat

@HolyBlackCat 显式未指定，但由输出迭代器强制执行。请注意，对于输出迭代器，一旦您将其递增，就不能引用任何先前的迭代器值。 - Daniel Langr

@DanielLangr，std::execution::par 怎么样？ - Sergei Krivonos

@Sergei 不明白你的问题。如果操作可以并行进行，你如何定义它们的顺序？如果它们应该有序，那么就不能进行并行处理。 - Daniel Langr