inplace_merge

Article
03/26/2013

Combine les éléments de deux plages triés consécutifs dans une plage trié unique, où le critère de 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 bidirectionnel adressant la position du premier élément de la première des deux plages triés consécutifs à combiner et être triées dans un intervalle unique.
_Middle
Un itérateur bidirectionnel adressant la position du premier élément de la deuxième de deux plages triés consécutifs à combiner et être triées dans un intervalle unique.
_Last
Un itérateur bidirectionnel adressant une position au delà de le dernier élément dans la deuxième de deux plages triés consécutifs à combiner et être triées dans un intervalle 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.

Notes

Les plages consécutifs sont 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.

Les plages consécutifs triés doivent toutes être réorganisés en tant qu'une condition préalable à l'application de l'algorithme d' inplace_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.Lorsqu'il existe des é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 combiné.

La complexité dépend de la mémoire disponible lorsque l'algorithme alloue de la mémoire vers une mémoire tampon temporaire.Si la mémoire suffisante est disponible, le meilleur cas est linéaire avec (_Last – _First) – les comparaisons 1 ; si aucune mémoire auxiliaire n'est disponible, le pire des cas est le journal N (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;
}