¿Cuál es la diferencia entre std :: merge y std :: set_union?

Question

La pregunta es clara, mi google- y cplusplus.com/reference-fu me están fallando.

Answer 1

set_union solo contendrá elementos que están presentes en ambos juegos una vez. merge los contendrá dos veces.

Ambos funcionan en rangos ordenados y devuelven un resultado ordenado.

Answer 2

std::merge combina todos los elementos, sin eliminar los duplicados, mientras que std::set_union elimina los duplicados. Es decir, este último aplica la regla de operación union de set theory.

Answer 3

std::merge mantiene todos los elementos de ambos rangos, elementos equivalentes de la primera gama que preceden a los elementos equivalentes del segundo rango en la salida. Donde aparecen elementos equivalentes en ambos rangos std::set_union toma solo el elemento del primer rango, de lo contrario, cada elemento se fusiona en orden como en std::merge.

Referencias: ISO/IEC 14882: 2003 25.3.4 [lib.alg.merge] y 25.3.5.2 [lib.set.union].

Answer 4

Esta es la verificación que sugerí en el comentario que publiqué en la respuesta aceptada (es decir, si un elemento está presente en uno de los conjuntos de entrada N veces, aparecerá N veces en la salida de set_union - así que set_union no no eliminar duplicados elementos equivalentes en la forma que nos 'natural' o 'matemática' esperar - Si, sin embargo, ambos de entrada rangos contenían un elemento común de una sola vez, y luego set_union tendríamos aparecerá para eliminar el duplicado)

#include <vector> 
#include <algorithm> 
#include <iostream> 
#include <cassert> 

using namespace std; 

void printer(int i) { cout << i << ", "; } 

int main() { 
    int mynumbers1[] = { 0, 1, 2, 3, 3, 4 }; // this is sorted, 3 is dupe 
    int mynumbers2[] = { 5 };    // this is sorted 


    vector<int> union_result(10); 
    set_union(mynumbers1, mynumbers1 + sizeof(mynumbers1)/sizeof(int), 
       mynumbers2, mynumbers2 + sizeof(mynumbers2)/sizeof(int), 
       union_result.begin()); 
    for_each(union_result.begin(), union_result.end(), printer); 

    return 0; 
} 

Esto imprimirá: 0, 1, 2, 3, 3, 4, 5, 0, 0, 0,

Answer 5

Para agregar a las respuestas anteriores, tenga en cuenta que la complejidad de std::set_union es el doble que la de std::merge. En la práctica, esto significa que el comparador en std::set_union se puede aplicar a un elemento después de se ha desreferenciado, mientras que con std::merge este nunca es el caso.

¿Por qué es importante? Considere algo como:

std::vector<Foo> lhs, rhs; 

Y se quiere producir una unión de lhs y rhs:

std::set_union(std::cbegin(lhs), std::cend(lhs), 
       std::cbegin(rhs), std::cend(rhs), 
       std::back_inserter(union)); 

Pero ahora supongamos Foo no es copiable, o es muy caro para copiar y que no es necesario los originales. Usted puede pensar de usar:

std::set_union(std::make_move_iterator(std::begin(lhs)), 
       std::make_move_iterator(std::end(lhs)), 
       std::make_move_iterator(std::begin(rhs)), 
       std::make_move_iterator(std::end(rhs)), 
       std::back_inserter(union)); 

pero esto es un comportamiento indefinido ya que hay una posibilidad de un movido Foo se compara! Por lo tanto, la solución correcta es:

std::merge(std::make_move_iterator(std::begin(lhs)), 
      std::make_move_iterator(std::end(lhs)), 
      std::make_move_iterator(std::begin(rhs)), 
      std::make_move_iterator(std::end(rhs)), 
      std::back_inserter(union)); 
union.erase(std::unique(std::begin(union), std::end(union), std::end(union)); 

que tiene la misma complejidad que std::set_union.