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::transform
garantiert nicht die ordnungsgemäße Anwendung vonunary_op
oderbinary_op
. Verwenden Sie zum Anwenden einer Funktion auf eine Sequenz in der angegebenen Reihenfolge oder zum Anwenden einer Funktion, die die Elemente einer Sequenz ändertstd::for_each
.
Dies soll vermutlich parallele Implementierungen ermöglichen. Der dritte Parameter von std::transform
ist jedoch a, für LegacyOutputIterator
den die folgende Nachbedingung gilt ++r
:
Danach muss dieser Vorgang
r
nicht mehr inkrementierbar sein, und Kopien des vorherigen Werts von müssenr
nicht 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_op
mö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 LegacyOutputIterator
sie durch Inkrementieren von Kopien ungültig gemacht werden kann.
Was vermisse ich?
quelle
transform
Version, die entscheidet, ob Paralelismus verwendet wird oder nicht. Dastransform
für große Vektoren schlägt fehl.s
, wodurch Iteratoren ungültig werden.std::transform
Exaktionsrichtlinie verwenden, ist ein Iterator mit wahlfreiem Zugriff erforderlich, derback_inserter
nicht erfüllt werden kann. Die von IMO zitierte Teiledokumentation bezieht sich auf dieses Szenario. Beispiel in der Dokumentation beachtenstd::back_inserter
.Antworten:
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
transform
die Transformationen in der richtigen Reihenfolge angewendet werden. Wir betrachten ein Implementierungsdetail.Dies
std::transform
erfordert 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 vonfirst
und weiter zulast
").quelle
Von
n4385
:§25.6.4 Transformieren :
§23.5.2.1.2 back_inserter
§23.5.2.1 Klassenvorlage back_insert_iterator
So
std::back_inserter
kann nicht mit parallelen Versionen verwendet werdenstd::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.quelle
std::advance
nur 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 .ForwardIterator
das 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 sieForwardIterator
nicht verwendenOutputIterator
.Das, was ich vermisst habe, ist, dass die parallelen Versionen
LegacyForwardIterator
s nehmen , nichtLegacyOutputIterator
. ALegacyForwardIterator
kann inkrementiert werden, ohne Kopien davon ungültig zu machen. Daher ist es einfach, damit eine Parallele außerhalb der Reihenfolge zu implementierenstd::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!)quelle
transform
in Ordnung sein muss.LegacyOutputIterator
es in der richtigen Reihenfolge zu verwenden.std::back_insert_iterator<std::vector<T>>
und unterschiedlich spezialisierenstd::vector<T>::iterator
. Der erste muss in Ordnung sein. Der zweite hat keine solche EinschränkungLegacyForwardIterator
in das Nicht-Parallele übergibsttransform
, könnte es eine Spezialisierung für das haben, was es nicht in Ordnung bringt. Guter Punkt.Ich glaube, dass die Transformation garantiert in der richtigen Reihenfolge verarbeitet wird .
std::back_inserter_iterator
ist ein Ausgabe-Iterator (sein Elementtypiterator_category
ist ein Alias fürstd::output_iterator_tag
) gemäß [back.insert.iterator] .Folglich
std::transform
gibt es keine andere Möglichkeit, wie mit der nächsten Iteration fortzufahren, als ein Mitgliedoperator++
für denresult
Parameter aufzurufen .Dies gilt natürlich nur für Überladungen ohne Ausführungsrichtlinie, die
std::back_inserter_iterator
mö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::transform
gibt es kein Zitat über die Reihenfolge der Operationen.quelle