inplace_merge

Artikel
03/26/2013

Kombiniert die Elemente von zwei aufeinander sortierten Bereiche 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 bidirektionaler Iterator, der die Position des ersten Elements in der ersten von zwei aufeinander sortierten Bereichen behandelt kombiniert werden und in einen einzelnen Bereich sortiert wurden.
_Middle
Ein bidirektionaler Iterator, der die Position des ersten Elements in der zweiten von zwei aufeinander sortierten Bereichen behandelt kombiniert werden und in einen einzelnen Bereich sortiert wurden.
_Last
Ein bidirektionaler Iterator, der die Position eine hinter dem letzten Element in der zweiten von zwei aufeinander sortierten Bereichen behandelt kombiniert werden und in einen einzelnen Bereich sortiert wurden.
_Comp
Benutzerdefiniertes Prädikatfunktionsobjekt, dem dem Sinne definiert, in dem ein Element größer als andere.Das binäre Prädikat verwendet zwei Argumente und sollte true , wenn das erste Element kleiner als ist, das zweite Element und false andernfalls zurückgeben.

Hinweise

Die sortierten nachfolgenden Bereiche, auf die verwiesen wird, müssen gültig sein, alle Zeiger müssen dereferenzierbar sein und, innerhalb jeder Sequenz, muss die letzte Position von der ersten durch Zunahme erreichbar sein.

Die sortierten nachfolgenden Bereiche müssen jedes als Vorbedingung zur Verwendung des inplace_merge Algorithmus in Übereinstimmung mit der Reihenfolge angeordnet werden, wie, durch den Algorithmus verwendet werden, um das Sortieren der kombinierten Bereiche ist.Der Vorgang ist stabil, da die relative Reihenfolge der Elemente innerhalb eines Bereichs beibehalten wird.Wenn es entsprechende Elemente in beiden Quellbereichen gibt, wird das Element der ersten Bereichs vor dem Element der zweiten kombinierten im Bereich.

Die Komplexität hängt vom verfügbaren Arbeitsspeicher ab, wie der Algorithmus zu einem temporären Puffer gemeint ist.Wenn genügend verfügbarer Arbeitsspeicher verfügbar ist, ist der beste Fall mit linear (_Last - _First) - Vergleiche 1; Wenn kein zusätzlicher Arbeitsspeicher verfügbar ist, ist der schlimmste Fall N-Protokoll (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;
}