remove_if based on vector index with a functor

Question

This question showed how to use erase/remove_if based on vector indices using a function predicate. This works well the first time the function is called but because the local static variable maintains state, on the next call to a different vector I'd be out of luck. So I thought I could use a functor with a private variable that would be re-usable. It mostly works except for the first element. There's something specific to the way remove_if uses the functor that messes up initialization of the private variable

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

using namespace std;

class is_IndexEven_Functor {
public:
  is_IndexEven_Functor() : k(0) {}

  bool operator()(const int &i) {
    cout << "DEBUG: isIndexEvenFunctor: k " << k << "\ti " << i << endl; ////

    if(k++ % 2 == 0) {
      return true;
    } else {
      return false;
    }
  }
private:
  int k;
};

int main() {

  is_IndexEven_Functor a;
  a(0);
  a(1);
  a(2);
  a(3);

  vector<int> v;
  v.push_back(0);
  v.push_back(1);
  v.push_back(2);
  v.push_back(3);

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

  is_IndexEven_Functor b;
  v.erase( remove_if(v.begin(), v.end(), b), v.end() );

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

  return 0;
}

Here's the output:

DEBUG: isIndexEvenFunctor: k 0  i 0
DEBUG: isIndexEvenFunctor: k 1  i 1
DEBUG: isIndexEvenFunctor: k 2  i 2
DEBUG: isIndexEvenFunctor: k 3  i 3

Before
0 1 2 3 

DEBUG: isIndexEvenFunctor: k 0  i 0
DEBUG: isIndexEvenFunctor: k 0  i 1  // why is k == 0 here ???
DEBUG: isIndexEvenFunctor: k 1  i 2
DEBUG: isIndexEvenFunctor: k 2  i 3

After
2

The crux of the question is why is the value of k equal to 0 on the second call to the functor (and how do I fix it)? I'm guessing this has something to do with remove_if using it as temporary object or something but I don't really understand what that means.

EDIT: it would be great if I could avoid c++11

Vaughn Cato · Accepted Answer · 2015-12-24T21:29:48.967

6

Yes, the implementation is allowed to copy the function, so you can get confusing behavior if the functional has mutable state. There are a couple of ways to work around this. The easiest is probably to use a std::reference_wrapper, which can be created using the std::ref function:

is_IndexEven_Functor b;
v.erase( remove_if(v.begin(), v.end(), std::ref(b)), v.end() );

Now, instead of making a copy of the function object, the implementation copies a wrapper, so there is only one instance of the original function object.

Another option is to keep the index separate from the function:

class is_IndexEven_Functor {
public:
    is_IndexEven_Functor(int &index) : k(index) {}

    .
    .
    .
private:
    int &k;
};

and use it like this:

int index = 0;
is_IndexEven_Functor b(index);
v.erase( remove_if(v.begin(), v.end(), b), v.end() );

edited Dec 24 '15 at 21:29

answered Dec 24 '15 at 19:21

Vaughn Cato

63,448
5
82
132

Thanks, this works great with c++11. Is there workaround for c++03? – confusedCoder Dec 24 '15 at 21:25
@confusedCoder: I've added an example. – Vaughn Cato Dec 24 '15 at 21:31
@confusedCoder: You can also make your own `reference_wrapper` pretty easily. – Vaughn Cato Dec 24 '15 at 21:34

score 4 · Answer 2 · answered Dec 24 '15 at 19:21

Generally, functors with state are not so great for STL algorithms, as they do not guarantee anything about the handling of functor. For all it cares, it could create a new copy of the functor (from the original!) for every iteration to perform checks. STL assumes functors are stateless.

To overcome this, you should use references to state inside your functors (in your case, have your k a reference to int, which is initialized before) or pass functors themselves in reference wrappers. To answer particular question (that is, what's happening in the remove_if), let's take a look into the implementation (one of implementations, of course):

 __remove_if(_ForwardIterator __first, _ForwardIterator __last,
                _Predicate __pred)
    {
      __first = std::__find_if(__first, __last, __pred);
      if (__first == __last)
        return __first;
      _ForwardIterator __result = __first;
      ++__first;
      for (; __first != __last; ++__first)
        if (!__pred(__first))
          {
            *__result = _GLIBCXX_MOVE(*__first);
            ++__result;
          }
      return __result;
    }

As you see, it is using a COPY of a predicate for find_if, and than continues with original predicate from found position - but original knows nothing about new position, reflected in the copy.

remove_if based on vector index with a functor

2 Answers2