Wieso Iteratoren statt Zeigern oder statt Indizes?

krümelkacker

Eisflamme schrieb:

Okay. Bäume sind neben Random-Access und verketteten Listen ja eine weitere "Zugriffsart" (wenn man das so benennen möchte, zumindest muss man hier für neu überlegen und das möchte ich mit dem Begriff hier ausdrücken).

Ich würde das nicht Zugriffsart nennen, sondern einfach Datenstruktur. Das, was all die Datenstrukturen (ich meine speziell die STL-Container damit) gemeinsam haben, ist, dass sie ein oder mehrere Element(e) speichern. Und die "Zugriffsart", die all diese Container anbieten, ist die eines "Bidi-Iterators", von dem man sich von Element zu Element vor- und zurückhangeln kann. Darüber hinaus bietet ein solcher Iterator ggf noch einen Indexoperator an, sofern dadurch ein Zugriff in konstanter Zeit möglich ist.

Das einzige, was mich an Iteratoren nervt, ist, dass man immer zwei davon braucht, um eine Sequenz mit Anfang und Ende beschreiben zu können. Von daher gefiel mir eigentlich Andrei's Ansatz, das, was zwei Iteratoren eisten, als eigene/neue Abstraktion einzuführen. Beispiel:

class forward_range
{
  ...
  ...
public:
  typedef ... value_type;
  typedef ... reference;
  ...
  bool empty() const;
  void pop_front();
  reference front() const;
};

...

template<class Range>
void show(Range r)
{
  cout << "Sequenz geht los...\n";
  while (!r.empty()) {
    cout << r.front() << '\n';
    r.pop_front();
  }
  cout << "Das war's schon\n";
}

Vom Konzept her hatte "Range" wie Iteratoren auch so etwas wie "Referenz-Semantik", also, Ranges wären dann auch leichtgewichtige Objekte, die man fix kopieren kann, wobei sich die Kopie dann immer noch auf dieselbe Sequenz bezieht und ein ++ (bzw pop_front) den Container nicht verändert, sondern nur den Iterator (bzw das Range-Objekt). Das schöne ist jetzt, dass wir nur noch ein Objekt haben und man könnte dann so Dinge schreiben wie

list<int> primzahlen_unter_1000 = ...;
  show(reverse(primzahlen_unter_1000.all()));

wobei reverse dann etwas der folgenden Art machen könnte:

template<class BaseRange>
class reversed_range
{
  BaseRange rng_;
  ...
public:
  ...
  bool empty() const { return rng_.empty(); }
  void pop_front() {rnd_.pop_back();}
  void pop_back() {rnd_.pop_front();}
  reference front() const { return rng_.back(); }
  reference back() const { return rng_.front(); }
  ...
};

template<class Rng> reversed_range<Rng> reverse(Rng r);
template<class Rng> Rng reverse(reversed_range<Rng> r);

Ich denke, man kann sich gut vorstellen, wie man dann on-the-fly und ohne großen Aufwand diverse "lazy Filter" auf ranges laufen lassen kann. Wenn man zwei Iteratoren hat und sich per boost::transform_iterator oder boost::filter_iterator einen neuen zusammenbauen will, ist das eher ein Krampf. Das Funktionsobjekt/Prädikat liegt dann auch zweimal vor (in jedem Iterator) statt nur einmal im Range-Objekt.

Anderer Vorteil ist, dass man nicht mehr versehentlich zwei Iteratoren als Range behandelt, die gar nichts miteinander zu tun haben.

kk

Tachyon

krümelkacker schrieb:

[...]

Naja, im Prinzip hast Du das doch mit boost.range . Inzwischen gibt es da sogar die Adaptoren (seit 1.44, glaube ich) mit denen man ein paar zusätzliche nette Konzepte bekommt:

std::vector<MysticType> dataVector;
std::list<MysticType> dataList;

boost::copy(dataVector | boost::adaptors::strided(2), std::back_inserter(dataList)); //jeden zweiten Wert in dataList einfuegen.

Überall da, wo ein Range erwartet wird, kann man ein std::pair<T,T>(begin, end) benutzen. Eigentlich ganz praktisch.

PS: Man kann das auch nett kombinieren:

boost::copy
   ( dataVector | boost::adaptors::reversed | boost::adaptors::strided(2) ////jeden zweiten Wert in dataList in umgekehrter Reihenfolge einfuegen
   , std::back_inserter(dataList));

Eisflamme

mrr... ist das eine intuitive Operatorenüberladung?

Tachyon

Eisflamme schrieb:

Wie war das mit Operatoren nur intuitiv überladen?

Wenn man Pipes kennt, ist das sehr intuitiv.

Eisflamme

Mach mich nur fertig. ^^

Aber ist | in C++ standardmäßig als Pipe-Operator gedacht? Es geht doch um die Intuitivität eines C++-Operators in dem, was man darunter normalerweise versteht. Und | ist für mich XOR oder Flags verknüpfen.

Tachyon

Eisflamme schrieb:

Mach mich nur fertig. ^^

Aber ist | in C++ standardmäßig als Pipe-Operator gedacht? Es geht doch um die Intuitivität eines C++-Operators in dem, was man darunter normalerweise versteht. Und | ist für mich XOR oder Flags verknüpfen.

Nein, standardmäßig nicht. Aber auch nicht als XOR. Trotzdem finde ich das jetzt nicht sonderlich unübersichtlich. Vielleicht hätte man da operator>> nehmen sollen. Aber wie gesagt: Ich finde die Pipe-Idee jetzt nicht so verwerflich.

ipsec

Dann verknüpfst du halt die Range mit einem Strided-Flag. Ist m.E. auch intuitiv.
Zumindest ist es intuitiv genug, dass man beim ersten Blick erahnen kann, was passiert und es nach dem zweiten Blick in die Doku nicht mehr vergisst. Das ist m.E. ausreichend.

Eisflamme

Hm... nach der Definition könnte man viel Unsinn treiben, glaube ich. Aber ich schweige dazu stille, bis ich bessere Argumente habe oder vollends überzeugt bin.

volkard

Tachyon schrieb:

Ich finde die Pipe-Idee jetzt nicht so verwerflich.

Man hat sich dran gewöhnt. Ist halt typisch boost. Verspielte Lösung mit vielen neuen nur für diese eine sub-lib benötigten Begriffen und kaum Mehrwert. Hier möglicherweise sogar mal Null Mehrwert, also ich kann mich geade nicht daran erinnern, daß ich mal jeden zweiten Wert gebraucht hätte.

Tachyon

volkard schrieb:

Tachyon schrieb:

Ich finde die Pipe-Idee jetzt nicht so verwerflich.

Man hat sich dran gewöhnt. Ist halt typisch boost. Verspielte Lösung mit vielen neuen nur für diese eine sub-lib benötigten Begriffen und kaum Mehrwert. Hier möglicherweise sogar mal Null Mehrwert, also ich kann mich geade nicht daran erinnern, daß ich mal jeden zweiten Wert gebraucht hätte.

Ich brauche es ständig. Sogar an Stellen, an denen es schnell gehen muss. So unterschiedlich können die Bedürfnisse sein. Man glaubt es kaum.

volkard

Tachyon schrieb:

volkard schrieb:

Tachyon schrieb:

Ich finde die Pipe-Idee jetzt nicht so verwerflich.

Man hat sich dran gewöhnt. Ist halt typisch boost. Verspielte Lösung mit vielen neuen nur für diese eine sub-lib benötigten Begriffen und kaum Mehrwert. Hier möglicherweise sogar mal Null Mehrwert, also ich kann mich geade nicht daran erinnern, daß ich mal jeden zweiten Wert gebraucht hätte.

Ich brauche es ständig. Sogar an Stellen, an denen es schnell gehen muss. So unterschiedlich können die Bedürfnisse sein. Man glaubt es kaum.

Speicherst Du key/value-Paare in Arrays mit keys an gerade-zahligen Indizes und values an den ungeraden?

Tachyon

volkard schrieb:

Speicherst Du key/value-Paare in Arrays mit keys an gerade-zahligen Indizes und values an den ungeraden?

Nein. Ich multipliziere jeden n-ten Wert mit einem passenden Koeffizienten, um ein ganzzahliges Upsampling zu erreichen. Nur so als Beispiel.

volkard

Tachyon schrieb:

Nein. Ich multipliziere jeden n-ten Wert mit einem passenden Koeffizienten, um ein ganzzahliges Upsampling zu erreichen. Nur so als Beispiel.

Verstehe ich nicht.
Wenn ich http://de.wikipedia.org/wiki/Upsampling anschaue, wo nehmen die jeden n-ten Wert?
Wie sähe so ein Upsampling wie auf Wikipedia gezeigt, mit den Boost-Pipes aus?

Tachyon

volkard schrieb:

Wenn ich http://de.wikipedia.org/wiki/Upsampling anschaue, wo nehmen die jeden n-ten Wert?

Ich stimmte Dir zu. Der Mehrwert der Multplikationen mit Null ist gigantisch. Ich ändere mal und mutlipliziere doch jeden Wert. Den Code für die Range basierte Faltung packe ich jetzt nicht hier ins Forum. Aber ich bin zuversichtlich, dass Du das auch selbst hinbekommst.

volkard

Tachyon schrieb:

Ich stimmte Dir zu. Der Mehrwert der Multplikationen mit Null ist gigantisch. Ich ändere mal und mutlipliziere doch jeden Wert.

Aha!
Statt erst std::copy und dann std::transform kann man mit Expression Templates beide verbinden und nur einmal laufen, was gut für die lahmen Ram-Zugriffe ist. Der Vorteil liegt nicht in der seltsamen Syntax, sondern sie ist Folge des Bemühens umd mehr Compilzeitlogik. Sag das doch gleich.

Tachyon

volkard schrieb:

Tachyon schrieb:

Ich stimmte Dir zu. Der Mehrwert der Multplikationen mit Null ist gigantisch. Ich ändere mal und mutlipliziere doch jeden Wert.

Aha!
Statt erst std::copy und dann std::transform kann man mit Expression Templates beide verbinden und nur einmal laufen, was gut für die lahmen Ram-Zugriffe ist. Der Vorteil liegt nicht in der seltsamen Syntax, sondern sie ist Folge des Bemühens umd mehr Compilzeitlogik. Sag das doch gleich.

Naja, man spart sich Mutliplikationen und Dereferenzierungen. Zusätzliches Kopieren ist auch ziemlich übeflüssig, weil man das in einem Rutsch machen kann. Würdest Du wirklich echt nullen einfügen? Ehrlich jetzt?

volkard

Tachyon schrieb:

Würdest Du wirklich echt nullen einfügen? Ehrlich jetzt?

Ich kenne die Aufgabe nicht. Wenn sich Nullen-Einfügen lahm anfühlt, würde ich es wohl nicht machen.

Tachyon

volkard schrieb:

Tachyon schrieb:

Würdest Du wirklich echt nullen einfügen? Ehrlich jetzt?

Ich kenne die Aufgabe nicht. Wenn sich Nullen-Einfügen lahm anfühlt, würde ich es wohl nicht machen.

Es ist genau das Upsampling wie bei Wikepedia beschrieben. Nur muss man es nicht auf die Brute-Force-Methode implementieren. Man bekommt das deutlich besser hin, ohne die vorhandene Flexibilität zu verlieren.
Anstatt n Nullen enzufügen kannst Du auch jeden n-ten Koeffizienten multiplizieren und die resultierende Summe gleich in den Zielvektor schreiben. Das spart tatsächlich erstaunlich viel Zeit. Du sparst Dir nicht nur Kopiererei sondern auch Dereferenzierungen und Multiplikationen, wie gesagt.

volkard

Tachyon schrieb:

volkard schrieb:

Tachyon schrieb:

Würdest Du wirklich echt nullen einfügen? Ehrlich jetzt?

Ich kenne die Aufgabe nicht. Wenn sich Nullen-Einfügen lahm anfühlt, würde ich es wohl nicht machen.

Es ist genau das Upsampling wie bei Wikepedia beschrieben. Nur muss man es nicht auf die Brute-Force-Methode implementieren. Man bekommt das deutlich besser hin, ohne die vorhandene Flexibilität zu verlieren.
Anstatt n Nullen enzufügen kannst Du auch jeden n-ten Koeffizienten multiplizieren und die resultierende Summe gleich in den Zielvektor schreiben. Das spart tatsächlich erstaunlich viel Zeit. Du sparst Dir nicht nur Kopiererei sondern auch Dereferenzierungen und Multiplikationen, wie gesagt.

Das sagt mir leider gar nichts. Bin weiter neugierig, wie das mit den Pipes aussieht. Falls es mir tatsächlich gelingen sollte, den Code zu verstehen, würde ich mir überlegen können, ob er sich ohne Pipes auch hübsch anfühlen würde.

Ich würde wohl keine Nullen einfügen, um sie gleich darauf wieder durch richtige Werte zu ersetzen. Nur weiß ich gar nicht, wie man die richtigen Werte berechnet.

edit: Alles zurück. Hast recht. Für Signalverarbeitung würde ich auch so vorgehen.

Tachyon

Ich bin mir nicht so sicher, ob es eine gute Idee ist, den Code hier zu posten, da es für meinen Arbeitgeber ist. Der ist normalerweise nicht so glücklich, wenn man irgendwelche Produktivcode ins Netz packt. Das hat nichtmal was damit zu tun, dass das nun so großartig speziell ist. Ist es nicht.
Grundsätzlich geht es so, dass Du jeden n-ten Koeffizienten pro Faltung multiplizierst. Der Index für den Datenvektor (also das, was hochgetastet werden soll) geht alle n Faltungen eins weiter, wobei n die Anzahl der virtuell eingefügten Nullen ist. Innerhalb Deiner Koeffizienten hast Du außerdem noch einen Offset, der von der Position der aktuell indizierten virtuellen Null abhängig ist. Mit mit den slice- und stride Adaptoren kann man sich dann die passenden Koeffizienten rauspicken. Geht natürlich auch ohne von Hand, aber mit den Adaptoren ist das relativ einfach.
Mal es Dir vielleicht einfach mal auf ein Blatt Papier (mit echten Nullen) und schiebe ein Filter an den Daten vorbei. Dabei begucke Dir, welche Koeffizienten mit Werten ungleich null multipliziert werden. Dabei sollte das Prinzip theoretisch klar werden.