Ist es gültig, std :: transform mit std :: back_inserter zu verwenden?

20

Cppreference hat diesen Beispielcode für std::transform:

std::vector<std::size_t> ordinals;
std::transform(s.begin(), s.end(), std::back_inserter(ordinals),
               [](unsigned char c) -> std::size_t { return c; });

Es heißt aber auch:

std::transformgarantiert nicht die ordnungsgemäße Anwendung von unary_opoder binary_op. Verwenden Sie zum Anwenden einer Funktion auf eine Sequenz in der angegebenen Reihenfolge oder zum Anwenden einer Funktion, die die Elemente einer Sequenz ändert std::for_each.

Dies soll vermutlich parallele Implementierungen ermöglichen. Der dritte Parameter von std::transformist jedoch a, für LegacyOutputIteratorden die folgende Nachbedingung gilt ++r:

Danach muss dieser Vorgang rnicht mehr inkrementierbar sein, und Kopien des vorherigen Werts von müssen rnicht mehr dereferenzierbar oder inkrementierbar sein.

Es scheint mir also, dass die Zuordnung der Ausgabe in der richtigen Reihenfolge erfolgen muss. Bedeuten sie einfach, dass die Anwendung von unary_opmöglicherweise nicht in Ordnung ist und an einem temporären Speicherort gespeichert, aber in der angegebenen Reihenfolge in die Ausgabe kopiert wird? Das klingt nicht nach etwas, das Sie jemals tun möchten.

Die meisten C ++ - Bibliotheken haben noch keine parallelen Executoren implementiert, Microsoft jedoch. Ich bin mir ziemlich sicher, dass dies der relevante Code ist, und ich denke, er ruft diese populate()Funktion auf, um Iteratoren in Blöcken der Ausgabe aufzuzeichnen, was sicherlich keine gültige Vorgehensweise ist, da LegacyOutputIteratorsie durch Inkrementieren von Kopien ungültig gemacht werden kann.

Was vermisse ich?

Timmmm
quelle
Ein einfacher Test in Godbolt zeigt, dass dies ein Problem ist. Mit C ++ 20 und einer transformVersion, die entscheidet, ob Paralelismus verwendet wird oder nicht. Das transformfür große Vektoren schlägt fehl.
Croolman
6
@Croolman Ihr Code ist falsch, da Sie zurück in einfügen s, wodurch Iteratoren ungültig werden.
Daniel Langr
@ DanielsaysreinstateMonica Oh Schnitzel du hast recht. Hat es optimiert und in einem ungültigen Zustand belassen. Ich nehme meinen Kommentar zurück.
Croolman
Wenn Sie eine std::transformExaktionsrichtlinie verwenden, ist ein Iterator mit wahlfreiem Zugriff erforderlich, der back_inserternicht erfüllt werden kann. Die von IMO zitierte Teiledokumentation bezieht sich auf dieses Szenario. Beispiel in der Dokumentation beachten std::back_inserter.
Marek R
@Croolman Beschließt, Parallelität automatisch zu verwenden?
Neugieriger

Antworten:

9

1) Die Anforderungen an den Ausgabe-Iterator im Standard sind vollständig gebrochen. Siehe LWG2035 .

2) Wenn Sie einen reinen Ausgabe-Iterator und einen reinen Eingabequellenbereich verwenden, kann der Algorithmus in der Praxis nur wenig anderes tun. es bleibt nichts anderes übrig, als in der richtigen Reihenfolge zu schreiben. (Eine hypothetische Implementierung kann sich jedoch dafür entscheiden, ihre eigenen Typen als Sonderfall festzulegen, z. B. std::back_insert_iterator<std::vector<size_t>>Ich verstehe nicht, warum eine Implementierung dies hier tun möchte, aber es ist zulässig, dies zu tun.)

3) Nichts in der Norm garantiert, dass transformdie Transformationen in der richtigen Reihenfolge angewendet werden. Wir betrachten ein Implementierungsdetail.

Dies std::transformerfordert nur Ausgabe-Iteratoren. Dies bedeutet nicht, dass in solchen Fällen keine höheren Iteratorstärken erkannt und die Operationen neu angeordnet werden können. Tatsächlich versenden Algorithmen auf Iterator Kraft die ganze Zeit , und sie haben eine spezielle Behandlung für spezielle Iteratortypen (wie Zeiger oder Vektor Iteratoren) die ganze Zeit .

Wenn der Standard eine bestimmte Bestellung garantieren möchte, weiß er, wie man es sagt (siehe std::copy"Ausgehend von firstund weiter zu last").

TC
quelle
5

Von n4385:

§25.6.4 Transformieren :

template<class InputIterator, class OutputIterator, class UnaryOperation>
constexpr OutputIterator
transform(InputIterator first1, InputIterator last1, OutputIterator result, UnaryOperation op);

template<class ExecutionPolicy, class ForwardIterator1, class ForwardIterator2, class UnaryOperation>
ForwardIterator2
transform(ExecutionPolicy&& exec, ForwardIterator1 first1, ForwardIterator1 last1, ForwardIterator2 result, UnaryOperation op);

template<class InputIterator1, class InputIterator2, class OutputIterator, class BinaryOperation>
constexpr OutputIterator
transform(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, OutputIterator result, BinaryOperation binary_op);

template<class ExecutionPolicy, class ForwardIterator1, class ForwardIterator2, class ForwardIterator, class BinaryOperation>
ForwardIterator
transform(ExecutionPolicy&& exec, ForwardIterator1 first1, ForwardIterator1 last1, ForwardIterator2 first2, ForwardIterator result, BinaryOperation binary_op);

§23.5.2.1.2 back_inserter

template<class Container>
constexpr back_insert_iterator<Container> back_inserter(Container& x);

Rückgabe: back_insert_iterator (x).

§23.5.2.1 Klassenvorlage back_insert_iterator

using iterator_category = output_iterator_tag;

So std::back_inserterkann nicht mit parallelen Versionen verwendet werden std::transform. Die Versionen, die Ausgabeiteratoren unterstützen, lesen mit Eingabeiteratoren aus ihrer Quelle. Da Eingabe-Iteratoren nur vor und nach dem Inkrementieren ausgeführt werden können (§23.3.5.2 Eingabe-Iteratoren) und nur eine sequentielle ( dh nicht parallele) Ausführung erfolgt, muss die Reihenfolge zwischen ihnen und dem Ausgabe-Iterator beibehalten werden.

Paul Evans
quelle
2
Beachten Sie, dass diese Definitionen aus dem C ++ - Standard Implementierungen nicht vermeiden, um spezielle Versionen von Algorithmen bereitzustellen, die für zusätzliche Iteratortypen ausgewählt wurden. Hat beispielsweise std::advancenur eine Definition, die Eingabe-Iteratoren akzeptiert, aber libstdc ++ bietet zusätzliche Versionen für bidirektionale Iteratoren und Iteratoren mit wahlfreiem Zugriff . Die bestimmte Version wird dann basierend auf dem Typ des übergebenen Iterators ausgeführt .
Daniel Langr
Ich denke nicht, dass Ihr Kommentar richtig ist - ForwardIteratordas bedeutet nicht, dass Sie die Dinge in der richtigen Reihenfolge tun müssen. Aber Sie haben das hervorgehoben, was ich verpasst habe - für die parallelen Versionen, die sie ForwardIteratornicht verwenden OutputIterator.
Timmmm
1
Ah richtig, ja ich denke wir sind uns einig.
Timmmm
1
Diese Antwort könnte davon profitieren, einige Wörter hinzuzufügen, um zu erklären, was es tatsächlich bedeutet.
Barry
1
@Barry Einige Wörter hinzugefügt, alle Rückmeldungen sehr geschätzt.
Paul Evans
0

Das, was ich vermisst habe, ist, dass die parallelen Versionen LegacyForwardIterators nehmen , nicht LegacyOutputIterator. A LegacyForwardIterator kann inkrementiert werden, ohne Kopien davon ungültig zu machen. Daher ist es einfach, damit eine Parallele außerhalb der Reihenfolge zu implementieren std::transform.

Ich denke, die nicht parallelen Versionen von std::transform müssen in der richtigen Reihenfolge ausgeführt werden. Entweder ist cppreference falsch, oder der Standard lässt diese Anforderung möglicherweise nur implizit, da es keine andere Möglichkeit gibt, sie zu implementieren. (Schrotflinte watet nicht durch den Standard, um es herauszufinden!)

Timmmm
quelle
Die nicht parallelen Versionen der Transformation werden möglicherweise nicht in der richtigen Reihenfolge ausgeführt, wenn alle Iteratoren ausreichend stark sind. Im Beispiel in der Frage sind sie nicht, so dass die Spezialisierung von transformin Ordnung sein muss.
Caleth
Nein, das können sie nicht, weil Sie gezwungen sind, LegacyOutputIteratores in der richtigen Reihenfolge zu verwenden.
Timmmm
Es kann sich für std::back_insert_iterator<std::vector<T>>und unterschiedlich spezialisieren std::vector<T>::iterator. Der erste muss in Ordnung sein. Der zweite hat keine solche Einschränkung
Caleth
Ah, warte, ich verstehe, was du meinst - wenn du zufällig ein LegacyForwardIteratorin das Nicht-Parallele übergibst transform, könnte es eine Spezialisierung für das haben, was es nicht in Ordnung bringt. Guter Punkt.
Timmmm
0

Ich glaube, dass die Transformation garantiert in der richtigen Reihenfolge verarbeitet wird . std::back_inserter_iteratorist ein Ausgabe-Iterator (sein Elementtypiterator_category ist ein Alias ​​für std::output_iterator_tag) gemäß [back.insert.iterator] .

Folglich std::transformgibt es keine andere Möglichkeit, wie mit der nächsten Iteration fortzufahren, als ein Mitglied operator++für den resultParameter aufzurufen .

Dies gilt natürlich nur für Überladungen ohne Ausführungsrichtlinie, die std::back_inserter_iteratormöglicherweise nicht verwendet werden (es handelt sich nicht um einen Weiterleitungsiterator ).


Übrigens würde ich nicht mit Zitaten von cppreference argumentieren. Die Aussagen dort sind oft ungenau oder vereinfacht. In solchen Fällen ist es besser, sich den C ++ - Standard anzusehen. Wo in Bezug auf std::transformgibt es kein Zitat über die Reihenfolge der Operationen.

Daniel Langr
quelle
"C ++ Standard. Wo gibt es in Bezug auf std :: transform kein Zitat über die Reihenfolge der Operationen ? " Da die Reihenfolge nicht erwähnt wird, ist sie nicht nicht spezifiziert?
HolyBlackCat
@HolyBlackCat Explizit nicht angegeben, aber vom Ausgabe-Iterator auferlegt. Beachten Sie, dass Sie bei Ausgabe-Iteratoren nach dem Inkrementieren möglicherweise keinen vorherigen Iteratorwert dereferenzieren.
Daniel Langr