set_union mit Multiset-Containern?

Question

Was ist die Rückgabe des Algorithmus std: set_union, wenn einer oder beide Eingabe-Container Multi-Sets mit duplizierten Objekten sind? Gehen die Dups verloren?

ist zum Beispiel Nehmen wir an:

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()); 

Was wäre die Ausgabe sein?

Answer 1

Aus dem Standard, 25.3.5:

Die Semantik der Mengenoperationen verallgemeinert werden in üblicher Weise zu Multimengen von union() definieren die maximale Anzahl von Vorkommnissen von jedem Element zu enthalten, zu intersection() enthalten Minimum und so weiter.

So in Ihrem Beispiel, wird das Ergebnis (1,1,1,2,2,3,4,0,0,0) sein, da Sie den Vektor mit einer Länge von 10 initialisiert

Answer 2

Von der documentation of std::set_union (Hervorhebung hinzugefügt).

Im einfachsten Fall set_union führt die "Vereinigung" -Operation aus Mengenlehre: Der Ausgabebereich enthält eine Kopie von jedem Element, das in [first1 enthalten ist, last1), [first2, last2), oder beides. Der allgemeine Fall ist komplizierter, da die Eingabebereiche doppelte Elemente enthalten können. Die Verallgemeinerung ist, dass, wenn ein Wert m mal in [first1, last1) und n-mal in [first2, last2] erscheint (wobei m oder n Null sein kann), dann im Ausgabebereich max (m, n) erscheint. [1] Set_union ist stabil, was bedeutet, dass die relative Reihenfolge der Elemente in jedem Eingabebereich erhalten bleibt und dass, wenn ein Element in beiden Eingabebereichen vorhanden ist, es aus dem ersten Bereich und nicht aus dem zweiten Bereich kopiert wird.

Es wird max(m,n) mal erscheinen, wo m die Anzahl der Male ist es tritt in ms1 und n die Anzahl der Male ist es in ms2 auftritt.

Answer 3

Aus dem C++ - Standard §25.3.5/1:

In diesem Abschnitt werden alle grundlegenden Operationen für sortierte Strukturen definiert. Sie arbeiten auch mit Multisets (23.3.4), die mehrere Kopien äquivalenter Elemente enthalten. Die Semantik der Mengenoperationen wird auf eine Standardweise zu Multimengen verallgemeinert, indem union() so definiert wird, dass sie die maximale Anzahl von Vorkommen jedes Elements enthält, intersection() das Minimum enthält und so weiter.