question about Predicate

[cheneydeng]

I have a code as following:

#include <iostream>
#include <algorithm>
#include <list>
using namespace std;

//the class Nth is a predicates
class Nth{
    private:
         int nth;
         int count;
    public:
         Nth(int n):nth(n),count(0){}
         bool operator()(int){
             return ++count == nth;
        }
};

int main()
{
       list<int> lst;
 
       for(int i=1;i<10;i++)
           lst.push_back(i);

       copy(lst.begin(),lst.end(),ostream_iterator<int>(cout," "));
       cout<<endl;

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

       copy(lst.begin(),lst.end(),ostream_iterator<int>(cout," "));
       cout<<endl;
} 

the output is:
1 2 3 4 5 6 7 8 9
1 2 4 5 7 8 9
Not as I expect:
1 2 3 4 5 6 7 8 9
1 2 4 5 6 7 8 9
The book explained:
This happens because the usual implementation of the algorithm copies the predicate internally during the algorithm:

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

and it says it is possible to avoid this surprise behavior like this:

template<class ForwIter,class Predicate>
ForwIter std::remove_if(ForwIter beg,ForeIter end,Predicate op)
{
       while(beg != end && !op(*beg))
            beg++;
       if(pos == end)
            return beg;
       else{
            ForwIter next = beg;
            return remove_copy_if(++next,end,beg,op);
       }
}

I don't know what the difference between the two implementations is.I think i was able to understand the first one,but why the second one works fine?I thought they were the same.Any help will be appreciated.

[kbw]

I'd think the implementations are equivalent (btw if(pos == end) should be if(beg == end)).

The real problem is your predicate is counting the number of times it's called. A precondition of it working is that the algorithm that uses it must call it once per entry in the collection, which isn't quite right.

[jsmith]

The typical pattern for saving state is to use references:

struct Nth {
    Nth( int n, int& count ) : n( n ), count( count )
        { count = 0; }
    bool operator()( int ) const { return ++count == n; }
  private:
    int n;
    int& count;
};

int count;
Nth nth( 3, count );
list<int>::iterator pos = remove_if(lst.begin(),lst.end(), nth );
lst.erase(pos,lst.end());

However, there is already an algorithm called std::advance() in <iterator> which
would simplify this.

list<int>::iterator pos = lst.begin();
std::advance( pos, 3 );
lst.erase( pos );

It's really annoying that std::advance doesn't return the modified iterator, so I usually write a functional wrapper around it:

namespace my
{
    template< typename Iter >
    Iter advance( Iter i, size_t n )
    {
        std::advance( i, n );
       return i;
   }
}

lst.erase( my::advance( lst.begin(), 3 ) );