Stateful functors & STL : Undefined behaviour

Question

I am following this Function objects tutorial

Copy-pasta below:

I am unable to understand the following:

Predicates should always be implemented as stateless function objects to avoid unexpected results. There is no guarantee how often an algorithm might internally copy the predicate. Thus, having predicates that are implemented as stateful function objects might have unexecpted results.

The example is as follows:

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

class predicate
{
public:
   predicate(int condition) :
      condition_(condition), state_(0) {}
   bool operator()(int) { return ++state_ == condition_; }

private:
   int condition_;
   int state_;
};

int main()
{
   std::vector<int> vec;
   vec.push_back(1);
   vec.push_back(2);
   vec.push_back(3);
   vec.push_back(4);
   vec.push_back(5);

   predicate p(2);
   std::vector<int>::iterator pos =
      std::remove_if(vec.begin(), vec.end(), p);
   vec.erase(pos, v.end());

   std::copy(vec.begin(), vec.end(),
             std::ostream_iterator<int>(std::cout, " "));

   return 0;
}

If I understand (read) it correctly , it is attempting to remove the element marked as 2 in the vector. remove_if algorithm returns a new end of the container and attempting to erase all of it.

Output :

1 3 5

Clearly, not only the second element has been removed but also the fourth one. The answer to this curiosity is simply that the used algorithm 'remove_if' internally copies the predicate during its execution. And this internal copy creates a new predicate object containing its original state.

Though I can read what seems to be happening, I am unable to picture what is happening behind the scenes which actually marked even the 4th element to be moved to the end of the container. Does this have to do with an algorithm being single pass or multiple pass? ( also I would be grateful if some one could point me in the right direction how to deduce the same)

On a side note , if i comment the erase & note the output.

1 3 5 4 5

What causes the container to get corrupted ?

Answer 1

The meaning of that quote should be taken at face value. For the majority of the STL algorithms, you should not implement your predicate functor such that it has observable state (AKA "side effects"), because:

• the iteration order over the container is not defined,
• the algorithm is free to make copies of the functor,
• the algorithm may depend on statelessness in order to not corrupt the container contents or crash.

The simplest way to enforce this upon yourself is to define operator() as const.

There are exceptions, such as for_each, for which none of the above apply. You are free to use stateful functors here. For more info, see this excellent article: http://drdobbs.com/cpp/184403769.

Behind the scenes, the authors of your STL implementation are free to write the remove_if (and other algorithms) any way they like, so long as it conforms to the requirements laid down by the standard. There's no real reason to worry too much about exactly why you're getting the behaviour you're seeing, beyond acknowledging that it's undefined. If you want to know the specifics, I would just take a look at the code for remove_if in the STL implementation that you're using.

As for your side-note; this is not "corruption", it's simply an artifact of how remove_if works (this would occur even for a valid predicate). The only requirement is that all the elements to the left of pos are valid (because they are to be retained). There are no requirements on what elements exist from pos onward (see here). (Chapter 32 of "Effective STL" by Scott Meyers has a good explanation of why remove_if (and so on) behave like this).