Стандартная формулировка на С++: означает ли "через все итераторы в диапазоне" последовательность?

Этот вопрос был вызван обсуждением std::generate и гарантий, сделанных стандартом. В частности, можете ли вы использовать функциональные объекты с внутренним состоянием и полагаться на generate(it1, it2, gen) на вызов gen(), сохранить результат в *it, снова вызвать gen(), сохранить в *(it + 1) и т.д. Или начать с назад, например?

В стандарте (n3337, §25.3.7/1) сказано следующее:

Эффекты: первый алгоритм вызывает объект функции gen и назначает возвращаемое значение gen через все итераторы в диапазоне [first,last). Второй алгоритм вызывает объект функции gen и присваивает возвращаемое значение gen через все итераторы в диапазоне [first,first + n), если n положителен, иначе он ничего не делает.

Кажется, что никакое упорядочение не гарантируется, тем более что другие абзацы имеют более сильную формулировку, например std::for_each (Эффекты: Применяет f к результату разыменования каждого итератора в диапазоне [first,last), начиная с первого и последующих до last - 1. Если мы возьмем это буквально, это только гарантирует начало в first и заканчивается на last, хотя - никаких гарантий при заказе между ними).

Но: Оба Microsoft и Стандартная библиотека Apache С++ дают примеры на своих страницах документации, которые требуют, чтобы оценка была последовательной. И как libС++ (в algorithm), так и libstdС++ (в bits/stl_algo.h) реализуют его таким образом. Кроме того, вы потеряете много потенциальных приложений для generate без этой гарантии.

Имеет ли нынешняя формулировка последовательность? Если нет, это был надзор со стороны членов комитета или намеренный?

(Я хорошо знаю, что не так много людей, которые могут дать проницательные ответы на этот вопрос, просто не спекулируя или обсуждая, но, по моему скромному мнению, это не делает этот вопрос "не конструктивным" в соответствии с рекомендациями SO. )

Спасибо @juanchopanza за то, что он указал на эту проблему и передал мне параграф о for_each.

Ответ 1

В обсуждении LWG475, std::for_each сравнивается с std::transform. Он отметил, что "transform не гарантирует порядок, в котором его объект функции называется". Итак, да, комитет осознает отсутствие последовательных гарантий в стандарте.

Не существует противоположного требования к несекретному поведению, поэтому Microsoft и Apache могут использовать последовательную оценку.

Ответ 2

В любом случае в стандарте не указывается порядок в алгоритме, вы должны предположить, что реализация может использовать это для parallelism. В документе n3408 обсуждаются варианты для параллелизации и указывает на Thrust, которая является одновременно используемой параллельной поддержкой повторной реализации стандартных алгоритмов и доказательством концепции для будущей стандартизации parallelism в алгоритмах.

Глядя на реализацию Thrust generate, он вызывает gen в параллельном цикле всякий раз, когда категория итератора является произвольным доступом. Как вы заметили, это соответствует стандарту, поэтому вы не должны предполагать, что generate всегда будет последовательным. (Например, поточно-безопасный std::rand можно эффективно использовать с generate и не требует последовательного вызова.)

Единственными алгоритмами, гарантирующими последовательный вызов, являются те, что указаны в numeric; если ваш код зависит от последовательного вызова, вы должны использовать iota вместо generate. Адаптация существующего генератора:

template<typename F> struct iota_adapter {
   F f;
   operator typename std::result_of<F()>::type() { return f(); }
   void operator++() {}
};
template<typename F> iota_adapter<F> iota_adapt(F &&f) { return {f}; }

Использовать как:

#include <numeric>
#include <iostream>

int main() {
   int v[5], i = 0;
   std::iota(std::begin(v), std::end(v), iota_adapt([&i]() { return ++i; }));
   for (auto i: v) std::cout << i << '\n';
}