3. Iterator implementieren

Iterator implementieren

  • B

    Hallo!

    Ich brauche einen bidirektionalen Iterator, mit dem ich über Daten iterieren
    kann, die nicht in einem Container liegen, sondern erst online bei Zugriff
    berechnet werden. Hier ein Minimalbeispiel:

    class testClass
{
int aNumber;

int nextNumber()
{
 ++aNumber;
 return aNumber;
}

int prevNumber()
{
 --aNumber;
 return aNumber;
}

};

main()
{
 testClass foo;
 for(testClass::iterator it=foo.begin();it!=foo.end();++it)
 {
   cout << (*it);
 }
}

    Klar, in diesem Minimal-Beispiel könnte ich eine Funktion "int access(bool
    direction)" rausgeben, die Lesezuriff erlaubt. Ein Iterator scheint mir
    aber eleganter und allgemeiner. Wie implementiert man sowas?

    lg

    0
  • Mod

    Ein bidirektionaler Iterator ist einfach nur eine Klasse, welche die folgenden Operationen sinnvoll implementiert:
    Kopierkonstruktor
    Inkrementierung mittels ++ (Prefix und Postfix)
    Prüfung auf Gleichheit/Ungleichheit mittels == und !=
    Dereferenzierung mittels * oder -> als rvalue
    Dereferenzierung mittels * als lvalue
    Defaultkonstruktor
    Dekrementierung mittels -- (Prefix und Postfix)

    Du musst dir überlegen wie diese Operationen sinnvoll in deinem Problem umgesetzt werden können und dann einfach implementieren.

    edit: Hier findest du eine Übersicht, welche Iteratoren welche Operationen implementieren müssen:
    http://www.cplusplus.com/reference/std/iterator/
    Dort findest du auch das Klassentemplate 'iterator', das selbst zwar noch nichts tut, das dir aber, wenn du davon erbst, das richtige Interface vorgibt. Bei der Klassenbeschreibung gibt es auch ein Beispiel für eine sehr einfache Iteratorklasse.

    0
  • B

    Danke, das Example http://www.cplusplus.com/reference/std/iterator/iterator/ ist spitze.

    lg

    0
  • S

    Um 100% kompatibel zum Rest der Standard-Bibliothek zu sein, solltest Du entweder in Deiner Klasse entsprechende typedefs für difference_type, value_type, pointer, reference, iterator_category anbieten oder einfach std::iterator_traits für Deinen Iterator spezialisieren. Letzteres ist wahrscheinlich am besten, da Du schlecht pointer und reference sinnvoll definieren kannst. Ich bin mir gerade nicht sicher, aber ich denke, nicht alle diese Typen sind Pflicht -- kommt aber wahrscheinlich auf die Iterator-Kategorie an.

    Als Kategorie solltest Du vielleicht einen InputIterator nehmen. Deine Elemente stehen nicht wirklich irgendwo alle gleichzeitig im Speicher, und alles über InputIterator (also Forward, Bidi, RandomAccess) muss laut Standard beim Dereferenzierungsoperator eine Referenz zurückgeben. InputIterator hingegen kann auch etwas anderes zurückgeben, was dann nur zu value_type konvertierbar sein muss.

    Gruß,
    SP

    0
  • U

    auch, wenns hier nicht um mich geht:

    SP schrieb:

    [...]std::iterator_traits für Deinen Iterator spezialisieren. Letzteres ist wahrscheinlich am besten, da Du schlecht pointer und reference sinnvoll definieren kannst.

    wie meinst du das?
    ob man iter-traits spez oder die typedefs ordentlich typedef-t ist doch dabei völlig egal - machen muss man es ja eh?
    und typedef int* pointer; sollte ja nun nicht das prob sein, oder was hab ich hier falsch verstanden?^^

    bb

    0
  • S

    unskilled schrieb:

    auch, wenns hier nicht um mich geht:

    SP schrieb:

    [...]std::iterator_traits für Deinen Iterator spezialisieren. Letzteres ist wahrscheinlich am besten, da Du schlecht pointer und reference sinnvoll definieren kannst.

    wie meinst du das?
    ob man iter-traits spez oder die typedefs ordentlich typedef-t ist doch dabei völlig egal - machen muss man es ja eh?

    Man könnte std::iterator_traits spezialisieren und einige typedefs weglassen, wenn man das will. Ob das eine gute Idee ist, weiß ich nicht. Ich hatte mich damit bisher nicht richtig auseinander gesetzt.

    Ein Blick in den Standard verrät, dass die Idee folgende ist:

    typeid(reference)       == typeid(*it)
typeid(pointer)         == typeid(it->)
typeid(difference_type) == typeid(it-it)

    wobei value_type und iterator_category auch "ordentlich" gesetzt sein sollten, (value_type sollte nie cv-qualifiziert sein).

    Ein OutputIterator darf allerdings alles außer iterator_category auf void setzen.

    Wie man diese typedefs bei einer "prozedural erzeugten Sequenz", bei der die Elemente nicht wirklich im Speicher stehen sondern on-the-fly erzeugt werden, sinnvoll definiert ist mir trotzdem nicht 100%ig klar. Vielleicht so ...

    class nniter // natural number iterator
{
  long v;
public:
  typedef std::random_access_iterator_tag iterator_category;
  typedef long value_type;
  typedef long const& reference;
  typedef long const* pointer;   // Typ von &*iter
  typedef long difference_type;

  nniter() : v(0) {}

  reference operator*() const {return v;}

  ...
};

    Der Haken ist allerdings, dass die von operator* zurückgegebene Referenz ungültig wird, wenn der Iterator zerstört wird. Alternativ dazu

    class nniter // natural number iterator
{
  long v;
public:
  typedef std::random_access_iterator_tag iterator_category;
  typedef long value_type;
  typedef long reference;
  typedef void pointer;   // Ausdruck &*iter ill-formed, daher void
  typedef long difference_type;

  nniter() : v(0) {}

  long operator*() const {return v;}

  ...
};

    Der Haken ist allerdings, dass reference wirklich eine Referenz sein sollte, falls es sich um einen ForwardIterator oder höher handeln sollte.

    Gruß,
    SP

    0
Anmelden zum Antworten