Resource icon

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

-AB-

Well-Known Member
c-b Team
c-b Experte
#1
-AB- hat eine neue Ressource erstellt:

[C++ Quicktip] Iterieren in zufälliger Reihenfolge - Über einen Container in zufälliger Reihenfolge iterieren.

Ü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...
Weitere Informationen zu dieser Ressource...
 

German

Well-Known Member
c-b Experte
#2
Die Idee Iteratoren in einen vector zu packen finde ich interessant :) Ich frag mich aber, wie sicher das ganze tatsächlich ist. Ich meine, wenn ein Container von vorn herein keine Random-Access-Iteratoren zur Verfügung stellt, hat das doch sicher einen Grund. Ist denn die Validität von Input-Iteratoren noch gewährleistet, wenn man sie in einem anderen Container sammelt? Immerhin sind das ja nur "vereinfachte" Forward-Iteratoren. Logisch wäre es denke ich schon, da ja zwischenzeitlich niemand Daten im Quellcontainer herumschubst und somit die Iteratoren immer noch auf die ursprünglichen Daten zeigen sollten (Multithreading schließt sich sowieso von selbst aus), andererseits kenne ich die genaue Implementation von Iteratoren für die einzelnen Containertypen nicht ...
 

-AB-

Well-Known Member
c-b Team
c-b Experte
#3
Ist denn die Validität von Input-Iteratoren noch gewährleistet, wenn man sie in einem anderen Container sammelt?
Prinzipiell, ja. Kopierbar sind sie alle.

Und natürlich darf kein anderer Thread gleichzeitig auf den Container schreiben, das würde (unter Umständen) die Iteratoren invalidieren. (Die Umstände kommen auf den Container an.) Aber die gleiche Einschränkung gilt natürlich auch z.B. für std::for_each.

Aber stimmt schon. Der Haken ist das initiale Iterieren: Es könnte auch jemand einen Input-Iterator rein geben - sagen wir, weil er eine Datei liest - und erwarten, dass es darauf auf funktioniert. Dazu heißt es: The previous iterator value is not required to be dereferenceable after the increase. Klar, wenn ich

Damit "Multi-pass: neither dereferencing nor incrementing affects dereferenceability" gilt, müsste es ein Forward-Iterator sein. Könnte man mit 2 Zeilen meta-programming lösen :) - zumindest werd ich meinen template-Parameter mal umbenennen.
 

-AB-

Well-Known Member
c-b Team
c-b Experte
#5
Ein bisschen template-meta-programmiert:
C++:
template <typename ForwardIterator, typename Action>
typename std::enable_if<std::is_base_of<std::forward_iterator_tag, typename ForwardIterator::iterator_category>::value, Action>::type
randomized_for_each(ForwardIterator first, ForwardIterator last, Action action)
{
    std::vector<ForwardIterator> iterators;
    for(ForwardIterator iter = first;iter != last; ++iter)
        iterators.emplace_back(iter);

    std::random_shuffle(iterators.begin(), iterators.end());

    std::for_each(iterators.begin(), iterators.end(),
            [&action](const auto& elem)
            {
                action(*elem);
            }
        );

    return action;
}
Dann braucht es noch eine Version für random_shuffle mit Generator, und eine, die std::shuffle unterstützt. Aber dann hat man alles. :)
 
Oben