std::seed_seq:: generate
|
template
<
class
RandomIt
>
void generate ( RandomIt begin, RandomIt end ) ; |
(depuis C++11) | |
Générez des graines non biaisées en remplissant la plage de sortie
[
begin
,
end
)
avec des valeurs entières non signées de 32 bits, basées sur les graines (potentiellement biaisées) stockées dans
v
.
- Si begin == end est true , ne fait rien.
- Sinon, génère des graines par l'algorithme de génération décrit ci-dessous.
Si std:: iterator_traits < RandomIt > :: value_type n'est pas un type entier non signé, ou si sa largeur est inférieure à 32, le programme est mal formé.
Si
RandomIt
ne satisfait pas aux exigences de
LegacyRandomAccessIterator
, ou s'il n'est pas
mutable
, le comportement est indéfini.
Table des matières |
Algorithme de génération
Étant donné les valeurs et opérations suivantes :
| Valeur | Définition |
| 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 |
| Opération | Définition |
| xor | intégré XOR bit à bit |
| rshift | intégré décalage à droite bit à bit |
| T(x) | x xor (x rshift 27) |
L'algorithme de génération comprend les étapes suivantes, où
S
i
désigne
begin
[
i
%
n
]
,
V
i
désigne
v
[
i
]
:
[
0
,
m
)
, effectue les opérations suivantes dans l'ordre :
- z , si k=0
- (k mod n)+V k-1 , si 0<k⩽z
- k mod n , si z<k
.
.
.
[
m
,
m
+
n
)
, effectue les opérations suivantes dans l'ordre :
.
.
.
Paramètres
| begin, end | - | les itérateurs délimitant la plage de sortie |
Exceptions
Ne lance que les exceptions levées par les
RandomIt
opérations sur
begin
et
end
.
Notes
L'algorithme de génération est adapté de la séquence d'initialisation du générateur Mersenne Twister par Makoto Matsumoto et Takuji Nishimura , intégrant les améliorations apportées par Mutsuo Saito en 2007 .
Exemple
#include <algorithm> #include <cassert> #include <cstdint> #include <iostream> #include <random> // Prototypage de la partie principale de 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; // // En supposant que v = {1, 2, 3, 4, 5} et distance(first, last) == 10. // // Étape 1 : remplir avec 0x8b8b8b8b // seeds = {2341178251, 2341178251, 2341178251, 2341178251, 2341178251, // 2341178251, 2341178251, 2341178251, 2341178251, 2341178251} // std::fill(first, last, 0x8b8b8b8b); // // Étape 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); // // Première itération, k = 0 ; r1 = 1371501266, r2 = 1371501271 // // seeds = {1371501271, 2341178251, 2341178251, 3712679517, 2341178251, // 2341178251, 3712679522, 2341178251, 2341178251, 2341178251} // // Itérations de k = 1 à 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} // // Itérations de k = 6 à 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]; // c'est-à-dire que begin[x] est pris 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; } // // Étape 3 // itérations de k = 10 à k = 19, en utilisant ^= pour modifier la sortie // // 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; // utilisation de la version std de 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'; // utilisation d'une version personnalisée de seed_seq seed_seq seq2(input); std::vector<std::uint32_t> seeds2(output_size); seq2.generate(seeds2.begin(), seeds2.end()); assert(seeds == seeds2); }
Sortie :
4204997637 4246533866 1856049002 1129615051 690460811 1075771511 46783058 3904109078 1534123438 1495905678
Rapports de défauts
Les rapports de défauts modifiant le comportement suivants ont été appliqués rétroactivement aux normes C++ précédemment publiées.
| DR | Appliqué à | Comportement publié | Comportement correct |
|---|---|---|---|
| LWG 2180 | C++11 |
seed_seq::generate
est non-lancant
|
il peut lancer des exceptions |