Vektor mischen in C++

Um die Elemente eines C++-Vektors zufällig und direkt im Vektor neu anzuordnen, rufen Sie std::shuffle mit den Iteratoren begin() und end() des Vektors sowie einem Zufallszahlengenerator auf. Der Algorithmus ordnet die Elemente im angegebenen Bereich neu an; er erstellt keinen zweiten Vektor. Verwenden Sie einen festen Startwert für den Generator, wenn Sie eine reproduzierbare Folge pseudozufälliger Entscheidungen benötigen. Soll sich die Folge bei verschiedenen Programmläufen in der Regel unterscheiden, initialisieren Sie den Generator mit einer geeigneten Quelle.

Einen Vektor mit std::shuffle mischen

std::shuffle ist im Header <algorithm> deklariert. Die ersten beiden Argumente geben einen halboffenen Iteratorbereich an: Der erste Iterator zeigt auf das erste einzubeziehende Element, der zweite direkt hinter das letzte. Bei einem Vektor umfasst der Bereich mit values.begin() und values.end() daher den gesamten Vektor. Das dritte Argument ist ein UniformRandomBitGenerator, häufig ein Generator wie std::mt19937. Er liefert die Zufallsbits, anhand derer die Permutation ausgewählt wird; er ist keine Callback-Funktion, die einen bereits gemischten Vektor zurückgibt.

Dieses vollständige Beispiel verwendet einen festen Startwert, sodass der Generator bei jedem Programmlauf mit demselben Zustand beginnt. Die konkrete gemischte Reihenfolge ist durch std::shuffle jedoch nicht festgelegt: Sie kann je nach Implementierung der Standardbibliothek variieren. Betrachten Sie die folgende Ausgabe daher als Beispiel und nicht als garantierte Folge.

Führen Sie dieses Beispiel aus:

#include <algorithm>
#include <cstddef>
#include <iostream>
#include <random>
#include <vector>

int main() {
    std::vector<int> values{12, 32, 43, 53, 23, 65, 84};
    std::mt19937 engine(42);

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

    for (std::size_t i = 0; i < values.size(); ++i) {
        if (i != 0) {
            std::cout << ' ';
        }
        std::cout << values[i];
    }
    std::cout << '\n';
}

Der Eingabevektor lautet 12 32 43 53 23 65 84. Beim bereitgestellten erfolgreichen Programmlauf wurde die folgende gemischte Reihenfolge ausgegeben:

23 12 43 53 84 65 32

Mit einem festen Startwert lässt sich die Folge des pseudozufälligen Generators bei gleicher Implementierung und gleicher Umgebung reproduzieren. Eine identische gemischte Ausgabe über alle Implementierungen der Standardbibliothek hinweg ist damit nicht garantiert, denn der Algorithmus legt keine universelle Folge konkreter Entscheidungen fest. Wenn die Ergebnisse bei verschiedenen Läufen variieren sollen, initialisieren Sie einen Generator einmal und verwenden Sie ihn anschließend für mehrere Mischvorgänge wieder, statt für jedes Element oder jeden Aufruf einen neuen Generator zu erzeugen. std::random_device wird häufig als Quelle für Startwerte verwendet, sein Verhalten hängt jedoch von der Implementierung und der Umgebung ab. Es garantiert weder Nichtdeterminismus noch kryptografische Zufälligkeit.

Sie können den Bereich auch mit std::begin(values) und std::end(values) angeben, die über die Standard-Iterator-Hilfsfunktionen verfügbar sind. Diese Schreibweise ist praktisch, wenn Sie eine generische Hilfsfunktion für verschiedene Container oder eingebaute Arrays schreiben. Für einen Aufruf mit einem Vektor sind dessen Member-Iteratoren direkt und übersichtlich. Achten Sie bei beiden Varianten darauf, dass die Endpunkte zum selben Container gehören und der Bereich genau die Elemente umfasst, die Sie permutieren möchten. Der Vorgang ändert die Reihenfolge im Vektor selbst. Späterer Code, der ihn liest oder durchläuft, sieht daher die gemischte Anordnung.

Älteren Code mit std::random_shuffle behandeln

std::random_shuffle ist ein älterer Algorithmus der Standardbibliothek, der in bestehendem C++-Code vorkommen kann. Ob er verfügbar ist, hängt vom für das Projekt gewählten Sprachstandard und von der verwendeten Implementierung der Standardbibliothek ab. Prüfen Sie bei der Wartung solchen Codes diese Einstellungen, bevor Sie davon ausgehen, dass der Name verfügbar ist. Ältere Überladungen können eine implementierungsdefinierte Zufallsquelle verwenden; Überladungen mit einem Generator stellen andere Anforderungen als das Generatorargument von std::shuffle.

Verwenden Sie für neuen oder überarbeiteten Code bevorzugt std::shuffle und übergeben Sie einen expliziten Zufallszahlengenerator. Dadurch ist die Zufallsquelle sichtbar, die Reproduzierbarkeit lässt sich über einen Startwert steuern und Sie sind nicht auf die ältere Schnittstelle angewiesen. Schließen Sie aus dem Vorkommen von std::random_shuffle in einer Codebasis weder, dass der Name in jedem Compiler-Modus verfügbar ist, noch, dass std::shuffle in jeder älteren Umgebung fehlt. Maßgeblich für die Kompatibilität sind die Konfiguration des Sprachstandards und die verwendete Standardbibliothek des Projekts. Muss ein Projekt älteren Code beibehalten, beschränken Sie diese Kompatibilitätsentscheidung auf das betreffende Projekt und prüfen Sie sie mit der Compilerkonfiguration, die für den Build verwendet wird.