Un programa C++ STL que utiliza el functor como predicado

Question

En el siguiente programa STL de C++, defino un functor Nth y devuelve verdadero si es revocado en el enésimo tiempo. Y lo transformo en el algoritmo genérico remove_if, obtengo algo extraño.

El código:

#include <iostream> 
#include <list> 
#include <algorithm> 
#include "print.hpp" 

using namespace std; 

class Nth{ 
private: 
    int nth,ncount; 
public: 
    Nth(int n):nth(n),ncount(0){} 

    bool operator()(int) 
    { 
     return ++ncount == nth; 
    } 
}; 

int main() 
{ 
    list<int> col; 
    for (int i = 1;i <=9 ;++i) 
    { 
     col.push_back(i); 
    } 

    PRINT_ELEMENTS(col,"col : "); 

    list<int>::iterator pos; 
    pos = remove_if(col.begin(),col.end(), 
     Nth(3)); 

    col.erase(pos,col.end()); 

    PRINT_ELEMENTS(col,"nth removed : "); 
} 

print.hpp:

#include <iostream> 

template <class T> 
inline void PRINT_ELEMENTS (const T& coll, const char* optcstr="") 
{ 
    typename T::const_iterator pos; 

    std::cout << optcstr; 
    for (pos=coll.begin(); pos!=coll.end(); ++pos) { 
     std::cout << *pos << ' '; 
    } 
    std::cout << std::endl; 
} 

lo ejecuto en Microsoft Visual Studio 2008 y obtener el resultado: Elimina los elementos 3 y 6 que no es lo que quiero. Pensé que solo 3 serían eliminados. ¿Podría alguien interpretar para mí? Muchas gracias.

Answer 1

De La C++ biblioteca estándar: un tutorial y de referencia de Nicolai M. Josuttis

Esto sucede debido a que la aplicación habitual de las copias del algoritmo del predicado internamente durante el algoritmo:

template <class ForwIter, class Predicate> 
    ForwIter std::remove_if(ForwIter beg, ForwIter end, 
          Predicate op) 
    { 
     beg = find_if(beg, end, op); 
     if (beg == end) { 
      return beg; 
     } 
     else { 
     ForwIter next = beg; 
      return remove_copy_if(++next, end, beg, op); 
     } 
    } 

Los usos del algoritmo find_if() para encontrar el primer elemento que debe eliminarse. Sin embargo, luego usa una copia de la operación predicada pasada para procesar los elementos restantes, si los hay. Aquí, Nth en su estado original se usa nuevamente y también elimina el tercer elemento de los elementos restantes, que de hecho es el sexto elemento.

Este comportamiento no es un error. El estándar no especifica con qué frecuencia un predicado puede ser copiado internamente por un algoritmo. Por lo tanto, para obtener el comportamiento garantizado de la biblioteca estándar de C++, no debe pasar un objeto de función para el cual el comportamiento depende de la frecuencia con que se copie o llame. Por lo tanto, si llama a un predicado unario para dos argumentos y ambos argumentos son iguales, entonces el predicado siempre debe arrojar el mismo resultado. Es decir, un predicado no debe cambiar su estado debido a una llamada, y una copia de un predicado debe tener el mismo estado que el original. Para asegurarse de que no puede cambiar el estado de un predicado debido a una llamada de función, debe declarar operator() como función de miembro constante.

Answer 2

No utilice std::remove_if en un std::list. En su lugar, utilice la función de miembro de la lista:

col.remove_if(Nth(3)); 

El algoritmo genérico reordena los valores de los elementos para que pueda borrar de forma segura desde el final, pero para una lista, el algoritmo miembro elimina los no deseados nodos directamente sin tocar cualquier otro elemento.

Actualización. Como se señaló, esto no está garantizado para resolver su problema, ya que no se permite que su predicado tenga un estado interno de valor por valor. Tal vez puedas probar:

struct Nth 
{ 
    const int n; 
    int & counter; 
    Nth(int N, int & c) : n(N), counter(c) { } 
    bool operator()(int) const { return ++counter == N; } 
}; 

{ 
    int counter = 0; 
    cols.remove_if(Nth(3, counter)); 
} 

Este nuevo predicado es copiable y actúa como un contenedor de referencia alrededor de su variable de contador (externa).

Answer 3

leí el "La biblioteca estándar de C++", y encuentro otra solution.That es: re-implementar la función remove_if:

template <class ForwIter,class Predicate> 
ForwIter remove_if_re(ForwIter begin,ForwIter end,Predicate op) 
{ 
    while(begin != end && !op(*begin)) 
     ++begin; 
    if(begin == end) 
     return begin; 
    else{ 
     ForwIter next = begin; 
     return remove_copy_if(++next,end,begin,op); 
    } 
} 

No funciona.

Pero estoy un poco curioso. ¿Este implemento no usa una copia del operador pasado para procesar los elementos restantes?

Soy nuevo en aprender STL. Aprecio las respuestas de sus pacientes.

Muchas gracias.