c ++ STL ensemble différence

La structure de données définie en C ++ STL a-t-elle un opérateur de différence de set?

Oui, il est dans et s’appelle: std::set_difference . L’utilisation est la suivante:

 #include  #include  #include  // ... std::set s1, s2; // Fill in s1 and s2 with values std::set result; std::set_difference(s1.begin(), s1.end(), s2.begin(), s2.end(), std::inserter(result, result.end())); 

En fin de compte, le result défini contiendra le s1-s2 .

Oui, il y a une fonction set_difference dans l’en-tête des algorithmes.

Edits:

FYI, la structure de données définie est capable d’utiliser efficacement cet algorithme, comme indiqué dans sa documentation . L’algorithme fonctionne également non seulement sur les ensembles, mais sur toute paire d’iterators sur les collections sortingées.

Comme d’autres l’ont mentionné, il s’agit d’un algorithme externe et non d’une méthode. Je suppose que cela convient à votre demande.

Pas un “opérateur” au sens du langage, mais il y a l’algorithme set_difference dans la bibliothèque standard:

http://www.cplusplus.com/reference/algorithm/set_difference.html

Bien sûr, les autres opérations de base sont également présentes – (union, etc.), comme le suggère la section “Voir aussi” à la fin de l’article lié.

La réponse choisie est correcte, mais contient des erreurs de syntaxe.

Au lieu de

 #include  

utilisation

 #include  

Au lieu de

 std::insert_iterator(result, result.end())); 

utilisation

 std::insert_iterator >(result, result.end())); 

Pas comme une méthode, mais il y a la fonction d’algorithme externe set_difference

 template  OutputIterator set_difference(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, OutputIterator result); 

http://www.sgi.com/tech/stl/set_difference.html

Apparemment, c’est le cas.

SGI – set_difference

Encore une fois, booster à la rescousse:

 #include  #include  #include  std::set set0, set1, setDifference; boost::set_difference(set0, set1, std::inserter(setDifference, setDifference.begin()); 

setDifference contiendra set0-set1.

pouvons-nous simplement utiliser

  set_difference(set1.begin(), set1.end(), set2.begin(). set2,end(),std::back_inserter(result)). 

C ++ ne définit pas d’opérateur de différence de set mais vous pouvez définir le vôtre (en utilisant le code fourni dans d’autres réponses):

 template set operator -(set reference, set items_to_remove) { set result; std::set_difference( reference.begin(), reference.end(), items_to_remove.begin(), items_to_remove.end(), std::inserter(result, result.end())); return result; } 

Toutes les réponses que je vois ici sont O (n). Ne serait-ce pas mieux?

 template  std::set set_subtract(std::set&& lhs, const std::set& rhs) { if (lhs.empty()) { return lhs; } // First narrow down the overlapping range: const auto rhsbeg = rhs.lower_bound(*lhs.begin()); const auto rhsend = rhs.upper_bound(*lhs.rbegin()); for (auto i = rhsbeg; i != rhsend; ++i) { lhs.erase(*i); } return std::move(lhs); } 

Cela semble faire la bonne chose. Je ne sais pas comment traiter le cas où le type de Compare ne spécifie pas complètement son comportement, comme si Compare était un std::function , mais à part cela, cela semble pour fonctionner correctement et devrait être comme O ((num recouvrant) • log ( lhs.size() )).

Dans le cas où lhs ne contient pas *i , il est probablement possible d’optimiser davantage en effectuant une recherche O (log ( rhs.size() )) pour l’élément suivant de rhs qui est> = l’élément suivant de lhs . Cela optimiserait le cas où lhs = {0, 1000} et rhs = {1, 2, ..., 999} pour effectuer la soustraction en temps de log.