inplace_merge
Combina los elementos de dos intervalos ordenados consecutivos en un único intervalo ordenados, donde el criterio de ordenación se puede especificar por un predicado binario.
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
);
Parámetros
_First
Un iterador bidireccional que dirige la posición del primer elemento de la primera de dos intervalos ordenados consecutivos que combinarse y en un único intervalo._Middle
Un iterador bidireccional que dirige la posición del primer elemento de la segunda de dos intervalos ordenados consecutivos que combinarse y en un único intervalo._Last
Un iterador bidireccional que dirige la posición una más allá del último elemento de la segunda de dos intervalos ordenados consecutivos que combinarse y en un único intervalo._Comp
Objeto definido por el usuario de la función de predicado en el que define el sentido que un elemento es mayor que otro.El predicado binario toma dos argumentos y debe devolver TRUE cuando el primer elemento es menor que el segundo elemento y Falso de otra manera.
Comentarios
Intervalos consecutivos ordenados hace referencia deben ser válidos; todos los punteros deben ser dereferenceable y, dentro de cada secuencia, la posición última debe ser accesible de primera por el aumento.
Intervalos consecutivos ordenados deben cada organizar mientras una condición previa a la aplicación del algoritmo de inplace_merge de acuerdo con el mismo de ordenación que es utilizar el algoritmo para ordenar los intervalos combinados.La operación es estable como el orden relativo de elementos dentro de cada intervalo se conserva.Cuando hay elementos equivalentes en ambos intervalos de origen, el elemento es el primer rango precede al elemento del segundo en el intervalo combinado.
La complejidad depende de la memoria disponible mientras el algoritmo asigna memoria a un búfer temporal.Si suficiente memoria disponible, el mejor caso es lineal con (_Last – _First) las comparaciones 1; si no hay memoria auxiliar disponibles, el peor caso es el registro n (N), donde n = (_Last – _First).
Ejemplo
// 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;
}
Requisitos
encabezado: <algoritmo>
espacio de nombres: std