Boost Any_range Leistung: std :: prev (Iterator) gegen --iterator

Question

Boost Any_range Leistung: std :: prev (Iterator) gegen --iterator

8

Ich habe vor kurzem begonnen, die freien Funktionen std::next und std::prev explizit zum Kopieren und Inkrementieren / Dekrementieren von Iteratoren zu bevorzugen. Jetzt sehe ich seltsames Verhalten in einem ziemlich speziellen Fall, und ich würde jede Hilfe bei der Entmystifizierung schätzen.

Ich habe eine Interpolations- / Extrapolationsfunktion, die auf einem boost::any_range von einigen X_type arbeitet. Die vollständige Definition des Bereichstyps lautet:

%Vor%

Das any_range wird in diesem speziellen Fall von einem iterator_range zugewiesen, das zwei Zeiger auf const X_type hält, was als X_type Ansicht von ungefähr der Hälfte des data() Bereichs eines vector<char> dient. .

Kompilieren meiner Anwendung in MSVC 2010, alles funktioniert gut. Kompiliert man den gleichen Code in MinGW g ++ 4.7.0, so schien es an einem bestimmten Ort zu hängen, auf den ich mich dann (leicht abgekürzt) beschränkt habe:

%Vor%

Als ich den Code in gdb durchging, fand ich heraus, dass es nicht hängen blieb, es dauerte sehr lange, bis ich vom einzelnen std::prev Aufruf zurückkam - was in libstdc ++ in std::advance implementiert wurde und schließlich in += operator.

Indem Sie einfach die return -Zeile durch:

ersetzen %Vor%

Die Leistung ist wieder großartig und es gibt praktisch keine Verzögerung.

Ich bin mir des Overheads der Verwendung von Typ-gelöschten Iteratoren bewusst (die von any_range ), aber trotzdem, sollen die beiden obigen Fälle wirklich so unterschiedliche Kosten tragen? Oder mache ich etwas falsch?

c++ c++11 performance boost iterator

motiz88 01.07.2012, 10:43

quelle

1 Antwort

Tags und Links c++ c++11 performance boost iterator

Django: Verwenden von Annotate, Count und Distinct in einem Queryset UIView Frame ändert sich von viewWillAppear: to viewDidAppear:

score 3 · Accepted Answer

___ tag123performance ___ Für Fragen zur Messung oder Verbesserung der Code- und Anwendungseffizienz. ___ qstnhdr ___ Boost Any_range Leistung: std :: prev (Iterator) gegen --iterator ___ tag123c11 ___ C ++ 11 ist eine 2011 verabschiedete Version des C ++ - Sprachstandards. Sie hat viele Änderungen und Ergänzungen der Kernsprache sowie der verbesserten und erweiterten C ++ - Standardbibliothek vorgenommen. ___ tag123iterator ___ Ein Iterator ist ein objektorientiertes Programmiermuster, das das Durchlaufen einer Sammlung unabhängig von der tatsächlichen Implementierung oder Objektadressen im physischen Speicher ermöglicht. Es ist eines der Verhaltensmuster der Gang of Four. ___ tag123boost ___ Boost ist eine große Sammlung von hochwertigen Bibliotheken, die für die Verwendung in C ++ gedacht sind. Boost ist kostenlos und wird oft als "zweite Standard-Bibliothek" angesehen. ___ antwort13260745 ___

Okay, nachdem ich auf Kommentar von SplinterOfChaos reagiert habe, I etwas realisiert. Das Problem liegt in Ihrer Verwendung des any_range. Insbesondere das dritte Argument, das angibt, dass das Argument Reference ein const int ist. Wenn in der Boost-Iterator-Fassade die Referenz keine echte Referenz ist, wird entweder std::input_iterator_tag verwendet oder es wird kein STL-äquivalentes Tag bereitgestellt.

Es hat damit zu tun, dass streng genommen alle Vorwärts-, bidirektionalen und Random-Access-STL-Iteratoren eine echte Referenz für ihren Referenztyp verwenden müssen. Von 24.2.5 des C ++ 11-Standards:

Eine Klasse oder ein eingebauter Typ X erfüllt die Anforderungen eines Vorwärtsiterators, wenn
- X erfüllt die Anforderungen eines Eingabe-Iterators (24.2.3),

- X erfüllt die DefaultConstructible-Anforderungen (17.6.3.1),

- Wenn X ein veränderbarer Iterator ist, ist Referenz eine Referenz auf T; Wenn X ein konstanter Iterator ist, ist Referenz eine Referenz auf const T

- Die Ausdrücke in Tabelle 109 sind gültig und haben die angegebene Semantik und

- Objekte des Typs X bieten die unten beschriebene Mehrfachgarantie.

In diesem Fall gibt es ein std::input_iterator_tag zurück, wenn nach seinem iterator_category abgefragt wird, was den Aufruf von std::prev() veer in Undefiniertes Verhalten verursacht.

Wie auch immer, die Lösung besteht darin, (falls möglich) die Verwendung von boost::any_range wie folgt zu ändern:
%Vor%
Dies wird dazu führen, dass es eine iterator_category von std::random_access_iterator_tag hat, und führt die Operation wie erwartet aus.

___ qstntxt ___

Ich habe vor kurzem begonnen, die freien Funktionen %code% und %code% explizit zum Kopieren und Inkrementieren / Dekrementieren von Iteratoren zu bevorzugen. Jetzt sehe ich seltsames Verhalten in einem ziemlich speziellen Fall, und ich würde jede Hilfe bei der Entmystifizierung schätzen.

Ich habe eine Interpolations- / Extrapolationsfunktion, die auf einem %code% von einigen %code% arbeitet. Die vollständige Definition des Bereichstyps lautet:
%Vor%
Das %code% wird in diesem speziellen Fall von einem %code% zugewiesen, das zwei Zeiger auf %code% hält, was als %code% Ansicht von ungefähr der Hälfte des %code% Bereichs eines %code% dient. .

Kompilieren meiner Anwendung in MSVC 2010, alles funktioniert gut. Kompiliert man den gleichen Code in MinGW g ++ 4.7.0, so schien es an einem bestimmten Ort zu hängen, auf den ich mich dann (leicht abgekürzt) beschränkt habe:
%Vor%
Als ich den Code in gdb durchging, fand ich heraus, dass es nicht hängen blieb, es dauerte sehr lange, bis ich vom einzelnen %code% Aufruf zurückkam - was in libstdc ++ in %code% implementiert wurde und schließlich in %code% operator.

Indem Sie einfach die %code% -Zeile durch:
ersetzen %Vor%
Die Leistung ist wieder großartig und es gibt praktisch keine Verzögerung.

Ich bin mir des Overheads der Verwendung von Typ-gelöschten Iteratoren bewusst (die von %code% ), aber trotzdem, sollen die beiden obigen Fälle wirklich so unterschiedliche Kosten tragen? Oder mache ich etwas falsch?

___ tag123c ___ C ++ ist eine universelle Programmiersprache. Es wurde ursprünglich als Erweiterung von C entworfen und behält eine ähnliche Syntax, ist aber jetzt eine komplett andere Sprache. Verwenden Sie dieses Tag für Fragen zu Code, der mit einem C ++ - Compiler kompiliert werden soll. ___