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);

Answer 2

Almost every meaningful generator is stateful. Think about it: a generator invocation has no arguments. If the generator were stateless it would thus have to generate the same value every time. In other words, the only stateless generator is a constant generator:

template <typename T>
struct constant {
    constant(T&& value) : value{value} {}

    T const& operator ()() const { return value; }

private:
    T const value;
};

Or, alternatively, you could have a generator which has state external to the object itself, such as std::random_device. But these are really the only two applicable cases. This would be awfully restrictive. So yes – it is definitely possible to have a stateful generator.

The source for this statement that you refer to is not talking about generators – instead, it is talking about predicats, which are a different class of functions, and have different requirements (a predicate is a function with a single argument which returns a bool value).

Answer 3

As far as the standard is concerned, you have no guaranteed. An implementation can copy a functional object any time it wants. The idea is that an implementation could potentially divide the range into sub-ranges, and process each sub-range in a separate thread. (At least, this was what was claimed at one point in the standardization process.)

Globally, of course, for some algorithms, like generate or accumulate, allowing multiple copies or reordering would make the algorithm useless. Usually, such algorithms guarantee order; they seem to have forgotten generate in this. And while the standard does seem to have forgotten allowing copies, pratically, if order is guaranteed, there is no need for multiple copies in the processing, so I think we can safely assume that there aren't, even in the absense of a strict guarantee.