set_union avec des conteneurs multiset?

Question

Quel est le retour de l'algorithme std: set_union lorsqu'un ou les deux conteneurs d'entrée sont des multisets avec des objets dupliqués? Les dups se perdent-ils?

Supposons par exemple:

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

Qu'est-ce que la sortie soit?

Answer 1

de la norme, 25.3.5:

La sémantique des opérations de réglage sont généralisés à multiensembles de façon standard en définissant union() pour contenir le nombre maximum d'occurrences de chaque élément, intersection() pour contenir le minimum, et ainsi de suite.

Donc, dans votre exemple, le résultat sera (1,1,1,2,2,3,4,0,0,0), puisque vous initialisés le vecteur de longueur 10.

Answer 2

Du documentation of std::set_union (emphase ajoutée).

Dans le cas le plus simple, set_union effectue l'opération « union » de la théorie des ensembles: la plage de sortie contient une copie de chaque élément qui est contenu dans [Premier1, last1), [first2, dernier2), ou les deux. Le cas général est plus compliqué, car les plages d'entrée peuvent contenir des éléments en double. La généralisation est que si une valeur apparaît m fois dans [first1, last1) et n fois dans [first2, last2) (où m ou n peut être nul), alors elle apparaît max (m, n) fois dans la plage de sortie. [1] Set_union est stable, ce qui signifie que l'ordre relatif des éléments dans chaque plage d'entrée est préservé et que si un élément est présent dans les deux plages d'entrée, il est copié de la première plage plutôt que de la seconde.

Il apparaîtra max(m,n) fois où m est le nombre de fois qu'il se produit dans ms1 et n est le nombre de fois qu'il se produit dans ms2.

Answer 3

À partir de la norme C++, §25.3.5/1:

Cette section définit toutes les opérations d'ensemble de base sur les structures triées. Ils fonctionnent également avec des multisets (23.3.4) contenant plusieurs copies d'éléments équivalents. La sémantique des opérations d'ensemble est généralisée aux multisets d'une manière standard en définissant union() pour contenir le nombre maximum d'occurrences de chaque élément, intersection() pour contenir le minimum, et ainsi de suite.