Program C++ STL używający funktora jako predykatu

Question

W poniższym programie C++ STL definiuję funktor Nth i zwraca on wartość true, jeśli jest odwołana w n-tym czasie. I przekształcam ją w ogólny algorytm remove_if, otrzymuję coś dziwne.

Kod:

#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; 
} 

go uruchomić w programie Microsoft Visual Studio 2008 i uzyskać wynik: usuwa elementy 3 i 6, które nie chcę. Myślałem, że tylko 3 zostaną usunięte. Czy ktoś może mnie interpretować? Wielkie dzięki.

Answer 1

Od C++ Standard Library: A Tutorial i Reference Nicolai M. Josuttis

Dzieje się tak dlatego, że zwykle realizacja kopii algorytmu orzecznik wewnętrznie podczas algorytmu:

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

zastosowań algorytmu find_if(), aby znaleźć pierwszy element, który powinien zostać usunięty. Jednakże używa kopii przesłanego predykatu op do przetworzenia pozostałych elementów, jeśli takie istnieją. Tutaj N-ty w swoim pierwotnym stanie jest używane ponownie, a także usuwa trzeci element pozostałych elementów, który w rzeczywistości jest szóstym elementem.

To zachowanie nie jest błędem. Standard nie określa, jak często predykat może być kopiowany wewnętrznie przez algorytm. Zatem, aby uzyskać gwarantowane zachowanie standardowej biblioteki C++, nie należy przekazywać obiektu funkcji, którego zachowanie zależy od częstotliwości jego kopiowania lub wywoływania. Zatem jeśli wywołasz jednoargumentowy predykat dla dwóch argumentów i oba argumenty są równe, to predykat powinien zawsze dawać taki sam wynik. Oznacza to, że predykat nie powinien zmieniać swojego stanu z powodu wywołania, a kopia predykatu powinna mieć ten sam stan, co oryginał. Aby upewnić się, że nie można zmienić stanu predykatu z powodu wywołania funkcji, należy zadeklarować operator() jako stałą funkcję składową.

Answer 2

Nie używaj std::remove_if na std::list. Zamiast korzystać z listy w funkcji użytkownika:

col.remove_if(Nth(3)); 

Algorytm generic przestawia wartości elementów, dzięki czemu można bezpiecznie usunąć z końca, ale na liście, algorytm członkiem usuwa niechciane węzły bezpośrednio bez dotykania wszelkie inne elementy.

Aktualizacja. Jak już wspomniano, nie jest to faktycznie gwarantowane, aby rozwiązać twój problem, ponieważ twój predykat nie może mieć wewnętrznego stanu wartości. Spróbuj tego zamiast:

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

Ten nowy predykat jest dostępny do kopiowania i działa jako opakowanie referencyjne wokół zmiennej licznika (zewnętrznego).

Answer 3

czytam "The Standard C++ Library", a znajdę inny solution.That jest: ponowne wdrożenie remove_if funkcję:

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

To działa.

Ale jestem trochę ciekawy. Czy to narzędzie nie używa kopii przekazanego predykatu op do przetworzenia pozostałych elementów?

Jestem nowy, aby uczyć się STL. Będę wdzięczny za udzielenie odpowiedzi pacjentowi.

Wielkie dzięki.