Wieso Iteratoren statt Zeigern oder statt Indizes?

[Tachyon]

volkard schrieb:

Tachyon schrieb:

Und was passiert bei einem Wraparound des Index? Wenn Du den sinnvoll zulassen willst, hast Du keinen Index mehr, sondern einen Iterator.

Groß genug machen. 64 Bit. Das reicht bei 1000 Milliarden Zugriffen pro Sekunde, uups, nur ein halbes Jahr. 128 Bit reicht aber ne ganze Weile lang.

Ich kann hier keine 64 Bit, geschweige denn 128 Bit. Lösung? Klasse basteln? -> Iteratoren.

[Eisflamme]

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).

volkard:
Gut, das sehe ich ein, das wäre umständlich, inperformant oder speicherfressend. Der iterator wird sich einfach ein paar Infos merken und dann ist halt gut.

Hm... ja, da versagen Indizes dann schließlich in voller Breite. Dann mag ich Iteratoren jetzt vollkommen. Danke, das hat meinem Gesamtprogrammierverständnis ein klein wenig geholfen, glaub ich.

PS: Wieso lösen Iteratoren das Problem mit den 64 Bit? Wenn man nicht mehr adressieren kann, weil zu viel im Speicher liegt, hat man doch sowieso verloren?

[volkard]

Tachyon schrieb:

Ich kann hier keine 64 Bit, geschweige denn 128 Bit. Lösung? Klasse basteln? -> Iteratoren.

Och, aus 16-Bittern sich einen 128-Bitter zu basteln, der ++ kann und was ich hier nicht mache, + und -, das klingt nicht so schwer. * ist schon gemeiner und / ist gemein.

struct StreamIndex{
   unsigned short a,b,c,d;
   Index& operator++(){
      if(!++a)if(!++b)if(!++c)++d;
      return *this;
   }
   ...
};

Hmm, könnte recht lahm werden. Und natürlich, man kann nicht auf Streampositionen lesen, die schon gelesen wurden, also eigentlich ist es ein ForwardOnlyStreamIndex. Das ist schlimm, denn dann ist es doch nur ein Iterator, nur daß man nicht *i schreiben darf, sondern cont[i] schreiben muß und die Algorithmen mehr Übergabeparameter brauchen.

[Tachyon]

volkard schrieb:

[...]

Örks. Da finde ich es irgendwie einfacher, mir einen Iter... ach, lassen wir das.

[Shade Of Mine]

Eisflamme schrieb:

PS: Wieso lösen Iteratoren das Problem mit den 64 Bit? Wenn man nicht mehr adressieren kann, weil zu viel im Speicher liegt, hat man doch sowieso verloren?

Stell dir eine Liste vor, mit unendlich vielen Elementen. zB eine Liste die sich mit Daten aus einer Messstation füllt. Die Station misst ja konstant und liefert dir konstant Daten. Die verwendest du in einem Algorithmus.

Das Problem mit indizes ist nun: irgendwann stehst du an und musst von vorne anfangen mit dem zählen. Bei iteratoren machst du einfach immer ++ und fertig.

[volkard]

Eisflamme schrieb:

PS: Wieso lösen Iteratoren das Problem mit den 64 Bit? Wenn man nicht mehr adressieren kann, weil zu viel im Speicher liegt, hat man doch sowieso verloren?

Vorm Netzwerkstream kommen einfach Objekte, und mit ++it gehe ich in meinem lokalen(!) Puffer weiter und wenn der lokale Puffer ausgelesen ist, werden mit read() oder recv() wieder 4096 Bytes gelesen. Das kann endlos gehen und es gibt gar keinen Überlauf. Es gibt keine Probleme, weil if(it1<it2) gar nicht angeboten wurde. Man braucht nur begrenzten Speicher.
Edit: Und die 4096 Bytes Speicher braucht man nur, um die Sache zu beschleunigen. Es würde auch gehen, bei jedem op++ recv() aufzurufen und Speicher für nur ein Objekt vorzuhalten, das im op* dann herausgegeben wird.

[Tachyon]

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).

Damit erklärst Du Dir ja eigentlich auch schon selbst, wo der Vorteil liegt. Du bist nun schon bei drei Zugriffsarten, während Du über Iteratoren gleichartig auf alles zugreifen kannst. Insbesondere für die generischen Algorithmen ist das schon sehr praktisch.

[knivil]

Indizes sind auch nur Iteratoren ... ich verstehe gar nicht, was das ganze Theater soll.

[volkard]

Shade Of Mine schrieb:

Stell dir eine Liste vor, mit unendlich vielen Elementen.

Aus Dir spricht der Mathematiker.

[Eisflamme]

volkard, ShadeOfMine:
Okay, so habe ich Container bislang noch nie genutzt. Ergibt aber Sinn.

Tachyon:
Meine Lösung über Indizes sagt ja, dass man alles in Indexzugriffsart übersetzen würde, damit hätte man einen einheitlichen Zugriff auch. Iteratoren bieten ebenfalls eine Zugriffsschicht, kennzeichnen das aber klarer als solche. Wenn jeder auf Indizes übersetzt, kann ich auch Indizes an Algorithmen übergeben, daher zählt das Argument für mich nicht.

[Tachyon]

Eisflamme schrieb:

Tachyon:
Meine Lösung über Indizes sagt ja, dass man alles in Indexzugriffsart übersetzen würde, damit hätte man einen einheitlichen Zugriff auch. Iteratoren bieten ebenfalls eine Zugriffsschicht, kennzeichnen das aber klarer als solche. Wenn jeder auf Indizes übersetzt, kann ich auch Indizes an Algorithmen übergeben, daher zählt das Argument für mich nicht.

Du hast aber keine einheitlichen Index-Typen. Bei assoziativen Container können die Indizes nahezu beliebig vielfältig sein. Bau mal generische Algorithmen, welche mit allen potentiel möglichen Arten von Indizes umgehen können.

[Eisflamme]

Wie, keine einheitlichen Indextypen? Ich lasse alles übersetzen auf eine Range von [0..size[ und biete einen getter dafür an, der das versteht. Achso oder meinst Du, dass z.B. so was wie reverse-iterator dann einen zweiten Getter benötigen würde? Das wäre natürlich Mist.

[volkard]

Tachyon schrieb:

Du hast aber keine einheitlichen Index-Typen. Bei assoziativen Container können die Indizes nahezu beliebig vielfältig sein. Bau mal generische Algorithmen, welche mit allen potentiel möglichen Arten von Indizes umgehen können.

Es verdichtet sich zu

class ForwardOnlyIndex...

und die assozialen Container haben zwei (oder noch mehr) op[]-Überladungen, eine davon kann auch op[](ForwardOnlyIndex const& it).

[Tachyon]

Eisflamme schrieb:

Wie, keine einheitlichen Indextypen? Ich lasse alles übersetzen auf eine Range von [0..size[ und biete einen getter dafür an, der das versteht. Achso oder meinst Du, dass z.B. so was wie reverse-iterator dann einen zweiten Getter benötigen würde? Das wäre natürlich Mist.

Naja, bei assoziativen Containern hast Du eigentlich schon Indextypen. Bei einen std::set<T> ist T der Indextyp. Bei einer std::map<K,T> ist K der Indextyp. Du willst das ganze nun doppelt indizieren, also zusätzlich nich einen Ganzzahl-Index zur Verfügung stellen. Ziemlich verwirrend.

[volkard]

Eisflamme schrieb:

Wie, keine einheitlichen Indextypen? Ich lasse alles übersetzen auf eine Range von [0..size[ und biete einen getter dafür an, der das versteht. Achso oder meinst Du, dass z.B. so was wie reverse-iterator dann einen zweiten Getter benötigen würde? Das wäre natürlich Mist.

Nein, er meint, daß die map<AnsiString,double(*)(double)> schon einen operator[](AnsiString const&) hat, also einen op[], wo der Index vom Typ AnsiString ist. AnsiString ist aber als Index für viele Algorithmen extrem unpraktisch.

[Eisflamme]

Oh, achso. Ich gehe eigentlich immer nur über den Key. Die Map ist doch auch darauf optimiert, oder? Wenn man in beide Richtungen mappen will, gibt es doch extra spezielle Container (boost hat doch irgendwas in der Richtung).

[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.