set_union con contenedores multiset?

Question

¿Cuál es el retorno del algoritmo std: set_union cuando uno o ambos contenedores de entrada son multisectos con objetos duplicados? ¿Los dúplex se pierden?

Supongamos por ejemplo:

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

¿Cuál sería el resultado?

Answer 1

de la norma, 25.3.5:

La semántica de las operaciones de conjuntos se generalizan a conjuntos múltiples de una manera estándar mediante la definición de union() para contener el número máximo de ocurrencias de cada elemento, para contener el intersection() mínimo, y así sucesivamente.

Así que en tu ejemplo, el resultado será (1,1,1,2,2,3,4,0,0,0), ya que se inicializa el vector con una longitud de 10.

Answer 2

Desde el documentation of std::set_union (énfasis añadido).

En el caso más simple, set_union realiza la operación de "unión" de la teoría de conjuntos: el rango de salida contiene una copia de cada elemento que se encuentra en [first1, last1), [primero2, ultimo2), o ambos. El caso general es más complicado, porque los rangos de entrada pueden contener elementos duplicados. La generalización es que si aparece un valor m veces en [first1, last1) yn veces en [first2, last2) (donde m o n puede ser cero), aparece max (m, n) veces en el rango de salida. [1] Set_union es estable, lo que significa que se conserva el orden relativo de los elementos dentro de cada rango de entrada, y que si un elemento está presente en ambos rangos de entrada, se copia desde el primer rango en lugar del segundo.

Aparecerá max(m,n) veces donde m es el número de veces que se produce en ms1 y n es el número de veces que se produce en ms2.

Answer 3

A partir del estándar C++, §25.3.5/1:

Esta sección define todas las operaciones de conjunto básico en estructuras ordenadas. También funcionan con multisectos (23.3.4) que contienen varias copias de elementos equivalentes. La semántica de las operaciones establecidas se generaliza a multisecuencias de forma estándar al definir union() para contener el número máximo de apariciones de cada elemento, intersection() para contener el mínimo, y así sucesivamente.