c++ - que - punto de interseccion entre rectas

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

Question

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

He creado una pequeña muestra de prueba 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 ningún resultado, pero espero tener un nuevo conjunto (llamémoslo s3 ) con los siguientes valores:

s3 = [ 1 , 3 ]

En su lugar, estoy recibiendo 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 en set_intersection que acepte Rb_tree_const_iterator<int> como parámetro.

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

¿hay una mejor manera de encontrar la intersección de dos std::set en C ++? Preferiblemente una función incorporada?

¡Muchas gracias!

Answer 1

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 intersección, 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));

Answer 2

El primer comentario (bien votado) de la respuesta aceptada se queja de un operador faltante para las operaciones de conjuntos 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 de retorno en los operadores. Puede ser, esto podría resolverse usando la asignación de movimientos pero esto aún está más allá de mis habilidades.

Debido a mi conocimiento limitado acerca de estas semánticas de movimientos "nuevos", me preocupé por las devoluciones del operador que podrían causar copias de los conjuntos devueltos. señaló que estas preocupaciones no son necesarias ya que std::set ya está equipado con un constructor / asignación de movimientos.

Aunque le creí, estaba pensando cómo comprobarlo (para algo como "auto-convincente"). En realidad, es bastante fácil. Como las plantillas deben proporcionarse en el código fuente, puede simplemente 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 std::set::set(_myt&& _Right) inmediatamente a std::set::set(_myt&& _Right) : et voilà - el constructor de movimientos. Gracias, Olaf, por la (mi) iluminación.

Para completar, también implementé los operadores de asignación correspondientes

• operator *=() para intersección "destructiva" de conjuntos
• operator +=() para 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 }

$

Answer 3

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

Arregla esto haciendo algo como

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

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

Answer 4

Solo comenta aquí. Creo que es hora de agregar unión, operación de intersección a la interfaz establecida. Propongamos esto en los futuros estándares. He estado usando el std durante mucho tiempo, cada vez que usé la operación de configuración deseé que el std fuera mejor. Para algunas operaciones de configuración complicadas, como la 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 set_intersection

Por ejemplo, si su salida es un conjunto, puede dar salida a .insert (* first1). Además, es posible que su función no tenga plantilla. Si su código puede ser más corto que usar la función std set_intersection, entonces continúe con él.

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

Answer 5

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

Ver Ideone para la lista completa.