C++-Programmierung/ Eine Matrix-Bibliothek – mitrax/ Die Matrixklasse
Das matrix-Klassentemplate ist das Herzstück von mitrax. Alle Inhalte dieses Kapitels stehen in der Datei matrix.hpp. Wir haben bereits festgestellt, dass eine Matrix aus einer Dimension und den entsprechend angeordneten Elementen besteht. Einen Datentyp für die Dimension haben wir uns im letzten Kapitel geschaffen. Den Datentyp für die Elemente wollen wir nicht selbst vorgeben, daher ist dies ein Templateparameter. Somit bleibt noch die Frage, wie wir unsere Elemente speichern. Was wir benötigen, ist im Grunde, ein zweidimensionales Array. Da uns die Standardbibliothek keinen entsprechenden Container zur Verfügung stellt, werden wir uns selbst um die zweidimensionale Anordnung unserer Elemente kümmern müssen. Da wir einen schnellen Zugriff auf alle Elemente wünschen, werden wir einen Container wählen, der Random-Access-Iteratoren anbietet. Anhand dieser Überlegungen erscheint std::vector geeignet.
Klassendeklaration[Bearbeiten]
Sie werden sich möglicherweise fragen, warum wir uns überhaupt auf einen spezifischen Container festlegen sollten. Wir könnten den Container schließlich genauso gut als Templateparameter festlegen und dem Nutzer somit die Möglichkeit, für besondere Optimierungen anbieten. Tatsächlich werden wir dies auch machen, aber es ergibt sofort ein Problem dadurch. Unsere matrix-Klasse sollte möglichst einfach zu Handhaben sein. Wenn ein Benutzer also eine Matrix aus float-Elementen wünscht, dann wird er sich in den meisten Fällen, keine Gedanken darüber machen wollen, in welchem Container die Elemente innerhalb der Matrix gespeichert sind. Wir verpassen dem zweiten Parameter daher als Standardwert einen std::vector.
template < typename Type, template< typename > class Container = std::vector >
class matrix;
Wenn Sie versuchen diese Deklaration zu machen, wird sich ihr Compiler beschweren, dass die Templateargumentliste von std::vector nicht kompatibel zur angegeben Liste ist. Dort steht, dass Container nur ein Templateargument erhalten soll, std::vector bekommt jedoch zwei Argumente. Das Erste ist natürlich der Datentyp der Elemente, als Zweites kann jedoch noch ein spezieller Allocator angegeben werden. Da dieser einen Standardwert besitzt, fällt dies normalerweise nicht auf, aber an dieser Stelle prüft C++ nicht, ob die Deklarationen, unter Berücksichtigung der Standardargumente, kompatibel sind. Wir müssten also für den Container zwei Templateargumente spezifizieren und innerhalb der Definition von matrix, manuell den Standard-Allocator angeben. Dies hat jedoch gleich zwei Nachteile. Zum einen ist matrix dadurch sofort inkompatibel zu allen Containern, die nicht als ersten Parameter den Typ für die Elemente und als Zweiten den Typ für einen Allocator übernehmen. Zum anderen können wir keinen eigenen Allocator mehr spezifizieren.
Dies schränkt die Möglichkeiten zu optimieren durch einen eigenen Container viel zu stark ein. Wir benötigen eine andere Strategie, um den Container zu spezifizieren. Eine für uns einfache Möglichkeit bestünde darin, nur den Container angeben zu lassen und den Typ der Daten dann aus diesem zu extrahieren. Typischerweise existiert innerhalb eines Container ein typedef auf den Datentyp, den die Elemente haben. Das Ganze könnte dann etwa so aussehen.
template < typename Container >
class matrix{
// Typ von dem unsere Elemente sind
typedef typename Container::value_type type;
};
Wir haben jedoch bereits erläutert, dass der Container in irgendeiner Weise, standardmäßig std::vector sein sollte. Bei diesem Vorgehen haben wir keine Chance dies anzugeben. Der Nutzer müsste den Container immer selbst mit angeben. Hinzu kommt natürlich noch, dass der Container-Typ einen typedef namens value_type anbieten muss. Dies ist nicht sonderlich kritisch, aber die Abhängigkeiten sollten dennoch möglichst gering gehalten werden. Glücklicherweise gibt es einen Mechanismus, der es uns erlaubt, den Datentyp der Elemente anzugeben und diesen auch gleich als Argument für einen Standardcontainer zu verwenden.
template < typename Type, typename Container = std::vector< Type > >
class matrix;
Jetzt muss der Nutzer zwar zweimal den Typ für die Elemente angeben, wenn er einen anderen Container wünscht, aber im Gegenzug kann er auch wirklich jeden beliebigen Container benutzen, der Elemente vom Typ Type speichert. Wenn der Nutzer keinen eigenen Container wünscht, muss er nur den Datentyp für die Elemente angeben. Die Nachteile halten sich also in Grenzen und treten insbesondere auch nur dann zu Tage, wenn der Nutzer ohnehin Sonderwünsche hat. Typischerweise wir er aufgrund dessen, ohnehin in die Dokumentation der matrix-Klasse schauen müssen, um dort zu erfahren, wie in Zusammenhang mit dem Containertypen optimiert werden kann. Diese Technik wird übrigens auch in der Standardbibliothek verwendet. Sehen Sie sich beispielsweise mal den Container-Adapter std::stack an.
Falls Sie sich nun Fragen, wie diese Optimierungsmöglichkeiten denn aussehen könnten, dann denken Sie noch einmal an den Allocator von std::vector zurück. Dieser ist eine solche Optimierungsmöglichkeit. Eine andere bestünde darin, einen Container zu verwenden, der spätes Kopieren unterstützt. Bei dieser Technik werden die Daten bei einer Zuweisung nicht sofort kopiert. Stattdessen, verweist jeder Container nur auf ein Datenpaket und dieses speichert, wie viele Container derzeit auf es verweisen. Solange kein Container schreibend auf die Daten zugreift, spricht nichts dagegen, wenn mehrere Container sich die gleichen Daten teilen. Eine Kopie muss erst ausgeführt werden, wenn ein Container schreiben auf Daten zugreift, die gerade von mehr als einem Container verwendet werden. Dies kann in bestimmten Anwendungsfällen zu erheblichen Beschleunigen führen.
Den Datentyp der Dimension können wir auf dimension< std::size_t > oder einen anderen unsigned int-Typen festlegen. Es würden sich keine praktisch relevanten Vorteile daraus ergeben, den Datentyp für die Anzahl der Zeilen und Spalten variablen zu gestalten. Negative Angaben sind nicht Sinnvoll und die Wahl eines kleineren unsigned-Typs ist praktisch ebenfalls irrelevant. Im Vergleich zur Größe der Elemente, fällt der hier genutzte Speicherplatz nicht ins Gewicht. Falls der Nutzer ohnehin nur mit sehr kleinen Matrizen arbeiten will, wird er sich nicht für die Verwendung vom mitrax entscheiden, sondern eine Bibliothek wählen, bei der er den Overhead für beliebig große Matrizen nicht zahlen muss.
Klassendefinition[Bearbeiten]
Das Grundgerüst für unsere Implementierung sieht folgendermaßen aus:
template < typename T, typename Container = std::vector< T > >
class matrix{
public:
// ... folgt noch
private:
dimension_type dimension_;
container_type data_;
};
Als Erstes wollen wir uns Gedanken darüber machen, welche Typen unsere Klasse nach außen hin anbieten sollte. Sie erkennen an der Deklaration der Datenmember bereits, dass die Typen für die Dimension und den Container mittels typedef definiert sein müssen. Weiterhin benötigen wir natürlich Zugriff auf den Datentyp der Elemente. Bei dieser Gelegenheit, werden wir auch gleich, analog zu den Containerklassen, typedefs für eine Referenz und eine Referenz auf const für die Elemente einführen. Neben dem Datentyp für die Dimension, sollten wir auch den Datentyp der Dimensionselemente verfügbar machen. Dies erleichtert die Lesbarkeit. Der Container verwaltet intern ebenfalls Elemente, daher sollte er auch einen size_type anbieten. Diesen werden wir einfach von der Dimension übernehmen.
Da wir ein Iteratorinterface anbieten wollen, müssen wir die typedefs iterator und const_iterator anbieten. Zusätzlich benötigen wir einen difference_type, der die Entfernung zwischen zwei Iteratoren wiedergibt. Auch hier bedienen wir uns beim Container, denn dieser muss ebenfalls alle drei anbieten. Schließlich benötigen wir noch die Typen der Proxyklassen, die wir für den Zugriff auf Zeilen und Spalten verwenden. Natürlich ist auch hier je eine konstante und eine nicht-konstante Variante notwendig. Die Datentypen, die hinter diesen typedefs stehen werden wir später noch schreiben. Für den Moment sollten Sie annehmen, dass diese bereits existieren. Das Ganze sieht dann folgendermaßen aus:
// Daten
typedef T value_type;
typedef T& reference;
typedef T const& const_reference;
typedef Container container_type;
// Dimension
typedef typename Container::size_type size_type;
typedef mitrax::dimension< size_type > dimension_type;
// Iteratoren
typedef typename Container::iterator iterator;
typedef typename Container::const_iterator const_iterator;
typedef typename Container::difference_type difference_type;
// Elementzugriff
typedef mitrax::row_proxy< matrix > row_proxy;
typedef mitrax::row_const_proxy< matrix > row_const_proxy;
typedef mitrax::column_proxy< matrix > column_proxy;
typedef mitrax::column_const_proxy< matrix > column_const_proxy;
Sicher werden Sie sich fragen, warum wir für dimension und die Proxyklassen explizit den Namensraum mitrax spezifizieren. matrix steht schließlich selbst in diesem Namensraum. Die Antwort ist für die Proxys bei genauerem hinsehen sofort ersichtlich. Wir überschreiben innerhalb unserer Klasse den Namen mit einer neuen Bedeutung. So ist beispielsweise row_proxy innerhalb unserer Klasse ein typedef auf irgendetwas und folglich kann der Compiler das Klassentemplate row_proxy, welches außerhalb der Klasse matrix deklariert ist, nicht mehr finden. Daher müssen wir dem Compiler an dieser Stelle sagen, dass er im Namensraum mitrax nach dem Bezeichner row_proxy suchen soll. Wir werden in Kürze eine Funktion namens dimension einführen, womit auch dieser Bezeichner überdeckt wird.
Konstruktoren[Bearbeiten]
Wir werden mehrere Konstruktoren anlegen. Als Erstes natürlich einen Standardkonstruktor, der eine Matrix mit null Zeilen und Spalten definiert. Dann einen Konstruktor, der eine Matrix durch Angabe einer Dimension erstellt und dabei alle Elemente standardkonstruiert. Sinnvollerweise werden wir diese Variante als Spezialfall (Standardparameter) eines Konstruktors implementieren, der alle Elemente mit einem vorgegeben Wert belegt. Letztlich brauchen wir noch einen Konstruktor, der eine schnelle Initialisierung bei gegebenen Elementen gewährleistet. Die beiden Konstruktoren, die eine Dimension übernehmen, werden wir jeweils in zwei Ausführungen implementieren. Die Erste bekommt ein dimension-Objekt und die Zweite bekommt Zeilen und Spalten getrennt. Dies ist lediglich eine Vereinfachung für den Benutzer, da beide Varianten häufig genutzt werden.
Für die effiziente Elementinitialisierung machen wir uns die swap()-Funktion zu nutzte. Ein Container besitzt intern immer einen Zeiger auf seine Daten und entsprechend ist die swap-Funktion für gewöhnlich so überladen, dass nur die internen Zeiger ausgetauscht werden müssen. Der Nutzer kann also einen eigenen Container mit den gewünschten Daten füllen und anschließend sein Containerobjekt gegen das leere Objekt in der Matrixklasse austauschen. Dies bringt natürlich den Nachteil mit sich, dass der Nutzer für die Belegung seines Containers, die zweidimensionale Position selbst berechnen muss. Wir werden später eine Hilfsklasse konstruieren, die dieses Problem ein wenig kompensiert. Falls die Größe des übergebenen Containers nicht zur Dimension passt, werden wir eine Ausnahme werfen. Die Unannehmlichkeiten, die anschließend noch für den Nutzer verbleiben, sind der Preis, den er zahlen muss, wenn er eine effiziente Vorbelegung seiner Elemente wünscht.
Gewöhnlich würden wir die Definition nicht innerhalb der Klasse vornehmen, aber um etwas Platz zu sparen, werden wir dies innerhalb der Kapitel tun. In der Quelltextübersicht, am Ende dieses Abschnitts, finden Sie Deklaration und Definition getrennt. Unserer Konstruktoren sehen somit folgendermaßen aus:
public:
matrix(){}
matrix(dimension_type const& size, const_reference fill = value_type()):
dimension_(size),
data_(elements(), fill)
{}
matrix(size_type const& rows, size_type const& columns, const_reference fill = value_type()):
dimension_(dimension_type(rows, columns)),
data_(elements(), fill)
{}
matrix(dimension_type const& size, container_type& data):
dimension_(size)
{
raw_data_swap(dimension_, data);
}
matrix(size_type const& rows, size_type const& columns, container_type& data):
dimension_(dimension_type(rows, columns))
{
raw_data_swap(dimension_, data);
}
private:
void raw_data_swap(dimension_type const& size, container_type& data){
if(elements(size) != data.size()){
throw error::data_size("mitrax::matrix<>::raw_data_swap", size, data);
}
using std::swap;
swap(data_, data);
}
Wie Sie sehen, wurde das Austauschen der Container in eine private Methode ausgelagert. Da wir dies sowieso im Funktionsrumpf erledigen, haben wir keine Laufzeiteinbußen und wir werden diese Funktion später noch einmal an anderer Stelle verwenden. Den Datentyp error::data_size werden wir später im Kapitel über Ausnahmebehandlung einführen. Falls Sie das Ganze schon mal testen möchten, können Sie auch einfach einen std::logic_error werfen.
Der Standardkonstruktor setzt voraus, dass der Container standardkonstruierbar ist. Die nachfolgenden beiden Konstruktoren verlangen, dass der Container über einen Konstruktor verfügt, der eine Größe und ein Füllelement übernimmt. Die letzten beiden Konstruktoren erwarten, dass für den Container die swap()-Funktion überladen ist oder dass der Container standardkonstruierbar und kopierzuweisbar ist. Letzteres wird benötigt, falls wider Erwarten auf std::swap() zurückgegriffen werden muss. In diesem Fall sind die Konstruktoren jedoch sehr wahrscheinlich ineffizient.
Iteratorinterface[Bearbeiten]
Das Iteratorinterface der Matrixklasse macht uns nur sehr wenig Mühe. Wir reichen einfach die entsprechenden Funktionen an den Container weiter. Wir bieten begin() und end() jeweils in einer konstanten und einer nicht-konstanten Variante an und zusätzlich die Funktionen cbegin() und cend(), welche äquivalent zu den konstanten Versionen sind. Diese beiden Funktionen sind auch Teil des kommenden C++-Standards. Wir werden sie jedoch die aktuellen Container-Methoden begin() und end() aufrufen lassen, was mit dem jetzigen und dem kommenden Standard kompatibel ist. Im Gegensatz zu den Standard-Iteratorfunktionen werden unsere Funktionen alle samt konstante Objekte zurückgeben. Leider ist dies bei den Standardfunktionen nicht so, weshalb man beispielsweise begin()++ schreiben kann, was, wenn Sie kurz darüber nachdenken, vollkommen sinnfrei ist. Unser Iteratorinterface sieht somit so aus:
public:
iterator const begin() { return data_.begin(); }
const_iterator const begin()const { return data_.begin(); }
iterator const end() { return data_.end(); }
const_iterator const end()const { return data_.end(); }
const_iterator const cbegin()const { return begin(); }
const_iterator const cend()const { return end(); }
Kapazität[Bearbeiten]
Unter dieser Überschrift wollen wir die Methoden zum Abfragen der Dimension einführen. Die Methode dimension() soll uns das Dimensionsobjekt liefern, zusätzlich werden wir aber noch die Methoden rows() und columns() anlegen. In der Praxis kommt es in etwa gleich häufig vor, dass die komplette Dimension benötigt wird und dass nur ein Teil der Dimension benötigt wird. Keine der beiden Varianten lässt sich effizient durch die jeweils andere ersetzen, daher bieten wir beide an. Außerdem erhöhen wir die Lesbarkeit von Clientcode, indem wir erlauben, ihn kürzer zu fassen, ohne dass dabei Information für den Leser verloren geht. Sie können ja mal versuchen, nur mit der dimension()-Methode oder nur mit den Methoden rows() und columns(), Code zu schreiben, in dem die jeweils andere Schnittstelle der matrix-Klasse günstiger wäre. Die Methoden sehen folgendermaßen aus:
public:
dimension_type const dimension()const { return dimension_; }
size_type const rows()const { return dimension_.rows(); }
size_type const columns()const { return dimension_.columns(); }
Dimension ändern[Bearbeiten]
Es gibt eine reichliche Menge an Situationen, in denen es sinnvoll ist, die Größe einer Matrix im Nachhinein zu verändern. Dabei muss man zwei Fälle unterscheiden. Im Ersten werden die Elemente der Matrix komplett verworfen und neu initialisiert. Im zweiten Fall wird nur die Dimension geändert, die Elemente, die auch mit der neuen Dimension noch existieren, bleiben erhalten. Betrachten wir beide Fälle etwas genauer.
Fall Eins lässt sich noch einmal nach der Art der Neuinitialisierung der Elemente aufteilen. Wie schon bei den Konstruktoren, kann auch hier wieder ein Element als Vorlage für alle anderen übergeben werden, oder es kann ein Container mit passender Größe, gegen den aktuellen Elemente-Container ausgetauscht werden. Diese zweite Variante werden wir in einer Methode namens reinit() implementieren. Sie besitzt die gleichen Nachteile wie der entsprechende Konstruktor, bietet aber auch die gleiche, sehr hohe, Effizienz.
Wenn die Elemente an ihren Positionen erhalten bleiben sollen, stellt sich natürlich die Frage, was zu tun ist, wenn die neue Matrix Elemente enthält, die in der alten nicht vorhanden waren. Wir werden das Problem dahingehend lösen, dass wir entsprechende Elemente mit einem übergeben Element auffüllen. Dieses Übergebene Element soll selbstverständlich als Standardparameter das standardkonstruierte Element verwenden, so dass der Benutzer nicht zwingend etwas angeben muss. Speziell wenn er weiß, das er die Matrix verkleinert, wäre es ziemlich nervig, einen Parameter angeben zu müssen, der niemals genutzt wird. Somit wird dies der letzte Parameter unserer resize()-Methode. Die Entscheidung bestehende Elemente zu erhalten, werden wir Standardmäßig auf true setzen. Wenn der Nutzer dies nicht wünscht, muss er es explizit abschalten, andernfalls braucht er sich keine Gedanken darüber zu machen. Unsere Implementierung sieht so aus:
public:
void resize(dimension_type const& size,
bool preserve = true, const_reference fill = value_type()
){
container_type init(elements(size), fill); // Neuer Container
if(preserve){
// Länge der pro Zeile zu kopierenden Elemente ermitteln
size_type min_columns = std::min(size.columns(), dimension_.columns());
// Differenz von kurzen und langen Zeilen
size_type dif_columns = std::max(size.columns(), dimension_.columns()) - min_columns;
// Iteratoren beider Container
iterator data_iter = data_.begin();
iterator init_iter = init.begin();
// Iterator mit den längeren Zeilen ermitteln
iterator& bigger = size.columns() < dimension_.columns() ? data_iter : init_iter;
// Zeilenweise durchlaufen
for(size_type i = size_type(); i < size.rows() && i < dimension_.rows(); ++i){
// Iteratoren hinter das Ende des zu kopierenden Bereiches setzen
iterator begin_data_iter = data_iter;
iterator begin_init_iter = init_iter;
std::advance(data_iter, min_columns);
std::advance(init_iter, min_columns);
// Kopie durchführen
std::copy(begin_data_iter, data_iter, begin_init_iter);
// Iterator mit den längeren Zeilen auf den Anfang der nächsten Zeile setzen
std::advance(bigger, dif_columns);
}
}
using std::swap;
swap(data_, init);
dimension_ = size;
}
void resize(size_type const& rows, size_type const& columns,
bool preserve = true, const_reference fill = value_type()
){
resize(matrix_size_type(rows, columns), preserve, fill);
}
void reinit(dimension_type const& size, container_type& data){
raw_data_swap(size, data);
dimension_ = size;
}
void reinit(size_type const& rows, size_type const& columns, container_type& data){
reinit(matrix_size_type(rows, columns), data);
}
Wie Sie erkennen, stellen wir auch für diese Methoden wieder je eine Version mit einem dimension-Objekt und eine mit den Einzelangaben für die Anzahl der Zeilen und Spalten bereit. Die Implementierung erfolgt natürlich nur in einer Version, da am Ende ohnehin ein dimension-Objekt benötigt wird, wird diese Version durch die andere aufgerufen. Bei der Reinitiallisierung verwenden wir wieder die Hilfsmethode raw_data_swap(), welche wir mit den Konstruktoren eingeführt haben. Da diese eine Ausnahme werfen kann, erfolgt dieser Aufruf als erstes. Somit steigt die Wahrscheinlichkeit, dass das matrix-Objekt unverändert bleibt, falls eine Ausnahme geworfen wird. Eine Garantie hierfür, kann man natürlich erst geben, wenn der Containertyp bekannt ist.
In der resize()-Methode legen wir zunächst einen neuen Container mit passender Größe an und lassen ihn mit unserem Füllelement auffüllen. Dies stellt an den Container die Anforderung, dass dieser einen entsprechenden Konstruktor anbietet. Falls preserve gesetzt ist, werden anschließend zeilenweise die Elemente aus dem alten Container kopiert, die für beide Dimensionen existieren. Die übrigen Elemente sind ja bereits auf den Füllwert gesetzt. An dieser Stelle setzten wir voraus, dass der Container Iteratoren anbietet. Da wir dies jedoch bereits in der Klassendefinition verlangt haben, muss dies immer der Fall sein. Schließlich tauschen wir den alten Container gegen den Neuen aus und weisen die neue Dimension zu.
Elementzugriff[Bearbeiten]
Für den Zugriff auf Zeilen und Spalten werden wir sogenannte Proxyklassen verwenden. Der Nutzer unserer Matrixklasse muss von diesen Proxyklassen nicht unbedingt etwas mitbekommen. Was wir erreichen wollen, ist, dass der Zugriff auf ein Element innerhalb der Matrix syntaktisch mit matrix_object[3][2] oder auch mittels matrix_object.column(2).row(3) möglich ist. Dies erreichen wir, indem wir die Memberfunktion von Matrix (operator[]() bzw. column()) ein Objekt zurückgeben lassen, welches von einem Typ ist, der wiederum die zweite Memberfunktion (operator[]() bzw. row()) bereitstellt. Diesen „Zwischentyp“ bezeichnet man als Proxyklasse. Wie genau diese Proxyklasse heißt oder aussieht, ist für den Nutzer erst interessant, wenn er eine Zeile oder Spalte als Parameter an eine eigene Funktion übergeben möchte. Solange er nur auf Elemente zugreift, muss er lediglich wissen, wie der Aufruf syntaktisch aussieht.
Wir werden die Proxyklassen in einem eigenen Kapitel behandeln. An dieser Stelle werden wir einfach annehmen, sie würden bereits existieren. Unsere Zugriffsmethoden der matrix-Klasse werden also ein Objekt vom Typ einer Proxyklasse erstellen, ihm die Information mitteilen, die sie selbst erhalten haben (welche Zeile / Spalte) und das Objekt schließlich zurückgeben. Zu beachten ist, dass es für konstante und nicht-konstante Versionen der Zugriffsfunktionen getrennte Proxyklassen gibt. Dies ist äquivalent zu den Funktionen für Iteratoren, denn genau wie die Iteratoren, müssen ja auch die Proxy-Objekte wissen, ob Sie auf eine konstante oder auf eine nicht-konstante Matrix verweisen. Ob die Iteratoren bzw. Proxys selbst konstant oder nicht-konstant sind, gibt keinen Aufschluss über die Daten, auf die sie verweisen. Die zurückgegeben Objekte sind natürlich, wie schon bei den Iteratoren, wieder konstant. Somit erhalten wir folgende Zugriffsmethoden für matrix:
public:
row_proxy const operator[](size_type const& row_number) { return row(row_number); }
row_const_proxy const operator[](size_type const& row_number)const { return row(row_number); }
row_proxy const row(size_type const& number){
return row_proxy(*this, number);
}
row_const_proxy const row(size_type const& number)const{
return row_const_proxy(*this, number);
}
column_proxy const column(size_type const& number){
return column_proxy(*this, number);
}
column_const_proxy const column(size_type const& number)const {
return column_const_proxy(*this, number);
}
Modifizierer[Bearbeiten]
Als Modifizierer bezeichnen wir Methoden, welche Zeilen oder Spalten (nachfolgend mit Linien abgekürzt) entfernen oder hinzufügen. Das Hinzufügen von Linien lassen wir in mitrax außen vor. Da es jedoch einige Algorithmen gibt, welche einzelne Linien löschen, werden wir diese Möglichkeit anbieten. Als Parameter bekommen unsere beiden Methoden, eine Position und die Anzahl der Linien, welche nach dieser Position gelöscht werden sollen. Das mehrere Zeilen oder Spalten gelöscht werden, kommt zwar relativ selten vor, aber wenn es doch mal nötig ist, wäre es sehr ineffizient die beiden aufeinander folgenden Linien einzeln zu löschen. Außerdem macht es uns kaum Mehrarbeit und als Standardwert werden wir für den zweiten Parameter natürlich eine Eins angeben.
Vor der eigentlichen Löschung prüfen wir, ob die entsprechenden Linien auch existieren. Falls dies nicht der Fall ist, werfen wir eine entsprechende Ausnahme. Sie können zum Testen eine std::out_of_range-Ausnahme werfen. Anschließend löschen wir die entsprechenden Elemente in unserem Daten-Container. Zum Schluss setzen wir die Dimension auf ihren neuen Wert. Das ganze sieht folgendermaßen aus:
public:
void erase_row(size_type const& number, size_type const& count = size_type(1)){
if(rows() > number + count){
throw error::row_access("mitrax::matrix<>::erase_row", dimension_, rows());
}
// Zeilen löschen
iterator iter = data_.begin();
iter += number * columns();
data_.erase(iter, iter + count * columns());
// Dimension anpassen
dimension_.resize(rows() - count, columns());
}
void erase_column(size_type const& number, size_type const& count = size_type(1)){
if(columns() < number + count){
throw error::column_access("mitrax::matrix<>::erase_column", dimension_, columns());
}
// Zeilen löschen
for(size_type i = size_type(); i < rows(); ++i){
iterator iter = data_.begin();
iter += number + (columns() - count) * i;
data_.erase(iter, iter + count);
}
// Dimension anpassen
dimension_.resize(rows(), columns() - count);
}
Wir wollen nachfolgend einige theoretische Betrachtungen zu den Anforderungen an size_type in diesen beiden Methoden vornehmen. Praktisch werden diese höchstwahrscheinlich immer erfüllt sein, den der size_type eines Container ist so gut wie immer ein ganzzahliger eingebauter Datentyp.
Falls der Standardwert für den zweiten Parameter genutzt wird, muss der Integerliteral 1 in ein size_type-Objekt konvertierbar sein. Wäre nicht explizit eine Erstellung eines size_type-Objekts angegeben, müsste diese Umwandlung zusätzlich implizit möglich sein. Die beiden Methoden verlangen, dass size_type standardkonstruierbar ist. Außerdem müssen die Operatoren operator<(), operator++(), operator+(), operator-() und operator*() für size_type überladen sein. Bei der üblichen Implementierung der letzten drei Operatoren folgt, dass size_type kopierkonstruierbar sein muss. Wegen den Vorschriften die C++ zu Random-Access-Iteratoren macht, muss size_type implizit in difference_type konvertierbar sein. Der zweite Parameter des operator+=() eines Random-Access-Iterators muss nämlich von diesem Typ sein.
swap[Bearbeiten]
Wie zuvor schon erwähnt wurde, ist swap() für Container normalerweise durch eine sehr effiziente Variante überladen. Wenn Sie sich nun an unsere Überlegungen zur swap-Funktion von dimension erinnern, werden Sie dieses mal zu dem Schluss kommen, dass sich die Überladung für matrix lohnt. Wir werden einfach für alle Datenmember von matrix swap() aufrufen. Der einzige Nachteil, der sich theoretisch daraus ergibt, besteht darin, dass die swap()-Funktion ihre beiden Operanden in einem undefinierten Zustand belässt, falls bei einem der Unteraufrufe eine Ausnahme geworfen wird. Dies ist jedoch ausgesprochen unwahrscheinlich. Das swap() für die dimension-Objekte kann keine Ausnahme werfen. Dass das swap() für die Container eine Ausnahme wirft, ist ebenfalls unwahrscheinlich, denn wie bereits erläutert haben, werden hier typischerweise nur zwei Zeiger vertauscht. Da das Container-swap() noch einen Hauch kritischer ist, werden wir diesen Aufruf zuerst tätigen. Falls hier tatsächlich eine Ausnahme geworfen werden sollte, haben wir dimension noch nicht verändert und somit ist alles in Ordnung. Die Implementierung sieht wie Folgt aus:
public:
void swap(matrix& m){
using std::swap;
swap(data_, m.data_);
swap(dimension_, m.dimension_);
}
// Außerhalb der Klasse
template < typename T, typename Container >
void swap(matrix< T, Container >& lhs, matrix< T, Container >& rhs){
lhs.swap(rhs);
}
Helferlein[Bearbeiten]
Wie bereits angedeutet, werden wir noch eine kleine Helferklasse einführen, die es den Nutzer ermöglicht, auf einfache Weise die Position in einem eindimensionalen Feld anhand einer zweidimensionalen Angabe zu berechnen. Wir erstellen zu diesem Zweck einen Funktor, also eine Klasse, die den Funktionsoperator überlädt. Im Konstruktor teilen wir dem Funktor mit, wie viele Spalten unsere Matrix letztlich haben soll. Dem Funktionsoperator übergeben wir die X- und die Y-Position. Das Ergebnis wird die eindimensionale Position innerhalb des Containers sein.
Der Datentyp der Positionen ist von der verwendeten matrix-Instanz anhängig. Da es jedoch sehr viele matrix-Instanzen gibt, die den gleichen size_type verwenden, ist es sinnvoll, wenn wir nur eine Templateinstanz unseres Funktors pro size_type anlegen. Daher werden wir die Klasse als Template mit einem Parameter anlegen. Den Zugriff auf die passende Funktorklasse realisieren wir, indem wir innerhalb unserer matrix-Klasse einen typedef für die passende Funktorklasse hinzufügen. Da der Nutzer folglich keine Kenntnis von der Definition der Funktorklasse haben muss, werden wir diese im Namensraum detail innerhalb von mitrax deklarieren.
Diesen Namensraum werden wir innerhalb des Projekts für alles verwenden, mit dem der Nutzer niemals direkten Kontakt haben sollte. Wir werden den Nutzer lediglich innerhalb der Dokumentation über die Verwendung bei indirekter Nutzung aufklären. Das hat für uns den Vorteil, dass wir uns keine größeren Gedanken über den Teil der Schnittstelle machen müssen, den der Nutzer sowieso nicht sieht. Insbesondere können wir auf diese Weise, bei einer späteren Version unserer Bibliothek, problemlos den Teil der Schnittstellen ändern, mit denen der Clientcode keinen Kontakt hat. In Zusammenhang mit den Iteratoren für die Proxyklassen werden Sie dies leicht anhand der Konstruktoren erkennen. Wir werden unsere Funktorklasse auf den Namen position_adapter taufen. Der typedef wird den gleichen Namen tragen.
namespace detail{
template < typename SizeType >
class position_adapter{
public:
position_adapter(SizeType columns):columns_(columns){}
position_adapter(dimension< SizeType > const& dim):columns_(dim.columns()){}
SizeType const operator()(SizeType const& row, SizeType const& column){
return row * columns_ + column;
}
private:
SizeType columns_;
};
}
template < typename T, typename Container = std::vector< T > >
class matrix{
public:
// andere typdefs
typedef detail::position_adapter< size_type > position_adapter;
// ...
};
Der Nutzer kann nun zur effizienten Initialisierung einer Matrix beispielsweise folgendes schreiben, ohne sich Gedanken über die Berechnung der eindimensionalen Position machen zu müssen.
typedef mitrax::matrix< int > matrix;
matrix::dimension_type dimension(3, 5);
matrix::container_type init(elements(dimension));
matrix::position_adapter index(dimension);
for(matrix::size_type row = 0; row < dimension.rows(); ++row)
for(matrix::size_type column = 0; column < dimension.columns(); ++column)
init[index(row, column)] = row;
matrix a1(dimension, init);