inplace_merge

Article
06/09/2015

Associe les éléments de plusieurs plages triées consécutives dans une seule plage triée, où le respect du classement peut être spécifié par un attribut binaire.

template<class BidirectionalIterator>
   void inplace_merge(
      BidirectionalIterator _First, 
      BidirectionalIterator _Middle,
      BidirectionalIterator _Last
   );
template<class BidirectionalIterator, class Predicate>
   void inplace_merge(
      BidirectionalIterator _First, 
      BidirectionalIterator _Middle,
      BidirectionalIterator _Last,
      Predicate _Comp
   );

Paramètres

_First
Un itérateur bidirectionnelle adressage la position du premier élément de la première de plusieurs plages triées consécutives à la combinaison et être triées dans une seule plage.
_Middle
Un itérateur bidirectionnelle adressage la position du premier élément dans la seconde de plusieurs plages triées consécutives à la combinaison et être triées dans une seule plage.
_Last
Un itérateur bidirectionnelle adressage la position une après le dernier élément de la seconde de plusieurs plages triées consécutives à la combinaison et être triées dans une seule plage.
_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.

Notes

Les plages consécutives 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 la collection contenue par l'augmentation.

Les plages consécutives triées doivent tous être organisées comme une condition préalable à l'application de l'algorithme d'inplace_merge conformément à la même classe qui n'est pas être 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é. En présence de éléments équivalents dans les deux plages sources, l'élément est la première plage précède l'élément du deuxième dans la plage associée.

La complexité dépend de la mémoire disponible lorsque l'algorithme alloue la mémoire dans une mémoire tampon temporaire. Si suffisamment de mémoire est disponible, le meilleur cas un-à-un avec (_Last – _First) – 1 les comparaisons ; si aucune stockage de sauvegarde n'est disponible, le pire cas est N log*(N), où N = (_Last – _First*).

Exemple

// alg_inplace_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> v1;
   vector <int>::iterator Iter1, Iter2, Iter3;

   // Constructing vector v1 with default less-than ordering
   int i;
   for ( i = 0 ; i <= 5 ; i++ )
   {
      v1.push_back( i );
   }

   int ii;
   for ( ii =-5 ; ii <= 0 ; ii++ )
   {
      v1.push_back(  ii  );
   }

   cout << "Original vector v1 with subranges sorted by the\n "
        <<  "binary predicate less than is  v1 = ( " ;
   for ( Iter1 = v1.begin( ) ; Iter1 != v1.end( ) ; Iter1++ )
      cout << *Iter1 << " ";
   cout << ")" << endl;
   
   // Constructing vector v2 with ranges sorted by greater
   vector <int> v2 ( v1 );
   vector <int>::iterator break2;
   break2 = find ( v2.begin ( ) , v2.end ( ) , -5 );
   sort ( v2.begin ( ) , break2 , greater<int> ( ) );
   sort ( break2 , v2.end ( ) , greater<int> ( ) );
   cout << "Original vector v2 with subranges sorted by the\n "
        << "binary predicate greater is v2 = ( " ;
   for ( Iter2 = v2.begin( ) ; Iter2 != v2.end( ) ; Iter2++ )
      cout << *Iter2 << " ";
   cout << ")" << endl;

   // Constructing vector v3 with ranges sorted by mod_lesser
   vector <int> v3 ( v1 );
   vector <int>::iterator break3;
   break3 = find ( v3.begin ( ) , v3.end ( ) , -5 );
   sort ( v3.begin ( ) , break3 , mod_lesser );
   sort ( break3 , v3.end ( ) , mod_lesser );
   cout << "Original vector v3 with subranges sorted by the\n "
        << "binary predicate mod_lesser is v3 = ( " ;
   for ( Iter3 = v3.begin( ) ; Iter3 != v3.end( ) ; Iter3++ )
      cout << *Iter3 << " ";
   cout << ")" << endl;

   vector <int>::iterator break1;
   break1 = find (v1.begin ( ) , v1.end ( ) , -5 );
   inplace_merge ( v1.begin( ), break1, v1.end( ) );
   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>( )
   inplace_merge ( v2.begin( ), break2 , v2.end( ) , 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
   inplace_merge ( v3.begin( ), break3, v3.end( ), 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;
}