◐ Shell
clean mode source ↗

std::set_intersection — cppreference.com

De cppreference.com

<metanoindex/>

<tbody> </tbody>

Déclaré dans l'en-tête

<algorithm>

template< class InputIt1, class InputIt2, class OutputIt > OutputIt set_intersection( InputIt1 first1, InputIt1 last1, InputIt2 first2, InputIt2 last2, OutputIt d_first );

 (1)

template< class InputIt1, class InputIt2, class OutputIt, class Compare > OutputIt set_intersection( InputIt1 first1, InputIt1 last1, InputIt2 first2, InputIt2 last2, OutputIt d_first, Compare comp );

 (2)

Construit une gamme débutant triés à d_first constitué d'éléments que l'on retrouve dans les deux gammes triés [first1, last1) et [first2, last2). 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. Si un élément est trouvé m fois en [first1, last1) et n fois dans [first2, last2), les éléments std::min(m, n) premiers seront copiés à partir de la première plage à la plage de destination. L'ordre des éléments équivalents est préservée. La gamme résultante ne peut pas faire double emploi avec l'une des plages d'entrée .

Original:

Constructs a sorted range beginning at d_first consisting of elements that are found in both sorted ranges [first1, last1) and [first2, last2). 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. If some element is found m times in [first1, last1) and n times in [first2, last2), the first std::min(m, n) elements will be copied from the first range to the destination range. The order of equivalent elements is preserved. 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 -

la première gamme d'éléments à examiner

Original:

the first 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 -

la seconde plage d'éléments à examiner

Original:

the second 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.

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·(N1+N2-1), où N1 = std::distance(first1, last1) et N2 = std::distance(first2, last2) .

Original:

At most 2·(N1+N2-1) comparisons, where N1 = std::distance(first1, last1) and N2 = 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_intersection(InputIt1 first1, InputIt1 last1,
                          InputIt2 first2, InputIt2 last2,
                          OutputIt d_first)
{
    while (first1 != last1 && first2 != last2) {
        if (*first1 < *first2) {
            ++first1;
        } else  {
            if (!(*first2 < *first1)) {
                *d_first++ = *first1++;
            }
            ++first2;
        }
    }
    return d_first;
}
Second version 
template<class InputIt1, class InputIt2,
         class OutputIt, class Compare>
OutputIt set_intersection(InputIt1 first1, InputIt1 last1,
                          InputIt2 first2, InputIt2 last2,
                          OutputIt d_first, Compare comp)
{
    while (first1 != last1 && first2 != last2) {
        if (comp(*first1, *first2)) {
            ++first1;
        } else {
            if (!comp(*first2, *first1)) {
                *d_first++ = *first1++;
            }
            ++first2;
        }
    }
    return d_first;
}

Exemple

#include <iostream>
#include <vector>
#include <algorithm>
#include <iterator>
int main()
{
    std::vector<int> v1{1,2,3,4,5,6,7,8};
    std::vector<int> v2{        5,  7,  9,10};
    std::sort(v1.begin(), v1.end());
    std::sort(v2.begin(), v2.end());

    std::vector<int> v_intersection;

    std::set_intersection(v1.begin(), v1.end(),
                          v2.begin(), v2.end(),
                          std::back_inserter(v_intersection));
    for(int n : v_intersection)
        std::cout << n << ' ';
}

Résultat :

Voir aussi

calcule l'union de deux ensembles

Original:

computes the union of 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]