This page is a snapshot from the LWG issues list, see the Library Active Issues List for more information and the meaning of New status.

4492. std::generate and std::ranges::generate wording is unclear for parallel algorithms

Section: 26.7.7 [alg.generate] Status: New Submitter: Ruslan Arutyunyan Opened: 2025-12-12 Last modified: 2025-12-20

Priority: Not Prioritized

View all issues with New status.

Discussion:

std::generate and std::ranges::generate are confusing for parallel algorithms. For both of those Effects says "Assigns the result of successive evaluations of gen() through each iterator in the range [first, first + N)." The word "successive" is confusing when we talk about parallelism. This wording was the preexisting one; P3179 "Parallel Range Algorithms" didn't modify that, so the problem existed even before.

Another problem is that there is nothing about what is allowed to do with the Generator template parameter type for C++17 parallel generate. Intel, NVIDIA, and GNU libstdc++ implementations do multiple copies of Generator object to maximize parallelism, while it's not technically allowed if I am reading the standard correctly. But without Generator being copyable we have point of contention and extra synchronization (or we put synchronization part as users' responsibility, which is also not obvious).

There is no clear solution right away. We could try to fix the wording for both ranges and C++17 parallel generate but it seems like it requires extra effort because we need to at least verify the new behavior with LLVM libc++ implementation if we want to make Generator copyable; libc++ currently does not create per-thread copy of gen object. Perhaps, the best strategy for now is to remove ranges::generate and ranges::generate_n and return them back in C++29 time frame when we figure out the proper fix.

Proposed resolution:

This wording is relative to N5032.

  1. Modify 26.4 [algorithm.syn], header <algorithm> synopsis, as indicated:

    […]
// 26.7.7 [alg.generate], generate
template<class ForwardIterator, class Generator>
  constexpr void generate(ForwardIterator first, ForwardIterator last,
                          Generator gen);
template<class ExecutionPolicy, class ForwardIterator, class Generator>
  void generate(ExecutionPolicy&& exec,   // freestanding-deleted, see 26.3.5 [algorithms.parallel.overloads]
                ForwardIterator first, ForwardIterator last,
                Generator gen);
template<class OutputIterator, class Size, class Generator>
  constexpr OutputIterator generate_n(OutputIterator first, Size n, Generator gen);
template<class ExecutionPolicy, class ForwardIterator, class Size, class Generator>
  ForwardIterator generate_n(ExecutionPolicy&& exec,   // freestanding-deleted, see 26.3.5 [algorithms.parallel.overloads]
                             ForwardIterator first, Size n, Generator gen);
                             
namespace ranges {
  template<input_or_output_iterator O, sentinel_for<O> S, copy_constructible F>
    requires invocable<F&> & indirectly_writable<O, invoke_result_t<F&>>
    constexpr O generate(O first, S last, F gen);
  template<class R, copy_constructible F>
    requires invocable<F&> & output_range<R, invoke_result_t<F&>>
    constexpr borrowed_iterator_t<R> generate(R&& r, F gen);
  template<input_or_output_iterator O, copy_constructible F>
    requires invocable<F&> & indirectly_writable<O, invoke_result_t<F&>>
    constexpr O generate_n(O first, iter_difference_t<O> n, F gen);
  template<execution-policy Ep, random_access_iterator O, sized_sentinel_for<O> S,
           copy_constructible F>
    requires invocable<F&> & indirectly_writable<O, invoke_result_t<F&>>
    O generate(Ep&& exec, O first, S last, F gen); // freestanding-deleted
  template<execution-policy Ep, sized-random-access-range R, copy_constructible F>
    requires invocable<F&> & indirectly_writable<iterator_t<R>, invoke_result_t<F&>>
    borrowed_iterator_t<R> generate(Ep&& exec, R&& r, F gen); // freestanding-deleted
  template<execution-policy Ep, random_access_iterator O, copy_constructible F>
    requires invocable<F&> & indirectly_writable<O, invoke_result_t<F&>>
    O generate_n(Ep&& exec, O first, iter_difference_t<O> n, F gen); // freestanding-deleted
}
[…]

  2. Modify 26.7.7 [alg.generate] as indicated:

    template<class ForwardIterator, class Generator>
  constexpr void generate(ForwardIterator first, ForwardIterator last,
                          Generator gen);
template<class ExecutionPolicy, class ForwardIterator, class Generator>
  void generate(ExecutionPolicy&& exec,
                ForwardIterator first, ForwardIterator last,
                Generator gen);

template<class OutputIterator, class Size, class Generator>
  constexpr OutputIterator generate_n(OutputIterator first, Size n, Generator gen);
template<class ExecutionPolicy, class ForwardIterator, class Size, class Generator>
  ForwardIterator generate_n(ExecutionPolicy&& exec,
                             ForwardIterator first, Size n, Generator gen);
                             
template<input_or_output_iterator O, sentinel_for<O> S, copy_constructible F>
  requires invocable<F&> & indirectly_writable<O, invoke_result_t<F&>>
  constexpr O ranges::generate(O first, S last, F gen);
template<class R, copy_constructible F>
  requires invocable<F&> & output_range<R, invoke_result_t<F&>>
  constexpr borrowed_iterator_t<R> ranges::generate(R&& r, F gen);
template<input_or_output_iterator O, copy_constructible F>
  requires invocable<F&> & indirectly_writable<O, invoke_result_t<F&>>
  constexpr O ranges::generate_n(O first, iter_difference_t<O> n, F gen);
template<execution-policy Ep, random_access_iterator O, sized_sentinel_for<O> S,
         copy_constructible F>
  requires invocable<F&> & indirectly_writable<O, invoke_result_t<F&>>
  O ranges::generate(Ep&& exec, O first, S last, F gen);
template<execution-policy Ep, sized-random-access-range R, copy_constructible F>
  requires invocable<F&> & indirectly_writable<iterator_t<R>, invoke_result_t<F&>>
  borrowed_iterator_t<R> ranges::generate(Ep&& exec, R&& r, F gen);
template<execution-policy Ep, random_access_iterator O, copy_constructible F>
  requires invocable<F&> & indirectly_writable<O, invoke_result_t<F&>>
  O ranges::generate_n(Ep&& exec, O first, iter_difference_t<O> n, F gen);

    -1- Let N be max(0, n) for the generate_n algorithms, and last - first for the generate algorithms.

    […]