26

このSOの質問std::generateは、標準によって行われた保証についての議論を引き起こしました。特に、内部状態の関数オブジェクトを使用して、呼び出し、結果の格納、再generate(it1, it2, gen)呼び出し、格納などに依存できますか、それとも、たとえば、後ろから開始できますか?gen()*itgen()*(it + 1)

標準(n3337、§25.3.7/ 1)はこれを述べています:

効果:最初のアルゴリズムは関数オブジェクトを呼び出しgen、範囲内のすべてのイテレーターを介してgenの戻り値を割り当てます[first,last)[first,first + n)2番目のアルゴリズムは、関数オブジェクトgenを呼び出し、が正の場合は範囲​​内のすべてのイテレータを介してgenの戻り値を割り当てn、それ以外の場合は何もしません。

特に、他の段落の言い回しが強いため、順序が保証されていないようですstd::for_each効果:f範囲内のすべてのイテレータを[first,last)最初から順に逆参照した結果に適用されますlast - 1これを文字通りに解釈する場合は、ただし、開始firstと終了を保証しlastます-その間の順序については保証しません)。

ただし、MicrosoftApacheのC ++標準ライブラリはどちらも、評価を順次行う必要があるドキュメントページに例を示しています。そして、libc ++(in algorithm)とlibstdc ++(in)の両方bits/stl_algo.hがそれをそのように実装します。generateさらに、この保証がないと、多くの潜在的なアプリケーションが失われます。

現在の言い回しは連続性を意味しますか?そうでない場合、これは委員会のメンバーによる見落としでしたか、それとも意図的なものでしたか?

(私は、単に推測したり議論したりせずにこの質問に洞察に満ちた答えを提供できる人は多くないことをよく知っていますが、私の謙虚な意見では、これはこの質問をSOガイドラインに従って「建設的ではない」ものにしません。)


この問題を指摘し、についての段落を参照してくれた@juanchopanzaに感謝しfor_eachます。

4

2 に答える 2

8

LWG475の説明では、std::for_eachと比較されstd::transformます。transform「関数オブジェクトが呼び出される順序を保証するものではない」ことに注意してください。したがって、はい、委員会は、規格に順次保証がないことを認識しています。

非順次動作にも反対の要件はないため、MicrosoftとApacheは自由に順次評価を使用できます。

于 2013-02-12T10:55:19.847 に答える
5

標準でアルゴリズムの順序が指定されていない場合は、実装が並列処理のためにそれを利用できると想定する必要があります。論文n3408は、並列化のオプションについて説明し、Thrustライブラリを示しています。これは、標準アルゴリズムの使用可能な並列対応の再実装であり、アルゴリズムの並列処理の将来の標準化の概念実証でもあります。

Thrustのの実装を見ると、イテレータカテゴリがランダムアクセスである場合は常に並列ループgenerateで呼び出します。genあなたが観察したように、これは標準と一致しているので、それgenerateが常にシーケンシャルであると仮定するべきではありません。(たとえば、スレッドセーフstd::randはで効率的に使用できgenerate、順次呼び出しを必要としません。)

順次呼び出しを保証する唯一のアルゴリズムは、numeric;のアルゴリズムです。コードが順次呼び出しに依存している場合はiota、の代わりにを使用する必要がありgenerateます。既存のジェネレーターの適応:

template<typename F> struct iota_adapter {
   F f;
   operator typename std::result_of<F()>::type() { return f(); }
   void operator++() {}
};
template<typename F> iota_adapter<F> iota_adapt(F &&f) { return {f}; }

使用:

#include <numeric>
#include <iostream>

int main() {
   int v[5], i = 0;
   std::iota(std::begin(v), std::end(v), iota_adapt([&i]() { return ++i; }));
   for (auto i: v) std::cout << i << '\n';
}
于 2013-02-12T11:34:31.083 に答える