c++ - std::transform が順序を保証しないのはなぜですか (しかし for_each は順序を保証します)? これは、パフォーマンスのためのトリックの実装を許可しませんか?

Question

標準では、関数コールバックを適用する順序が保証されていないことに気付きましたstd::transform。また、コールバック関数またはファンクターに副作用を与えることはできません。しかし同時に、std::for_each実際には注文を保証します。

1 つの推測では、変換は順序を保証しない高性能アルゴリズムを使用することができますが、O(N) は既に最高のアルゴリズムです。

では、コールバック関数の適用順序の観点から、標準がtransform動作を行わないのはなぜですか? for_eachユーザーは、この保証から利益を得ます。

Answer 1

以前のいくつかの回答にもかかわらず、 std::transform を並行して実装することは可能だと思います。たとえば、次のようにします。

1) すべての入力を順番にフェッチします。

2) OutputIterator を繰り返し、ダミー オブジェクトを初期化し、各出力への参照を保持します。

3) 対応する出力反復子を使用して入力を異なるスレッドに分散し、それぞれが独立して変換を行います。

このように、反復子は許可されている場合にのみインクリメントされます。

clcto で指摘されているように、別の実装では、最初にステップ 1) を実行してから、すべての出力要素のベクトルを作成し、指定された関数引数を使用してこれらすべてを並列に計算し、出力に順番に書き込むことができます。

Answer 2

この制限のない定義により、並列計算が可能になります。実装では、複数のスレッドを使用して変換機能を適用することを選択できます。関連する質問も参照してください: STL アルゴリズムと並行プログラミング

これは、アルゴリズムのセマンティックの違い (つまり、単なる別のツールではなく、プログラマーの意図を表すもの) と考えてください。あなたfor_eachはシーケンシャルスキャンが必要だと述べています。transformコンテナ内のすべてのアイテムに関数を適用するだけでよいと述べていますが、それがどのように行われるかは気にしません。