como encontrar a interseção de dois std :: set em C ++?

Tenho tentado encontrar a interseção entre dois std :: set em C ++, mas continuo recebendo um erro.

Eu criei um pequeno teste de amostra para este

#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;
}

O último programa não gera nenhuma saída, mas espero ter um novo conjunto (vamos chamá-lo s3) com os seguintes valores:

s3 = [ 1 , 3 ]

Em vez disso, estou recebendo o erro:

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

O que entendi desse erro, é que não existe uma definição set_intersectionque aceite Rb_tree_const_iterator<int>como parâmetro.

Além disso, suponho que o std::set.begin()método retorna um objeto desse tipo,

existe uma maneira melhor de encontrar a interseção de dois std::setem C ++? De preferência, uma função embutida?

Muito obrigado!

Você não forneceu um iterador de saída para set_intersection

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

Corrija isso fazendo algo como

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

Você precisa de um std::insertiterador, pois o conjunto está vazio agora. Não podemos usar back_ ou front_inserter, pois set não suporta essas operações.

Dê uma olhada no exemplo no link: http://en.cppreference.com/w/cpp/algorithm/set_intersection

Você precisa de outro contêiner para armazenar os dados de interseção, o código abaixo deve funcionar:

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

Veja std :: set_intersection . Você deve adicionar um iterador de saída, onde armazenará o resultado:

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

Veja Ideone para uma lista completa.

Basta comentar aqui. Acho que é hora de adicionar a operação de união e interseção à interface definida. Vamos propor isso nos padrões futuros. Eu tenho usado o std por um longo tempo, cada vez que usei a operação de conjunto desejei que o std fosse melhor. Para alguma operação de conjunto complicada, como intersect, você pode simplesmente (mais fácil?) Modificar o seguinte 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 exemplo, se sua saída for um conjunto, você pode output.insert (* first1). Além disso, sua função não pode ser modelada. Se seu código pode ser mais curto do que usar a função std set_intersection, vá em frente com ela.

Se você quiser fazer uma união de dois conjuntos, você pode simplesmente setA.insert (setB.begin (), setB.end ()); Isso é muito mais simples do que o método set_union. No entanto, isso não funcionará com vetor.

O primeiro comentário (bem votado) da resposta aceita reclama sobre a falta de um operador para as operações de conjunto padrão existentes.

Por um lado, entendo a falta de tais operadores na biblioteca padrão. Por outro lado, é fácil adicioná-los (para a alegria pessoal) se desejar. Eu sobrecarreguei

• operator *() para interseção de conjuntos
• operator +() para união de conjuntos.

Amostra 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 e testado:

$ 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 }

$ 

O que eu não gosto é a cópia dos valores de retorno nas operadoras. Pode ser, isso poderia ser resolvido usando a atribuição de movimento, mas isso ainda está além das minhas habilidades.

Devido ao meu conhecimento limitado sobre essas semânticas de movimento "nova fantasia", fiquei preocupado com os retornos do operador que poderiam causar cópias dos conjuntos retornados. Olaf Dietsche apontou que essas preocupações são desnecessárias, pois std::setjá está equipado com o construtor / atribuição de movimento.

Embora acreditasse nele, estava pensando em como verificar isso (algo como "autoconvencimento"). Na verdade, é bem fácil. Como os modelos devem ser fornecidos no código-fonte, você pode simplesmente avançar com o depurador. Assim, coloquei um ponto de interrupção bem no return s;de operator *()e continuei com uma única etapa que me levou imediatamente a std::set::set(_myt&& _Right): et voilà - o construtor de movimento. Obrigado, Olaf, pela (minha) iluminação.

Para fins de integridade, implementei os operadores de atribuição correspondentes também

• operator *=() para interseção "destrutiva" de conjuntos
• operator +=() para união "destrutiva" de conjuntos.

Amostra 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 e testado:

$ 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 }

$