cómo encontrar la intersección de dos std::set en C++?

Echa un vistazo a la muestra en el enlace: http://en.cppreference.com/w/cpp/algorithm/set_intersection

Necesita otro contenedor para almacenar los datos de intersección, por debajo del código se supone que funciona:

std::vector<int> common_data;
set_intersection(s1.begin(),s1.end(),s2.begin(),s2.end(), std::back_inserter(common_data));

Ver std::set_intersection. Debe agregar un iterador de salida, donde almacenará el resultado:

#include <iterator>
std::vector<int> s3;
set_intersection(s1.begin(),s1.end(),s2.begin(),s2.end(), std::back_inserter(s3));

Véase Ideone para la lista completa.

Solo comente aquí. Creo que es hora de agregar unión, operación de intersección a la interfaz establecida. Vamos a proponer esto en las normas futuras. He estado usando la ets durante mucho tiempo, cada vez que usé la operación del conjunto deseé que la ets fuera mejor. Para alguna operación de conjunto complicado, como intersect, usted puede simplemente (más fácil?) modificar el siguiente código:

template <class InputIterator1, class InputIterator2, class OutputIterator>
  OutputIterator set_intersection (InputIterator1 first1, InputIterator1 last1,
                                   InputIterator2 first2, InputIterator2 last2,
                                   OutputIterator result)
{
  while (first1!=last1 && first2!=last2)
  {
    if (*first1<*first2) ++first1;
    else if (*first2<*first1) ++first2;
    else {
      *result = *first1;
      ++result; ++first1; ++first2;
    }
  }
  return result;
}

Copiado de http://www.cplusplus.com/reference/algorithm/set_intersection/

Por ejemplo, si su la salida es un conjunto, puede salir.insértese (*primero1). Además, es posible que su función no esté templada.Si el código puede ser más corto que el uso de la función std set_intersection, siga adelante con él.

Si desea hacer una unión de dos conjuntos puede simplemente setA.insértese (setB.begin (), setB.end ()); Esto es mucho más simple que el método set_union. Sin embargo, esto no funcionará con vector.

El primer comentario (bien votado) de la respuesta aceptada se queja de que falta un operador para las operaciones de conjunto de std existentes.

Por un lado, entiendo la falta de tales operadores en la biblioteca estándar. Por otro lado, es fácil agregarlos (para la alegría personal) si se desea. He sobrecargado

• operator *() para la intersección de conjuntos
• operator +() para la unión de conjuntos.

Muestra test-set-ops.cc:

#include <algorithm>
#include <iterator>
#include <set>

template <class T, class CMP = std::less<T>, class ALLOC = std::allocator<T> >
std::set<T, CMP, ALLOC> operator * (
  const std::set<T, CMP, ALLOC> &s1, const std::set<T, CMP, ALLOC> &s2)
{
  std::set<T, CMP, ALLOC> s;
  std::set_intersection(s1.begin(), s1.end(), s2.begin(), s2.end(),
    std::inserter(s, s.begin()));
  return s;
}

template <class T, class CMP = std::less<T>, class ALLOC = std::allocator<T> >
std::set<T, CMP, ALLOC> operator + (
  const std::set<T, CMP, ALLOC> &s1, const std::set<T, CMP, ALLOC> &s2)
{
  std::set<T, CMP, ALLOC> s;
  std::set_union(s1.begin(), s1.end(), s2.begin(), s2.end(),
    std::inserter(s, s.begin()));
  return s;
}

// sample code to check them out:

#include <iostream>

using namespace std;

template <class T>
ostream& operator << (ostream &out, const set<T> &values)
{
  const char *sep = " ";
  for (const T &value : values) {
    out << sep << value; sep = ", ";
  }
  return out;
}

int main()
{
  set<int> s1 { 1, 2, 3, 4 };
  cout << "s1: {" << s1 << " }" << endl;
  set<int> s2 { 0, 1, 3, 6 };
  cout << "s2: {" << s2 << " }" << endl;
  cout << "I: {" << s1 * s2 << " }" << endl;
  cout << "U: {" << s1 + s2 << " }" << endl;
  return 0;
}

Compilado y probado:

$ g++ -std=c++11 -o test-set-ops test-set-ops.cc 

$ ./test-set-ops     
s1: { 1, 2, 3, 4 }
s2: { 0, 1, 3, 6 }
I: { 1, 3 }
U: { 0, 1, 2, 3, 4, 6 }

$ 

Lo que no me gusta es la copia de los valores devueltos en los operadores. Puede ser, esto podría ser resuelto usando la asignación de movimiento, pero esto todavía está más allá de mis habilidades.

Debido a mi conocimiento limitado sobre estas semánticas de movimiento "nuevas fantasías", estaba preocupado por los retornos de operadores que podrían causar copias de los conjuntos devueltos. Olaf Dietsche señaló que estas preocupaciones son innecesarias, ya que std::set ya está equipado con move constructor/asignación.

Aunque le creí, estaba pensando cómo comprobar esto (para algo como "auto-convincente"). En realidad, es bastante fácil. Como las plantillas deben proporcionarse en el código fuente, simplemente puede pasar por el depurador. Por lo tanto, coloqué un punto de ruptura justo en el return s; del operator *() y procedí con un solo paso que me llevó inmediatamente a std::set::set(_myt&& _Right): et voilà-el constructor de movimiento. Gracias, Olaf, por la (mi) aclaración.

Por el bien de completitud, también implementé los operadores de asignación correspondientes

• operator *=() para la intersección "destructiva" de conjuntos
• operator +=() para la unión "destructiva" de conjuntos.

Muestra test-set-assign-ops.cc:

#include <iterator>
#include <set>

template <class T, class CMP = std::less<T>, class ALLOC = std::allocator<T> >
std::set<T, CMP, ALLOC>& operator *= (
  std::set<T, CMP, ALLOC> &s1, const std::set<T, CMP, ALLOC> &s2)
{
  auto iter1 = s1.begin();
  for (auto iter2 = s2.begin(); iter1 != s1.end() && iter2 != s2.end();) {
    if (*iter1 < *iter2) iter1 = s1.erase(iter1);
    else {
      if (!(*iter2 < *iter1)) ++iter1;
      ++iter2;
    }
  }
  while (iter1 != s1.end()) iter1 = s1.erase(iter1);
  return s1;
}

template <class T, class CMP = std::less<T>, class ALLOC = std::allocator<T> >
std::set<T, CMP, ALLOC>& operator += (
  std::set<T, CMP, ALLOC> &s1, const std::set<T, CMP, ALLOC> &s2)
{
  s1.insert(s2.begin(), s2.end());
  return s1;
}

// sample code to check them out:

#include <iostream>

using namespace std;

template <class T>
ostream& operator << (ostream &out, const set<T> &values)
{
  const char *sep = " ";
  for (const T &value : values) {
    out << sep << value; sep = ", ";
  }
  return out;
}

int main()
{
  set<int> s1 { 1, 2, 3, 4 };
  cout << "s1: {" << s1 << " }" << endl;
  set<int> s2 { 0, 1, 3, 6 };
  cout << "s2: {" << s2 << " }" << endl;
  set<int> s1I = s1;
  s1I *= s2;
  cout << "s1I: {" << s1I << " }" << endl;
  set<int> s2I = s2;
  s2I *= s1;
  cout << "s2I: {" << s2I << " }" << endl;
  set<int> s1U = s1;
  s1U += s2;
  cout << "s1U: {" << s1U << " }" << endl;
  set<int> s2U = s2;
  s2U += s1;
  cout << "s2U: {" << s2U << " }" << endl;
  return 0;
}

Compilado y probado:

$ g++ -std=c++11 -o test-set-assign-ops test-set-assign-ops.cc 

$ ./test-set-assign-ops
s1: { 1, 2, 3, 4 }
s2: { 0, 1, 3, 6 }
s1I: { 1, 3 }
s2I: { 1, 3 }
s1U: { 0, 1, 2, 3, 4, 6 }
s2U: { 0, 1, 2, 3, 4, 6 }

$