Can functor provided to std::generate be stateful?

Question

Recently I read that some STL algorithms have undefined behaviour if the passed functor is stateful (has internal side-effects). I've used the std::generate function with a functor similar (less trivial) to the following:

class Gen
{
public:
    explicit Gen(int start = 0)
        : next(start)
    {
    }

    int operator() ()
    {
        return next++;
    }

private:
    int next;
};

Is this safe to use with std::generate? Is the order of generating values guaranteed?

Edit: Claim made here Stateful functors & STL : Undefined behaviour

Answer 1

Introduction

There's no problem using a stateful functor with functions such as std::generate, but one has to be careful not to run into issues where the underlying implementation makes a copy that will change the semantics of a program in a way that is different from what the developer have in mind.

25.1p10 Algorithms library - General [algorithms.general]

[ Note: Unless otherwise specified, algorithms that take function objects as arguments are permitted to copy those function obejcts freely. Programmers for whom object identity is imoprtant should consider using a wrapper class that points to a noncopied implementation object such as reference_wrapper, or some equivalent solution. -- end note ]

---

Order of assignment/evaluation

The standard explicitly states that exactly last - first (N) assignments and invocations of the generator will be made, but it doesn't state in what order. More can be read in the following Q&A:

• C++ standard wording: Does “through all iterators in the range” imply sequentiality?

---

Stateful functors + std::generate, unsafe?

Generally no, but there are a few caveats.

Within std::generate the standard guarantees that the same instance of the functor type will be invoked for every element in the given range, but as can be hinted by the declaration of std::generate we might run into issues where we forget that the passed functor invoked inside the function will be a copy of the one passed as argument.

See the below snippet where we declare a functor to generate "unique" ids:

#include <iostream>
#include <algorithm>

template<class id_type>
struct id_generator {
  id_type operator() () {
    return ++idx;
  }

  id_type next_id () const {
    return idx + 1;
  }

  id_type idx {};
};

int main () {
  id_generator<int> gen;

  std::vector<int>  vec1 (5);
  std::vector<int>  vec2 (5);

  std::generate (vec1.begin (), vec1.end (), gen);
  std::generate (vec2.begin (), vec2.end (), gen);

  std::cout << gen.next_id () << std::endl; // will print '1'
}

After running the above we might expect gen.next_id () to yield 11, since we have used it to generate 5 ids for vec1, and 5 ids for vec2.

This is not the case since upon invoking std::generate our instance of id_generator will be copied, and it is the copy that will be used inside the function.

---

What would be the solution?

There are several solutions to this problem, all of which prevents a copy from being made when you pass your functor to some algorithm function related to std::generated.

Alternative #1

The recommended solution is to wrap your functor in a std::reference_wrapper with the use of std::ref from <functional>. This will effectively copy the reference_wrapper, but the referred to instance of generate_id will stay the same.

std::generate (vec1.begin (), vec1.end (), std::ref (gen));
std::generate (vec2.begin (), vec2.end (), std::ref (gen));

std::cout << gen.next_id () << std::endl; // will print '11'

Alternative #2

You could, of course, also make your fingers stronger by writing something as confusing as the below:

std::generate<decltype(vec1.begin()), id_generator<int>&>(vec1.begin(), vec1.end(), gen);