Ordnungsrelation von Random Access Iteratoren
-
Ich implementiere gerade einen Iterator für eine gewisse Datenstruktur. Prinzipiell gibt die Datenstruktur es her, dass man random access haben kann, daher sollte der Iterator auch möglichst ein random access iterator sein. Das passt auch alles, bis auf eine Sache: Der Standard verlangt eine Ordnungsrelation. Genauer gesagt muss es eine Totalordnung für die Iteratoren geben. Mein Problem: Die Information im Iterator (im Prinzip bloß ein Pointer auf ein Element) reicht nicht aus um (ohne große Verrenkungen) zu rekonstruieren, wie sich die Elemente in der Ordnung des Containers zueinander verhalten (es ist eine Baumstruktur).
Nun könnte ich natürlich dem Wortlaut des Standards folgen und einfach die internen Pointer vergleichen, was mir eine totale Ordnung aller Iteratoren geben würde. Aber irgendwie wäre das wohl nicht ganz in dem Sinne, wie es gemeint ist: Der Iterator auf das kleinste Element wäre nicht zwangsläufig der "kleinste" Iterator nach dieser Ordnung. Ebenso käme, wenn ich einen Iterator um einen positiven Betrag erhöhe, nicht unbedingt ein größerer Iterator heraus.Gehe ich da zu weit in meiner Interpretation? Oder habe ich irgendeine Klausel übersehen? Ich hatte das Gefühl, dass mein Iterator mit so einigen Standardalgorithmen nicht laufen würde, obwohl er strenggenommen standardkonform wäre.
-
Wenn Random Acces geht, geht ja auch die Differenz der Iteratoren. Ich weiß nicht, wie die Diferenzfunktion beschaffen ist, aber eventuell reicht es schon, anhand des Vorzeichens der Differenz auf größer oder kleiner zu schließen.
Ansonsten kannst du jedem Iterator noch den Beginn-Iterator mitgeben und über die Differenz zu diesen die Position im Container bestimmen. Ist dann natürlich etwas Overhead im Speicherverbrauch.Ansonsten würde ich bei einem Iterator aber schon davon ausgehen wollen, dass immer
it < it + n, auch wenn man den Standard anders auslegen könnte (fällt dir ein Anwendungsbeispiel ein, wo man eine totale Ordnung braucht, die aber nicht im Zusammenhang mit der Reihenfolge im Container stehen muss?).
-
ipsec schrieb:
(fällt dir ein Anwendungsbeispiel ein, wo man eine totale Ordnung braucht, die aber nicht im Zusammenhang mit der Reihenfolge im Container stehen muss?).
Eben nicht. Der ganze Teil im Standard ist ohne Interpretation eher sinnlos, weswegen ich mich frage, ob ich da was übersehen habe.
Wenn Random Acces geht, geht ja auch die Differenz der Iteratoren.
Hehe, ja das geht, ist aber aus den gleichen Gründen nicht so ganz einfach. Ist jedenfalls eine sehr teure Aktion, sofern ich nicht anfange, ansonsten unnötige Hilfsvariablen für diesen einen Fall mitzuschleppen.
-
Wenn auch Differenz nicht geht, ist es aber dann mit Sicherheit kein Random-Access-Iterator mehr. Und da gibt es auch definitiv Standardalgorithmen, die daran dann versagen.
Unter dem Aspekt würde ich einen normalen Bidirectional-Iterator daraus machen, aber optimierte Versionen von
advanceund Konsorten anbieten.
-
ipsec schrieb:
Unter dem Aspekt würde ich einen normalen Bidirectional-Iterator daraus machen, aber optimierte Versionen von
advanceund Konsorten anbieten.Was ich streng nach Standard natürlich auch nicht darf
.Vielleicht sollte ich auch einfach den Frosch schlucken und die Hilfsvariable mitschleppen.
-
Ich kann nicht erkennen, dass < an ++ gekoppelt sein muss; man denke z.B. an Ringpuffer.
-
Ich frage mich, wie solche Dinge wie
std::nth_elementohne klare Ordnung funktionieren sollen.
-
camper schrieb:
Ich kann nicht erkennen, dass < an ++ gekoppelt sein muss; man denke z.B. an Ringpuffer.
Ich verstehe die Aussage irgendwie nicht.
-
camper schrieb:
Ich kann nicht erkennen, dass < an ++ gekoppelt sein muss; man denke z.B. an Ringpuffer.
Ich erkenne Dein Argument nicht.
Jedes push_back zerstört die bisherige Iterator-Ordnung.
-
volkard schrieb:
camper schrieb:
Ich kann nicht erkennen, dass < an ++ gekoppelt sein muss; man denke z.B. an Ringpuffer.
Ich erkenne Dein Argument nicht.
Jedes push_back zerstört die bisherige Iterator-Ordnung.Das meinte ich nicht. Allerings ist mein Argument auch keins, also schnell wieder vergessen.
