comment trouver l'intersection de deux std :: set en C ++?

J'ai essayé de trouver l'intersection entre deux std :: set en C ++, mais j'obtiens toujours une erreur.

J'ai créé un petit exemple de test pour cela

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

Ce dernier programme ne génère aucune sortie, mais je m'attends à avoir un nouvel ensemble (appelons-le s3) avec les valeurs suivantes:

s3 = [ 1 , 3 ]

Au lieu de cela, j'obtiens l'erreur:

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

Ce que je comprends de cette erreur, c'est qu'il n'y a pas de définition set_intersectionqui accepte Rb_tree_const_iterator<int>comme paramètre.

De plus, je suppose que la std::set.begin()méthode renvoie un objet de ce type,

y a-t-il une meilleure façon de trouver l'intersection de deux std::seten C ++? De préférence une fonction intégrée?

Merci beaucoup!

Vous n'avez pas fourni d'itérateur de sortie pour set_intersection

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

Corrigez cela en faisant quelque chose comme

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

Vous avez besoin d'un std::insertitérateur car l'ensemble est désormais vide. Nous ne pouvons pas utiliser back_ ou front_inserter car set ne prend pas en charge ces opérations.

Jetez un œil à l'exemple dans le lien: http://en.cppreference.com/w/cpp/algorithm/set_intersection

Vous avez besoin d'un autre conteneur pour stocker les données d'intersection, sous le code supposé fonctionner:

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

Voir std :: set_intersection . Vous devez ajouter un itérateur de sortie, dans lequel vous stockerez le résultat:

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

Voir Ideone pour la liste complète.

Juste commenter ici. Je pense qu'il est temps d'ajouter l'union, l'opération d'intersection à l'interface définie. Proposons cela dans les futures normes. J'utilise le std depuis longtemps, chaque fois que j'utilisais l'opération set, j'aurais souhaité que le std soit meilleur. Pour une opération d'ensemble compliquée, comme l'intersection, vous pouvez simplement (plus facilement?) Modifier le code suivant:

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

copié de http://www.cplusplus.com/reference/algorithm/set_intersection/

Par exemple, si votre sortie est un ensemble, vous pouvez output.insert (* first1). De plus, votre fonction peut ne pas être modélisée.Si votre code peut être plus court que l'utilisation de la fonction std set_intersection, continuez avec.

Si vous voulez faire une union de deux ensembles, vous pouvez simplement setA.insert (setB.begin (), setB.end ()); C'est beaucoup plus simple que la méthode set_union. Cependant, cela ne fonctionnera pas avec le vecteur.

Le premier commentaire (bien voté) de la réponse acceptée se plaint d'un opérateur manquant pour les opérations existantes de l'ensemble std.

D'une part, je comprends l'absence de tels opérateurs dans la bibliothèque standard. D'autre part, il est facile de les ajouter (pour la joie personnelle) si vous le souhaitez. J'ai surchargé

• operator *() pour l'intersection d'ensembles
• operator +() pour l'union d'ensembles.

Échantillon 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;
}

Compilé et testé:

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

$ 

Ce que je n'aime pas, c'est la copie des valeurs de retour dans les opérateurs. Peut-être, cela pourrait être résolu en utilisant l'affectation de déménagement, mais cela dépasse toujours mes compétences.

En raison de ma connaissance limitée de cette sémantique de mouvement «nouvelle fantaisie», j'étais préoccupé par les retours d'opérateurs qui pourraient provoquer des copies des ensembles retournés. Olaf Dietsche a souligné que ces préoccupations sont inutiles car il std::setest déjà équipé d'un constructeur de déménagement / d'une affectation.

Bien que je l'ai cru, je pensais comment vérifier cela (pour quelque chose comme "auto-convaincant"). En fait, c'est assez facile. Comme les modèles doivent être fournis dans le code source, vous pouvez simplement parcourir le débogueur. Ainsi, j'ai placé un point de rupture juste à la fin return s;de la operator *()et j'ai procédé à une seule étape qui m'a immédiatement conduit àstd::set::set(_myt&& _Right) : et voilà - le constructeur de mouvement. Merci, Olaf, pour (ma) illumination.

Par souci d'exhaustivité, j'ai également implémenté les opérateurs d'affectation correspondants

• operator *=() pour l'intersection "destructive" d'ensembles
• operator +=() pour l'union "destructive" d'ensembles.

Échantillon 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;
}

Compilé et testé:

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

$