0

次のページでset_unionに指定されたコードを解釈する方法について混乱しています:http ://www.cplusplus.com/reference/algorithm/set_union/

関数が戻ったときに、アルゴリズムはどのようにして結果が2つのセットの和集合を保持することを保証しますか?たとえば、次のリストのset_unionを検索したい場合:

L1        L2

hi        goodbye
bye       hello
see       hi
two       bye
three     hooray

それぞれの前後にイテレータがあると仮定して、誰かがこのようなリストに対してアルゴリズムがどのように機能するかを教えてもらえますか?

4

2 に答える 2

3

が機能するための重要な要件がset_unionありません。渡す範囲は両方ともsortedである必要があります。あなたが投稿したリンクから:

set_union2 つの並べ替えられた範囲[first1,last1)との和集合を使用して、result が指す位置から始まる並べ替えられた範囲を構築し[first2,last2)ます。

このページに示されているコードは、事前に並べ替えられた 2 つのシーケンスのマージを実行するだけです。

于 2013-02-26T04:05:11.800 に答える
1

重要な情報は、アルゴリズムが要素が両方の範囲で順序付けられていることを前提条件として想定していることです。したがって、あなたの場合は次のようになります。

L1:  bye, hi, see, three, two
L2:  bye, goodbye, hello, hi, hooray

それを念頭に置いて、アルゴリズムが何をするかを理解することは難しくありません。

両方の範囲に要素が含まれている間、反復子が指す要素のうち最小のものを和集合に追加し、その反復子を進めます。両方の反復子が同じ要素を参照する場合は、それを追加して両方の反復子を進めます (2 回挿入したくない)。

範囲の 1 つが空になったら、残りのすべての要素を他の範囲からソリューションにコピーします。

この場合、bye両方のイテレータを挿入goodbyeして進め、2 番目のイテレータを挿入helloして進め、2 番目のイテレータを挿入hiして進め、両方のイテレータを挿入hoorayして進め、2 番目のイテレータを挿入して進めます。2 番目の範囲は空なので、最初の範囲の残りの要素で完了します。

于 2013-02-26T04:03:29.733 に答える