6

一方または両方の入力コンテナが重複したオブジェクトを持つマルチセットである場合、アルゴリズムstd：set_unionの戻り値は何ですか？重複は失われますか？

たとえば、次のように仮定します。

multiset<int> ms1;
ms1.insert(1);
ms1.insert(1);
ms1.insert(1);
ms1.insert(2);
ms1.insert(3);

multiset<int> ms2;
ms2.insert(1);
ms2.insert(1);
ms2.insert(2);
ms2.insert(2);
ms2.insert(4);

vector<int> v(10);
set_union( ms1.begin(), ms1.end(), ms2.begin(), ms2.end(), v.begin() );

出力はどうなりますか？

4

3 に答える 3

4

標準、25.3.5 から:

union()集合操作のセマンティクスは、すべての要素の最大出現回数を含むように定義することによって、標準的な方法で多重集合に一般化さintersection()れます。

したがって、この例では、ベクトルを長さ 10 で初期化したため、結果は (1,1,1,2,2,3,4,0,0,0) になります。

于 2010-07-07T15:06:59.993 に答える
2

std::set_unionのドキュメントから(強調を追加)。

最も単純なケースでは、set_union は集合論から「結合」操作を実行します。出力範囲には、[first1, last1)、[first2, last2)、またはその両方に含まれるすべての要素のコピーが含まれます。入力範囲に重複する要素が含まれる可能性があるため、一般的なケースはより複雑です。一般化すると、ある値が [first1, last1) に m 回出現し、[first2, last2) に n 回出現する場合 (m または n はゼロの場合もあります)、出力範囲に max(m,n) 回出現します。[1] Set_union は安定しています。つまり、各入力範囲内の要素の相対的な順序が保持され、要素が両方の入力範囲に存在する場合、2 番目ではなく最初の範囲からコピーされます。

は で発生する回数で、max(m,n)はで発生する回数です。mms1nms2

于 2010-07-07T15:04:10.257 に答える
2

C++ 標準から、§25.3.5/1:

このセクションでは、ソートされた構造に対するすべての基本的な集合操作を定義します。それらは、同等の要素の複数のコピーを含むマルチセット (23.3.4) でも機能します。set 操作のセマンティクスは、union() を定義してすべての要素の最大出現数を含めたり、intersection() を最小数を含めたりすることによって、標準的な方法でマルチセットに一般化されます。

于 2010-07-07T15:07:25.037 に答える