merge
Combine tous les éléments de deux plages sources triées dans un intervalle unique et trié de destination, où le critère de classement peut être spécifié par un attribut binaire.
template<class InputIterator1, class InputIterator2, class OutputIterator>
OutputIterator merge(
InputIterator1 _First1,
InputIterator1 _Last1,
InputIterator2 _First2,
InputIterator2 _Last2,
OutputIterator _Result
);
template<class InputIterator1, class InputIterator2, class OutputIterator, class BinaryPredicate>
OutputIterator merge(
InputIterator1 _First1,
InputIterator1 _Last1,
InputIterator2 _First2,
InputIterator2 _Last2,
OutputIterator _Result
BinaryPredicate _Comp
);
Paramètres
_First1
Un itérateur d'entrée adressant la position du premier élément de la première des deux a trié des plages sources à combiner et être triées dans un intervalle unique._Last1
Un itérateur d'entrée adressant une position au delà de le dernier élément de la première des deux a trié des plages sources à combiner et être triées dans un intervalle unique._First2
Un itérateur d'entrée adressant la position du premier élément de la deuxième de deux plages sources triées consécutives à combiner et être triées dans un intervalle unique._Last2
Un itérateur d'entrée adressant une position au delà de le dernier élément dans la deuxième de deux plages sources triées consécutives à combiner et être triées dans un intervalle unique._Result
Un itérateur de sortie adressant la position du premier élément de la plage de destination où les deux plages sources doivent être combinées dans une plage trié unique._Comp
Objet défini par l'utilisateur de fonction de prédicat dans lequel définit le sens celles l'élément est supérieur à un autre.L'attribut binaire accepte deux arguments et doit retourner true lorsque le premier élément est moins que le deuxième élément et false sinon.
Valeur de retour
Un itérateur de sortie adressant une position au delà de le dernier élément dans la plage trié de destination.
Notes
Les plages sources triées référencés doivent être valides ; tous les pointeurs doivent être deréférençables et dans chaque séquence la dernière position doit être accessible dès le début par l'augmentation.
La plage de destination ne doit pas se chevaucher non plus de plages sources et doit être assez étendu pour contenir la plage de destination.
Les plages sources triées doivent toutes être organisées en tant qu'une condition préalable à l'application de l'algorithme de merge conformément à la même chose qui classe qui est utilisée par l'algorithme pour trier les plages combinés.
L'exécution est stable lorsque la commande relative d'éléments dans chaque plage est conservée dans la plage de destination.Les plages sources ne sont pas modifiées par l'algorithme merge.
Les types valeur des itérateurs d'entrée doivent être inférieur à comparable être ordonné, de sorte que, avec deux éléments, il puisse déterminer l'un ou l'autre qu'ils sont équivalents (dans le sens que ni l'un ni l'autre n'est inférieure à l'autre) ou qu'il est inférieure à l'autre.Cela provoque le classement entre les éléments d'inégalité.Lorsqu'il existe des é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.
La complexité de l'algorithme est linéaire avec au plus (_Last1 – _First1) (_Last2 – _First2) – les comparaisons 1.
La classe de liste fournit une fonction membre fusion pour fusionner les éléments de deux listes.
merge a deux formes associées :
Pour plus d'informations sur ces fonctions se comportent, consultez Itérateurs vérifiés.
Exemple
// alg_merge.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;
// Constructing vector v1a and v1b with default less than ordering
int i;
for ( i = 0 ; i <= 5 ; i++ )
v1a.push_back( i );
int ii;
for ( ii =-5 ; ii <= 0 ; 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 vector v2 with ranges sorted by greater
vector <int> v2a ( v1a ) , v2b ( v1b ) , v2 ( v1 );
vector <int>::iterator Iter2a, Iter2b, Iter2;
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 vector v3 with ranges sorted by mod_lesser
vector <int> v3a ( v1a ), v3b ( v1b ) , v3 ( v1 );
vector <int>::iterator Iter3a, Iter3b, Iter3;
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 merge inplace in ascending order with default binary
// predicate less <int> ( )
merge ( v1a.begin ( ) , v1a.end ( ) , v1b.begin ( ) , v1b.end ( ) , v1.begin ( ) );
cout << "Merged inplace with default order,\n vector v1mod = ( " ;
for ( Iter1 = v1.begin( ) ; Iter1 != v1.end( ) ; Iter1++ )
cout << *Iter1 << " ";
cout << ")." << endl;
// To merge inplace in descending order, specify binary
// predicate greater<int>( )
merge ( v2a.begin ( ) , v2a.end ( ) , v2b.begin ( ) , v2b.end ( ) ,
v2.begin ( ) , greater <int> ( ) );
cout << "Merged inplace with binary predicate greater specified,\n "
<< "vector v2mod = ( " ;
for ( Iter2 = v2.begin( ) ; Iter2 != v2.end( ) ; Iter2++ )
cout << *Iter2 << " ";
cout << ")." << endl;
// Applying A user-defined (UD) binary predicate mod_lesser
merge ( v3a.begin ( ) , v3a.end ( ) , v3b.begin ( ) , v3b.end ( ) ,
v3.begin ( ) , mod_lesser );
cout << "Merged inplace with binary predicate mod_lesser specified,\n "
<< "vector v3mod = ( " ; ;
for ( Iter3 = v3.begin( ) ; Iter3 != v3.end( ) ; Iter3++ )
cout << *Iter3 << " ";
cout << ")." << endl;
}
Sortie
Original vector v1a with range sorted by the
binary predicate less than is v1a = ( 0 1 2 3 4 5 ).
Original vector v1b with range sorted by the
binary predicate less than is v1b = ( -5 -4 -3 -2 -1 0 ).
Original vector v2a with range sorted by the
binary predicate greater is v2a = ( 5 4 3 2 1 0 ).
Original vector v2b with range sorted by the
binary predicate greater is v2b = ( 0 -1 -2 -3 -4 -5 ).
Original vector v3a with range sorted by the
binary predicate mod_lesser is v3a = ( 0 1 2 3 4 5 ).
Original vector v3b with range sorted by the
binary predicate mod_lesser is v3b = ( 0 -1 -2 -3 -4 -5 ).
Merged inplace with default order,
vector v1mod = ( -5 -4 -3 -2 -1 0 0 1 2 3 4 5 ).
Merged inplace with binary predicate greater specified,
vector v2mod = ( 5 4 3 2 1 0 0 -1 -2 -3 -4 -5 ).
Merged inplace with binary predicate mod_lesser specified,
vector v3mod = ( 0 0 1 -1 2 -2 3 -3 4 -4 5 -5 ).
Configuration requise
en-tête : <algorithm>
l'espace de noms : DST