3. 2-Iterator-Design

2-Iterator-Design

  • A

    Ich versuche, einen STL-kompatiblen B-Baum zu programmieren, der ein ähnliches Verhalten wie std::map zu Tage bringen soll. In einem früheren Thread kam bei mir das Thema schon mal in diese Richtung, aber nun frage ich lieber doch mal ausführlich:

    Ich habe eine Tree-Klasse als Interface, eine Node-Klasse, die den Root und andere Knoten repräsentiert und nun will ich einen Iterator und einen Konstanten Iterator hinzufügen.
    In der Node-Klasse befindet sich ein std::vector mit den Schlüssel/Wert-Paaren ( std::pair ) als Zeiger, da sie ja vom Allokator erzeugt werden. Der ist logischerweise privat, also sind Forward-Deklarationen der Iteratoren als friends zu finden:

    template < ... elend lang ... >
class node {
private:
   std::vector<pointer> keyval;

   ...

public:
   template < ... auch lang ...>
   friend class tree_iterator;

   template < ... auch lang ...>
   friend class const_tree_iterator;

   typedef tree_iterator<blaaaa> iterator;
   typedef const_tree_iterator<blubblub> const_iterator;

   ...
};

    So, jetzt haben die beiden Iteratoren Zugriff auf den Vektor, den sie ja benötigen. Um aber ein solches Schlüssel/Wert-Paar im Baum zu addressieren, muss ich ja nicht nur einen Iterator auf diesen Vektor, sondern auch einen zeiger auf den Node, in dem sich der Vektor befindet, im Iterator speichern. Die beiden Iteratoren haben also jeweils 2 Membervariablen:

    template < sehr lang>
class const_tree_iterator : public std::iterator<std::bidirectional_iterator_tag, typename std::vector<paar*>::const_iterator >
{
private:
   const node* curr_node; // Zeiger auf den aktuellen Knoten im Baum
   value_type curr_elem; // Vom Typ std::vector<paar*>::const_iterator, um das Element komplett zu addressieren

public:
   // Konstruktoren und Operatorüberladungen ...
};

    Das ist der konstante Iterator, der auch soweit erst mal funktioniert. In den Standard-Header-Files von VS habe ich mal dem Iterator von std::vector auf die Finger geschaut. Dort erbt tatsächlich der nicht-konstante Iterator vom Konstanten öffentlich, um nicht alles doppelt definieren zu müssen. Ist das eine gute Idee? Wirkt die Beziehnung "Ein Iterator ist ein Konstanter Iterator" nicht irgendwie falsch?

    0
  • ?

    Und die Implementierung sagt dir nicht, was es bringt?
    Ansonsten hat Meyers einen netten Aufsatz über Iteratoren-Verwendung geschrieben, vllt interessiert dich das ja (keine Ahnung ob es dich in deiner Einschätzung der Vererbung im konkreten Fall weiter bringt).

    http://www.aristeia.com/Papers/CUJ_June_2001.pdf

    0
  • C
    Mod

    Ad aCTa schrieb:

    Ist das eine gute Idee?

    Eine gute Idee? Wahrscheinlich nicht - weil es einige naive Annahmen über das Verhältnis von iteratoren und const_iteratoren verletzt. Es widerspricht aber wahrscheinlich nicht dem Standard - schließlich ist es bei set und multiset sogar zulässig, dass iterator und const_iterator den gleichen Typ haben.

    Ad aCTa schrieb:

    Wirkt die Beziehnung "Ein Iterator ist ein Konstanter Iterator" nicht irgendwie falsch?

    Das ist keine solche Beziehung sondern ein reines Implementationsdetail.
    Öffentliche Vererbung bedeutet nicht "ist ein" - es sei denn, man übertreibt, um auf etwas hinzuweisen: öffentliche Vererbung ist für gewöhnlich gerechtfertigt, wenn zwischen den Klassen ein "ist ein"-Verhältnis besteht, wenn es um polymorphe Klassen geht.
    Mit Polymorphie hat dieser Fall aber nichts zu tun.

    0
  • ?

    camper schrieb:

    Ad aCTa schrieb:

    Ist das eine gute Idee?

    Eine gute Idee? Wahrscheinlich nicht - weil es einige naive Annahmen über das Verhältnis von iteratoren und const_iteratoren verletzt. Es widerspricht aber wahrscheinlich nicht dem Standard - schließlich ist es bei set und multiset sogar zulässig, dass iterator und const_iterator den gleichen Typ haben.

    Ich denke, es ist anders rum (const_iterator von iterator erben lassen) einfach zu gefährlich, es macht den const_iterator nutzlos. Denn so ist es möglich einen const_iterator in einen iterator zu casten.

    Gcc hat eine template-Klasse __normal_iterator. Es gibt keine Ableitung.
    In vector selber steht dann sowas:

    typedef __gnu_cxx::__normal_iterator<pointer, vector> iterator;
typedef __gnu_cxx::__normal_iterator<const_pointer, vector> const_iterator;

    Ist wahrscheinlich sauberer...

    0
  • A

    In einem gewissen Sinne ist es auch meine Absicht gewesen, einen konstanten Iterator in einen Nicht-konstanten zu verwandeln. Der Artikel zeigte aber, dass es allgemein keine solche Konvertierungsrichtung gibt.
    Das Problem ist, dass ich den Suchalgorithmus in meinem Baum mit const_tree_iterator arbeiten lassen wollte, da bei der Suche ja nichts verändert wird. So funktionierte es erst mal:

    const_iterator find(const key_t& k) const {
	return root_ptr->search(k); // Rufe den Algorithmus auf
}

    Die nicht-konstante Variante wollte ich dann so anbieten:

    iterator find(const key_t& k) {
   return iterator(static_cast<const tree*>(this)->find(k)); // Caste mich zu const und rufe die andere, überladene Memberfunktion auf
}

    Aber das geht ja nicht, einen solchen Konstruktor kann ich nicht anbieten. Sollte ich es nun anders herum machen? Sollen die Algorithmen (also die Memberfunktionen) immer mit iterator arbeiten, sodass ich dann einfach einen Konvertierungskonstruktor iterator --> const_iterator erstelle? Also genau umgedreht:

    iterator find(const key_t& k) {
   return root_ptr->search(k);
}

const_iterator find(const key_t& k) const {
   return const_cast<tree>(this)->find(k);
}

    Eigentlich soll es ja der Anfang für eine Datenbank sein, nur leider komme ich immer an den C++-Formalien nicht weiter. 😃 :xmas2:

    0
Anmelden zum Antworten