C++-Programmierung/ Eine Matrix-Bibliothek – mitrax/ Iteratoren für die Proxys
In diesem Kapitel werden wir uns mit der Erstellung eigener Iteratorklassen beschäftigen und die Schnittstellen der Proxyklassen vervollständigen. Der Nutzer von mitrax sollte mit den Iteratorklassen selbst, keinen direkten Kontakt haben, daher werden wir diese vollständig im Namensraum detail platzieren. Wir werden diese Tatsache im folgenden nicht jedes mal explizit wieder erwähnen. Sofern nicht anderes angegeben, gehören die Inhalte dieses Kapitels in die Datei proxy_iterator.hpp. Da alles in dieser Datei im Namensraum detail liegt, befindet sich proxy_iterator.hpp in einem Unterverzeichnis detail/.
Einführung zu Iteratoren
BearbeitenEhe wir uns der Entwicklung unserer Iteratorklassen widmen, wollen wir uns ansehen, was Iteratoren eigentlich sind. Vielleicht ist Ihnen bekannt, dass jeder Zeiger auch ein Iterator ist. Jedoch ist nicht jeder Iterator auch ein Zeiger. Iteratoren sind abstrakte Objekte, die, je nachdem zu welcher Iteratorkategorie sie gehören, bestimmte Eigenschaften besitzen müssen. Jedes Objekt, das die Eigenschaften einer Iteratorkategorie erfüllt, ist ein Iterator der entsprechenden Kategorie. Zeiger erfüllen beispielsweise alle Eigenschaften, die ein Random-Access-Iterator besitzen muss.
C++ kennt standardmäßig fünf Iteratorkategorien. Die einfachsten sind Input- und Output-Iteratoren. Darüber stehen die Forward-Iteratoren, sie erfüllen alle Anforderungen, die an Input-Iteratoren gestellt werden. Die Bidirectional-Iteratoren erfüllen alle Anforderungen, die an Forward-Iteratoren gestellt werden und schließlich erfüllen Random-Access-Iteratoren alle Anforderungen, die an Bidirectional-Iteratoren gestellt werden. Jede dieser Kategorien macht natürlich noch zusätzlich Vorgaben, welche Ausdrücke nutzbar sein müssen. Iteratoren die zusätzlich die Anforderungen erfüllen, die an Output-Iteratoren gestellt werden, bezeichnet man als veränderliche Iteratoren, alle anderen werden als konstante Iteratoren bezeichnet. Jede dieser Iteratorkategorien wird durch ein sogenanntes Iterator-Tag repräsentiert. Die fünf Iterator-Tags, die in der Standard-Headerdatei iterator definiert sind, hängen wie folgt zusammen:
struct input_iterator_tag{};
struct output_iterator_tag{};
struct forward_iterator_tag: public input_iterator_tag{};
struct bidirectional_iterator_tag: public forward_iterator_tag{};
struct random_access_iterator_tag: public bidirectional_iterator_tag{};
Vielleicht fragen Sie sich, warum forward_iterator_tag nicht auch von output_iterator_tag abgleitet ist. Dies liegt daran, dass die Ausgabe auf einen Iterator, wie bereits erwähnt, zusätzlich zur Eingabe erfüllt sein kann. Nehmen wir als Beispiel die Iteratoren des Containers std::vector. Dieser bietet Random-Access-Iteratoren an. Iteratoren vom Typ std::vector< T >::iterator sind sowohl Input-, als auch Output-Iteratoren, wohingegen Iteratoren vom Typ std::vector< T >::const_iterator ausschließlich Input-Iteratoren sind. Obgleich es sich auch bei diesen um Random-Access-Iteratoren handelt, ist ein Schreiben über diese unmöglich. Eben deshalb werden diese Iteratoren auch als konstant bezeichnet, während es sich bei std::vector< T >::iterator um veränderliche Iteratoren handelt.
Für alle Iteratoren sind fünf Typen als sogenannte Iterator-Traits (auf Deutsch etwa Eigenschaften oder Charakteristika) definiert. Diese können über das Template std::iterator_traits< Iterator > abgefragt werden. value_type ist der Typ, der bei einer Dereferenzierung zurückgegeben wird. reference ist eine Referenz und pointer ein Zeiger auf diesen Typ. difference_type ist ein vorzeichenbehafteter ganzzahliger Datentyp, der eine Entfernung zwischen zwei Iteratoren aus dem gleichen Bereich beschreibt. iterator_category ist ein typedef auf eines der fünf Iterator-Tags. Wenn wir einen neuen Iterator entwerfen, müssen wir das Template std::iterator_traits nicht spezialisieren. Wir müssen diese fünf typedefs lediglich innerhalb unserer Iteratorklassen anbieten. Die allgemeine Implementation von std::iterator_traits sieht nämlich folgendermaßen aus:
template< typename Iterator >
struct iterator_traits{
typedef typename Iterator::difference_type difference_type;
typedef typename Iterator::value_type value_type;
typedef typename Iterator::pointer pointer;
typedef typename Iterator::reference reference;
typedef typename Iterator::iterator_category iterator_category;
};
Ein Iterator b wird als, von einem Iterator a aus, erreichbar bezeichnet, wenn durch eine endliche Anwendung von ++a, die Bedingung b == a wahr wird. Die beiden Iteratoren befinden sich dann in der gleichen Sequenz. Jeder Iterator, für den der Ausdruck *a ein gültiges Objekt liefert, wird als dereferenzierbar bezeichnet. Für jede Sequenz von Iteratoren, muss ein Iterator existieren, der hinter das letzte Element zeigt. Dieser muss nicht dereferenzierbar sein.
Nun wollen wir uns noch die Eigenschaften ansehen, die Iteratoren der verschiedenen Kategorien erfüllen müssen. Alle Iteratoren müssen einen value_type besitzen, der kopierkonstruierbar, kopierzuweisbar und destruierbar ist. Außerdem müssen zwei Objekte von value_type mittels swap() vertauschbar sein. Beachten Sie, dass dies nicht zwingend std::swap() sein muss. Wenn iterator_type der Typ eines Iterators und a ein Objekt dieses Typs ist, dann muss der Ausdruck *a eine Referenz auf value_type zurückgeben, vorausgesetzt, der Iterator zeigt auf ein gültiges Objekt. Andernfalls ist das Verhalten, wie bei ungültigen Zeigern, undefiniert. Der Ausdruck ++a muss eine Referenz auf iterator_type zurückgeben.
Für zwei Input-Iteratoren a und b des gleichen Typs muss der Vergleichsoperator auf Gleichheit definiert sein. Der Vergleichsoperator auf Ungleichheit muss ebenfalls definiert sein und dem Verhalten des Ausdrucks !(a == b) entsprechen. Beide müssen einen Typ zurückgeben, der implizit in bool konvertiert werden kann. Der Ausdruck *a muss einen Typ zurückgeben, der implizit in value_type konvertierbar ist. Wenn a dereferenzierbar ist, müssen die Ausdrücke a->m und (*a).m identisch sein. Nach Anwendung des Ausdrucks ++a auf einen dereferenzierbaren Iterator a, muss a entweder wieder dereferenzierbar sein, oder hinter das letzte Element einer Sequenz zeigen. Die Ausdrücke (void)++a und (void)a++ müssen identisch sein. Der Ausdruck *a++ muss einen Typ zurückgeben, der implizit in value_type konvertiert werden kann. Außerdem muss er dem Verhalten von { value_type tmp = *a; ++a; return tmp;} entsprechen. Input-Iteratoren dürfen nur einmal gelesen werden und ihr value_type muss nicht kopierzuweisbar sein.
Ein Output-Iterator a vom Typ iterator_type muss den Ausdruck *a = value zulassen. Der Rückgabetyp dieses Ausdrucks ist nicht spezifiziert. Die übliche Konvention besagt natürlich, dass es sich um eine Referenz auf *a handeln sollte, dies ist aber keine Anforderung, die von Iteratoren gestellt wird. Der Ausdruck ++a muss eine Referenz auf iterator_type sein. Der Rückgabetyp des Ausdrucks a++ muss implizit nach iterator_type const& konvertierbar sein und der Ausdruck muss dem Verhalten von { iterator_type tmp = a; ++a; return tmp;} entsprechen. Der Ausdruck *a++ = value muss spezifiziert sein. Der Rückgabetyp dieses Ausdrucks ist wiederum nicht spezifiziert. Auf Output-Iterator darf nur einmal geschrieben werden.
Forward-Iteratoren dürfen beliebig oft gelesen und, sofern sie veränderlich sind, auch beschrieben werden. Sie müssen defaultkonstruierbar sein. Falls iterator_type ein veränderlicher Iterator ist, so ist reference äquivalent zu value_type&, andernfalls zu value_type const&. Für zwei dereferenzierbare Forward-Iteratoren a und b impliziert a == b gleich true, dass auch ++a == ++b wahr sein muss. Wenn a und b dereferenzierbar sind, so darf a == b ausschließlich dann wahr sein, wenn a und b zur gleichen Sequenz gehören. Der Typ des Ausdrucks a++ muss implizit in value_type const& konvertierbar sein und der Ausdruck muss dem Verhalten von { iterator_type tmp = a; ++a; return tmp;} entsprechen. Der Rückgabetyp des Ausdrucks *a++ muss vom Typ reference sein.
Mit Bidirectional-Iteratoren kann man eine Sequenz sowohl vorwärts, als auch rückwärts durchlaufen. Sie entsprechen Forward-Iteratoren und erfüllen weiterhin die nachfolgenden Bedingungen. --a gibt eine Referenz auf iterator_type zurück. Der Ausdruck ist anwendbar, wenn ein Iterator b existiert, für den a == ++b wahr ist. Wenn a dereferenzierbar ist, muss außerdem --(++a) == a wahr sein und wenn --a == --b wahr ist, muss auch a == b wahr sein. Der Ausdruck a-- muss einen Rückgabetyp besitzen, der implizit in iterator_type const& konvertierbar ist und er muss dem Verhalten von { iterator_type tmp = a; --a; return tmp;} entsprechen. Der Rückgabetyp des Ausdrucks *a-- muss reference sein.
Die umfangreichsten Ansprüche stellen Random-Access-Iterator, sie erfüllen alle Anforderungen der Bidirectional-Iteratoren und bieten einen wahlfreien Zugriff auf Elemente einer Sequenz. Wenn n vom Typ difference_type ist, muss der Ausdruck a += n eine Referenz auf iterator_type zurückgeben und dem Verhalten von { difference_type m = n; if(m >= 0) while(m--) ++a; else while(m++) --a; return a;} entsprechen. Die Ausdrücke a + n und n + a müssen ein Objekt vom Typ iterator_type zurückgeben und dabei dem Verhalten von { iterator_type tmp = a; return a += n;} entsprechen. Weiterhin muss a + n == n + a wahr sein. Der Ausdruck a -= n muss den Rückgabetyp iterator_type& besitzen und sich wie return a += -n; verhalten. Der Ausdruck a - n muss ein Objekt vom Typ iterator_type zurückgeben und dem Verhalten von { iterator_type tmp = a; return tmp -= n;} entsprechen. Vorausgesetzt es existiert ein Wert n vom Typ difference_type, für welchen a + n == b wahr ist, so muss der Ausdruck b - a ein Objekt vom Typ difference_type zurückgeben, welches dem Wert n entspricht. Der Ausdruck a[n] muss ein Objekt zurückgeben, das implizit in reference konvertiert werden kann und er muss dem Verhalten von *(a + n) entsprechen. Schließlich müssen die vier übrigen Vergleichsoperatoren für Random-Access-Iterator definiert sein. Alle vier müssen ein Objekt zurückgeben, das implizit in bool konvertiert werden kann. a < b muss dem Verhalten von b - a > 0 entsprechen. a > b muss dem Verhalten von b < a entsprechen. a >= b muss dem Verhalten von !(a < b) entsprechen und schließlich muss a <= b dem Verhalten von !(a > b) entsprechen.
Mit diesem Wissen, kennen Sie zwar noch nicht alle Details der C++-Iteratoren, aber Sie haben schon einen guten Überblick und sind gerüstet, um Ihre ersten eigenen Iteratorklassen zu schreiben. Wenn Sie dereinst tatsächlich selbst eine Iteratorklasse schreiben müsse, dann besorgen Sie sich am besten einen C++-Standard, in welchem Sie sämtlich Details noch einmal nachlesen können. Unter der Adresse http://www.open-std.org/JTC1/SC22/WG21/ finden Sie die Website der Arbeitsgruppe das C++-Standardkomitees. Den aktuellen Standard bekommen Sie dort zwar nicht, aber die Arbeitsentwürfe (Working Drafts) können frei eingesehen werden. Dies eröffnet ihnen übrigens auch die Möglichkeit, sich über die Pläne für kommende Standards auf dem laufenden zu halten, sofern Sie dies Wünschen.
Allgemeine Basis
BearbeitenSie haben nun eine ganze Menge sehr trockener Theorie studiert. Sicher ist Ihnen dabei dennoch aufgefallen, dass viele der aufgeführten Ausdrücke direkt anhand der Ausdrücke implementiert werden können, deren Verhalten sie entsprechen sollen. Dies tatsächlich zu tun, hat für uns zwei wesentliche Vorteile. Zum Ersten haben wir weniger Schreibarbeit und zum Zweiten vermeiden wir dadurch auch Codeverdopplung. Da diese Operationen jedoch obendrein für alle Iteratoren den gleichen Quellcode besitzen, lohnt es sich, eine allgemeine Basisklasse zu schreiben, welche von den eigentlichen Iteratorklassen nur noch geerbt werden muss.
In dieser Basisklasse muss der Typ der abgeleiteten Klasse bekannt sein. Dies realisieren wir, indem wir diese, als Templateparameter an die Basisklasse hochreichen. Auf diese Weise ist auch gleich sichergestellt, dass jede dieser Basisklasseninstanzen zu genau einer Iteratorklasse gehört. Wie wir bereits festgelegt haben, werden wir Random-Access-Iteratoren für die Proxys bereitstellen. Da wir ja soeben die verschiedenen Iteratorkategorien durchgegangen sind, werden wir aber nicht einfach eine Basisklasse verwenden, sondern drei Klassen, in denen jeweils die Operatoren für Forward-Iteratoren, Bidirectional-Iteratoren und Random-Access-Iterator definiert sind. Auf diese Weise machen wir uns noch einmal klar, welche Operatoren zu welcher Kategorie gehören. Prinzipiell könnte man von den jeweiligen Klassen dann natürlich auch andere Iteratorklassen, als nur jene für unsere Proxys ableiten.
Für Forward-Iteratoren können wir den Post-Inkrement-Operator und den Ungleichheitsoperator verallgemeinert nutzen. Für den Ungleichheitsoperator haben Sie bereits gelernt, dass es schlechter Stiel ist, wenn nur der zweite Parameter eine implizite Typumwandlung unterstützt. Daher werden wir diesen als friend-Funktion innerhalb der Klasse definieren. Den Post-Inkrement-Operator würden wir auf den ersten Blick als Member deklarieren. Allerdings werden Sie spätestens nach der Definition des Pre-Inkrement-Operators innerhalb der abgeleiteten Iteratorklasse vor einem Problem stehen. Die Prefix- und Postfix-Versionen dieses Iterators werden durch einen ungenutzten int-Parameter unterschieden. Der Compiler behandelt Sie daher wie eine Funktionsüberladung und wie Sie sich sich hoffentlich erinnern werden, verdeckt die Redeklaration einer Methode in einer abgeleiteten Klasse, alle Deklarationen in den Basisklassen. Folglich wäre der Operator nicht mehr sichtbar, wenn wir ihn als Member implementieren. Nehmen wir die Deklaration als friend-Funktion innerhalb der Klasse vor, so besteht dieses Problem nicht. Um eine unerwünschte implizite Typumwandlung für den ersten Parameter müssen wir uns dabei nicht sorgen, denn dieser ist eine nicht-konstante Referenz auf die abgeleitete Iteratorklasse und für nicht-konstante Referenzen kann keine implizite Typumwandlung erfolgen. Dass die Funktionen mit der Basisklasse befreundet sind, muss uns kein Kopfzerbrechen bereiten, den Freundschaft wird ja nicht vererbt.
Somit bleibt noch die Frage zu klären, wie wir das direkte Erstellen von Objekten unserer Basisklassen verhindern. Die Antwort darauf lautet, wir Deklarieren die Konstruktoren im protected-Bereich. Die Klassen beinhalten keine Datenmember, daher müssen die Konstruktoren nichts tun. Im Grunde würde es daher genügen, den Standardkonstruktor zu definieren. Da unsere abgeleiteten Iteratorklassen jedoch den compilergenerierten Kopierkonstruktor benutzen könnten und dieser den Kopierkonstruktor der Basisklasse aufruft, ist auch die Deklaration des Kopierkonstruktors notwendig. An dieser Stelle sein noch einmal darauf hingewiesen, dass ein selbst definierter Kopierkonstruktor, sofern nicht anderes angegeben, den Standardkonstruktor der Basisklasse aufruft. Folglich wäre es also ausreichend, wenn wir die Definition des Kopierkonstruktors nur für unsere Random-Access-Iterator-Basisklasse angeben und in den anderen beiden, lediglich eine Deklaration verwenden. Da es jedoch, zumindest prinzipiell, möglich sein sollte, auch von den anderen beiden Basisklassen konkrete Iteratoren der entsprechenden Iteratorkategorie abzuleiten, werden wir auch hier eine Definition schreiben. Man weiß ja nie, was in einer späteren Version noch dazukommt. Außerdem besteht der zusätzliche Schreibaufwand in einem einzigen Zeichen. Statt eines Semikolons geben wir leere geschweifte Klammern an. Weiterhin schadet es auch nicht, wenn Sie explizit den Standard- oder Kopierkonstruktor der Basisklasse aufrufen. Je nach Compilereinstellung vermeiden Sie dadurch Warnungen. Wir werden dies hier aus Platzgründen jedoch nicht tun.
template < typename Derived >
class forward_iterator_base{
protected:
forward_iterator_base(){}
forward_iterator_base(forward_iterator_base const&){}
public:
friend Derived const operator++(Derived& self, int){
Derived tmp(self); ++self; return tmp;
}
friend bool operator!=(Derived const& lhs, Derived const& rhs){
return !(lhs == rhs);
}
};
Über die Basisklasse für Bidirectional-Iteratoren gibt es nicht viel zu sagen. Sie spezifiziert den Post-Dekrement-Operator in äquivalenter Weise zum Post-Inkrement-Operator von forward_iterator_base und ist natürlich von forward_iterator_base abgeleitet. Der Templateparameter wird dabei an die Basisklasse weitergegeben.
template < typename Derived >
class bidirectional_iterator_base: public forward_iterator_base< Derived >{
protected:
bidirectional_iterator_base(){}
bidirectional_iterator_base(bidirectional_iterator_base const&){}
public:
friend Derived const operator--(Derived& self, int){
Derived tmp(self); --self; return tmp;
}
};
Die Basisklasse für Random-Access-Iteratoren erhält noch einen zweiten Templateparameter. Da wir die Plus- und Minus-Operatoren, welche mit einem Iterator und einer Differenz aufgerufen werden, implementieren möchten, benötigen wir den difference_type. Beachten Sie, dass Sie sich diesen nicht mittels typename aus dem Templateparameter Derived extrahieren können. Die abgeleitete Klasse Derived kann zum Zeitpunkt der Basisklasseninstantiierung noch nicht instantiiert sein. Folglich ist es unmöglich, auf deren Definition zuzugreifen. Die drei erwähnten Operatoren werden natürlich auch wieder als friend-Funktionen innerhalb der Klasse definiert. Ebenso die vier verbleibenden Vergleichsoperatoren. Anders sieht es beim operator-=() aus, diesen werden wir als Member implementieren, weil nichts dagegen spricht. Damit der genutzte operator+=(), in der abgeleiteten Klasse gefunden werden kann, muss der this Zeiger in diese Umgewandelt werden. Da wir mit Sicherheit wissen, dass das aktuelle Objekt in Wahrheit vom Typ der abgeleiteten Iteratorklasse ist, können wir die Umwandlung bedenktenlos mit static_cast vornehmen.
template < typename Derived, typename DifferenceType >
class random_access_iterator_base: public bidirectional_iterator_base< Derived >{
protected:
random_access_iterator_base(){}
random_access_iterator_base(random_access_iterator_base const&){}
public:
friend bool operator<(Derived const& lhs, Derived const& rhs){
return rhs - lhs > DifferenceType();
}
friend bool operator>(Derived const& lhs, Derived const& rhs){
return rhs < lhs;
}
friend bool operator<=(Derived const& lhs, Derived const& rhs){
return !(lhs > rhs);
}
friend bool operator>=(Derived const& lhs, Derived const& rhs){
return !(lhs < rhs);
}
Derived& operator-=(DifferenceType const& difference){
return static_cast< Derived& >(*this) += -difference;
}
friend Derived const operator+(Derived lhs, DifferenceType const& rhs){
return lhs += rhs;
}
friend Derived const operator+(DifferenceType const& rhs, Derived lhs){
return lhs += rhs;
}
friend Derived const operator-(Derived lhs, DifferenceType const& rhs){
return lhs -= rhs;
}
};
Somit haben wir eine Klasse, von der wir unsere vier Iteratorklassen ableiten können und die uns in der Folge eine menge Arbeit abnimmt. Wie ihnen sicher aufgefallen ist, verwenden wir in diesen Basisklassen sehr intensiv eine Abart der Technik, die im Kapitel über den Datentyp dimension vorgestellt wurde, um für Funktionstemplates eine implizierte Typumwandlung für beide Parameter zu ermöglichen. Mit der Verwendung bei den Postfix-Operatoren haben Sie ein weiteres Anwendungsfeld dieser Technik kennen gelernt. Dass die Rückgabetypen der Postfix-Inkrement- und -Dekrement-Operatoren, sowie der Plus- und Minus-Operatoren konstant sind, widerspricht zwar den Vorgaben, die für Iteratoren eigentlich im Standard gemacht werden, aber es wurde schon im Kapitel über die Proxyklassen gezeigt, dass wir uns auf diese Weise einiges an Ärger ersparen und real dürfte es wohl kaum einen Fall geben, in dem unsere konstanten Rückgabetypen ein Problem darstellen.
Basis der Iteratorklassen für konstante und nicht-konstante Matrizen
BearbeitenBevor wir mit der Implementierung der konkreten Iteratorklassen beginnen, sollten wir uns noch kurz Gedanken darüber machen, zu welchem Objekt ein Iteratorobjekt gehört. Wir könnten jeden Iterator an ein Proxyobjekt binden, bedenken Sie jedoch, was dies bedeuten würde. Die Proxyobjekte sind meist selbst nur temporäre Objekte. Wenn wir einen Iterator intern auf einen Proxy verweisen lassen, dann wird es nicht selten passieren, dass dieser Proxy schneller wieder inexistent ist, als der erzeugte Iterator. In der Folge wäre der Iterator ungültig, obwohl die Zeile oder Spalte, auf die er sich bezieht, in der Matrix immer noch existiert. Außerdem wären die Iteratoren verschiedener Proxyobjekte, welche auf die gleiche Zeile oder Spalte verweise, nicht in der gleichen Sequenz. Beides macht uns deutlich, dass dieses Vorgehen eine sehr schlechte Idee wäre. Wir binden die Iteratoren stattdessen an die Matrizen, auf welche die Proxyklassen verweisen. Auf diese Weise umgehen wir beide Probleme.
Der zweite Punkt, über den wir uns vorweg Gedanken machen können, sind die Unterschiede zwischen den Iteratoren für konstante und nicht-konstante Proxys. Bei den Proxyklassen haben wir ja bereits festgestellt, dass sich die dortigen Versionen sehr ähnlich sind. Bei den Iteratorklassen ist dies noch mehr der Fall. Die Versionen für konstante Matrizen besitzen einen zusätzlichen Konstruktor für die implizite Typumwandlung aus den Versionen für nicht-konstante Matrizen. Alle übrigen Implementierungen unterscheiden sich lediglich im Typ, der auf das Matrixobjekt verweist. Quelltextmäßig ist die Implementierung völlig identisch. Folglich können wir diese in einem gemeinsamen Basisklassentemplate zusammenfassen, dem wir lediglich die Typen als Parameter übergeben, in denen sich die beiden Versionen unterscheiden.
Natürlich benötigt auch diese Basisklasse wieder die abgeleitete Klasse als Templateparameter. Wenn wir schließlich unsere Versionen für konstante und nicht konstante Matrizen öffentlich von dieser Klasse ableiten, dann müssen wir in diesen nur noch die Konstruktoren definieren und haben für alle benötigten Operatoren eine funktionsfähige Version geerbt.
Diese Technik hat eine ganze Reihe von Vorteilen. Offensichtlich ist natürlich, dass wir uns Schreibarbeit ersparen. Außerdem vermeiden wir Codeverdopplung, was die Wartbarkeit deutlich vereinfacht. Da der Compiler aufgrund des Templates sehr leicht erkennen kann, welche Teile der Klasseninstantiierung immer identisch sind, ermöglichen wir ihm eine gute Gelegenheit zu Optimierung. Letzten Endes verdeutlichen wir einem Leser unsere Quellcodes natürlich auch noch, dass sich diese beiden Versionen, bis auf die Datentypen, identisch verhalten.
Iteratoren für Zeilenproxys
BearbeitenWir werden, unseren eben angestellten Überlegungen entsprechend, die eigentliche Implementierung der Operatoren innerhalb einer typunabhängigen Basisklasse vornehmen. Zunächst müssen wir uns jedoch darüber im klaren sein, welche Datenmember unsere Zeileniteratoren benötigen. Da alle Elemente einer Zeile im Datenfeld der Matrix hintereinander liegen, können wir die Iteratoren einer Zeile auf eine Teilsequenz der Iteratoren des Datenfeldes abbilden. Wir werden also einen Datenmember vom Typ der Iteratoren der Matrixklasse benötigen, denn diese reicht ja einfach die Iteratoren ihres Datenfeldes durch. Dies allein genügt anscheinend bereits für die Implementierung der Member.
Allerdings wird an den Gleichheitsoperator noch die Bedingung gestellt, dass das Ergebnis für zwei dereferenzierbare Iteratoren dann und nur dann true sein darf, wenn diese auch zur gleichen Sequenz gehören. Wir müssen also prüfen, ob wir möglicherweise auch noch einen Vergleich für die Zeile durchführen müssen, auf die sich die beiden Operatorargumente beziehen, denn diese Information ist im Iterator der Matrix ja nicht enthalten. Glücklicherweise kommt uns hier die Vorbedingung dieser Anforderung zu gute. Die Iteratoren müssen beide dereferenzierbar sein und wir geben keine Garantie dafür, dass ein Iterator, der außerhalb der Zeile liegt, für die er erzeugt wurde, dereferenzierbar ist. Das Verhalten des Ausdrucks *iter ist somit undefiniert und damit ist der Iterator iter per Definition nicht dereferenzierbar, auch wenn das Zufallsbedingt klappen kann. Wenn wir also in unserem Vergleichsoperator nur auf die Gleichheit der Matrixiteratoren prüfen und dieser für zwei Iteratoren, aus unterschiedlichen Zeilen true ergibt, so war mindestens einer der beiden Iteratoren außerhalb seines gültigen Bereichs und somit per Definition nicht dereferenzierbar. Unter diesen Umständen ist auch die Rückgabe des Vergleichsoperators nicht definiert. Wir können völlig beliebig true oder false zurückgeben oder das Programm mit einem Ausnahmefehler beenden oder abstürzen lassen, wenn wir dies wünschen würden. Dieses Verhalten ist übrigens äquivalent zu dem, gewöhnlicher Zeiger. Auch dort kann ein Zeiger ja ohne weiteres ein Element hinter einem Array referenzieren. Was bei der Dereferenzierung passiert ist allerdings dem Zufall überlassen.
Es bleibt also bei dieser einen Membervariable. Die Konstruktoren werden wir so gestalten, dass ein Matrixiterator übergeben wird. Die Proxymethoden begin() und end() können dann die korrekte Position des entsprechenden Matrixiterators berechnen und aus diesen, ein Zeileniteratorobjekt erzeugen. Für den zwar unwahrscheinlichen, aber nicht unmöglichen Fall, dass der Matrixiteratortyp ein eingebauter Datentyp ist, werden wir ihn explizit durch ein standardkonstruiertes Objekt initialisieren. Da wir nicht wollen, dass von dieser Klasse direkt Objekte erzeugt werden können, werden wir die Konstruktoren wiederum in protected-Bereich deklarieren. Da wir von dieser Klasse öffentlich ableiten wollen, müssen wir auch den Kopierkonstruktor im protected-Bereich deklarieren. Leider hat dies zur Folge dass wir ihn diesmal tatsächlich selbst schreiben müssen, denn die compilergenerierte Version würde im öffentlichen Bereich stehen. Da die Basisklassen dieser Basisklasse keine Datenmember besitzen, müssen wir uns zumindest nicht die Mühe machen, deren Kopierkonstruktoren aufzurufen. Genau wie wir es in diesen Basisklassen bereits getan haben, wird unser Kopierkonstruktor einfach implizit den Standardkonstruktor der unmittelbaren Basisklasse aufrufen.
Natürlich müssen wir für unsere Iteratoren die fünf typedefs bereitstellen, die für die Iterator-Traits benötigt werden. Die Iteratorkategorie ist natürlich Random-Access. Für die anderen vier Typen bedienen wir uns bei den Iteratoren der Matrixklasse. Da wir unsere Zeileniteratoren auf diese abbilden ist es nur folgerichtig, wenn wir auch deren Iterator-Traits übernehmen.
Unsere Basisklasse muss somit zwei Templateparameter besitzen. Zum Ersten die konkrete abgeleitete Iteratorklasse und zum Zweiten natürlich den konkreten Iteratortyp der Matrixklasse. Dieser kann ja sowohl matrix< T >::iterator, als auch matrix< T >::const_iterator sein und wie an anderer Stelle schon erwähnt, kann auf Informationen aus der abgeleiteten Klasse, zum Zeitpunkt der Basisklasseninstantiierung, noch nicht zugegriffen werden. Wir müssen diese Information daher zwingend als Templateparameter übergeben.
Die Implementierung der übrigen Operatoren enthält keine großen Überraschungen, im wesentlichen reichen Sie alle ihre Parameter an die entsprechende Operation des Matrixiterators weiter. Der Datenmember ist im protected-Bereich deklariert, damit die abgeleitete Iteratorklasse darauf zugreifen kann. Das <ganze sieht somit wie Folgt aus:
template < typename Derived, typename MatrixIterator >
class row_iterator_base:
public random_access_iterator_base< Derived, typename MatrixIterator::difference_type >
{
public:
typedef typename MatrixIterator::value_type value_type;
typedef typename MatrixIterator::difference_type difference_type;
typedef typename MatrixIterator::pointer pointer;
typedef typename MatrixIterator::reference reference;
typedef std::random_access_iterator_tag iterator_category;
reference operator*()const{return *pos_;}
pointer operator->()const{return pos_;}
Derived& operator++(){ ++pos_; return static_cast< Derived& >(*this); }
Derived& operator--(){ --pos_; return static_cast< Derived& >(*this); }
friend bool operator==(Derived const& lhs, Derived const& rhs){ return lhs.pos_ == rhs.pos_; }
Derived& operator+=(difference_type const& difference){
pos_ += difference; return static_cast< Derived& >(*this);
}
friend difference_type const operator-(Derived const& lhs, Derived const& rhs){
return lhs.pos_ - rhs.pos_;
}
reference operator[](difference_type const& index)const{ return *(pos_ + index); }
protected:
row_iterator_base(): pos_(MatrixIterator()){}
row_iterator_base(MatrixIterator const& pos): pos_(pos){}
row_iterator_base(row_iterator_base const& iter): pos_(iter.pos_){}
MatrixIterator pos_;
};
Alles, was wir jetzt noch tun müssen, ist unsere konkreten Iteratorklassen jeweils von einer Klasseninstanz des Templates row_iterator_base öffentlich abzuleiten und in den abgeleiteten Klassen die benötigten Konstruktoren, sowie für row_iterator den operator row_const_iterator() zu definieren. Sämtliche Operatoren und Typen werden aus dieser Klasseninstanz geerbt. Unsere beiden konkreten Iteratorklassen, sehen somit folgendermaßen aus.
template < typename Matrix >
class row_const_iterator:
public row_iterator_base< row_const_iterator< Matrix >, typename Matrix::const_iterator >
{
private:
typedef row_iterator_base< row_const_iterator< Matrix >, typename Matrix::const_iterator > base;
public:
row_const_iterator(){}
row_const_iterator(typename Matrix::const_iterator const& pos): base(pos){}
};
template < typename Matrix >
class row_iterator:
public row_iterator_base< row_iterator< Matrix >, typename Matrix::iterator >
{
private:
typedef row_iterator_base< row_iterator< Matrix >, typename Matrix::iterator > base;
public:
row_iterator(){}
row_iterator(typename Matrix::iterator const& pos): base(pos){}
operator row_const_iterator< Matrix >()const{
return row_const_iterator< Matrix >(this->pos_);
}
};
Die privaten base-typedefs dienen lediglich der besseren Übersicht, da der Basisklassenname sehr lang wird.
Iteratoren für Spaltenproxys
BearbeitenDas Vorgehen für die Spaltenproxys ist vom Prinzip her vollkommen äquivalent. Allerdings können wir diesmal nicht einfach eine Teilsequenz durchreichen. Wir müssen uns stattdessen selbst Gedanken über eine einigermaßen effiziente Implementierung machen. Wir könnten intern beispielsweise eine Variable verwalten, welche eine Position speichert, die vom Anfang des in matrix enthaltenen Datenfeldes aus gemessen wird. Wenn wir diese nach der Initialisierung immer nur noch genau um ein vielfaches der Zeilenlänge, also der Anzahl der Spalten, verschieben, so erreichen wir genau alle gültigen Positionen innerhalb einer Spalte.
Falls Sie nun auf die Idee kommen, einen Matrixiterator dafür zu verwenden, dann denken Sie noch einmal darüber nach, wie dieser sich verhält, wenn er über das Ende seiner gültigen Sequenz hinaus verschoben wird. Da es sich um einen Random-Access-Iterator handelt, stehen die Chancen nicht schlecht, dass das Addieren eines Wertes, mit anschließendem wieder Abziehen, exakt wieder die Position erreicht, die der Iterator zuvor hatte. Das muss aber nicht zwingen so sein. betrachten wir das Ganze mal an einem Beispiel. Nehmen Sie an, sie hätten einen Iterator, der auf das letzte Element einer Sequenz zeigt. Wenn Sie mittels operator++() eins addieren, dann wird der Iterator auf das erste gedachte Element hinter der Sequenz zeigen und dieses ist das einzige Element, das zwingend nach der Sequenz existieren muss. Addieren Sie noch einmal eins, dann wird ein Random-Access-Iterator in den meisten Fällen auf ein zweites gedachtes Element hinter der gültigen Sequenz verweisen. Bei einem Bidirectional-Iterator wäre es hingegen sehr wahrscheinlich, dass er weiterhin auf das erste Element hinter der gültigen Sequenz zeigt. Wenn Sie also wieder eins abziehen, dann würde der Random-Access-Iterator anschließend wahrscheinlich auf das erste gedachte Element hinter der Sequenz zeigen. Wenn dem so ist, könnten wir eine solche Implementierung ins Auge fassen. Leider darf sich aber auch ein Random-Access-Iterator so verhalten, wie es ein Bidirectional-Iterator wahrscheinlich tun würde. Diese würde nämlich anschließend auf das letzte Element zeigen und bei einem derartigen Verhalten, wären wir plötzlich in der falschen Spalte. Da das Verhalten hier nicht sicher definiert ist, können wir diese Variante auch nicht guten Gewissens verwenden.
Wir speichern die Position stattdessen als ganzzahligen Wert, welchen wir bei einer angeforderten Dereferenzierung einfach zum Anfangsiterator des matrix-Objekt addieren. Auf dieses Weise ist sichergestellt, dass sich unser Iterator so verhält, wie es ein Random-Access-Iterator üblicherweise tun würde. Insbesondere ist aber auch sichergestellt, dass niemals versehentlich ein Objekt, aus einer anderen Spalte, referenziert werden kann, auch wenn unser Iterator zuvor schon einmal auf das erste Element hinter der Sequenz gezeigt hat, welches ja bezüglich den Matrixiteratoren auch mehrere Elemente hinter dessen letztem Element liegen kann. Hätten wir beispielsweise eine Matrix der Dimension 3, dann würden die Positionen, die für die zweite Spalte zwingend existieren müssen, bezüglich das Datenfeldes aus Matrix so aussehen:
123456789xxx Datenfeld ^ ^ ^ ^ Spalteniteratorpositionen
Wir benötigen für unsere Implementierung also einen Verweis auf das zugehörige matrix-Objekt und eine ganzzahlige Variable. Wie schon bei den Zeilenproxys werden wir diese beiden Datenmember gemeinsam mit den drei Konstruktoren, im protected-Bereich platzieren. Die ganzzahlige Variable wird vom Typ difference_type sein, da wir eine Entfernung ausdrücken wollen und bei einigen Berechnungen, innerhalb der Implementierung, können auch negative Werte entstehen. So etwa beim Subtrahieren zweier Iteratoren. Hierbei müssen intern die Positionen subtrahiert werden. Das matrix-Objekt kann entweder konstant oder nicht konstant sein, entsprechend werden wir dessen Typ als Templateparameter Matrix übergeben lassen. Der Member matrix_ ist dann vom Typ Matrix*, so dass der Zuweisungsoperator für die Klasse erzeugt werden kann. Außerdem benötigen wir für die typedefs wieder den passenden Iteratortyp der Matrixklasse. Diesen können wir leider nicht aus dem Templateparameter Matrix extrahieren, da der typedef iterator für matrix und matrix const immer noch identisch ist, wir benötigen für konstante Matrizen aber explizit matrix::const_iterator. Daher müssen wir uns auch diesen als Templateparameter übergeben lassen.
Für den Zugriff auf die Zeilenlänge werden wir uns eine Helfermethode im privaten Bereich anlegen, welche die Anzahl der Spalten aus dem matrix-Objekt zurückgibt. Da dies die Schrittweite für unsere Positionsvariable ist, werden wir die Methode step_width() nennen. Der Inkrement- bzw. Dekrement-Operator erhöht bzw. verringert unsere Positionsvariable um step_width(). Der operator+=() erhöht die Position um seinen Parameter mal step_width(). Der Gleichheitsoperator prüft, ob die Position und das matrix-Objekt übereinstimmen. Die Position wird hierbei zuerst geprüft, da es sehr wahrscheinlich ist, dass diese nicht übereinstimmt und dann muss die zweite Prüfung nicht mehr durchgeführt werden. Der Subtraktionsoperator für zwei Iteratoren bildet die Positionsdifferenz und teilt diese durch step_width(). Die Ganzzahldivision geht dabei immer genau auf. Der Indexoperator ruft den Plusoperator auf und gibt anschließend das dereferenziert Ergebnis zurück. Unsere Implementierung sieht somit wie Folgt aus:
template < typename Derived, typename Matrix, typename MatrixIterator >
class column_iterator_base:
public random_access_iterator_base< Derived, typename MatrixIterator::difference_type >
{
public:
typedef typename MatrixIterator::value_type value_type;
typedef typename MatrixIterator::difference_type difference_type;
typedef typename MatrixIterator::pointer pointer;
typedef typename MatrixIterator::reference reference;
typedef std::random_access_iterator_tag iterator_category;
reference operator*()const{ return *(matrix_->begin() + pos_); }
pointer operator->()const{ return matrix_->begin() + pos_; }
Derived& operator++(){
pos_ += step_width();
return static_cast< Derived& >(*this);
}
Derived& operator--(){
pos_ -= step_width();
return static_cast< Derived& >(*this);
}
friend bool operator==(Derived const& lhs, Derived const& rhs){
return lhs.pos_ == rhs.pos_ && lhs.matrix_ == rhs.matrix_;
}
Derived& operator+=(difference_type const& difference){
pos_ += difference * step_width();
return static_cast< Derived& >(*this);
}
friend difference_type const operator-(Derived const& lhs, Derived const& rhs){
return (rhs.pos_ - lhs.pos_) / lhs.step_width();
}
reference operator[](difference_type const& index)const{
return *(static_cast< Derived const& >(*this) + index);
}
protected:
column_iterator_base():
matrix_(0), pos_(difference_type()){}
column_iterator_base(Matrix& matrix, difference_type const& pos):
matrix_(&matrix), pos_(pos){}
column_iterator_base(column_iterator_base const& iter):
matrix_(iter.matrix_), pos_(iter.pos_){}
Matrix* matrix_;
difference_type pos_;
private:
difference_type const step_width(){ return matrix_->columns(); }
};
Die Definition der abgeleiteten Proxyklassen ist komplett analog zu jener, die wir für die Iteratoren für konstante Matrizen vorgenommen haben.
template < typename Matrix >
class column_const_iterator:
public column_iterator_base<
column_const_iterator< Matrix >, Matrix const, typename Matrix::const_iterator
>{
private:
typedef column_iterator_base<
column_const_iterator< Matrix >, Matrix const, typename Matrix::const_iterator
> base;
public:
column_const_iterator(){}
column_const_iterator(Matrix const& matrix, typename base::difference_type const& pos):
base(matrix, pos){}
};
template < typename Matrix >
class column_iterator:
public column_iterator_base<
column_iterator< Matrix >, Matrix, typename Matrix::iterator
>{
private:
typedef column_iterator_base<
column_iterator< Matrix >, Matrix, typename Matrix::iterator
> base;
public:
column_iterator(){}
column_iterator(Matrix& matrix, typename base::difference_type const& pos):
base(matrix, pos){}
operator column_const_iterator< Matrix >()const{
return column_const_iterator< Matrix >(*this->matrix_, this->pos_);
}
};
Schnittstellen der Proxyklassen
BearbeitenJetzt müssen wir die Iteratorklassen nur noch in den Proxyklassen benutzten. Für alle vier Proxyklassen werden jetzt die typedefs iterator, const_iterator und difference_type eingeführt. Zum Erstellen von Iteratorobjekten gibt es jeweils die Methoden begin() und end(), die einen Iterator auf den Anfang, beziehungsweise hinter das Ende einer Sequenz erstellen. Die Berechnungen für konstante und nicht-konstante Matrizen sind immer identisch, die Methoden unterscheiden sich hier lediglich im Datentyp. Daher können wir diese wieder in einem entsprechenden Template zusammenfassen. Somit benötigen wir also vier Funktionstemplates zur Erstellung unserer Iteratorobjekte. Diese vier Funktionstemplates werden wir natürlich wieder im Namensraum detail deklarieren. Da sie zu den Proxyklassen gehören, stehen sie auch in der Datei proxy.hpp.
Die vier Funktionstemplates bekommen jeweils eine Referenz auf das matrix-Objekt und die Zeile bzw. Spalte, für die der jeweilige Iterator erstellt werden soll. Das matrix-Objekt kann konstant oder nicht-konstant sein. Der Iteratortyp muss entsprechend ein iterator oder const_iterator sein. Leider können wir den zu erstellenden Iteratortyp nicht vom Typ der Matrix ableiten, daher müssen wir beides als Templateparameter übergeben.
template < typename Matrix, typename Iterator >
inline Iterator const create_begin_row_iterator(
Matrix& matrix, typename Matrix::size_type const& row
){
return Iterator(matrix.begin() + (matrix.columns() * row));
}
template < typename Matrix, typename Iterator >
inline Iterator const create_end_row_iterator(
Matrix& matrix, typename Matrix::size_type const& row
){
return Iterator(matrix.begin() + (matrix.columns() * (row + 1)));
}
template < typename Matrix, typename Iterator >
inline Iterator const create_begin_column_iterator(
Matrix& matrix, typename Matrix::size_type const& column
){
return Iterator(matrix, column);
}
template < typename Matrix, typename Iterator >
inline Iterator const create_end_column_iterator(
Matrix& matrix, typename Matrix::size_type const& column
){
return Iterator(matrix, column + matrix.columns() * matrix.rows());
}
Die Iteratorinterfacemethoden sollen sich gegenseitig aufrufen, wenn Sie die gleiche Bedeutung haben. Nur wenn dies nicht der Fall ist, greifen wir auf die passende Funktionsinstanz des entsprechenden, eben definierten, Funktionstemplates zurück. Wie schon beim Iteratorinterface der Matrix, werden wir auch hier wieder konstante Iteratorobjekte zurückgeben um unsinnige Operationen explizit zu verbieten. Die Ergänzungen in den Proxyklassen sehen so aus:
template < typename Matrix >
class row_const_proxy: private detail::line_const_proxy< Matrix >{
public:
typedef detail::row_const_iterator< matrix_type > const_iterator;
typedef const_iterator iterator;
typedef typename const_iterator::difference_type difference_type;
// ...
const_iterator const begin()const{ return cbegin(); }
const_iterator const end()const{ return cend(); }
const_iterator const cbegin()const{
return detail::create_begin_row_iterator< matrix_type const, const_iterator >(
this->matrix_const(), pos()
);
}
const_iterator const cend()const{
return detail::create_end_row_iterator< matrix_type const, const_iterator >(
this->matrix_const(), pos()
);
}
};
template < typename Matrix >
class column_const_proxy: private detail::line_const_proxy< Matrix >{
public:
typedef detail::column_const_iterator< matrix_type > const_iterator;
typedef const_iterator iterator;
typedef typename const_iterator::difference_type difference_type;
// ...
const_iterator const begin()const{ return cbegin(); }
const_iterator const end()const{ return cend(); }
const_iterator const cbegin()const{
return detail::create_begin_column_iterator< matrix_type const, const_iterator >(
this->matrix_const(), pos()
);
}
const_iterator const cend()const{
return detail::create_end_column_iterator< matrix_type const, const_iterator >(
this->matrix_const(), pos()
);
}
};
template < typename Matrix >
class row_proxy: private detail::line_proxy< Matrix >{
public:
typedef typename row_const_proxy< matrix_type >::const_iterator const_iterator;
typedef detail::row_iterator< matrix_type > iterator;
typedef typename row_const_proxy< matrix_type >::difference_type difference_type;
// ...
iterator const begin()const{
return detail::create_begin_row_iterator< matrix_type, iterator >(
this->matrix(), pos()
);
}
iterator const end()const{
return detail::create_end_row_iterator< matrix_type, iterator >(
this->matrix(), pos()
);
}
const_iterator const cbegin()const{
return detail::create_begin_row_iterator< matrix_type const, const_iterator >(
this->matrix_const(), pos()
);
}
const_iterator const cend()const{
return detail::create_end_row_iterator< matrix_type const, const_iterator >(
this->matrix_const(), pos()
);
}
};
template < typename Matrix >
class column_proxy: private detail::line_proxy< Matrix >{
public:
typedef typename column_const_proxy< matrix_type >::const_iterator const_iterator;
typedef detail::column_iterator< matrix_type > iterator;
typedef typename column_const_proxy< matrix_type >::difference_type difference_type;
// ...
iterator const begin()const{
return detail::create_begin_column_iterator< matrix_type, iterator >(
this->matrix(), pos()
);
}
iterator const end()const{
return detail::create_end_column_iterator< matrix_type, iterator >(
this->matrix(), pos()
);
}
const_iterator const cbegin()const{
return detail::create_begin_column_iterator< matrix_type const, const_iterator >(
this->matrix_const(), pos()
);
}
const_iterator const cend()const{
return detail::create_end_column_iterator< matrix_type const, const_iterator >(
this->matrix_const(), pos()
);
}
};
Somit haben wir das Kapitel Proxyklassen abgeschlossen und verfügen über ein vollständiges Iteratorinterface für die gesamte Matrix, sowie deren Zeilen und deren Spalten. Als nächstes werden wir uns der Ein- und Ausgabe von Matrizen widmen. Auch hier werden wir wieder eine Ein- und Ausgabe für einzelne Zeilen uns Spalten anbieten und dabei von unseren Iteratorinterfaces Gebrauch machen.