Mit der Klasse 'CSimpleTemplateArray' habe ich bereits einen dynamischen Array vorgestellt. Allerdings ist diese Klasse noch sehr dürftig. Daten können bereits sehr einfach kopiert werden, aber ist ein Array einmal erstellt worden, dann lässt er sich in der Größe nicht mehr verändern. Es wären noch Funktionen angebracht, die einzelne Elemente hinzufügen oder entfernen können. Außerdem sollte es möglich sein, einen Array jederzeit neu zu erstellen. Aus diesem Grunde werden wir die bereits existierende Variante von 'CSimpleTemplateArray' verwenden, diese aber in 'CArray' umbenennen und im folgenden um einige Funktionen erweitern.
So sieht die Klasse 'CArray' bisher aus:
template <typename T>
class CArray
{
private:
T *m_pData;
int m_Length;
//Kopiermethode
void _Copy(const CArray<T>& arr);
public:
//Konstruktor
CArray(int = 0);
//Kopierkonstruktor
CArray(const CArray<T>&);
//Länge des Arrays
int GetLength(void) {return m_Length;}
//Destruktor
~CArray(void);
//Wert setzen
T& DataAt(int);
//Operator '='
CArray<T>& operator=(const CArray<T>&);
//Operator '[]'
T& operator[](int Index) {return DataAt(Index);}
};
//Kopiermethode
template <typename T>
void CArray<T>::_Copy(const CArray<T>& arr)
{
//Zunächst prüfen ob die Instanz sich selbst kopieren soll
if (&arr == this) return;
//erst evtl. bestehende Daten löschen
if (m_pData) delete[] m_pData;
//Arraylänge übernehmen
m_Length = arr.m_Length;
//neuen Speicher reservieren
m_pData = new T[m_Length];
//Element für Element kopieren:
for (int iPos = 0; iPos < m_Length; iPos++)
{
m_pData[iPos] = arr.m_pData[iPos];
}
}
//Konstruktor
template <typename T>
CArray<T>::CArray(int Length)
{
if (Length <= 0) m_Length = 1;
else m_Length = Length;
//Speicher reservieren
m_pData = new T[m_Length];
}
//Kopierkonstruktor
template <typename T>
CArray<T>::CArray(const CArray<T>& arr)
{
//Daten initialisieren
m_pData = 0;
m_Length = 0;
_Copy(arr);
}
//Destruktor
template <typename T>
CArray<T>::~CArray(void)
{
if (m_pData)
{
delete[] m_pData;
m_pData = 0;
}
}
//Wert setzen
template <typename T>
T& CArray<T>::DataAt(int Index)
{
if (Index < 0 || Index >= m_Length)
{Index = 0;}
return *(m_pData + Index);
}
//Operator '='
template <typename T>
CArray<T>& CArray<T>::operator=(const CArray<T>& arr)
{
_Copy(arr);
//Instanz zurückgeben
return *this;
}
Da sich in den bereits implementierten Funktionen wenig bis gar nichts ändern wird, habe ich diese nun alle außerhalb der Klasse implementiert, damit nicht jedes Mal wenn die gesamte Klassendeklaration erneut aufgelistet wird, alle Funktionsimplementierungen auch erneut auftauchen. Die einzigen Ausnahmen sind dabei die Funktionen, für deren Implementierung eine Zeile ausreicht. Diese Klasse soll jetzt in den folgenden Abschnitten nach und nach erweitert werden.
Wie bereits erwähnt soll es immer wieder möglich sein eine bestehende Instanz neu zu verwenden. Dazu muss dann zunächst der gesamte Speicher wieder freigegeben und neuer reserviert werden. Dabei muss nur die neue Arraylänge übergeben werden. Die Methode soll nun im folgenden auf den Namen 'Create' hören. Diese Methode soll anschließend auch vom Konstruktor und allen weiteren Methoden aufgerufen werden, welche den Array neu erstellen. Bei der Erstellung zukünftig aber kein Element mehr zusätzlich reserviert, wenn als Länge '0' übergeben wird. Wird als Länge '0' übergeben, dann wird einfach nur der Speicher freigegeben, aber kein neuer reserviert. Ein Aufruf von 'Create' mit '0' als Längenangabe entspricht im Prinzip also einem Löschvorgang. Nach einem Löschvorgang sollte die Methode 'DataAt' keinesfalls mehr aufgerufen werden, da es sonst zwangsläufig zu ungewollten Ergebnissen oder gar zu einem Absturz kommt. Für die Implementierung von 'Create' kann die bisherige Implementierung des Konstruktors mit einer entsprechenden Abwandlung verwendet werden:
//Methode zum Erstellen
template <typename T>
bool CArray<T>::Create(int Length)
{
//erst evtl. bestehende Daten löschen
if (m_pData)
{
delete[] m_pData;
m_pData = 0;
}
//Arraylänge übernehmen
m_Length = Length;
if (m_Length < 0) m_Length = 0;
//neuen Speicher reservieren (wenn nötig)
if (m_Length) m_pData = new T[m_Length];
//Neuer Speicher reserviert?
if (!m_pData) {m_Length = 0; return false;}
else return true;
}
Diese Methode gibt ein Wert vom Datentyp 'bool' zurück, je nachdem ob neuer Speicher reserviert wurde, oder nicht. Nachdem die Methode auch in der Klasse deklariert wurde, lässt sie sich nun vom Konstruktor, vom Destruktor und von der Methode '_Copy' verwenden. Deren Implementierungen ändern sich dann wie folgt:
//Kopiermethode
template <typename T>
void CArray<T>::_Copy(const CArray<T>& arr)
{
//Zunächst prüfen ob die Instanz sich selbst kopieren soll
if (&arr == this) return;
//Array neu erstellen
if (!Create(arr.m_Length)) return;
//Element für Element kopieren:
for (int iPos = 0; iPos < m_Length; iPos++)
{
m_pData[iPos] = arr.m_pData[iPos];
}
}
//Konstruktor
template <typename T>
CArray<T>::CArray(int Length) : m_pData(0), m_Length(0)
{
Create(Length);
}
//Destruktor
template <typename T>
CArray<T>::~CArray(void)
{
Create(0);
}
Die Member (zumindest 'm_pData') sollten innerhalb des Konstruktors in jedem Fall initialisiert werden. Wird nämlich 'm_pData' nicht initialisiert, dann enthält er irgendeinen Wert der wahrscheinlich nicht '0' ist. Die Methode 'Create' wird aber davon ausgehen, dass, wenn der Zeiger einen anderen Wert als '0' besitzt, auf einen reservierten Speicher zeigt. 'Create' gibt diesen vermeintlich vorhandenen Speicher zunächst frei, was zwangsläufig zum Absturz führen wird. Die Member ließen sich natürlich auch (wie bereits bei dem Kopierkonstruktor) innerhalb des Konstruktors initialisieren, ich habe aber hier die Initialisierung über die Elementinitialisierungsliste gewählt. Um Einheitlichkeit zu erreichen, werden die Member nun auch beim Kopierkonstruktor über die Elementinitialisierungslisten initialisiert:
//Kopierkonstruktor
template <typename T>
CArray<T>::CArray(const CArray<T>& arr) : m_pData(0), m_Length(0)
{
_Copy(arr);
}
Da nunmehr die Implementierungen beider Konstruktoren und der des Konstruktors nur noch aus jeweils einer Zeile bestehen, werde ich beide Implementierungen nun in die Klassendeklaration verbannen. Die gesamte Klassendeklaration sieht nun wie folgt aus:
template <typename T>
class CArray
{
private:
T *m_pData;
int m_Length;
//Kopiermethode
void _Copy(const CArray<T>& arr);
public:
//Array (neu) erstellen
bool Create(int);
//Konstruktor
CArray(int Length = 0) : m_pData(0), m_Length(0)
{Create(Length);}
//Kopierkonstruktor
CArray(const CArray<T>& arr) : m_pData(0), m_Length(0)
{_Copy(arr);}
//Länge des Arrays
int GetLength(void) {return m_Length;}
//Destruktor
~CArray(void) {Create(0);}
//Wert setzen
T& DataAt(int);
//Operator '='
CArray<T>& operator=(const CArray<T>&);
//Operator '[]'
T& operator[](int Index) {return DataAt(Index);}
};
Nun lässt sich eine Instanz immer wieder verwenden. Damit wäre der erste Teil der Ergänzungen abgeschlossen. Es fehlen jedoch noch einige weiter Methoden.
Eine weitere Methode, die nicht fehlen sollte, ist eine Methode zum Einfügen einzelner oder mehrerer Elemente. Am besten man implementiert zunächst eine Methode, die mehrere Elemente in Form eines Arrays einfügen kann. Anschließend könnte man diese Methode dann für das Einfügen eines Elements überladen. Diese erstellt dann einfach einen Array mit dem einzufügenden Element und ruft dann die entsprechende Methode zum Einfügen eines Arrays auf. Zunächst muss die Methode, die im folgenden 'Insert' heißen soll, aber erst implementiert werden. Der Methode wird neben dem einzufügenden Array auch ein Index übergeben, welcher angibt, an welcher Position die Elemente schließlich eingefügt werden sollen. Alle Elemente, welche zuvor an dieser Stelle existierten, werden im Prinzip nach hinten verschoben. Programmieren ließe sich dies wie folgt: Zunächst wird genügend Speicher reserviert um sowohl die alten als auch die neuen Elemente aufnehmen zu können. Anschließend wird Element für Element aus dem alten Speicher und aus dem Speicher des hinzuzufügenden Arrays in den neuen Speicher kopiert. Soviel zur Theorie, nun zur Praxis:
//Methode zum Einfügen mehrerer Elemente
template <typename T>
bool CArray<T>::Insert(const CArray<T>& arr, int Index)
{
//Im Falle eines leeren Arrays kein Einfügen notwendig
if (arr.m_Length == 0) return false;
//Array soll sich nicht in sich selber einfügen
if (this == &arr) return false;
//Gültigkeit des Indexes überprüfen
if (Index < 0) Index = 0;
if (Index > m_Length) Index = m_Length;
//Alte Member aus der Instanz entfernen
T* pOldData = m_pData; m_pData = 0;
int OldLength = m_Length; m_Length = 0;
//Instanz neu erstellen
if (!Create(OldLength + arr.m_Length))
{
//Erstellung nicht erfolgreich
delete[] pOldData;
return false;
}
//Positionszeiger auf gegenwärtiges Element
T* pSrcPos = pOldData;
T* pTarPos = m_pData;
int iPos = 0;
//Alte Elemente bis Index kopieren
for (iPos = 0; iPos < Index; iPos++, pSrcPos++, pTarPos++)
{
*pTarPos = *pSrcPos;
}
//Quellpositionszeiger neu setzen
pSrcPos = arr.m_pData;
//Alle Elemente des einzufügende Arrays kopieren
for (iPos = 0; iPos < arr.m_Length; iPos++, pSrcPos++, pTarPos++)
{
*pTarPos = *pSrcPos;
}
//Quellpositionszeiger neu setzen
pSrcPos = pOldData + Index;
//Alte Elemente ab Index kopieren
for (iPos = Index; iPos < OldLength; iPos++, pSrcPos++, pTarPos++)
{
*pTarPos = *pSrcPos;
}
//Alten Speicher wieder freigeben und Funktion beenden
delete[] pOldData;
return true;
}
Um sowenig wie möglich Speicher kopieren zu müssen, werden zunächst die Daten der aufrufenden Instanz "geklaut". Anschließend stehen die Daten nur noch der Funktion (durch die Variablen 'pOldData' und 'OldLength') nicht aber der Instanz zur Verfügung. Nach der Erstellung werden dann zwei Zeiger ('pSrcPos' und 'pTarPos') deklariert, die dann jeweils auf das Element zeigen, in das kopiert oder von dem kopiert werden soll. Der Zeiger 'pTarPos' läuft im Prinzip durch die gesamten Daten des neuen Arrays. Der Zeiger 'pSrcData' durchläuft die gesamten Daten des alten Arrays. Zwischendurch verweist er aber auf die Daten des hinzuzufügenden Arrays. Am Ende wird dann zurückgegeben, ob der Vorgang erfolgreich war oder nicht. Das dürfte als Erklärung reichen. Nun wollen wir uns der Überladung der Funktion 'Insert' widmen, mit der man dann lediglich auch einfach nur ein Element kopieren kann:
//Methode zum Einfügen eines Elements
template <typename T>
bool CArray<T>::Insert(const T& el, int Index)
{
//Array aus dem übergebenen Element erstellen
CArray<T> arr(1);
arr[0] = el;
//Element einfügen
return Insert(arr, Index);
}
Mit einer Methode zum Einfügen besteht auch die Möglichkeit zum einfachen Anfügen. Gewöhnlich wird dafür eine Methode 'Add' implementiert. Eine andere Variante wäre stattdessen den Operator '+=' zu überladen. Ich werde hier beide Varianten vorstellen, da sie sich im Grunde nur durch den Funktionsnamen unterscheiden und sich somit in der Implementierung kaum unterscheiden. Allerdings soll die Methode 'Add' wie die Methode 'Insert' den Wert 'bool', während der Operator die eigene Instanz als Referenz zurückliefert. Die Implementierungen sähen dann wohl wie folgt aus:
//Methode zum Anfügen eines Arrays
template <typename T>
bool CArray<T>::Add(const CArray<T>& arr)
{
return Insert(arr, m_Length);
}
//Methode zum Anfügen eines Elements
template <typename T>
bool CArray<T>::Add(const T& el)
{
return Insert(el, m_Length);
}
//Operator '+=' zum Anfügen eines Arrays
template <typename T>
CArray<T>& CArray<T>::operator += (const CArray<T>& arr)
{
Insert(arr, m_Length);
return *this;
}
//Operator '+=' zum Anfügen eines Elements
template <typename T>
CArray<T>& CArray<T>::operator += (const T& el)
{
Insert(el, m_Length);
return *this;
}
Wenn nun schon der Operator '+=' überladen wird, dann sollte auch der Operator '+' überladen werden, der zwei Arrays oder ein Array und ein Wert zusammenfügt und den neu entstandenen Array zurückgibt. Ihre Implementierungen dürften in etwa wie folgt aussehen:
//Operator '+' zum Anfügen eines Arrays
template <typename T>
CArray<T> CArray<T>::operator + (const CArray<T>& arr) const
{
//Kopie der Instanz erstellen und übergebenen Array anfügen
CArray<T> arrrtn = *this;
arrrtn.Insert(arr, arrrtn.m_Length);
return arrrtn;
}
//Operator '+' zum Anfügen eines Elements
template <typename T>
CArray<T> CArray<T>::operator + (const T& el) const
{
//Kopie der Instanz erstellen und übergebenes Element anfügen
CArray<T> arrrtn = *this;
arrrtn.Insert(el, arrrtn.m_Length);
return arrrtn;
}
Nun müssen alle Methoden und Operatoren noch innerhalb der Klassendeklaration aufgenommen werden. Die gesamte Klasse sieht dann in etwa so aus (die Implementierungen der beiden 'Add'-Methoden werden wieder in die Klassendeklaration verbannt):
template <typename T>
class CArray
{
private:
T *m_pData;
int m_Length;
//Kopiermethode
void _Copy(const CArray<T>& arr);
public:
//Array (neu) erstellen
bool Create(int);
//Methoden zum Einfügen
bool Insert(const CArray<T>&, int);
bool Insert(const T&, int);
//Methoden zum Anfügen
bool Add(const CArray<T>& arr) {return Insert(arr, m_Length);}
bool Add(const T& el) {return Insert(el, m_Length);}
//Operatoren zum Anfügen
CArray<T>& operator += (const CArray<T>&);
CArray<T>& operator += (const T&);
CArray<T> operator + (const CArray<T>&) const;
CArray<T> operator + (const T&) const;
//Konstruktor
CArray(int Length = 0) : m_pData(0), m_Length(0)
{Create(Length);}
//Kopierkonstruktor
CArray(const CArray<T>& arr) : m_pData(0), m_Length(0)
{_Copy(arr);}
//Länge des Arrays
int GetLength(void) {return m_Length;}
//Destruktor
~CArray(void) {Create(0);}
//Wert setzen
T& DataAt(int);
//Operator '='
CArray<T>& operator=(const CArray<T>&);
//Operator '[]'
T& operator[](int Index) {return DataAt(Index);}
};
Nun ist die Funktionalität implementiert um ein Array zu erstellen, ihn zu kopieren, einzelne Elemente zu ändern, und Elemente an- und einzufügen. Nun fehlt noch die Möglichkeit einzelne Elemente zu entfernen. Eine Methode, mit der man Elemente entfernen kann, wird Thema des nächsten Abschnitts sein.
Um die Möglichkeit zu gestatten gleich mehrere Elemente zu entfernen sollte die Methode zwei Indexwerte übernehmen. Alle Elemente, deren Index dann zwischen diesen beiden Indices liegt, werden dann entfernt und der Array wird dementsprechend kleiner. Eine mögliche Implementierung wäre folgende:
//Methode zum Entfernen von Elementen
template <typename T>
bool CArray<T>::Remove(int Start, int End)
{
//Im Falle eines leeren Arrays kein Entfernen möglich
if (m_Length == 0) return false;
//Indices überprüfen
if (Start > End)
{
int Index = Start;
Start = End;
End = Index;
}
if (Start < 0) Start = 0;
if (Start >= m_Length) Start = m_Length - 1;
if (End < 0) End = 0;
if (End >= m_Length) End = m_Length - 1;
//Länge des Bereichs bestimmen, der gelöscht werden soll
int RegLength = End - Start + 1;
//Alte Member aus der Instanz entfernen
T* pOldData = m_pData; m_pData = 0;
int OldLength = m_Length; m_Length = 0;
//Instanz neu erstellen
if (!Create(OldLength - RegLength))
{
//Erstellung nicht erfolgreich
delete[] pOldData;
return false;
}
//Positionszeiger auf gegenwärtiges Element
T* pSrcPos = pOldData;
T* pTarPos = m_pData;
int iPos = 0;
//Alte Elemente bis Start kopieren
for (iPos = 0; iPos < Start; iPos++, pSrcPos++, pTarPos++)
{
*pTarPos = *pSrcPos;
}
//Quellpositionszeiger neu setzen
pSrcPos = pOldData + End + 1;
//Alte Elemente ab End kopieren
for (iPos = End + 1; iPos < OldLength; iPos++, pSrcPos++, pTarPos++)
{
*pTarPos = *pSrcPos;
}
//Alten Speicher wieder freigeben und Funktion beenden
delete[] pOldData;
return true;
}
Diese Funktion weist in ihrer Implementierung sehr viele Parallelen mit der der Funktion 'Insert' auf. So werden auch hier die Daten der Instanz von der Funktion "geklaut" und sind anschließend für die Instanz nicht mehr zugänglich. Auch wird hier die Instanz neu erstellt. Auch hier werden zwei Positionszeiger deklariert, die wie bei der Methode 'Insert' auf die gegenwärtigen Positionen zeigen in die oder von den kopiert werden soll. Bei dem Kopiervorgang werden einfach die Elemente des alten Puffers (der geklaut wurde) beim Kopieren übergangen, die im Bereich der zu löschenden Objekte liegen. So werden nur die Objekte des alten Puffers in den Bereichen von '0' bis 'Start' und von 'End + 1' bis zum Pufferende in den neuen Puffer kopiert. Anschließend wird auch hier der alte Puffer freigegeben. Weiteres lässt sich aus dem Quellcode entnehmen. Nun macht es im Prinzip durchaus Sinn die Funktion 'Remove' ein- bis zweimal zu überladen. Es wäre durchaus auch sinnvoll nur einen Index zuzulassen. In diesem Falle wird dann nicht ein ganzer Bereich von Elementen angegeben, sondern nur der Index eines einzigen Elements. Die Implementierung sähe dann wohl wie folgt aus:
//Methode zum Entfernen eines Elements
template <typename T>
bool CArray<T>::Remove(int Index)
{
return Remove(Index, Index);
}
Eine weitere mögliche Überladung wäre, überhaupt keinen Parameter zu übergeben. Diese Überladung der Funktion 'Remove' könnte dann wie ein Aufruf von 'Create(0)' den ganzen Array wieder freigeben. Diese Implementierung könnte dann so aussehen:
//Methode zum Löschen aller Elemente
template <typename T>
bool CArray<T>::Remove(void)
{
return Remove(0, m_Length - 1);
}
Ein Aufruf von 'Create(0)' wäre aber wahrscheinlich effizienter, denn die Funktion 'Create' wird ja auch noch einmal innerhalb der Methode 'Remove' aufgerufen. Dies geschieht allerdings erst nach mehreren Überprüfungen. Aus diesem Grunde wäre es sinnvoller die letzte Methode wie folgt zu überschreiben:
//Methode zum Löschen aller Elemente
template <typename T>
bool CArray<T>::Remove(void)
{
return Create(0);
}
Nimmt man die Implementierungen der beiden Überladungen von 'Remove' mit in die Klassendeklaration, dann sollte die gesamte Klassendeklaration nun wie folgt aussehen:
template <typename T>
class CArray
{
private:
T *m_pData;
int m_Length;
//Kopiermethode
void _Copy(const CArray<T>& arr);
public:
//Array (neu) erstellen
bool Create(int);
//Methoden zum Einfügen
bool Insert(const CArray<T>&, int);
bool Insert(const T&, int);
//Methoden zum Anfügen
bool Add(const CArray<T>& arr) {return Insert(arr, m_Length);}
bool Add(const T& el) {return Insert(el, m_Length);}
//Operatoren zum Anfügen
CArray<T>& operator += (const CArray<T>&);
CArray<T>& operator += (const T&);
CArray<T> operator + (const CArray<T>&) const;
CArray<T> operator + (const T&) const;
//Funktionen zum Entfernen
bool Remove(int, int);
bool Remove(int Index) {return Remove(Index, Index);}
bool Remove(void) {return Create(0);}
//Konstruktor
CArray(int Length = 0) : m_pData(0), m_Length(0)
{Create(Length);}
//Kopierkonstruktor
CArray(const CArray<T>& arr) : m_pData(0), m_Length(0)
{_Copy(arr);}
//Länge des Arrays
int GetLength(void) {return m_Length;}
//Destruktor
~CArray(void) {Create(0);}
//Wert setzen
T& DataAt(int);
//Operator '='
CArray<T>& operator=(const CArray<T>&);
//Operator '[]'
T& operator[](int Index) {return DataAt(Index);}
};
Nun sind im Prinzip alle wesentlichen Methoden implementiert, die eine Klasse, die sich selbst 'CArray' nennt, implementieren sollte.
Da die Methode 'GetLength' keinen der Member der Klasse verändert, sondern lediglich die Länge des Arrays zurückgibt sollte diese als 'const' deklariert werden. (Wie dies geschieht, ist dem letzten Kapitel zu entnehmen.) Eine Arrayklasse könnte noch weitere Methoden implementieren. So wäre es beispielsweise denkbar eine Methode zu implementieren, welche ein Teil eines Arrays in Form eines neuen zurückgeben kann. Auch eine Methode, die den Array irgendwie sortiert wäre denkbar. Allerdings hätte letzteres wiederum zur Folge, dass nicht jeder Datentyp für den Array verwendet werden kann. Diese Klasse besitzt alle wesentlichen Funktionen, die eine Klasse, die sich selbst 'CArray' nennt, implementieren sollte. Ein Teilarray könnte beispielsweise auch ohne eine entsprechende Memberfunktion erstellt werden. (Man braucht nur ein Array geeigneter Größe erstellen, in dem man dann alle gewünschten Elemente eines bereits existierenden Arrays kopiert.) Ich sehe im Prinzip keinen Grund dafür die Klasse noch um Funktionen zu erweitern, die die Klasse nur noch mehr verkomplizieren würden.
Während der Erstellung dieser Klasse sind bereits einige Techniken (wie u.a. Operatorüberladung, Vorlagenklassen, etc.) aufgegriffen worden, die bereits zuvor eingeführt wurden. Weitere Techniken werden in den nächsten Lektionen noch zum Tragen kommen.
Hier noch einmal der Quelltext der aktuellsten Version der Klasse 'CArray':
array_src.exe (Quelltext, gepackt)
