9

私は非常に簡潔で直感的な C++ 構文を使用して、2 つのソート済み の共通部分を見つけ、vectorその結果を 3 番目の に入れていvectorます。

vector<bar> a,b,c;
//...
std::set_intersection(a.begin(),a.end(),b.begin(),b.end(),
                      std::back_inserter(c));

これは、がソートされていると仮定して、 cintersection( a, ) に設定する必要があります。bab

しかし、単に使用するとどうなりますc.begin()か (これのどこかで例を見たと思ったので、そうしました):

 std::set_intersection(a.begin(),a.end(),b.begin(),b.end(),
                       c.begin());

set_intersectionそのパラメータで を期待OutputIteratorします。私が信じている標準では、 a を返すことだけが必要c.begin()です。forward iteratorOutputIterator

とにかく、c.begin()clangの下でコンパイルされたコード。

標準で保証されていることは何ですか? これがコンパイルされた場合、何が起こる可能性がありますか?つまり、によって返されたイテレータc.begin()が最終的にベクターの終わりを超えてインクリメントされ、ポイントされた要素にアクセスしようとすると、何が起こる必要がありますか? この場合、適合する実装はサイレントにベクトルを拡張できるのでbegin()、実際には追加OutputIteratorのようなものback_inserterですか?

私は主に、標準がイテレータでどのように機能するかを理解するためにこれを求めています。つまり、実際に何が起こっているのかを理解して、STL を使用してコピーアンドペーストを超えて移動できるようにします。

4

3 に答える 3

10

back_inserter呼び出して範囲内に要素を挿入しpush_backます（そのため、操作back_inserterを提供しない範囲では使用できませんpush_back）。

したがって、コンテナが自動的に拡張されるため、範囲の終わりを超えても気にする必要はありません。push_backただし、insert using の場合はそうではありませんbegin()。

を使用している場合は、宛先範囲がすべての要素を保持するのに十分な大きbegin()さであることを確認する必要があります。そうしないと、コードが未定義の動作の領域に即座に転送されます。

于 2014-11-30T17:03:19.060 に答える
6

関数から有効なイテレータが返されるため、正常にコンパイルされますbeginが、ベクトルが空の場合はendイテレータが返され、そこから続行されます。

追加しようとする要素と同じ数の要素が宛先ベクトルに既に含まれている場合にのみ機能し、実際にはそれらの要素を上書きし、新しい要素を追加しません。

そして、要素を追加することはback_inserterイテレータが行うことであり、基本的push_backにベクトルに対して行うイテレータを返します。

于 2014-11-30T17:03:40.080 に答える
5

出力反復子の重要な要件は、出力の範囲
[out, out+サイズ)に対して有効で書き込み可能であることです。

渡すc.begin()と値が上書きされますが、これはコンテナーcが上書きするのに十分な要素を保持している場合にのみ機能します。c.begin()がサイズ 0 の配列へのポインターを返すと想像してください*out++ = 7;。

back_inserter は、割り当てられたすべての値をvector(経由で) に追加push_backし、STL アルゴリズムの範囲を拡張する簡潔な方法を提供します。イテレータに使用される演算子を適切にオーバーロードします。

したがって

 std::set_intersection(a.begin(),a.end(),b.begin(),b.end(),
                       c.begin());

は、出力反復子に何かを書き込むと、未定義の動作を呼び出しset_intersectionます。つまり、 と の集合の交点がa空bでない場合です。

この場合、適合する実装は、begin() が実際に追加OutputIteratorのようなものになるように、サイレントにベクトルを拡張できますback_inserterか?

もちろん。未定義の動作です。(これは、実装への影響に関係なく、これを使用することを検討する必要さえないことを伝えるユーモラスなアプローチです。)

于 2014-11-30T17:07:07.820 に答える