Гарантируется ли выполнение генерации последовательно?
мне сказали Вот тот:
Порядок генерации не гарантируется => в зависимости от реализации
Я посмотрел реализация GCC generate:
for (; __first != __last; ++__first)
*__first = __gen();
И Visual Studio реализует это идентично этому. Это облегчение для меня, как использование лямбда в generate это читает и пишет в захват, мог иметь недетерминированные результаты:
int foo[] = {1, 0, 13};
vector<int> bar(3);
generate(bar.begin(), bar.end(), [&]() {
static auto i = 0;
static auto total = 0;
total += foo[i];
return foo[i] / total;
});
Я жду bar содержать {1, 0, 0},
Если мне разрешат выполнить не по порядку, это может даже привести к ошибке деления на 0.
Так что я бы поспал легче, если бы на этот вопрос можно было ответить с доказательством того, что generate требуется выполнить последовательно.
Как примечание здесь, я знаю, что experimental::parallel::generate не будет последовательным Я просто спрашиваю о generate,
Решение
Я был заинтригован этим, поэтому сделал некоторые исследования.
Внизу этого ответа — копия соответствующего раздела стандарта от 2011 года.
Вы увидите из объявления шаблона std::generate<> что параметры итератора должны соответствовать концепции ForwardIterator а также OutputIterator соответственно.
ForwardIterator не поддерживает произвольный доступ. он может только читать или писать последовательно. OutputIterator еще более ограничительный — его operator* неявно включает в себя эффект operator++, Это явная особенность концепции.
Следовательно, подразумевается, что реализация этой функции должен обращаться к элементам последовательно (и, следовательно, генерировать значения последовательно), так как не делать этого нарушило бы контракт, неявный в интерфейсе.
Поэтому стандарт делает (неявно и тихо) гарантирует, что std::generate инициализируйте его элементы последовательно. Было бы невозможно написать правильно оформленную реализацию std::generate это не так.
QED
25.3.7. Создать [alg.generate]
template<class ForwardIterator, class Generator>
void generate(ForwardIterator first, ForwardIterator last,
Generator gen);
template<class OutputIterator, class Size, class Generator>
OutputIterator generate_n(OutputIterator first, Size n, Generator gen);
1 Эффекты: первый алгоритм вызывает объект функции gen и
присваивает возвращаемое значение gen всем итераторам в диапазоне
[первый Последний). Второй алгоритм вызывает объект функции gen и
присваивает возвращаемое значение gen всем итераторам в диапазоне
[first, first + n), если n положительно, иначе оно ничего не делает.2
Требуется: ген не имеет аргументов, размер должен быть преобразован в
интегральный тип (4.7, 12.3).3 Возвращает: generate_n возвращает первый + n для
неотрицательные значения n и сначала отрицательные значения.4 Сложность:
Точно последний — первый, n или 0 вызовов gen и назначений,
соответственно.
Другие решения
Вот все, что стандарт говорит об этом (25.7.3 / 1):
template<class ForwardIterator, class Generator>
void generate(ForwardIterator first, ForwardIterator last, Generator gen);
template<class OutputIterator, class Size, class Generator>
OutputIterator generate_n(OutputIterator first, Size n, Generator gen);
Первый алгоритм вызывает объект функции
поколения
и присваивает возвращаемое значение
поколения
через
все итераторы в диапазоне
[первый Последний)
, Второй алгоритм вызывает объект функции
поколения
и присваивает возвращаемое значение
поколения
через все итераторы в диапазоне
[сначала, сначала + n)
если
N
является
положительный, иначе ничего не делает.
Как видите, прямо не указано, что назначения итератора должны выполняться последовательно.