Encontrar la intersección del conjunto en C++

Jinku Hu 30 enero 2023
  1. Usa el método std::set_intersection para encontrar la intersección del conjunto en C++
  2. Usa el método std::set_symmetric_difference para encontrar la diferencia simétrica establecida en C++
Encontrar la intersección del conjunto en C++

Este artículo explicará varios métodos de cómo encontrar la intersección del conjunto en C++.

Usa el método std::set_intersection para encontrar la intersección del conjunto en C++

El método std::set_intersection es parte de la librería de algoritmos de C++, que está incluida en la cabecera <algorithm>. La operación del algoritmo set_intersection no está restringida a los objetos std::set, sino que puede procesar cualquier objeto basado en el rango, por ejemplo, std::vector. Nótese que ambos rangos de entrada deben ser ordenados antes de pasar a un algoritmo set_intersection.

En el siguiente ejemplo, declaramos dos variables std::set e iniciamos con elementos arbitrarios de tipo string. Los primeros cuatro parámetros de la función set_intersection son los iteradores de rango de los objetos correspondientes, y el quinto argumento es el comienzo del rango donde se almacena la intersección calculada. En este caso, declaramos un std::vector para guardar estos elementos.

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

using std::cout; using std::endl;
using std::cin; using std::string;
using std::set; using std::vector;

template<typename T>
void printVectorElements(vector<T> &vec)
{
    cout << "{ ";
    for (const auto &item : vec) {
        cout << item << ", ";
    }
    cout << "\b\b }" << endl;
}

int main() {
    set<string> s1 {"array", "vector",
                    "deque", "list",
                    "set", "map",
                    "multimap", "span"};
    set<string> s2(s1);
    s2.insert("stack");
    s2.insert("queue");

    vector<string> s1s2_intsec;

    std::set_intersection(s1.begin(), s1.end(),
                          s2.begin(), s2.end(),
                          std::back_inserter(s1s2_intsec));

    cout << "s1 ∩ s2: ";
    printVectorElements(s1s2_intsec);

    exit(EXIT_SUCCESS);
}

Producción :

s1 ∩ s2: ( array, deque, list, map, multimap, set, span, vector )

Aunque std::set_intersection almacena los elementos de intersección según lo especificado por el usuario, no debe ser el rango que se superpone con ninguno de los rangos de entrada. Otro punto importante que hay que tener en cuenta es especificar el rango de destino, que tiene suficiente espacio para almacenar los elementos de intersección. El método flexible para esto sería utilizar una array dinámica std::vector y utilizar el método std::back_inserter para empujar los elementos al objeto. Si especificas el vector.begin() iterador sin reservar la memoria como parámetro de destino, el algoritmo puede lanzar un fallo de segmentación. El siguiente ejemplo demuestra el método set_intersection en objetos vector.

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

using std::cout; using std::endl;
using std::cin; using std::string;
using std::set; using std::vector;

template<typename T>
void printVectorElements(vector<T> &vec)
{
    cout << "{ ";
    for (const auto &item : vec) {
        cout << item << ", ";
    }
    cout << "\b\b }" << endl;
}

int main() {
    vector<int> v1v2_intsec;
    vector<int> v1 {9,7,5,1,2};
    vector<int> v2 {4,3,2,1,7,8};
    std::sort(v1.begin(), v1.end());
    std::sort(v2.begin(), v2.end());

    std::set_intersection(v1.begin(), v1.end(),
                          v2.begin(), v2.end(),
                          std::back_inserter(v1v2_intsec));
    cout << "v1 ∩ v2: ";
    printVectorElements(v1v2_intsec);

    exit(EXIT_SUCCESS);
}

Producción :

v1 ∩ v2: ( 1, 2, 7 )

Usa el método std::set_symmetric_difference para encontrar la diferencia simétrica establecida en C++

Otro algoritmo de la biblioteca estándar de C++ es el std::set_symmetric_difference, que busca los elementos que se encuentran sólo en uno de los rangos de entrada. Los parámetros de la función son similares al método std::set_intersection. Ambos algoritmos toman rangos ordenados y almacenan los elementos encontrados también de forma ordenada. Observe que el contenedor std::set contiene por defecto elementos ordenados. Por lo tanto, puede ser pasado directamente como el rango de entrada. Mientras que el contenido de std::vector debe ser ordenado explícitamente antes de ser procesado por std::set_symmetric_difference.

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

using std::cout; using std::endl;
using std::cin; using std::string;
using std::set; using std::vector;

template<typename T>
void printVectorElements(vector<T> &vec)
{
    cout << "{ ";
    for (const auto &item : vec) {
        cout << item << ", ";
    }
    cout << "\b\b }" << endl;
}

int main() {
    vector<int> v1 {9,7,5,1,2};
    vector<int> v2 {4,3,2,1,7,8};
    std::sort(v1.begin(), v1.end());
    std::sort(v2.begin(), v2.end());

    vector<int> v1v2_symdif;
    std::set_symmetric_difference(v1.begin(), v1.end(),
                          v2.begin(), v2.end(),
                          std::back_inserter(v1v2_symdif));
    cout << "v1 △ v2: ";
    printVectorElements(v1v2_symdif);

    exit(EXIT_SUCCESS);
}

Producción :

v1 △ v2: ( 3, 4, 5, 8, 9 )
Autor: Jinku Hu
Jinku Hu avatar Jinku Hu avatar

Founder of DelftStack.com. Jinku has worked in the robotics and automotive industries for over 8 years. He sharpened his coding skills when he needed to do the automatic testing, data collection from remote servers and report creation from the endurance test. He is from an electrical/electronics engineering background but has expanded his interest to embedded electronics, embedded programming and front-/back-end programming.

LinkedIn Facebook

Artículo relacionado - C++ Set