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

He estado tratando de encontrar la intersección entre dos std :: set en C ++, pero sigo recibiendo un error.

Creé una pequeña prueba de muestra para esto

#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
using namespace std;

int main() {
  set<int> s1;
  set<int> s2;

  s1.insert(1);
  s1.insert(2);
  s1.insert(3);
  s1.insert(4);

  s2.insert(1);
  s2.insert(6);
  s2.insert(3);
  s2.insert(0);

  set_intersection(s1.begin(),s1.end(),s2.begin(),s2.end());
  return 0;
}

El último programa no genera ninguna salida, pero espero tener un nuevo conjunto (llamémoslo s3) con los siguientes valores:

s3 = [ 1 , 3 ]

En cambio, obtengo el error:

test.cpp: In function ‘int main()’:
test.cpp:19: error: no matching function for call to ‘set_intersection(std::_Rb_tree_const_iterator<int>, std::_Rb_tree_const_iterator<int>, std::_Rb_tree_const_iterator<int>, std::_Rb_tree_const_iterator<int>)’

Lo que entiendo de este error es que no hay una definición set_intersectionque acepte Rb_tree_const_iterator<int>como parámetro.

Además, supongo que el std::set.begin()método devuelve un objeto de ese tipo,

¿Hay una mejor manera de encontrar la intersección de dos std::seten C ++? ¿Preferiblemente una función incorporada?

¡Muchas gracias!

No ha proporcionado un iterador de salida para set_intersection

template <class InputIterator1, class InputIterator2, class OutputIterator>
OutputIterator set_intersection ( InputIterator1 first1, InputIterator1 last1,
                                InputIterator2 first2, InputIterator2 last2,
                                OutputIterator result );

Solucione esto haciendo algo como

...;
set<int> intersect;
set_intersection(s1.begin(),s1.end(),s2.begin(),s2.end(),
                  std::inserter(intersect,intersect.begin()));

Necesita un std::insertiterador ya que el conjunto está ahora vacío. No podemos usar back_ o front_inserter ya que set no admite esas operaciones.

Eche 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 la intersección, se supone que el código siguiente funciona:

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

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

Consulte Ideone para obtener una lista completa.

Solo comente aquí. Creo que es hora de agregar unión, operación de intersección a la interfaz establecida. Propongamos esto en los estándares futuros. He estado usando el std durante mucho tiempo, cada vez que usaba la operación de configuración deseaba que el std fuera mejor. Para alguna operación de conjunto complicada, como intersección, 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 salida es un conjunto, puede output.insert (* first1). Además, es posible que su función no tenga plantilla. Si su código puede ser más corto que el uso de la función std set_intersection, continúe con él.

Si desea hacer una unión de dos conjuntos, simplemente puede setA.insert (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 estándar 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 lo desea. Yo sobrecargué

• operator *() para intersección de conjuntos
• operator +() para 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 resolverse usando la asignación de movimiento, pero esto aún está más allá de mis habilidades.

Debido a mi conocimiento limitado acerca de esta semántica de movimientos "nueva y elegante", estaba preocupado por los retornos del operador que podrían causar copias de los conjuntos devueltos. Olaf Dietsche señaló que estas preocupaciones son innecesarias ya std::setque ya está equipado con un constructor / asignación de movimientos.

Aunque le creí, estaba pensando en cómo comprobar esto (para algo como "autoconvencimiento"). De hecho, 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 condujo inmediatamente a std::set::set(_myt&& _Right): et voilà - el constructor de movimientos. Gracias, Olaf, por la (mi) iluminación.

En aras de la integridad, 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 }

$