inplace_merge
Para ver el artículo en inglés, active la casilla Inglés. También puede ver el texto en inglés en una ventana emergente si pasa el puntero del mouse por el texto.
Traducción
Inglés

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

_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 de función de predicado definido por el usuario que define el sentido en el 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 false de lo contrario.

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;
}
          Vector original v1 con los subranges ordenados por
 predicado binario menos que v1 = (0 1 2 3 4 5 -5 -4 -3 -2 -1 0)
Vector original v2 con los subranges ordenados por
 el predicado binario mayor es v2 = (5 4 3 2 1 0 0 -1 -2 -3 -4 -5)
Vector original v3 con los subranges ordenados por
 el mod_lesser binario de predicado es v3 = (0 1 2 3 4 5 0 -1 -2 -3 -4 -5)
Combinado en el sitio con el orden predeterminado,
 vector v1mod = (-5 -4 -3 -2 -1 0 0 1 2 3 4 5)
Combinado en el sitio con mayor que haya especificado de predicado binario,
 vector v2mod = (5 4 3 2 1 0 0 -1 -2 -3 -4 -5)
Combinado en el sitio con el mod_lesser binario de predicado especificado,
 vector v3mod = (0 0 1 -1 2 -2 3 -3 4 -4 5 -5)

Requisitos

Encabezado: <algorithm>

Espacio de nombres: std

Mostrar:
© 2016 Microsoft