std::set_difference — cppreference.com

De cppreference.com

Déclaré dans l'en-tête `<algorithm>`
`template< class InputIt1, class InputIt2, class OutputIt > OutputIt set_difference( InputIt1 first1, InputIt1 last1, InputIt2 first2, InputIt2 last2, OutputIt d_first );`	(1)
`template< class InputIt1, class InputIt2, class OutputIt, class Compare > OutputIt set_difference( InputIt1 first1, InputIt1 last1, InputIt2 first2, InputIt2 last2, OutputIt d_first, Compare comp );`	(2)

Copie les éléments de la gamme [first1, last1) triés qui ne se trouvent pas dans la gamme triés [first2, last2) au début de la plage à d_first .

Original:

Copies the elements from the sorted range [first1, last1) which are not found in the sorted range [first2, last2) to the range beginning at d_first.

The text has been machine-translated via Google Translate.
You can help to correct and verify the translation. Click here for instructions.

La plage résultante est également triée. La première version prévoit à la fois d'entrée se situe à trier avec operator<, la deuxième version s'attend à ce qu'ils soient triés à la comp fonction de comparaison donnée. éléments équivalents sont traités individuellement , qui est, si un élément est trouvé m fois dans [first1, last1) et n fois dans [first2, last2), il sera copié dans d_first exactement std::max(m-n, 0) fois. La gamme résultante ne peut pas faire double emploi avec l'une des plages d'entrée .

Original:

The resulting range is also sorted. The first version expects both input ranges to be sorted with operator<, the second version expects them to be sorted with the given comparison function comp. Equivalent elements are treated individually, that is, if some element is found m times in [first1, last1) and n times in [first2, last2), it will be copied to d_first exactly std::max(m-n, 0) times. The resulting range cannot overlap with either of the input ranges.

The text has been machine-translated via Google Translate.
You can help to correct and verify the translation. Click here for instructions.

Paramètres

first1, last1	-	l'éventail des éléments à examiner Original: the range of elements to examine The text has been machine-translated via Google Translate. You can help to correct and verify the translation. Click here for instructions.
first2, last2	-	l'éventail des éléments à rechercher Original: the range of elements to search for The text has been machine-translated via Google Translate. You can help to correct and verify the translation. Click here for instructions.
comp	-	comparison function which returns `true` if the first argument is less than the second. The signature of the comparison function should be equivalent to the following: `bool cmp(const Type1 &a, const Type2 &b);` The signature does not need to have `const &`, but the function must not modify the objects passed to it. The types `Type1` and `Type2` must be such that objects of types `InputIt1` and `InputIt2` can be dereferenced and then implicitly converted to `Type1` and `Type2` respectively.
Type requirements
-`InputIt1` must meet the requirements of `InputIterator`.
-`InputIt2` must meet the requirements of `InputIterator`.
-`OutputIt` must meet the requirements of `OutputIterator`.

Retourne la valeur

Iterator-delà de la fin de la gamme construit .

Original:

Iterator past the end of the constructed range.

The text has been machine-translated via Google Translate.
You can help to correct and verify the translation. Click here for instructions.

Complexité

A comparaisons plupart 2·(N₁+N₂-1), où N₁ = std::distance(first1, last1) et N₂ = std::distance(first2, last2) .

Original:

At most 2·(N₁+N₂-1) comparisons, where N₁ = std::distance(first1, last1) and N₂ = std::distance(first2, last2).

The text has been machine-translated via Google Translate.
You can help to correct and verify the translation. Click here for instructions.

Mise en œuvre possible

First version
template<class InputIt1, class InputIt2, class OutputIt> OutputIt set_difference(InputIt1 first1, InputIt1 last1, InputIt2 first2, InputIt2 last2, OutputIt d_first) { while (first1 != last1) { if (first2 == last2) return std::copy(first1, last1, d_first); if (first1 < first2) { d_first++ = first1++; } else { if (! (first2 < first1)) { ++first1; } ++first2; } } return d_first; }
Second version
template<class InputIt1, class InputIt2, class OutputIt, class Compare> OutputIt set_difference( InputIt1 first1, InputIt1 last1, InputIt2 first2, InputIt2 last2, OutputIt d_first, Compare comp) { while (first1 != last1) { if (first2 == last2) return std::copy(first1, last1, d_first); if (comp(first1, first2)) { d_first++ = first1++; } else { if (!comp(first2, first1)) { ++first1; } ++first2; } } return d_first; }

First version

template<class InputIt1, class InputIt2, class OutputIt>
OutputIt set_difference(InputIt1 first1, InputIt1 last1,
                        InputIt2 first2, InputIt2 last2,
                        OutputIt d_first)
{
    while (first1 != last1) {
        if (first2 == last2) return std::copy(first1, last1, d_first);

        if (*first1 < *first2) {
            *d_first++ = *first1++;
        } else {
            if (! (*first2 < *first1)) {
                ++first1;
            }
            ++first2;
        }
    }
    return d_first;
}

Second version

template<class InputIt1, class InputIt2,
         class OutputIt, class Compare>
OutputIt set_difference( InputIt1 first1, InputIt1 last1,
                         InputIt2 first2, InputIt2 last2,
                         OutputIt d_first, Compare comp)
{
    while (first1 != last1) {
        if (first2 == last2) return std::copy(first1, last1, d_first);

        if (comp(*first1, *first2)) {
            *d_first++ = *first1++;
        } else {
            if (!comp(*first2, *first1)) {
                ++first1;
            }
            ++first2;
        }
    }
    return d_first;
}

Exemple

#include <iostream>
#include <algorithm>
#include <vector>
#include <iterator>

int main() {
    std::vector<int> v1 {1, 2, 5, 5, 5, 9};
    std::vector<int> v2 {2, 5, 7};
    std::vector<int> diff;
 
    std::set_difference(v1.begin(), v1.end(), v2.begin(), v2.end(), 
                        std::inserter(diff, diff.begin()));
  
    for (auto i : v1) std::cout << i << ' ';
    std::cout << "minus ";
    for (auto i : v2) std::cout << i << ' ';
    std::cout << "is: ";
  
    for (auto i : diff) std::cout << i << ' ';
    std::cout << '\n';
}

Résultat :

1 2 5 5 5 9 minus 2 5 7 is: 1 5 5 9

Voir aussi


	retourne vrai si un ensemble est un sous-ensemble de l'autre Original: returns true if one set is a subset of another The text has been machine-translated via Google Translate. You can help to correct and verify the translation. Click here for instructions. (fonction générique) [edit]

	calcule la différence symétrique entre deux ensembles Original: computes the symmetric difference between two sets The text has been machine-translated via Google Translate. You can help to correct and verify the translation. Click here for instructions. (fonction générique) [edit]