C++ STL question

[dophine]

Hi All,

I just read the book called "C++ coding stardards - 101 rules". And Found there is something I don't understand.

class FlagNth {
public:
  FlagNth( size_t n ) : current_(0), n_(n) {}

  // evaluate to true if and only if this is the n-th invocation
  template<typename T>
  bool operator()( const T& ) {return ++current_ == n_; }                  // bad: non-const

private:
  size_t current_, n_;
};

// … later …

v.erase( remove_if( v.begin(), v.end(), FlagNth(3) ) );

According to the book, it said "This is not guaranteed to remove the third element, even though that was intended. In most real-world STL implementations, it erases both the third and the sixth elements."

But since remove_if return a forward iterator pointing to the new end of the sequence, why the code above only can remove the third element?

thanks

[Narue]

According to the book, it said "This is not guaranteed to remove the third element, even though that was intended. In most real-world STL implementations, it erases both the third and the sixth elements."

Beware lack of context. Your quote is actually quite wrong when taken out of context, but the book is using that as an example for an implementation that implements remove_if in terms of find_if and remove_copy_if.

Perhaps it would help if I gave you an alternative implementation of remove_if that matches the description in your book:

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

using namespace std;

namespace jsw {
    template <typename FwdIt, typename Pred>
    FwdIt remove_if(FwdIt first, FwdIt last, Pred pred)
    {
        first = std::find_if(first, last, pred);

        if (first == last)
            return first;

        // operator+ is not defined for forward iterators,
        // so operator++ on a dummy is necessary
        FwdIt src = first;

        return std::remove_copy_if(++src, last, first, pred);
    }
}

class FlagNth {
public:
    FlagNth( size_t n ) : current_(0), n_(n) {}

    template<typename T>
    bool operator()( const T& ) {return ++current_ == n_; }
private:
    size_t current_, n_;
};

int main()
{
    int init[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
    vector<int> v(init, init + 10);

    copy(v.begin(), v.end(), ostream_iterator<int>(cout, " "));
    cout<<'\n';

    vector<int>::iterator end = v.erase(jsw::remove_if(v.begin(), v.end(), FlagNth(3)));

    copy(v.begin(), end, ostream_iterator<int>(cout, " "));
    cout<<'\n';
}

This example will fail as described because the predicate is being copied to both find_if and remove_copy_if. Each of their versions of n_ will be incremented independently. find_if will correctly find the third item, but the predicate it was given was a copy. The original predicate passed to remove_if still has an n_ of 0. This predicate is again copied to remove_copy_if, which in turn starts counting at 0 from the first item past the one returned by find_if. Thus remove_copy_if removes the sixth item as well.

You don't have control over how the standard library is implemented (unless you implement it yourself), so the FlagNth as written is a high risk design.

[dophine]

Thank you. I understand it now after giving the implementation of remove_if.