c++ STL set différence

Question

La structure de données set de la STL C++ dispose-t-elle d'un opérateur de différence de set ?

Answer 1

Une fois de plus, le boost vient à la rescousse :

#include <string>
#include <set>
#include <boost/range/algorithm/set_algorithm.hpp>

std::set<std::string> set0, set1, setDifference;
boost::set_difference(set0, set1, std::inserter(setDifference, setDifference.begin());

setDifference contiendra set0-set1.

Answer 2

Apparemment, c'est le cas.

SGI - set_difference

Answer 3

Toutes les réponses que je vois ici sont O(n). Ce ne serait pas mieux ?

template <class Key, class Compare, class Allocator>   
std::set<Key, Compare, Allocator> 
set_subtract(std::set<Key, Compare, Allocator>&& lhs,
             const std::set<Key, Compare, Allocator>& 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 être la bonne chose à faire. Je ne suis pas sûr de savoir comment gérer le cas où Compare ne spécifie pas complètement son comportement, comme dans le cas où Compare est un std::function<bool(int,int)> mais à part cela, cela semble fonctionner correctement et devrait être de l'ordre de O((nombre de chevauchements) - log( lhs.size() )).

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

Answer 4

Pas en tant que méthode mais il y a la fonction algorithmique externe set_difference

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

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

Answer 5

Pouvons-nous simplement utiliser

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