Baza znanjaCentar za ispite
HRHrvatski
Odaberi jezik13

CKTIS / C++

std::shuffle — nasumično preslagivanje elemenata

std::shuffle preslaguje elemente raspona na mjestu pomoću zadanog generatora slučajnih brojeva. Zahtijeva iteratore s pristupom po indeksu; fiksno sjeme ne jamči isti redoslijed u različitim implementacijama standardne biblioteke.

Verzija: C++23; repository compiler flag, production runtime not attested

Sintaksa

template<class RandomAccessIterator, class UniformRandomBitGenerator>
void std::shuffle(RandomAccessIterator first, RandomAccessIterator last,
                  UniformRandomBitGenerator&& g);

std::shuffle, deklariran u <algorithm>, nasumično preslaguje elemente poluotvorenog raspona [first, last). Ne dodaje ni uklanja elemente i vraća void. Ugovor zahtijeva jednaku vjerojatnost za svaku permutaciju, pa rezultat može zadržati izvorni redoslijed.

Iteratori moraju omogućavati nasumičan pristup, a elementi na koje upućuju moraju se moći zamjenjivati. Primjerice, prikladni su promjenjivi std::array i std::vector, ali ne i std::list. Argument g mora ispunjavati zahtjeve za uniform random bit generator, kao što ih ispunjava std::mt19937 iz <random>; nije riječ samo o sjemenu ni o proizvoljnoj funkciji koja vraća brojeve.

Složenost je linearna u odnosu na broj elemenata. Generator osigurava slučajnost, a njegovo se stanje može mijenjati. Fiksno sjeme olakšava ponavljanje testova unutar iste implementacije, no standard ne propisuje određeni rezultatni redoslijed između različitih implementacija standardne biblioteke.

Primjer pomoću std::is_permutation provjerava jesu li elementi sačuvani, umjesto da očekuje određeni redoslijed ili zahtijeva da se redoslijed promijeni. Zato je očekivani izlaz uvijek true ako je izvođenje ispravno.

Primjeri

#include <algorithm>
#include <array>
#include <iostream>
#include <random>

int main() {
    const std::array<int, 5> original{1, 2, 3, 4, 5};
    auto values = original;
    std::mt19937 engine{42};

    std::shuffle(values.begin(), values.end(), engine);

    std::cout << std::boolalpha
              << std::is_permutation(original.begin(), original.end(),
                                     values.begin(), values.end())
              << '\n';
}

Rezultat

true

Prikazani kôd i navedeni rezultat provjereni su u izoliranom okruženju metodom zabilježenom u dokazu provjere za ovu točnu verziju.

Izvori