std::seed_seq::generate

template< class RandomIt >
void generate( RandomIt begin, RandomIt end );

(начиная с C++11)

Генерирует непредвзятые начальные значения, заполняя выходной диапазон [begin, end) 32-разрядными беззнаковыми целыми значениями на основе (возможно, смещённых) начальных значений, хранящихся в v.

Если begin == end равен true, ничего не делает.
В противном случае генерирует начальные значения с помощью описанного ниже алгоритма генерации.

Если std::iterator_traits<RandomIt>::value_type не является беззнаковым целочисленным типом или его разрядность меньше 32, программа некорректно сформирована.

Если RandomIt не соответствует требованиям LegacyRandomAccessIterator или не является изменяемым, поведение не определено.

Алгоритм генерации

Заданы следующие значения и операции:

Значение	Определение
`z`	`v .size()`
`n`	`end - begin`
`m`	`std::max(z + 1, n)`
`t`	`(n >= 623) ? 11 : (n >= 68) ? 7 : (n >= 39) ? 5 : (n >= 7) ? 3 : (n - 1) / 2`
`p`	`(n - t) / 2`
`q`	`p + t`
Операция	Определение
\(\scriptsize \mathsf{xor} \)xor	встроенная операция побитового исключающего ИЛИ
\(\scriptsize \mathsf{rshift} \)rshift	встроенная операция побитового сдвига вправо
\(\scriptsize T(x) \)T(x)	\(\scriptsize x\ \mathsf{xor}\ (x\ \mathsf{rshift}\ 27) \)x xor (x rshift 27)

Алгоритм генерации состоит из следующих шагов, где \(\scriptsize S_i \)S_i обозначает begin[i % n], а \(\scriptsize V_i \)V_i обозначает v [i]:

1) Установить каждый элемент выходного диапазона в значение 0x8b8b8b8b.

2) Для каждого целого числа k в [0, m) выполнить следующие операции по порядку:

1) Пусть \(\scriptsize r_1 \)r₁ равно \(\scriptsize 1664525 \cdot T(S_k\ \mathsf{xor}\ S_{k+p}\ \mathsf{xor}\ S_{k-1}) \)1664525·T(S_k xor S_k+p xor S_k-1).

2) Пусть \(\scriptsize r_2 \)r₂ равно \(\scriptsize r_1 + j \)r₁+j, где \(\scriptsize j \)j равно:

\(\scriptsize z \)z, если \(\scriptsize k=0 \)k=0
\(\scriptsize (k \mod n)+V_{k-1} \)(k mod n)+V_k-1, если \(\scriptsize 0<k⩽z \)0<k⩽z
\(\scriptsize k \mod n \)k mod n, если \(\scriptsize z<k \)z<k

3) Установить для \(\scriptsize S_{k+p} \)S_k+p значение \(\scriptsize (S_{k+p}+r_1) \mod 2^{32} \)(S_k+p+r₁) mod 2³².

4) Установить для \(\scriptsize S_{k+q} \)S_k+q значение \(\scriptsize (S_{k+q}+r_2) \mod 2^{32} \)(S_k+q+r₂) mod 2³².

5) Установить для \(\scriptsize S_k \)S_k значение \(\scriptsize r_2 \mod 2^{32} \)r₂ mod 2³².

3) Для каждого целого числа k в [m, m + n) выполнить следующие операции по порядку:

1) Пусть \(\scriptsize r_3 \)r₃ равно \(\scriptsize 1566083941 \cdot T(S_k+S_{k+p}+S_{k-1}) \)1566083941·T(S_k+S_k+p+S_k-1).

2) Пусть \(\scriptsize r_4 \)r₄ равно \(\scriptsize r_3-(k \mod n) \)r₃-(k mod n).

3) Установить для \(\scriptsize S_{k+p} \)S_k+p значение \(\scriptsize (S_{k+p}\ \mathsf{xor}\ r_3) \mod 2^{32} \)(S_k+p xor r₃) mod 2³².

4) Установить для \(\scriptsize S_{k+q} \)S_k+q значение \(\scriptsize (S_{k+q}\ \mathsf{xor}\ r_4) \mod 2^{32} \)(S_k+q xor r₄) mod 2³².

5) Установить для \(\scriptsize S_k \)S_k значение \(\scriptsize r_4 \mod 2^{32} \)r₄ mod 2³².

Параметры

begin, end

итераторы, задающие выходной диапазон

Исключения

Выбрасываются только исключения, выбрасываемые операциями RandomIt над begin и end.

Примечания

Алгоритм генерации адаптирован из последовательности инициализации генератора Mersenne Twister, разработанного Макото Мацумото и Такудзи Нисимурой, с учётом усовершенствований, внесённых Муцуо Сайто в 2007 году.

Пример

#include <algorithm>
#include <cassert>
#include <cstdint>
#include <iostream>
#include <random>

// Prototyping the main part of std::seed_seq...
struct seed_seq
{
    std::vector<std::uint32_t> v;
    
    seed_seq(std::initializer_list<std::uint32_t> const il) : v{il} {}
    
    template<typename RandomIt>
    void generate(RandomIt first, RandomIt last)
    {
        if (first == last)
            return;
        //
        // Assuming v = {1, 2, 3, 4, 5} and distance(first, last) == 10.
        //
        // Step 1: fill with 0x8b8b8b8b
        // seeds = {2341178251, 2341178251, 2341178251, 2341178251, 2341178251,
        //          2341178251, 2341178251, 2341178251, 2341178251, 2341178251}
        //
        std::fill(first, last, 0x8b8b8b8b);
        //
        // Step 2:
        // n = 10, s = 5, t = 3, p = 3, q = 6, m = 10
        //
        const std::uint32_t n = last - first;
        const std::uint32_t s = v.size();
        const std::uint32_t t = (n < 7) ? (n - 1) / 2
                              : (n < 39) ? 3
                              : (n < 68) ? 5
                              : (n < 623) ? 7
                              : 11;
        const std::uint32_t p = (n - t) / 2;
        const std::uint32_t q = p + t;
        const std::uint32_t m = std::max(s + 1, n);
        //
        // First iteration, k = 0; r1 = 1371501266, r2 = 1371501271
        //
        // seeds = {1371501271, 2341178251, 2341178251, 3712679517, 2341178251,
        //          2341178251, 3712679522, 2341178251, 2341178251, 2341178251}
        //
        // Iterations from k = 1 to k = 5 (r2 = r1 + k % n + v[k - 1])
        //
        // r1 = 2786190137, 3204727651, 4173325571, 1979226628, 401983366
        // r2 = 2786190139, 3204727655, 4173325577, 1979226636, 401983376
        //
        // seeds = {3350727907, 3188173515, 3204727655, 4173325577, 1979226636,
        //           401983376, 3591037797, 2811627722, 1652921976, 2219536532}
        //
        // Iterations from k = 6 to k = 9 (r2 = r1 + k % n)
        //
        // r1 = 2718637909, 1378394210, 2297813071, 1608643617
        // r2 = 2718637915, 1378394217, 2297813079, 1608643626
        //
        // seeds = { 434154821, 1191019290, 3237041891, 1256752498, 4277039715,
        //          2010627002, 2718637915, 1378394217, 2297813079, 1608643626}
        //
        auto begin_mod = [first, n](std::uint32_t u) -> decltype(*first)&
        {
            return first[u % n]; // i.e. begin[x] is taken modulo n
        };
        auto T = [](std::uint32_t x) { return x ^ (x >> 27); };
        
        for (std::uint32_t k = 0, r1, r2; k < m; ++k)
        {
            r1 = 1664525 * T(begin_mod(k) ^ begin_mod(k + p) ^ begin_mod(k - 1));
            r2 = (k == 0) ? r1 + s
               : (k <= s) ? r1 + k % n + v[k - 1]
               :            r1 + k % n;
            begin_mod(k + p) += r1;
            begin_mod(k + q) += r2;
            begin_mod(k) = r2;
        }
        //
        // Step 3
        // iterations from k = 10 to k = 19, using ^= to modify the output
        //
        // r1 = 1615303485, 3210438310, 893477041, 2884072672, 1918321961,
        // r2 = 1615303485, 3210438309, 893477039, 2884072669, 1918321957
        //
        // seeds = { 303093272, 3210438309,  893477039, 2884072669, 1918321957,
        //          1117182731, 1772877958, 2669970405, 3182737656, 4094066935}
        //
        // r1 =  423054846, 46783064, 3904109085, 1534123446, 1495905687
        // r2 =  423054841, 46783058, 3904109078, 1534123438, 1495905678
        //
        // seeds = { 4204997637, 4246533866, 1856049002, 1129615051, 690460811,
        //           1075771511,   46783058, 3904109078, 1534123438, 1495905678}
        //
        for (std::uint32_t k = m, r3, r4; k < m + n; ++k)
        {
            r3 = 1566083941 * T(begin_mod(k) + begin_mod(k + p) + begin_mod(k - 1));
            r4 = r3 - k % n;
            begin_mod(k+p) ^= r3;
            begin_mod(k+q) ^= r4;
            begin_mod(k) = r4;
        }
    }
};

int main()
{
    const auto input = std::initializer_list<std::uint32_t>{1, 2, 3, 4, 5};
    const auto output_size = 10;
    
    // using std version of seed_seq
    std::seed_seq seq(input);
    std::vector<std::uint32_t> seeds(output_size);
    seq.generate(seeds.begin(), seeds.end());
    for (const std::uint32_t n : seeds)
        std::cout << n << '\n';
    
    // using custom version of seed_seq
    seed_seq seq2(input);
    std::vector<std::uint32_t> seeds2(output_size);
    seq2.generate(seeds2.begin(), seeds2.end());
    
    assert(seeds == seeds2);
}

Вывод:

Отчёты об исправлении ошибок

Следующие отчёты об исправлении ошибок, изменяющие поведение, были ретроактивно применены к ранее опубликованным стандартам C++.

Отчёт	Применён к	Опубликованное поведение	Корректное поведение
LWG 2180	C++11	`seed_seq::generate` не выбрасывает исключений	может выбрасывать исключения

© cppreference.com
Licensed under the Creative Commons Attribution-ShareAlike Unported License v3.0.
https://en.cppreference.com/cpp/numeric/random/seed_seq/generate