inplace_merge

아티클
03/27/2013

위치 정렬 기준을 이진 조건자에 지정 될 수 있습니다 단일 정렬 된 범위에 연속 된 두 개의 정렬 된 범위에서 요소를 결합 합니다.

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

매개 변수

_First
2 연속의 첫 번째 위치를 첫 번째 요소의 주소를 지정 하는 양방향 반복기 결합 하 고 단일 범위로 정렬 된 범위를 정렬 합니다.
_Middle
양방향 반복기를 첫 번째 요소의 위치에 두 번째 2 연속 주소 범위를 결합 하 고 단일 범위로 정렬 정렬.
_Last
양방향 반복기 위치 하나 마지막 요소에 두 번째 2 연속 주소 범위를 결합 하 고 단일 범위로 정렬 정렬.
_Comp
요소가 다른 보다 큰 하는 것이 정의 조건자 함수의 사용자 정의 개체입니다.이진 술 부 두 개의 인수를 사용 하 고 반환 해야 true 두 번째 요소의 첫 번째 요소인 미만 및 거짓 그렇지.

설명

참조 하는 정렬 된 연속 된 범위의 유효 해야 합니다. 모든 포인터는 dereferenceable 이어야 하 고 각 시퀀스에서 마지막 위치에서 첫 번째 접근할 수 여 증분 합니다.

정렬 된 연속 된 범위의 각 하려면 먼저 응용 프로그램의 정렬 해야는 inplace_merge 알고리즘으로 같은 순서에 따라 알고리즘에서 결합 된 범위를 정렬 하는 데 사용할 것입니다.각 범위 내에서 요소의 상대적 순서를 유지 작업 안정적입니다.두 원본 범위에 해당 하는 요소 때 첫 번째 범위에서 두 번째 요소의 결합 된 범위에서 앞에 요소가입니다.

알고리즘은 임시 버퍼에 메모리를 할당 하는 경우 복잡 한 사용 가능한 메모리에 따라 달라 집니다.충분 한 메모리가 있는 경우, 최상의 경우와 선형입니다 (_Last – _First)-1; 비교 보조 메모리가 있으면 최악의 경우 N 로그*(N)여기서 N = (_Last – _First*).

예제

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