Werbung

  1. Diese Seite verwendet Cookies. Wenn du dich weiterhin auf dieser Seite aufhältst, akzeptierst du unseren Einsatz von Cookies. Weitere Informationen

[C++ Quicktip] Iterieren in zufälliger Reihenfolge

Über einen Container in zufälliger Reihenfolge iterieren.

  1. -AB-
    Programmiersprache(n):
    C++
    Über einen Container in zufälliger Reihenfolge iterieren.

    Und wieder ein klitzekleiner Quicktip.
    Hin und wieder möchte mal mal über eine Kollektion von Daten data in zufälliger Reihenfolge drüberlaufen. Um einen Container durcheinander zu werfen, bietet die C++ STL std::random_shuffle (oder auch seit C++11 std::shuffle) an. Das könnte man auf data aufrufen, und danach drüber iterieren - allerdings klappt das nicht, wenn unser data const ist, wenn unser Container keinen random access erlaubt oder wenn die Sortierung des Containers ohnehin ein umsortieren verbietet (z.B. wenn data ein std::set oder eine std::map ist).

    (In manchen Fällen möchten wir auch unseren Container gar nicht ändern - z.B. würden Iteratoren invalidiert, das shufflen könnte - je nach Datentyp - teuer werden - oder wir mögen die Reihenfolge einfach, wie sie ist!)

    Code (C++):
    Quelltext kopieren
    1. std::vector<int> data{1,2,3,4,5,6};
    In dem Fall bietet es sich an, anstatt der echten Daten einen Container mit Referenzen auf diesen zu nutzen. Eine Referenz ist in diesem Falle ein Typ, der auf das Element im original-Container verweist - möglich wäre ein Pointer, ein Iterator bietet sich aber ebenso an.

    Wir holen uns also Iteratoren auf alle Elemente in data und legen sie in einen std::vector iterators ab. Einen vector deshalb, weil er uns random access erlaubt, was wir für das spätere shufflen brauchen.

    Code (C++):
    Quelltext kopieren
    1. std::vector<std::vector<int>::const_iterator> iterators;
    2. for(auto iter = data.begin();iter != data.end(); ++iter)
    3.     iterators.emplace_back(iter);
    Jetzt können wir mit
    Code (C++):
    Quelltext kopieren
    1. std::random_shuffle(iterators.begin(), iterators.end());
    die Reihenfolge randomisieren.

    Als nächstes kann man mit std::for_each über iterators laufen. Packt man das alles in eine Funktion, sieht da in etwa so aus:

    Code (C++):
    Quelltext kopieren
    1. template <typename ForwardIterator, typename Action>
    2. Action randomized_for_each(ForwardIterator first, ForwardIterator last, Action action)
    3. {
    4.     std::vector<ForwardIterator> iterators;
    5.     for(ForwardIterator iter = first;iter != last; ++iter)
    6.         iterators.emplace_back(iter);
    7.  
    8.     std::random_shuffle(iterators.begin(), iterators.end());
    9.  
    10.     std::for_each(iterators.begin(), iterators.end(),
    11.             [&action](const auto& elem)
    12.             {
    13.                 action(*elem);
    14.             }
    15.         );
    16.  
    17.     return action;
    18. }
    Dieser Funktion können wir dann - wie std::for_each - einen begin&end-Iterator übergeben, und dann eine Funktion, die ausgeführt werden soll. randomized_for_each nimmt alle Arten von Iteratoren an, die sich inkrementieren lassen - eignet sich also für std::sets, std::maps, const Containers....

    Der Aufruf - neben einem gewöhnlichen Aufruf von std::for_each - sähe in etwa so aus:
    Code (C++):
    Quelltext kopieren
    1. std::vector<int> data{1,2,3,4,5,6};
    2.  
    3. std::cout << "original order:" << std::endl;
    4. std::for_each(data.begin(), data.end(),
    5.     [](const auto& element)
    6.     {
    7.         std::cout << element << std::endl;
    8.     });
    9.  
    10. std::cout << "randomized:" << std::endl;
    11. randomized_for_each(data.begin(), data.end(),
    12.     [](const auto& element)
    13.     {
    14.         std::cout << element << std::endl;
    15.     });
    Laufzeitkomplexität ist O(3*n), wenn n die Länge von data ist - einmal das Anlegen von iterators, einmal das shufflen, einmal das Iterieren darüber. Wenn es jemand in geringerer Komplexität schafft, immer her damit :)


    Bei Fragen oder Anmerkungen, wenn etwas fehlt oder wer einfach nur ein bisschen quatschen will - oben unter dem Titel auf "Diskussion" gehen und schreiben.
    Fabolous gefällt das.

Letzte Rezensionen

  1. German
    German
    5/5,
    Die Idee, Iteratoren in einen vector zu kopieren, eröffnet Zugriffsmöglichkeiten, die nicht nur für ein random_shuffle interessant sein dürften.