inplace_merge

Artikel
06/09/2015

Kombiniert die Elemente von zwei aufeinander sortierten Bereichen in einen einzelnen sortierten Bereich, in dem das Sortierkriterium möglicherweise durch ein binäres Prädikat angegeben wird.

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
   );

Parameter

_First
Ein bidirektionalem Iterator, der die Position des ersten Elements in der ersten von zwei aufeinander sortierten Bereichen wird kombiniert werden und einen einzelnen Bereich sortiert wurde.
_Middle
Ein bidirektionalem Iterator, der die Position des ersten Elements in der zweiten von zwei aufeinander sortierten Bereichen wird kombiniert werden und einen einzelnen Bereich sortiert wurde.
_Last
Ein bidirektionalem Iterator, der die Position eine hinter dem letzten Element in der zweiten von zwei aufeinander sortierten Bereichen wird kombiniert werden und einen einzelnen Bereich sortiert wurde.
_Comp
Benutzerdefiniertes Prädikatfunktionsobjekt, das den Sinn definiert, in dem ein Element größer als ein anderes ist. Das binäre Prädikat akzeptiert zwei Argumente und sollte true zurückgeben, wenn das erste Element, kleiner als das zweite Element ist, und andernfalls false.

Hinweise

Die sortierte nachfolgenden Bereichen, auf die verwiesen wird, müssen gültig sein; alle Zeiger müssen dereferenzierbar sein, und in jeder Sequenz, muss die letzte Position der ersten von Zunahme erreichbar sein.

Die sortierte nachfolgenden Bereichen müssen jedes während eine Vorbedingung der Verwendung des inplace_merge - Algorithmus mit derselben Reihenfolge angeordnet werden, z, den Algorithmus verwendet werden, um die kombinierte Bereiche zu sortieren ist. Der Vorgang ist stabil, da die relative Position der Elemente in jedem Bereich beibehalten wird. Wenn das passende Elemente in beiden Quellbereichen gibt, wird das erste Element der Bereich vor dem Element der zweiten kombinierten im Bereich.

Die Komplexität hängt vom verfügbaren Speicher ab, wenn der Algorithmus auf einen temporären Puffer belegt. Wenn genügend verfügbarer Arbeitsspeicher verfügbar ist, ist der beste Fall linear mit (_Last – _First) – 1-Vergleichen; wenn kein zusätzlicher Speicherplatz verfügbar ist, ist der schlimmste Fall N log*(N), wobei N = (_Last – _First*).

Beispiel

// 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;
}