3. Abstract Iterator

Abstract Iterator

  • E

    Hallo allerseits.

    Bei meinem letzten Projekt habe ich einen "abstrakten Iterator", den sogenannten Abstract Iterator, geschrieben und bei einem bestimmten Designproblem als Loesung eingesetzt, die mir die Sprache C++ so nicht bieten konnte (und wenn doch, dann moege ich zur Hoelle fahren). Ich will diesen Iterator hier mal vorstellen und auf ein wenig Feedback hoffen. Eventuell kann den Code auch jemand gebrauchen.

    Also. Der "Abstract Iterator" soll die Polymorphie dort unterstuetzen, wo die Sprachmittel nicht mehr weiterhelfen. Mag sein, dass dieser Iterator auch bei anderen Problemen eingesetzt werden kann. Mir ist bislang aber nur eins untergekommen.

    Und das sieht folgendermassen aus: Jemand will eine Datenbank schreiben. Diese soll flexibel sein, denn Flexibilitaet ist in diesem Scenario das A und O. Das wirkt sich selbstverstaendlich auf's Design aus. Beispiel: Die Tabellen (class Table) sollen vielfaeltig sein. Der Anwender soll entscheiden koennen, welche Art von Tabelle benutzt werden soll. Es soll Tabellen geben, die mit einem std::vector, einer std::list oder einem Binary Tree implementiert sind. Wenn ich mich recht entsinne, habe ich das mal bei MySQL gesehen, nicht aber bei MS Access. Die Tabelle 'Kunde' bekommt die Implementierung des Binary Trees verpasst, die Tabelle 'Produkt' die des Vectors. Das muss sich im Design widerspiegeln. Und da OO-Programmierung eine feine Sache ist, entsteht eine abstrakte Basisklasse namens 'Table'. Von Table leiten sich die verschiedenen Implementierungen ab. Hier sind wir schon beim eigentlichen Problem angelangt, wenn wir die Klasse wie folgt gestalten:

    template<class Type> class Table
{
public:
	typedef Type value_type;
	typedef ?? iterator;
	typedef ?? const_iterator;

	virtual void insert(iterator where,value_type const&)=0;
	virtual void erase(iterator where)=0;
	virtual void erase(iterator a,iterator b)=0;
	virtual void clear()=0;
	virtual std::size_t size() const=0;
	virtual std::size_t max_size() const=0;
	virtual iterator begin()=0;
	virtual const_iterator begin() const=0;
	virtual iterator end()=0;
	virtual const_iterator end() const=0;
	virtual ~Table() {}
};

    Die Ableitungen folgen eifrig.

    template<class Type> class Vector_table: 
	public Table<Type>
{
public:
	typedef Type value_type;
	typedef ?? iterator;
	typedef ?? const_iterator;

	void insert(iterator,value_type const&);
	void erase(iterator);
	void erase(iterator,iterator);
	void clear();
	std::size_t size() const;
	std::size_t max_size() const;
	iterator begin();
	const_iterator begin() const;
	iterator end();
	const_iterator end() const;
private:
	std::vector<value_type>	c;
};

template<class Type> class List_table: 
	public Table<Type>
{
public:
	typedef Type value_type;
	typedef ?? iterator;
	typedef ?? const_iterator;

	void insert(iterator,value_type const&);
	void erase(iterator);
	void erase(iterator,iterator);
	void clear();
	std::size_t size() const;
	std::size_t max_size() const;
	iterator begin();
	const_iterator begin() const;
	iterator end();
	const_iterator end() const;

private:
	std::list<value_type> c;
};

    Die Instanziierung findet durch
    Vector_table<Product> products;
    statt.

    Nun ist das obige Design ja erstmal gar nicht umsetzbar, da die oeffentliche Schnittstelle von Table keinen gemeinsamen Iterator mit den Ableitungen teilen kann. Vector_table benutzt einen std::vector<Product>::iterator, die List_table einen std::list<Product>::iterator. Ihr seht schon, wo das Problem liegt.

    Der ganze Trick liegt lediglich darin, den Iteratoren eine identische Schinttstelle und einen gemeinsamen Namen zu verpassen. Der Abstract Iterator ist also nur ein Wrapper mit bidirektionalem Verhalten. Nicht mehr und nicht weniger. Wir setzten die Loesung sogleich ein:

    template<class Type> class Table
{
public:
	typedef Type value_type;
	typedef abstract_iterator<value_type> iterator;
	typedef const_abstract_iterator<value_type> const_iterator;
	...
};

template<class Type> class Vector_table: public Table<Type>
{
public:
	typedef Type value_type;
	typedef abstract_iterator<value_type> iterator;
	typedef const_abstract_iterator<value_type> const_iterator;
	...
};

template<class Type> class List_table: public Table<Type>
{
public:
	typedef Type value_type;
	typedef abstract_iterator<value_type> iterator;
	typedef const_abstract_iterator<value_type> const_iterator;
	...
};

    Das war's.

    Wenn man den Abstract Iterator verwenden will, kann man schreiben:

    std::vector<int> vec;
vec.push_back(3);

abstract_iterator<int> ai = vec.begin();

std::cout<<*ai<<std::endl;

    Die Ausgabe lautet natuerlich nicht 42 sondern 3.

    Eine Implementierung der Methode begin() sieht so aus:

    // Zur Erinnerung:
// Der Typ von Vector_table<Type>::iterator ist ein typedef auf 
// ein abstract_iterator<Type>.
// c ist eine Instanz von std::vector<Type>.

template<class Type> Vector_table<Type>::iterator Vector_table<Type>::begin() 
{	
	return c.begin();	
}

    Es gibt allerdings auch einen Tribut. Wenn der Abstract Iterator einen Iterator erstmal umhuellt hat, ist es nicht moeglich, ihn wieder freizugeben. *Ausser* man weiss den Typ. Was bei der Implementierung der Methode erase(iterator) und allen anderen eigentlich auch der Praxis entspricht:

    // Zur Erinnerung:
// 'iterator' ist vom Typ abstract_iterator<Type>, der wiederum einen 
// std::vector<Type>::iterator umhuellt.

template<class Type> void Vector_table<Type>::erase(iterator where)
{
	// Wir wissen, welchen Typ 'where' umhuellt, da wir 
	// die Implementierung von Vector_table selbst vornehmen.
	c.erase(where.unwrap<std::vector<value_type>::iterator>()); 
}

    Sollte dem Programmierer der Fehler unterlaufen, bei der Methode unwrap() den falschen Templateparameter anzugeben, wird, wie auch bei dynamic_cast, eine Exception geworfen.

    Prinzipiell muesste man den tatsaechlichen Typ zurueckverfolgen koennen.

    RTTI ist fuer die Verwendung notwendig.

    Ich poste mal den Code. Muss sich keiner ansehen. Kann Bugs enthalten. Der Code wurde getestet und fuer funktionstuechtig erklaert (von mir jedenfalls).

    Mir ist wichtig was ihr von der Grundidee haltet, von den Staerken (...oops, muss Singular sein!) und den Schwaechen (unwrap, Performanceabstieg aufgrund der Polymorphie, Zunahme der Programmgroessse, ...). Und ob ihr das jemals benutzen wuerdet.

    Danke.

    Hier ist der Inhalt der "abstract_iterator.h".
    [neue Version draussen.]

    0
  • ?

    welches konstrukt ist:

    void const* get_value_address() const
    {
        return &*it;
    }

    warum return &*it; ?

    0
  • E

    rudolfi schrieb:

    welches konstrukt ist:

    void const* get_value_address() const
    {
        return &*it;
    }

    warum return &*it; ?

    Das ist etwas knifflig.

    Wir wissen, dass man den von Abstract Iterator umschlossenen Iterator nur dann extrahieren kann, wenn man seinen Typ kennt. Bei einem Vergleich (operator==/operator!=) muessen uns beide Typen bekannt sein, um zum Beispiel zwei std::vector<int>::iterator zu extrahieren und miteinander auf Gleichheit zu pruefen.

    Du hast dir den Code angesehen? Dann hast du vielleicht bemerkt, dass nicht einmal das Modul abstract_iterator (bzw. const_abstract_iterator) den tatsaechlichen Typen des umschlossenen Iterators kennt. Das tut nur abstract_iterator_impl (bzw. const_abstract_iterator_impl).

    Dass der Abstract Iterator seine Aufgabe erledigen kann habe ich dem Handle/Body-Idiom zu verdanken (es scheint keine andere Loesung in C++ zu geben, um diese Funktionalitaet realisieren zu koennen).

    Jedenfalls sorgt eben genau dieses Idiom auch dafuer, dass nur abstract_iterator_impl den tatsaechlichen Typ des umschlossenen Iterators kennt. Irgendwann willst du zwei abstrakte Iteratoren auf Gleichheit pruefen. Der eine Iterator wird an die Vergleichsfunktion des anderen uebergeben. Man koennte das so machen, dass man den uebergebenen Parameter (den Iterator) weiter an die impl weiterleitet, um dort weiter zuvergleichen, weil diese impl den tatsaechlichen Typ schon griffbereit hat. Allerdings wuesste diese impl nicht, welchen Typ der andere Abstract Iterator beinhalten wuerde (zum Beispiel um unwrap<??>() aufzurufen und den umschlossenen Iterator zur Vergleichheit zu extrahieren). Also was tun? Jede impl kennt nur den eigenen tatsaechlichen Typ, aber nicht den des anderen.

    Der Trick liegt darin, einfach die Adressen der Objekte zu vergleichen, auf die die Iteratoren verweisen, die von den Wrappern umschlossen werden. Mit

    return &(*it);

    werden diese Adressen ermittelt und verglichen. Im Endeffekt kann man das so verstehen:

    ...
std::vector<int>::iterator i1 = vec.begin(), i2 = vec.begin();

// Statt wie ueblich mit i1 == i2 zu vergleichen, zwingen uns die Umstaende
// des Handle/Body-Idioms sowas zu machen:

(&(*i1)) == (&(*i2))

    Das Endergebnis ist das gleiche.

    0
Anmelden zum Antworten