c++ - plantillas - ¿por qué std:: remove_copy_if() realmente elimina?

stack c++ stl

Question

¿Podría ser esta la peor función nombrada en la STL? (pregunta retórica)

std :: remove_copy_if () en realidad no parece hacer ninguna eliminación . Lo mejor que puedo decir, se comporta más como copy_if_not.

La negación es un poco confusa, pero puede solucionarse con std :: not1 (), sin embargo, podría estar malinterpretando algo, ya que no puedo entender qué tiene que ver esta función con la eliminación. ¿Me estoy perdiendo algo?

De no ser así, ¿existe un algoritmo STL para eliminar (mover) elementos condicionantes de un contenedor y colocarlos en otro contenedor?

Edición para agregar un ejemplo para que los lectores estén menos confundidos.

El siguiente programa parece dejar el rango de entrada (V1) sin tocar:

#include <vector>
#include <iostream>
#include <algorithm>
#include <iterator>

using std::cout;
using std::endl;

int main (void)
{
    std::vector<int> V1, V2;
    V1.push_back(-2);
    V1.push_back(0);
    V1.push_back(-1);
    V1.push_back(0);
    V1.push_back(1);
    V1.push_back(2);

    std::copy(V1.begin(), V1.end(), std::ostream_iterator<int>(cout, " "));
    cout << endl;

    std::remove_copy_if(
        V1.begin(),
        V1.end(),
        std::back_inserter(V2),
        std::bind2nd(std::less<int>(), 0));

    std::copy(V2.begin(), V2.end(), std::ostream_iterator<int>(cout, " "));
    cout << endl;
    std::copy(V1.begin(), V1.end(), std::ostream_iterator<int>(cout, " "));
    cout << endl;
}

Produce:

-2 0 -1 0 1 2 
0 0 1 2 
-2 0 -1 0 1 2 

Esperaba ver algo como:

-2 0 -1 0 1 2 
0 0 1 2 
0 0 1 2 ? ? ?

Dónde ? Podría ser cualquier valor. Pero me sorprendió ver que el rango de entrada estaba intacto y que el valor de retorno no se puede utilizar con (en este caso) std :: vector :: erase (). (El valor de retorno es un iterador de salida .)

Answer 1

¿Existe un algoritmo STL para eliminar (mover) condicionalmente elementos de un contenedor y colocarlos en otro contenedor?

Lo más cercano que puedo pensar es std::stable_partition :

std::vector<int> v;
// ...
auto it = std::stable_partition(v.begin(), v.end(), pick_the_good_elements);
std::vector<int> w(std::make_move_iter(it), std::make_move_iter(v.end()));
v.erase(it, v.end());

Ahora v contendrá los elementos "buenos", y w contendrá los elementos "malos".

Answer 2

¿Podría ser esta la peor función nombrada en la STL?

Un poco de información de fondo: en la biblioteca estándar (o el STL original), hay tres conceptos, los contenedores, los iteradores en esos contenedores y los algoritmos que se aplican a los iteradores. Los iteradores sirven como cursor y elemento de acceso a los elementos de un rango pero no tienen una referencia al contenedor (como se mencionó anteriormente, es posible que ni siquiera haya un contenedor subyacente).

Esta separación tiene la buena característica de que puede aplicar algoritmos a rangos de elementos que no pertenecen a un contenedor (considere adaptadores de iteradores como std::istream_iterator o std::ostream_iterator ) o que, al pertenecer a un contenedor no considere todos los elementos ( std::sort( v.begin(), v.begin()+v.size()/2 ) para acortar la primera mitad del contenedor).

El lado negativo es que, como el algoritmo (y el iterador) no conocen realmente el contenedor, no pueden modificarlo realmente, solo pueden modificar los elementos almacenados (que es a lo que pueden acceder). Los algoritmos de mutación, como std::remove o std::remove_if funcionan sobre esta premisa: sobrescriben los elementos que no coinciden con la condición al eliminarlos del contenedor, pero no modifican el contenedor, solo los valores contenidos, es decir hasta la persona que llama en un segundo paso del lenguaje borrado-eliminar :

v.erase( std::remove_if( v.begin(), v.end(), pred ),
         v.end() );

Además, para los algoritmos de mutación (aquellos que realizan cambios), como std::remove existe una versión que no muta al agregar una copy al nombre: std::remove_copy_if . No se considera que ninguno de los algoritmos XXXcopyYYY cambie la secuencia de entrada (aunque puede XXXcopyYYY si usa iteradores de alias).

Si bien esto realmente no es una excusa para nombrar std::remove_copy_if , espero que ayude a entender lo que hace un algoritmo dado su nombre: remove_if modificará el contenido del rango y proporcionará un rango para el cual todos los elementos que coinciden con el predicado han sido eliminado (el rango devuelto es el formado por el primer argumento del algoritmo al iterador devuelto). std::remove_copy_if hace lo mismo, pero en lugar de modificar la secuencia subyacente, crea una copia de la secuencia en la que se eliminaron los elementos que coinciden con el predicado. Es decir, todos los algoritmos * copy * son equivalentes a copiar y luego aplicar el algoritmo original (tenga en cuenta que la equivalencia es lógica, std::remove_copy_if solo requiere un OutputIterator , lo que significa que posiblemente no podría copiar y luego recorrer el rango copiado aplicando std::remove_if .

La misma línea de razonamiento se puede aplicar a otros algoritmos de mutación: invierte los valores (recuerda, los iteradores no acceden al contenedor) en el rango, reverse_copy copia los elementos en el rango en un rango separado en el orden inverso.

De no ser así, ¿existe un algoritmo STL para eliminar (mover) elementos condicionantes de un contenedor y colocarlos en otro contenedor?

No hay tal algoritmo en el STL, pero podría ser fácilmente implementable:

template <typename FIterator, typename OIterator, typename Pred>
FIterator splice_if( FIterator first, FIterator last, OIterator out, Pred p )
{
   FIterator result = first;
   for ( ; first != last; ++first ) {
      if ( p( *first ) ) {
         *result++ = *first;
      } else {
         *out++ = *first;
      }
   }
   return result;
}

Answer 3

De no ser así, ¿existe un algoritmo STL para eliminar (mover) elementos condicionantes de un contenedor y colocarlos en otro contenedor?

Realmente no. La idea es que los algoritmos de modificación puedan "mover" (no en el sentido de C ++ de la palabra) los elementos en un contenedor, pero no pueden cambiar la longitud del contenedor. Por lo tanto, los algoritmos de remove podrían llamarse prepare_for_removal .

Por cierto, C ++ 11 proporciona std::copy_if , que te permite copiar elementos seleccionados de un contenedor a otro sin jugar juegos de lógica divertidos con remove_copy_if .

Answer 4

Estoy de acuerdo en que remove no es el mejor nombre para esta familia de funciones.

Pero como dijo Luc, hay una razón para que funcione como lo hace, y el artículo de GoTW que menciona explica cómo funciona. remove_if funciona exactamente de la misma forma que remove, que es lo que usted esperaría.

Quizás también quieras leer este artículo de Wikilibros .

Answer 5

Tienes razón, eso es lo que hace ... std :: remove_copy_if copia el vector, eliminando todo lo que coincida con el pred.

std :: remove_if ... elimina en condición (o mejor dicho, baraja las cosas).