Saltar al contenido

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

Solución:

std::set_union contendrá aquellos elementos que están presentes en ambos conjuntos solo una vez. std::merge los contendrá dos veces.

Por ejemplo, con A = 1, 2, 5; B = 2, 3, 4:

  • la unión dará C = 1, 2, 3, 4, 5
  • la fusión dará D = 1, 2, 2, 3, 4, 5

Ambos funcionan en rangos ordenados y devuelven un resultado ordenado.

Ejemplo corto:

#include <algorithm>
#include <iostream>
#include <set>
#include <vector>

int main()

  std::set<int> A = 1, 2, 5;
  std::set<int> B = 2, 3, 4;

  std::vector<int> out;
  std::set_union(std::begin(A), std::end(A), std::begin(B), std::end(B),
                 std::back_inserter(out));
  for (auto i : out)
  
    std::cout << i << " ";
  
  std::cout << 'n';

  out.clear();
  std::merge(std::begin(A), std::end(A), std::begin(B), std::end(B),
             std::back_inserter(out));
  for (auto i : out)
  
    std::cout << i << " ";
  
  std::cout << 'n';

Producción:

1 2 3 4 5 
1 2 2 3 4 5

std::merge mantiene todos los elementos de ambos rangos, elementos equivalentes del primer rango 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 con std::merge.

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

Esta es la verificación que sugerí en el comentario que publiqué en la respuesta aceptada (es decir, que si un elemento está presente en uno de los conjuntos de entrada N veces, aparecerá N veces en la salida de set_union, por lo que set_union sí no eliminar elementos equivalentes duplicados de la forma en que esperaríamos ‘naturalmente’ o ‘matemáticamente’; sin embargo, si ambos rangos de entrada contuvieran un elemento común solo una vez, entonces set_union 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,

¡Haz clic para puntuar esta entrada!
(Votos: 0 Promedio: 0)


Tags : / /

Utiliza Nuestro Buscador

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *