inplace_merge
命令の条件にバイナリ述語によって指定される単一の並べ替えられた範囲に 2 個の連続する分類された範囲の要素を結合します。
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 個の連続する 2 番目の並べ替え対象範囲の最初の要素の位置を示す双方向反復子。_Last
単一のスコープに結合され、並べ替えられる 2 個の連続する 2 番目の並べ替えの範囲の最後の要素の一つ前の位置 1 に対処双方向反復子。_Comp
要素が他方の値より大きいか意味を定義するユーザー定義の述語関数オブジェクト。バイナリ述語は最初の要素と 2 個の引数を受け取り、別の方法で 2 番目の要素と false 未満の true を返す必要があります。
解説
並べ替えられた参照される連続した範囲は有効である必要があります; すべてのポインターが dereferenceable、各シーケンス内の最後の位置は incrementation によって最初から到達できる必要があります。
並べ替えられた連続した範囲は同じ順序変更するに従って結合された範囲の並べ替えにアルゴリズムによって使用されるのは、にそれぞれと inplace_merge アルゴリズムのアプリケーションへの事前条件配置する必要があります。操作は、各スコープ内の要素の相対位置ディレクティブが維持されるため、安定しています。両方のソース範囲内に対応する要素がある場合、要素は最初のスコープ直前の結合された範囲の 2 番目の要素です。
複雑度は、使用できるメモリの容量によってアルゴリズムが一時バッファーにメモリを割り当てると異なります。十分なメモリが使用できる場合、最適な場合は (_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;
}
必要条件
ヘッダー: <algorithm>
名前空間: std