set_intersection
Regroupe tous les éléments de deux plages sources triées au sein d'une même plage de destination triée. Le critère de tri peut être spécifié par un prédicat binaire.
template<class InputIterator1, class InputIterator2, class OutputIterator>
OutputIterator set_intersection(
InputIterator1 _First1,
InputIterator1 _Last1,
InputIterator2 _First2,
InputIterator2 _Last2,
OutputIterator _Result
);
template<class InputIterator1, class InputIterator2, class OutputIterator, class BinaryPredicate>
OutputIterator set_intersection(
InputIterator1 _First1,
InputIterator1 _Last1,
InputIterator2 _First2,
InputIterator2 _Last2,
OutputIterator _Result,
BinaryPredicate _Comp
);
Paramètres
_First1
Un itérateur d'entrée s'adressant à la position du premier élément de la première de deux plages sources triées, à unir et trier dans une seule plage qui représente l'intersection des deux plages sources._Last1
Un itérateur d'entrée s'adressant à la position de l'élément immédiatement après le dernier de la première des deux plages sources triées, à unir et trier dans une seule plage qui représente l'intersection des deux plages sources._First2
Un itérateur d'entrée s'adressant à la position du premier élément de la deuxième de deux plages sources triées, à unir et trier dans une seule plage qui représente l'intersection des deux plages sources._Last2
Un itérateur d'entrée s'adressant à la position de l'élément immédiatement après le dernier élément de la deuxième de deux plages sources triées, à unir et trier dans une seule plage qui représente l'intersection des deux plages sources.**_**Résultat
Un itérateur de sortie s'adressant à la position du premier élément dans la plage de destination où les deux plages sources doivent être unies dans une seule plage triée qui représente l'intersection des deux plages sources._Comp
Objet de fonction de prédicat défini par l'utilisateur qui définit le sens dans lequel un élément est supérieur à un autre. Le prédicat binaire accepte deux arguments et doit retourner true lorsque le premier élément est plus petit que le deuxième élément et false sinon.
Valeur de retour
Un itérateur de sortie s'adressant à au premier élément après le dernier dans la plage de destination triée qui représente l'intersection de deux plages sources.
Notes
Les plages source triées référencées doivent être valides ; tous les pointeurs doivent être deréférençables et, dans chaque séquence, la dernière position doit être accessible à partir de la première par incrémentation.
La plage de destination ne doit pas se chevaucher l'une ou l'autre des plages sources et doit être assez importante pour contenir la plage de destination.
Les plages source triées doivent chacune être organisées comme une condition préalable à l'application de l'algorithme de fusion conformément au même critère de classement utilisé par l'algorithme pour trier les plages associées.
L'opération est stable car l'ordre relatif d'éléments dans chaque plage est conservé dans la plage de destination. Les plages sources ne sont pas modifiées par l'algorithme.
Les types de valeur des itérateurs d'entrée doivent être inférieurs à comparable pour être classés, afin que, avec deux éléments, il puisse être possible de déterminer si l'un ou l'autre est équivalent (dans le sens où aucune n'est inférieur à l'autre) ou que l'un est inférieur à l'autre. Cela entraîne un classement entre les éléments non-équivalents. En présence d'éléments équivalents dans les deux plages sources, les éléments de la première plage précèdent les éléments de la deuxième plage source dans la plage de destination. Si les plages sources contiennent des doublons d'un élément, la plage de destination contient le nombre maximal de ces éléments qui se apparaissent dans les deux plages sources.
La complexité de l'algorithme est linéaire avec au plus 2 * (_Last1 – _First1) + (_Last2 – _First2)) – 1 comparaisons pour les plages sources non vides.
set_intersection a deux formulaires connexes :
Pour plus d'informations sur le comportement de ces fonctions, consultez Itérateurs vérifiés.
Exemple
// alg_set_intersection.cpp
// compile with: /EHsc
#include <vector>
#include <algorithm>
#include <functional> // For greater<int>( )
#include <iostream>
// Return whether modulus of elem1 is less than modulus of elem2
bool mod_lesser (int elem1, int elem2 ) {
if ( elem1 < 0 )
elem1 = - elem1;
if ( elem2 < 0 )
elem2 = - elem2;
return elem1 < elem2;
}
int main() {
using namespace std;
vector <int> v1a, v1b, v1 ( 12 );
vector <int>::iterator Iter1a, Iter1b, Iter1, Result1;
// Constructing vectors v1a & v1b with default less than ordering
int i;
for ( i = -1 ; i <= 3 ; i++ )
v1a.push_back( i );
int ii;
for ( ii =-3 ; ii <= 1 ; ii++ )
v1b.push_back( ii );
cout << "Original vector v1a with range sorted by the\n "
<< "binary predicate less than is v1a = ( " ;
for ( Iter1a = v1a.begin( ) ; Iter1a != v1a.end( ) ; Iter1a++ )
cout << *Iter1a << " ";
cout << ")." << endl;
cout << "Original vector v1b with range sorted by the\n "
<< "binary predicate less than is v1b = ( " ;
for ( Iter1b = v1b.begin ( ) ; Iter1b != v1b.end ( ) ; Iter1b++ )
cout << *Iter1b << " ";
cout << ")." << endl;
// Constructing vectors v2a & v2b with ranges sorted by greater
vector <int> v2a ( v1a ) , v2b ( v1b ) , v2 ( v1 );
vector <int>::iterator Iter2a, Iter2b, Iter2, Result2;
sort ( v2a.begin ( ) , v2a.end ( ) , greater<int> ( ) );
sort ( v2b.begin ( ) , v2b.end ( ) , greater<int> ( ) );
cout << "Original vector v2a with range sorted by the\n "
<< "binary predicate greater is v2a = ( " ;
for ( Iter2a = v2a.begin ( ) ; Iter2a != v2a.end ( ) ; Iter2a++ )
cout << *Iter2a << " ";
cout << ")." << endl;
cout << "Original vector v2b with range sorted by the\n "
<< "binary predicate greater is v2b = ( " ;
for ( Iter2b = v2b.begin ( ) ; Iter2b != v2b.end ( ) ; Iter2b++ )
cout << *Iter2b << " ";
cout << ")." << endl;
// Constructing vectors v3a & v3b with ranges sorted by mod_lesser
vector <int> v3a ( v1a ), v3b ( v1b ) , v3 ( v1 );
vector <int>::iterator Iter3a, Iter3b, Iter3, Result3;
sort ( v3a.begin ( ) , v3a.end ( ) , mod_lesser );
sort ( v3b.begin ( ) , v3b.end ( ) , mod_lesser );
cout << "Original vector v3a with range sorted by the\n "
<< "binary predicate mod_lesser is v3a = ( " ;
for ( Iter3a = v3a.begin ( ) ; Iter3a != v3a.end ( ) ; Iter3a++ )
cout << *Iter3a << " ";
cout << ")." << endl;
cout << "Original vector v3b with range sorted by the\n "
<< "binary predicate mod_lesser is v3b = ( " ;
for ( Iter3b = v3b.begin ( ) ; Iter3b != v3b.end ( ) ; Iter3b++ )
cout << *Iter3b << " ";
cout << ")." << endl;
// To combine into an intersection in asscending order with the
// default binary predicate less <int> ( )
Result1 = set_intersection ( v1a.begin ( ) , v1a.end ( ) ,
v1b.begin ( ) , v1b.end ( ) , v1.begin ( ) );
cout << "Intersection of source ranges with default order,"
<< "\n vector v1mod = ( " ;
for ( Iter1 = v1.begin( ) ; Iter1 != Result1 ; ++Iter1 )
cout << *Iter1 << " ";
cout << ")." << endl;
// To combine into an intersection in descending order, specify
// binary predicate greater<int>( )
Result2 = set_intersection ( v2a.begin ( ) , v2a.end ( ) ,
v2b.begin ( ) , v2b.end ( ) ,v2.begin ( ) , greater <int> ( ) );
cout << "Intersection of source ranges with binary predicate"
<< " greater specified,\n vector v2mod = ( " ;
for ( Iter2 = v2.begin( ) ; Iter2 != Result2 ; ++Iter2 )
cout << *Iter2 << " ";
cout << ")." << endl;
// To combine into an intersection applying a user-defined
// binary predicate mod_lesser
Result3 = set_intersection ( v3a.begin ( ) , v3a.end ( ) ,
v3b.begin ( ) , v3b.end ( ) , v3.begin ( ) , mod_lesser );
cout << "Intersection of source ranges with binary predicate "
<< "mod_lesser specified,\n vector v3mod = ( " ; ;
for ( Iter3 = v3.begin( ) ; Iter3 != Result3 ; ++Iter3 )
cout << *Iter3 << " ";
cout << ")." << endl;
}
Sortie
Original vector v1a with range sorted by the
binary predicate less than is v1a = ( -1 0 1 2 3 ).
Original vector v1b with range sorted by the
binary predicate less than is v1b = ( -3 -2 -1 0 1 ).
Original vector v2a with range sorted by the
binary predicate greater is v2a = ( 3 2 1 0 -1 ).
Original vector v2b with range sorted by the
binary predicate greater is v2b = ( 1 0 -1 -2 -3 ).
Original vector v3a with range sorted by the
binary predicate mod_lesser is v3a = ( 0 -1 1 2 3 ).
Original vector v3b with range sorted by the
binary predicate mod_lesser is v3b = ( 0 -1 1 -2 -3 ).
Intersection of source ranges with default order,
vector v1mod = ( -1 0 1 ).
Intersection of source ranges with binary predicate greater specified,
vector v2mod = ( 1 0 -1 ).
Intersection of source ranges with binary predicate mod_lesser specified,
vector v3mod = ( 0 -1 1 2 3 ).
Configuration requise
En-tête : <algorithme>
Espace de noms : std