Nächste Seite: Was noch fehlt: Aufwärts: Lösungen Vorherige Seite: Felder beliebigen Typs mit Inhalt
Die Funktionsweise der Musterlösung sollte aus den Kommentaren hervorgehen; im Anschluß findet sich ein kleines Testprogramm.
//=============================================-*-c++-*-============== // // Time-stamp: "20.06.03 14:15 vararr.h klaus@wachtler.de" // //==================================================================== // // Die Klasse stellt eine template-Klasse für variable Felder // zur Verfügung. // //==================================================================// // // // Copyright: // // ========== // // // // ///| |||\ || |||| // // // ////| |||\\ || |||| // // // ////|| ||||\\ || |||| // // // //// || |||| \\ || |||| // // // ////==|| |||| \\|| ||||// // // //// || |||| \\| |||// // // //// || |||| \| ||// // // |// // // |||| /| // // ///| ||||=====// ////======= // // |||| /|| // // ////| |||| // //// // // |||| //|| // // ////|| |||| // //// // // |||| // || // // //// || |||| // //// // // ||||// ||// // ////==|| ||||=(( ((((======= // // |||// |// // //// || |||| \\ \\\\ // // |||/ |/ // //// || |||| \\ \\\\======= // // // // (C) 1997-2003 AnyWare // // // // Klaus Wachtler // // Breidingstr. 17 // // 29614 Soltau // // // // Tel. (49)-5191-70 2 71 // // eMail AnyWare@Wachtler.de // // // //==================================================================// // // Geschichte: // =========== // // Datum: Name: Vers. Änderung: // // 16.05.1997 kw 0.1 erster Entwurf aus [1] intarr.cc entnommen // // 12.06.1997 kw Fehlerbehandlung auf CError umgestellt // // 03.07.1997 kw 0.1b freigegeben // // 15.07.1997 kw 0.1c freigegeben // // 17.07.1997 kw Fehlerkorrektur: // Die Übergabe eines VarArr-Feldes an eine // Funktion erzeugte ein neues (temporäres) // Objekt, dabei wird ein default-Konstruktor // (statt: // VarArr<T>( const VarArr<T> & init ) // ) aufgerufen. // Dieser allokiert das Feld (p) nicht neu, // sondern kopiert nur den Zeiger. // beim Verlassen der Funktion wird der // Destruktor aufgerufen, und das allokierte // Feld (p) freigegeben (obwohl das zugehörige // ursprüngliche Objekt noch existiert!) // Beim Freigeben des ursprünglichen Objekts // wird der zugehörige Destruktor nochmals // (p) freigeben. // Lösung: // VarArr<T>( const VarArr<T> & init ) // korrekt definiert. // // Bei dieser Gelegenheit auch gleich: // VarArr<T> & operator=( const VarArr<T> ) // definiert. // // 18.07.1997 kw - Erweiterung auf negative Indizes // - Allokieren grösserer Blöcke statt // Verlängerung auf gerade benötigte Länge. // // 19.07.1997 kw Fehlerbehandlung mit CError wieder entfernt: // ohne feste untere Grenze gibt es auch keine // Benutzerfehler mehr (Setzen von l(), ug(), // und og() auf unsinnige Werte erklärt das Feld // einfach für freigegeben). // // 22.07.1997 kw Speicherfehler geknackt (Bei Adreßberechnung // von p0_neu, wenn Elementgröße kein Vielfaches // von 4 ist) // // 23.07.1997 kw 0.1d freigegeben // // 24.07.1997 kw - Kommentare korrigiert // - copy-Konstruktor: Kopieren mit "=" ersetzt // durch entsprechenden Teil aus operator=(), // da sonst eine Endlosschleife beim Zuweisen // entsteht. // // 28.01.1998 kw 0.2 einige vorhandene Funktionen als "... const" // definiert, sowie die Funktion: // T & operator[]( int index ) const // neu definiert. // Damit kann man mit einem Feldzugriff (mit []) // auch in Objekte fassen, die als const ver- // einbart sind. Bei einer Feldgrenzenüber- // schreitung wird dann nicht das Feld // vergrößert, sondern eine Ausnahme ausgeworfen // (CErrorVarArrFeldgrenzenConst). // Damit ist jetzt auch ein #include "cerror.h" // nötig. // // 30.01.1998 kw Feldgrenzenüberprüfung korrigiert; // die Überprüfung kann mit // #define VARARR_FELDGRENZENKONTROLLIEREN // eingeschaltet werden. // // 08.05.1998 kw Bei DEBUG ist etwas mehr public // // 23.05.1998 kw 0.3 Neuerung: // Wenn VOR dem #includen von vararr.h // ein VARARR_NULL_POINTER #definiert // wird, dann wird beim Verlängern eines // Feldes kontrolliert, ob der Name des // zugrundeliegenden Typs der Feldelemente // auf "*" endet. // Wenn ja, scheint es ein Zeigertyp zu sein, // und der gesamte neu allokierte Speicher wird // mit Nullen vorbelegt. // // 01.03.1999 kw Einbau von Kleinst- und Größtwerten, // bei deren Überschreitung eine assert()- // Verletzung generiert wird (MINASSERT, // MAXASSERT) // // 14.03.1999 kw So eingestellt, daß im Normalfall keine // weiteren Dateien nötig sind // (also VARARR_NULL_POINTER und // VARARR_FELDGRENZENKONTROLLIEREN aus) // 20.10.1999 kw // 27.05.2000 kw Anpassungen an Linux/gcc // Fehler mit Defaultwerten eliminiert; // in dieser Form jetzt für Formelinterpreter // unter Linux geeignet // // 08.09.2002 kw Mechanismus mit MINASSERT/MAXASSERT entfernt // (war nur zum Debuggen interessant), // sowie die Nullpointer (mit // VARARR_NULL_POINTER, nicht portabel) // // 09.09.2002 kw in operator[] einen Schnelltest eingefügt, // ob resize() überhaupt aufgerufen werden muß // //==================================================================== // // Prinzipiell können damit alle Objekte in dynamischen Feldern // verwaltet werden. // Voraussetzungen: // - bei Basisdatentypen: keine // - bei Klassen: // 1) die Objekte müssen mit new und new[] allokierbar sein, // mit delete und delete[] wieder gelöscht werden können. // Also: Saubere Konstruktoren (ohne Parameter, und mit // const&-Initialisierung) und Destruktor // 2) die Objekte müssen mit operator= kopierbar sein. // Der Standardoperator = kopiert nur byteweise. Wenn die // Objekte also beispielsweise mit malloc() oder new beschafften // Speicher haben, dann braucht man auch einen sauberen // Kopieroperator = (der ggf. ein Objekt sauber aufsetzt). // //==================================================================== // // Verwendung: // =========== // // Der Anwender vereinbart ein Feld von beispielsweise int-Werten // etwa so: // #include <vararr.h> // VarArr<int> feld; // // Dann kann er auf beliebige Feldelemente zugreifen, z.B.: // feld[5] = 10; // feld[-1] = 3; // feld[1] = feld[5]+feld[-1]; // cout << feld[1]; // // Dabei wird die Länge des Feldes dynamisch so angepaßt, daß // die angesprochenen Werte auch existieren. // // // Abfrage der aktuellen Feldgröße: // // Mit den Elementfunktionen ug(), og(), und l() kann man die // untere bzw. obere maximale Feldgrenze und die aktuelle Länge // erfragen. // Bei einem frisch vereinbarten Feld liefert ug() den Wert INT_MAX, // og() den Wert INT_MIN, und l() den Wert 0. // // // Setzen der Feldgröße: // // Mit l( int lneu ) kann man die aktuelle Gesamtlänge setzen. // Ein positives lneu setzt dabei die untere Grenze auf 0, und die // obere Grenze auf lneu-1, so daß nachfolgende Aufrufe von l() wieder // og()-ug()+1 liefern. // Negative Werte oder 0 setzen das Feld zurück, sodaß die Länge // wieder 0 ist. // Dabei wird kein Speicher freigegeben, siehe [Funktionsweise]. // // Mit ug( int ugneu ) und og( int ogneu ) kann man die jeweilige // Feldgrenze von Hand setzen. Nachfolgende Aufrufe von l() liefern // dann eine entsprechend korrigierte Länge. // Ist ugneu größer als die bisherige obere Grenze, dann wird das Feld // als leer betrachtet (wie mit l(0)). // Ebenso, wenn ogneu kleiner ist als die bisherige untere Grenze. // Bei einem vorher leeren Feld (neu vereinbart, oder mit l(0) // geleert) setzt wird mit der oberen Grenze auch gleichzeitig die // untere gesetzt, und umgekehrt. Bei einem leeren Feld setzt also // og(10) auch gleichzeitig die Untergrenze auf 10. Das Element [10] // ist dann das einzige Element im Feld. ug() und og() liefern dann // den Wert 10, l() liefert 1. // // ug(int), og(int), und l(int) liefern jeweils den neuen Wert des // entsprechenden Parameters zurück (ihr Argument, oder 0 für l(int), // INT_MAX für ug(int), und INT_MIN für og(int)). // // // Unbenutzte Lücken im Feld: // // Es wird intern NICHT kontrolliert, welche Elemente belegt sind. // Nur die Grenzen werden mitgeführt und gegebenenfalls angepaßt. // Das heißt, daß Elemente, die nie belegt wurden, gelesen werden // können, aber ihr Inhalt ist undefiniert (es sei denn, es ist // für die Elemente ein Konstruktor definiert, der eine definierte // Vorbelegung vornimmt). // // Bei Bedarf kann man mit SetDefault() einen Wert für zukünftig // entstehende Lücken setzen; bis an diese Elemente etwas anderes // zugewiesen wird, haben sie dann wenigstens einen definierten Inhalt // (beispielsweise macht es Sinn, für ein Feld von Zeigern NULL als // Standardwert zu verwenden). // // Bereits bestehende Lücken werden von SetDefault() nicht // beeinflußt. // // // Debug-Ausgabe: // // Durch #definieren von DEBUGVARARR vor dem #includen von vararr.h // ereicht man eine ausführliche Ausgabe der internen Vorgänge. // //==================================================================== // // Funktionsweise: // =============== // // Es wird beim ersten Zugriff auf ein Element ein Stück Speicher // nur für dieses Feldelement allokiert. // Bei jedem weiteren Zugriff (lesend oder schreibend) wird // geprüft, ob der Zugriff in dem allokierten Bereich erfolgt, oder // außerhalb. Gegebenenfalls wird das Feld in die richtige Richtung // vergrößert. Dabei wird aber nicht nur bis zum aktuell benötigten // Element vergrößert, sondern um REALLOC_MEHR Elemente mehr. // Dadurch werden die Fälle, in denen man neu allokieren und alle // alten Elemente umkopieren muß, wesentlich seltener. // Nachteil ist natürlich, daß immer ein paar unbenutzte Elemente // in der Gegend herumliegen. // // Es gibt zwei Feldbereiche mit eigenen Ober- und Untergrenzen: // - Den Bereich, den der Benutzer sieht. Er reicht vom untersten // benutzten Element, bis zum höchsten benutzten Element. // Dieser Bereich wird von _ug, _og, und _l beschrieben. // - Der allokierte Bereich ist meist größer, und reicht von // _pallok bis (_pallok+_lallok-1). // // Es werden intern zwei Zeiger auf das allokierte Feld gepflegt, // nämlich _p0 und_pallok. // _p0 zeigt auf das Element [0] (auch wenn die untere Grenze // positiv ist, oder die obere Grenze negativ; dann ist _p0[0] nicht // gültig; _p0 selbst aber wohl). // _pallok zeigt auf das allokierte Feld. // // Anhand von _pallok==NULL wird erkannt, daß das Feld noch nicht // allokiert wurde. // // Bei jeder Feldvergrößerung wird nicht nur bis zur aktuell // geforderten Länge vergrößert, sondern gleich ein ordentliches Stück // mehr genommen. Aber wieviel? Die Verlängerung ist der größere // der beiden Werte (REALLOC_MIN1) und (REALLOC_MIN2). // Um einerseits kleine Felder effektiv verwenden zu können, sollte // REALLOC_MIN1 ein kleiner konstanter Wert sein, z.B. (5). // Um andererseits bei großen Feldern das aufwendige Neuallokieren // zu begrenzen, sollte REALLOC_MIN2 längenabhängig sein, also mit // der Feldlänge mitwachsen, z.B.: (l_allok/2). // Einzige Ausnahme: der erste Zugriff mit beliebigem Index läßt nur // das geforderte Element allokieren, da VarArr nicht wissen kann, ob // das Feld in Zukunft nach oben oder nach unten wachsen wird. // // Durch dieses großzügige Allokieren muß _pallok nun nicht identisch // sein mit _p0[ug()]. // Der Benutzer sieht Feldelemente von [_ug] bis [_og], der // allokierte Bereich reicht von _pallok bis (_pallok+_lallok-1). // Diese beiden Bereiche müssen nicht identisch sein, aber: // Der Benutzerbereich liegt immer innerhalb des allokierten Bereichs. // // Beispiel: // REALLOC_MIN1 sei 3, und REALLOC_MIN2 sei (_lallok/2). // // Mit der Definition: // VarArr<int> feld; // wird ein neues Feld geschaffen. // feld sieht dann so aus: // // _l == 0 // _lallok == 0 // _og == INT_MIN // _ug == INT_MAX // _p0 == NULL // _pallok == NULL // // Durch die Zuweisung: // feld[0] = 12; // wird nur Platz für feld[0] allokiert. _p0 und _pallok zeigen auf // diesen Wert. // // feld hat dann beispielsweise | Der Speicher könnte so aussehen: // folgenden Inhalt: | // // _l == 1 // _lallok == 1 | | // 5004 +-------------------------+ // _og == 0 | (int)feld[0] | // _ug == 0 | == | // | (int)12 | // _p0 == 5000 -----+ | | // _pallok == 5000 -----+------> 5000 +-------------------------+ // | | // Durch den Zugriff: | | // feld[-2] = 13; // passiert folgendes: // - das Feld muß nach unten verlängert werden. Da REALLOC_MIN1 aber // 3 ist, müssen über das ohnehin nötige feld[-2] hinaus noch zwei // Elemente mehr allokiert werden (insgesamt also [-4] bis [-1]). // Es wird also ein Feld mit fünf Elementen allokiert, und das // alte Feld freigegeben (nach dem Kopieren des einzigen Elements) // - _pallok zeigt auf das niedrigste allokierte Element feld[-4] // - _p0 zeigt auf die neue Position von feld[0] // - _ug wird auf -2 gesetzt // - _l wird auf 3 gesetzt (weil für den Benutzer die Feldlänge // immer _og-_ug+1 ist) // - _lallok wird auf 5 gesetzt, da das Feld von einem auf // fünf Elemente verlängert wird. // // Die Situation könnte dann so aussehen: // // | | // 6016 +-------------------------+ // | (int)feld[0] | // | == | // | (int)12 | // | | // +---------> 6012 +-------------------------+ // | | (int)feld[-1] | // | | == | // | | ?? | // | | | // | 6008 +-------------------------+ // | | (int)feld[-2] | // | | == | // | | (int)13 | // | | | // | 6004 +-------------------------+ // | | (int)feld[-3] | // | | == | // _l == 3 | | ?? | // _lallok == 4 | | | // | 6000 +-------------------------+ // _og == 0 | | (int)feld[-4] | // _ug == -2 | | == | // | | ?? | // _p0 == 6012 --+ | | // _pallok == 5996 ------------> 5996 +-------------------------+ // // Aus Effizienzgründen wird allokierter Speicher für das eigentliche // Feld nie mehr freigegeben, // bis der Destruktor des gesamten Feldes aufgerufen wird. // Also wird auch beim Aufruf von l(0) nichts freigegeben, sondern es // werden nur _l, _ug, und _og gesetzt. _p0 bleibt auf das bisherige // Element [0] gerichtet. // // Ausnahme: wenn das Feld für leer erklärt wird (z.B. durch l(0)), // und danach als erstes auf ein Element außerhalb des allokierten // Bereichs zugegriffen wird, dann wird der gesamte allokierte Bereich // freigegeben und nur Platz für das aktuell nötige Element allokiert. // // Wenn _pallok!=NULL, dann gilt: // - ( _pallok ) zeigt auf das unterste allok. Element // - ( _pallok + _lallok ) zeigt HINTER das allokierte Feld // - ( _pallok + _lallok - 1 ) zeigt auf das letzte allokierte Element // - ( _p0 ) zeigt auf das Element [0] // - ( _p0 + _ug ) zeigt auf das unterste Benutzerelement // - ( _p0 + _og ) zeigt auf das oberste Benutzerelement // // Dazu sind private member-Funktionen definiert: // - _p_letzt() liefert Zeiger auf das letzte allokierte Element // - _p_ug() liefert Zeiger auf das unterste Benutzerelement // - _p_og() liefert Zeiger auf das oberste Benutzerelement // Achtung: // Diese darf man nur aufrufen, wenn _pallok!=NULL ist!!! // //==================================================================== // // Benötigt: // ========= // // --- // //==================================================================== // // Umgebung: // ========= // // getestet mit: // // + gcc/Linux // + Visual C++ 4.2 - 6.0, Windows NT 4.0/SP3 // //==================================================================== // // Literatur: // ========== // // [1] Klaus Wachtler: C++ // // [2] Gedruckte Dokumentation duh.ps, und // Online-Hilfe duh.hlp // //====================================================================
#ifndef _VARARR
#define _VARARR
#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <climits>
// Mit VARARR_FELDGRENZENKONTROLLIEREN kann man eine
// Feldgrenzenüberprüfung einschalten.
// Diese wird in
// T & operator[]( int index ) const
// wirksam, also beim Zugriff auf ein Element eines const-Objekts.
// In diesem Fall darf das Feld nicht implizit verlängert werden,
// weil ja "const". Eine Referenz auf ein Element darf dann
// auch nicht geliefert werden, also wird eine exception geworfen.
// Wenn VARARR_FELDGRENZENKONTROLLIEREN nicht definiert ist,
// dann findet keine Kontrolle statt. Vielmehr wird dann eine
// unbrauchbare Referenz auf irgendwas im Speicher geliefert.
// Viel Spaß damit!
// Seit 08.09.2002 wird in diesem Fall eine Ausnahme vom Typ
// std::out_of_range geworfen (vorher war es eine Ausnahme von einem
// eigenen Typ CError).
#define VARARR_FELDGRENZENKONTROLLIEREN
#define nDEBUGVARARR
#ifdef VARARR_FELDGRENZENKONTROLLIEREN
#include <stdexcept>
#endif /* ifdef VARARR_FELDGRENZENKONTROLLIEREN */
#ifndef REALLOC_MIN1
#define REALLOC_MIN1 (5)
#endif /* ndef REALLOC_MIN1 */
#ifndef REALLOC_MIN2
#define REALLOC_MIN2 (_lallok/2)
#endif /* ndef REALLOC_MIN2 */
// Es werden REALLOC_MEHR Elemente allokiert, als mindestens nötig.
// Mindestens nötig wäre immer 1 (für das aktuelle).
#ifndef REALLOC_MEHR
#define REALLOC_MEHR \
( ( REALLOC_MIN1>REALLOC_MIN2 ? REALLOC_MIN1 : REALLOC_MIN2 ) - 1 )
#endif /* ndef REALLOC_MEHR */
#ifndef assert
#include <assert.h>
#endif /* ifndef assert */
template<class T> class VarArr
{
private:
int _l; // momentane Länge (für Benutzer)
int _lallok; // allokierte Länge
int _ug; // untere Feldgrenze (für Benutzer)
int _og; // obere Feldgrenze (für Benutzer)
T * _p0; // Zeiger auf Element [0] (auch dann, wenn
// [0] nicht im Feld enthalten ist)
T * _pallok; // Zeiger auf das eigentliche Feld
T * _default; // NULL oder Zeiger auf default-Wert
// Vorbelegung für leeres Feld;
void reset()
{
#ifdef DEBUGVARARR
cerr << "[-] VarArr<T>::reset()" << endl;
#endif /* DEBUGVARARR */
_l
= _lallok
= 0;
_og = INT_MIN;
_ug = INT_MAX;
_p0
= _pallok
= _default
= NULL;
}
// gibt ein belegtes Feld frei (es wird nicht tatsächlich
// freigegeben; vielmehr werden _ug, _og und _l gesetzt):
void loesche()
{
#ifdef DEBUGVARARR
cerr << "[-] VarArr<T>::loesche()" << endl;
#endif /* DEBUGVARARR */
if( _default && _lallok>0 )
{
for( int i=0; i<_lallok; i++ )
{
_pallok[i] = *_default;
}
}
else
{
}
_l = 0;
_og = INT_MIN;
_ug = INT_MAX;
// Testweise geben wir alles frei:
delete[] _pallok; _pallok = NULL; // Speicher freigeben
reset(); // Initialisieren
//.
}
// liefert Zeiger auf das letzte allokierte Element
// (_pallok muß !=NULL sein!!!!!!!)
T *_p_letzt() const
{
#ifdef DEBUGVARARR
cerr << "[-] T * VarArr<T>::_p_letzt()" << endl;
#endif /* DEBUGVARARR */
assert( _pallok!=NULL );
return ( _pallok + _lallok - 1 );
}
// liefert Zeiger auf das unterste Benutzerelement
// (_pallok muß !=NULL sein!!!!!!!)
T *_p_ug() const
{
#ifdef DEBUGVARARR
cerr << "[-] T * VarArr<T>::_p_ug()" << endl;
#endif /* DEBUGVARARR */
assert( _pallok!=NULL );
return ( _p0 + _ug );
}
// liefert Zeiger auf das oberste Benutzerelement
// (_pallok muß !=NULL sein!!!!!!!)
T *_p_og() const
{
#ifdef DEBUGVARARR
cerr << "[-] T * VarArr<T>::_p_og()" << endl;
#endif /* DEBUGVARARR */
assert( _pallok!=NULL );
return ( _p0 + _og );
}
// sorgt dafür, daß das Element [index_neu] vorhanden ist.
void resize( int index_neu )
{
#ifdef DEBUGVARARR
cerr << "[-] VarArr<T>::resize( int index_neu = "
<< index_neu << ")" << endl;
cerr << "Default "
<< ( _default==NULL ? "nicht " : "" )
<< "gesetzt!\n";
#endif /* DEBUGVARARR */
if( !_pallok )
{
// noch gar kein Speicher allokiert!
// Aber das kann man nachholen:
#ifdef DEBUGVARARR
cerr << "[-] - bisher noch kein Speicher allokiert!" << endl;
#endif /* DEBUGVARARR */
_l = 1;
_lallok = 1;
_pallok = new T[1];
if( _default )
{
*_pallok = *_default;
}
else
{
}
_p0 = _pallok - index_neu;
_ug
= _og
= index_neu;
return;
}
else
{ // Feld ist schon allokiert.
#ifdef DEBUGVARARR
cerr << "[-] - Feld ist schon allokiert." << endl;
#endif /* DEBUGVARARR */
if( _l<=0 )
{ // Feld ist zwar allokiert, aber wieder freigegeben.
// Wenn der verlangte Wert feld[index_neu] im allokierten
// Bereich liegt, dann wird dieses eine Element als neues
// _ug und _og betrachtet; die Länge ist dann 1.
#ifdef DEBUGVARARR
cerr << "[-] - _l<=0, also Feld freigegeben." << endl;
#endif /* DEBUGVARARR */
if( ( _p0 + index_neu ) >= _pallok
&& ( _p0 + index_neu ) <= _p_letzt()
)
{ // feld[index_neu] liegt im bereits vorhandenen Feld.
#ifdef DEBUGVARARR
cerr << "[-] - index_neu liegt im allokierten "
<< "Bereich." << endl;
#endif /* DEBUGVARARR */
_l = 1;
_ug
= _og
= index_neu;
if( _default )
{
for( int i=0; i<_lallok; i++ )
{
_pallok[i] = *_default;
}
}
else
{
}
return ;
} // feld[index_neu] liegt im bereits vorhandenen Feld.
else
{
// Feld ist allokiert, aber wieder freigegeben,
// und das erste neue Element [index_neu] liegt
// außerhalb des allokierten Bereichs.
// Dann das Feld freigeben, und neu anfangen:
#ifdef DEBUGVARARR
cerr << "[-] - index_neu liegt ausse"
<< "rhalb des allokierten Bereichs.\n"
<< "[-] Also delete[], und neu "
<< "allokieren!" << endl;
#endif /* DEBUGVARARR */
delete[] _pallok; _pallok = NULL;
reset(); // Initialisieren
resize( index_neu ); // (rekursiv) allokieren
return;
}
} // Feld ist zwar allokiert, aber wieder freigegeben.
// Kontrollieren, ob die Grenzen zur Länge passen:
assert( (_l==( _og - _ug + 1 )) );
// Hier ist ein Feld vorhanden, und die Länge ist
// mindestens 1.
// reicht die allokierte Länge?
if( &_p0[index_neu] > _p_letzt() )
{ // Feld muß nach oben verlängert werden!
#ifdef DEBUGVARARR
cerr << "[-] - Feld muss nach oben verlaengert werden!"
<< endl;
#endif /* DEBUGVARARR */
// neue Länge:
int lallok_neu
// Adresse des letzten allokierten Elements, wenn
// das Feld an der gleichen Stelle bleiben würde:
= ( &_p0[index_neu + REALLOC_MEHR]
// minus Basisadresse ergibt (neue Länge-1)
- _pallok
// plus 1 ergibt neue Länge (Zaunlatten!)
+ 1
);
#ifdef DEBUGVARARR
cerr << "[-] - REALLOC_MIN1 = " << REALLOC_MIN1;
cerr << ", REALLOC_MIN2 = " << REALLOC_MIN2 << endl;
cerr << "[-] REALLOC_MEHR = " << REALLOC_MEHR
<< ", lallok_neu = " << lallok_neu << endl;
#endif /* DEBUGVARARR */
assert( lallok_neu>_lallok );
// neues Feld:
T * pallok_neu = new T[lallok_neu];
if( _default )
{
for( int i=_lallok; i<lallok_neu; i++ )
{
pallok_neu[i] = *_default;
}
}
else
{
}
// Zeiger auf neues Element [0]:
// Das neue Element [0] soll im neuen Feld den gleichen
// Offset haben, wie das alte [0] im alten Feld.
// Das heißt: ( _p0 - _pallok ) == ( p0_neu - pallok_neu )
// Oder: p0_neu == ( _p0 - _pallok + pallok_neu )
// Auch hier muß man sicherstellen, daß nur Differenzen
// von Zeigern gebildet werden, die sich auf EINEN
// allokierten Speicherblock beziehen (siehe unten):
// T * p0_neu = ( _p0 - _pallok + pallok_neu );
T * p0_neu = &pallok_neu[(_p0 - _pallok)];
// Änderung 27.05.2000 kw:
// dies war der alte Code:
// // Damit kann man die Elemente kopieren:
// for( int i=_ug; i<=_og; i++ )
// {
//#ifdef DEBUGVARARR
// cerr << "[-] - Kopiere Element " << i << endl;
//#endif /* DEBUGVARARR */
// p0_neu[i] = _p0[i];
// }
// Fehler darin ist, daß nur die Elemente des Bereichs
// umkopiert werden, die der Benutzer sieht
// ((_ug)...(_og)).
// Wenn jedoch (_default) gesetzt ist, dann muß man
// alle bisher allokierten Elemente umkopieren, weil
// sonst die Elemente, die durch Mehrallokieren
// außerhalb von (_ug)...(_og) liegen, verlorengehen.
// Diese "Vorratselemente" müssen ja auch mit in das
// neu allokierte Feld übernommen werden.
// Weil dies aber wiederum überflüssig ist, wenn
// (_default) nicht gesetzt ist, gibt es hier eine
// Fallunterscheidung:
if( _default )
{ // _default, also alle allokierten Elemente kopieren
for( int i=0; i<_lallok; i++ )
{
#ifdef DEBUGVARARR
cerr << "[-] - Kopiere all. Element " << i << endl;
#endif /* DEBUGVARARR */
pallok_neu[i] = _pallok[i];
}
} // _default, also alle allokierten Elemente kopieren
else
{ // KEIN _default, also nur von _ug bis _og kopieren
for( int i=_ug; i<=_og; i++ )
{
#ifdef DEBUGVARARR
cerr << "[-] - Kopiere Element " << i << endl;
#endif /* DEBUGVARARR */
p0_neu[i] = _p0[i];
}
} // KEIN _default, also nur von _ug bis _og kopieren
// Das alte Feld kann weg:
delete[] _pallok;
_pallok = pallok_neu;
_og = index_neu;
_p0 = p0_neu;
_lallok = lallok_neu;
_l = _og - _ug + 1;
#ifdef DEBUGVARARR
cerr << "[-] - _ug = " << _ug << endl;
cerr << "[-] _og = " << _og << endl;
cerr << "[-] _l = " << _l << endl;
#endif /* DEBUGVARARR */
return;
} // Feld muß nach oben verlängert werden!
else if( &_p0[index_neu] < _pallok )
{ // Feld muß nach unten verlängert werden!
#ifdef DEBUGVARARR
cerr << "[-] - Feld muss nach unten verlaengert werden!" << endl;
#endif /* DEBUGVARARR */
// neue Länge:
int lallok_neu =
// erste Adresse hinter dem allokierten Feld:
&_pallok[_lallok]
// minus Adresse des ersten allokierten Elements, wenn
// das Feld nach unten verlängert werden könnte:
- &_p0[index_neu-REALLOC_MEHR];
#ifdef DEBUGVARARR
cerr << "[-] - REALLOC_MIN1 = " << REALLOC_MIN1;
cerr << ", REALLOC_MIN2 = " << REALLOC_MIN2 << endl;
cerr << "[-] REALLOC_MEHR = " << REALLOC_MEHR
<< ", lallok_neu = " << lallok_neu << endl;
#endif /* DEBUGVARARR */
assert( lallok_neu>_lallok );
// neues Feld:
T * pallok_neu = new T[lallok_neu];
if( _default )
{
for( int i=0; i<(lallok_neu-_lallok); i++ )
{
pallok_neu[i] = *_default;
}
}
else
{
}
// Zeiger auf neues Element [0]:
// Das neue Element [0] soll im neuen Feld den gleichen
// Abstand vom Ende haben, wie das alte [0] im alten Feld.
// Das heißt:
// ( _pallok + _lallok - _p0 )
// ==
// ( pallok_neu + lallok_neu - p0_neu )
// Oder:
// p0_neu
// ==
// ( pallok_neu+lallok_neu-( _pallok+_lallok-_p0 ) )
// Oder:
// p0_neu
// ==
// ( pallok_neu+lallok_neu+( -_pallok-_lallok+_p0 ) )
// Oder:
// p0_neu
// ==
// ( pallok_neu+lallok_neu-_pallok-_lallok+_p0 )
//
//T * p0_neu =
// (&pallok_neu[lallok_neu]
// - &_pallok[_lallok]
// )
// + _p0;
// Diese Version geht schief (bei sizeof(T)!=n*8 kommen
// Adressen heraus, die nicht Vielfache von sizeof(T)
// sind!!!!!!!!!!!!!!!!!!!!!!!
//T * p0_neu = pallok_neu+lallok_neu-_pallok-_lallok+_p0;
// Vielmehr muß man den Ausdruck so zusammenfassen, daß
// nur Differenzen von Adressen gebildet werden, die in
// einem allokierten Block liegen.
// Haben die allokierten Blöcke nämlich einen Abstand, der
// ungleich einem Vielfachen der Elementgröße ist, dann
// kommen Rundungsfehler ins Spiel (weil die Differenzen
// von Adressen immer durch sizeof(...) geteilt werden.
T * p0_neu =
&pallok_neu[lallok_neu] - ( &_pallok[_lallok] - _p0 );
#ifdef DEBUGVARARR
cerr << "[-] - p0_neu, pallok_neu = "
<< p0_neu << ", " << pallok_neu << endl;
#endif /* DEBUGVARARR */
// Änderung 27.05.2000 kw:
// dies war der alte Code:
// // Damit kann man die Elemente kopieren:
// for( int i=_ug; i<=_og; i++ )
// {
//
//#ifdef DEBUGVARARR
// cerr << "[-] - Kopiere Element " << i << endl;
//#endif /* DEBUGVARARR */
//
// p0_neu[i] = _p0[i];
// }
// Fehler darin ist, daß nur die Elemente des Bereichs
// umkopiert werden, die der Benutzer sieht
// ((_ug)...(_og)).
// Wenn jedoch (_default) gesetzt ist, dann muß man
// alle bisher allokierten Elemente umkopieren, weil
// sonst die Elemente, die durch Mehrallokieren
// außerhalb von (_ug)...(_og) liegen, verlorengehen.
// Diese "Vorratselemente" müssen ja auch mit in das
// neu allokierte Feld übernommen werden.
// Weil dies aber wiederum überflüssig ist, wenn
// (_default) nicht gesetzt ist, gibt es hier eine
// Fallunterscheidung:
if( _default )
{ // _default, also alle allokierten Elemente kopieren
for( int i=0; i<_lallok; i++ )
{
#ifdef DEBUGVARARR
cerr << "[-] - Kopiere all. Element " << i << endl;
#endif /* DEBUGVARARR */
pallok_neu[i+lallok_neu-_lallok] = _pallok[i];
}
} // _default, also alle allokierten Elemente kopieren
else
{ // KEIN _default, also nur von _ug bis _og kopieren
for( int i=_ug; i<=_og; i++ )
{
#ifdef DEBUGVARARR
cerr << "[-] - Kopiere Element " << i << endl;
#endif /* DEBUGVARARR */
p0_neu[i] = _p0[i];
}
} // KEIN _default, also nur von _ug bis _og kopieren
// Das alte Feld kann weg:
delete[] _pallok;
_pallok = pallok_neu;
_ug = index_neu;
_p0 = p0_neu;
_lallok = lallok_neu;
_l = _og - _ug + 1;
#ifdef DEBUGVARARR
cerr << "[-] - _ug = " << _ug << endl;
cerr << "[-] _og = " << _og << endl;
cerr << "[-] _l = " << _l << endl;
#endif /* DEBUGVARARR */
return;
} // Feld muß nach unten verlängert werden!
else
{ // Feld ist vorhanden, Länge ist größer 0,
// keine Verlängerung nötig, &Element[index_neu] liegt im
// Bereich [_pallok,_p_letzt()]
// Dann muß man nur sehen, ob index_neu im Bereich
// _ug..._og liegt; gegebenenfalls _ug oder _og anpassen:
#ifdef DEBUGVARARR
cerr << "[-] - Feld ist vorhanden, " << endl;
cerr << "[-] Laenge ist groesser 0," << endl;
cerr << "[-] keine Verlaengerung noetig." << endl;
cerr << "[-] " << endl;
#endif /* DEBUGVARARR */
if( index_neu<_ug )
{
_ug = index_neu;
_l = _og - _ug + 1;
#ifdef DEBUGVARARR
cerr << "[-] - _ug auf " << _ug
<< " gesetzt." << endl;
cerr << "[-] _l auf " << _l
<< " gesetzt." << endl;
#endif /* DEBUGVARARR */
}
if( index_neu>_og )
{
_og = index_neu;
_l = _og - _ug + 1;
#ifdef DEBUGVARARR
cerr << "[-] - _og auf " << _og
<< " gesetzt." << endl;
cerr << "[-] _l auf " << _l
<< " gesetzt." << endl;
#endif /* DEBUGVARARR */
}
return;
} // Feld ist vorhanden, Länge ist größer 0,
} // Feld ist schon allokiert.
} // void resize( int index_neu )
public:
// Konstruktor:
VarArr()
{
#ifdef DEBUGVARARR
cerr << "[-] VarArr<T>:: VarArr()" << endl;
#endif /* DEBUGVARARR */
_default = (T *)NULL;
reset();
}
// 17. 7.97 kw: der fehlte noch, um temporäre Objekte schaffen zu
// können:
// Initialisieren mit Referenz auf const-Objekt:
VarArr<T>( const VarArr<T> & init )
{
#ifdef DEBUGVARARR
cerr << "[-] VarArr<T>::VarArr<T>( const VarArr<T> & init )"
<< endl;
#endif /* DEBUGVARARR */
// alles löschen:
reset();
if( init._default )
{
_default = new T( *(init._default) );
}
// Initialisierer zuweisen:
// 24. 7.97 kw:
// mit operator= zuweisen klappt, nicht, weil zu dessen Aufruf
// ein temporäres Objekt mit VarArr<T>( const VarArr<T> & init )
// angelegt, wird; darin wird wieder operator= aufgerufen, dazu
// wird...
// Klassische Rekursion; man lernt nie aus.
// hat das Feld einen Inhalt?
if( init._pallok && init._l>0 )
{
// JA!
#ifdef DEBUGVARARR
cerr << "[-] - Feld hat Inhalt." << endl;
#endif /* DEBUGVARARR */
// Kontrollieren, ob die Grenzen zur Länge passen:
assert( (init._l==( init._og - init._ug + 1 )) );
// Diese Werte kann man direkt übernehmen:
_l = init._l;
_ug = init._ug;
_og = init._og;
// Platz allokieren (nur soviel, wie nötig):
_lallok = _l;
_pallok = new T[_lallok];
// _p0 auf Element [0] zeigen lassen:
_p0 = _pallok - _ug;
// Die belegten Elemente von der rechten Seite nach links
// kopieren;
for( int i=_ug; i<=_og; i++ )
{
#ifdef DEBUGVARARR
cerr << "[-] - Kopiere Element " << i << endl;
#endif /* DEBUGVARARR */
_p0[i] = (init._p0)[i];
}
}
}
// Der Operator [] wird mit einer Funktion überladen, die
// a) ein Unter- oder Überschreiten des Feldes durch Verlängern
// erlaubt,
// b) eine Referenz auf das (index)-te Objekt liefert.
T & operator[]( int index )
{
#ifdef DEBUGVARARR
cerr << "[-] T & VarArr<T>::operator[]( int index = "
<< index << " )" << endl;
#endif /* DEBUGVARARR */
// 09.09.2002 kw: hier ein Schnelltest, ob resize() überhaupt
// nötig ist. Diese Tests werden zwar in resize()
// nochmals gemacht, aber in den meisten Fällen
// wird die Funktion gar nicht aufgerufen werden
// müssen (solange die meisten Zugriffe im
// existierenden Feld stattfinden).
// Damit sollte es so im Schnitt etwas schneller
// gehen:
if( index>_og || index<_ug || !_pallok )
{
resize( index ); // Ggf. das Feld verlängern lassen
}
return _p0[index]; // Referenz auf (index)-tes Objekt liefern
}
// Der Operator [] wird mit einer Funktion überladen, die
// a) ein Unter- oder Überschreiten des Feldes überwacht,
// und notfalls eine exception schmeißt,
// b) eine Referenz auf das (index)-te Objekt liefert.
// Im Gegensatz zum "normalen" Feldzugriff
// T & operator[]( int index ) wird das Feld nicht manipuliert!
// Deshalb ist diese Version auch für const-Objekte geeignet (und
// eventuell schneller).
T & operator[]( int index ) const
{
#ifdef DEBUGVARARR
cerr << "[-] T & VarArr<T>::operator[]( int index = "
<< index << " ) const" << endl;
#endif /* DEBUGVARARR */
#ifdef VARARR_FELDGRENZENKONTROLLIEREN
if( index < _ug || index > _og )
{
throw( std::out_of_range( "VarArr<>::operator[](int index) const" ) );
}
#endif // VARARR_FELDGRENZENKONTROLLIEREN
return _p0[index]; // Referenz auf (index)-tes Objekt liefern
}
// Die Funktionen l(), ug(), und og() liefern die Anzahl der
// belegten Elemente, den kleinsten belegten Index, und den
// größten belegten Index.
long int l() const
{
#ifdef DEBUGVARARR
cerr << "[-] VarArr<T>::l()" << endl;
#endif /* DEBUGVARARR */
return _l;
}
long int ug() const
{
#ifdef DEBUGVARARR
cerr << "[-] VarArr<T>::ug()" << endl;
#endif /* DEBUGVARARR */
return _ug;
}
// Destruktor:
~VarArr()
{
#ifdef DEBUGVARARR
cerr << "[-] VarArr<T>::~ VarArr()" << endl;
#endif /* DEBUGVARARR */
if( _pallok )
{
delete[] _pallok; _pallok = NULL;
}
reset();
if( _default )
{
delete _default;
}
}
// 17. 7.97 kw
// Zuweisung
VarArr<T> & operator=( const VarArr<T> init )
{
#ifdef DEBUGVARARR
cerr << "[-] VarArr<T>::operator=( const VarArr<T> init )"
<< endl;
#endif /* DEBUGVARARR */
// Ggf. altes Feld freigeben:
if( _pallok )
{
delete[] _pallok; _pallok = NULL;
}
reset();
// hat das Feld einen Inhalt?
if( init._pallok && init._l>0 )
{
// JA!
#ifdef DEBUGVARARR
cerr << "[-] - Feld hat Inhalt." << endl;
#endif /* DEBUGVARARR */
// Kontrollieren, ob die Grenzen zur Länge passen:
assert( (init._l==( init._og - init._ug + 1 )) );
// Diese Werte kann man direkt übernehmen:
_l = init._l;
_ug = init._ug;
_og = init._og;
// Platz allokieren (nur soviel, wie nötig):
_lallok = _l;
_pallok = new T[_lallok];
// _p0 auf Element [0] zeigen lassen:
_p0 = _pallok - _ug;
// Die belegten Elemente von der rechten Seite nach links
// kopieren;
for( int i=_ug; i<=_og; i++ )
{
#ifdef DEBUGVARARR
cerr << "[-] - Kopiere Element " << i << endl;
#endif /* DEBUGVARARR */
_p0[i] = (init._p0)[i];
}
}
return *this;
}
long int og() const
{
#ifdef DEBUGVARARR
cerr << "[-] VarArr<T>::og()" << endl;
#endif /* DEBUGVARARR */
return _og;
}
// Mit einem Parameter setzen die Funktionen l(int), ug(int),
// und og(int) die Anzahl der
// belegten Elemente (ab 0), resp. den kleinsten belegten Index,
// resp. den größten belegten Index.
long int l( int lneu )
{
#ifdef DEBUGVARARR
cerr << "[-] long int VarArr<T>::l( int lneu = "
<< lneu << " )" << endl;
#endif /* DEBUGVARARR */
if( lneu>0 )
{
// neuer Bereich ist [0,(lneu-1)].
// Dazu muß (lneu-1) existieren:
#ifdef DEBUGVARARR
cerr << "[-] - lneu>0" << endl;
#endif /* DEBUGVARARR */
resize( lneu - 1 );
resize( 0 );
_ug = 0;
_og = lneu - 1;
_l = lneu;
}
else
{
#ifdef DEBUGVARARR
cerr << "[-] - lneu<=0" << endl;
#endif /* DEBUGVARARR */
// Feld soll gelöscht werden.
loesche();
}
return _l;
}
long int ug( int ugneu )
{
#ifdef DEBUGVARARR
cerr << "[-] long int VarArr<T>::ug( int ugneu = "
<< ugneu << " )" << endl;
#endif /* DEBUGVARARR */
if( _l<=0 )
{
#ifdef DEBUGVARARR
cerr << "[-] - Feld ist leer, neu anlegen: [ugneu]"
<< endl;
#endif /* DEBUGVARARR */
// Feld ist bisher leer!
// Dann das Element [ugneu] schaffen:
resize( ugneu );
_og = _ug = ugneu;
_l = 1;
}
else if( ugneu>_og )
{
#ifdef DEBUGVARARR
cerr << "[-] - ugneu>_og, Feld soll freigegeben werden"
<< endl;
#endif /* DEBUGVARARR */
// Feld soll freigegeben werden:
loesche();
}
else
{
#ifdef DEBUGVARARR
cerr << "[-] - ugneu<=_og, F"
<< "eld soll am unteren Ende angepaßt werden"
<< endl;
#endif /* DEBUGVARARR */
// Feld soll am unteren Ende angepaßt werden:
resize( ugneu );
_ug = ugneu;
_l = _og - _ug + 1;
}
#ifdef DEBUGVARARR
cerr << "[-] - _ug ist jetzt " << _ug << endl;
cerr << "[-] - _og ist jetzt " << _og << endl;
cerr << "[-] _l ist jetzt " << _l << endl;
#endif /* DEBUGVARARR */
return _ug;
}
long int og( int ogneu )
{
#ifdef DEBUGVARARR
cerr << "[-] long int VarArr<T>::og( int ogneu = "
<< ogneu << " )" << endl;
#endif /* DEBUGVARARR */
if( _l<=0 )
{
#ifdef DEBUGVARARR
cerr << "[-] - Feld ist leer, neu anlegen: [ogneu]"
<< endl;
#endif /* DEBUGVARARR */
// Feld ist bisher leer!
// Dann das Element [ogneu] schaffen:
resize( ogneu );
_og = _ug = ogneu;
_l = 1;
}
else if( ogneu<_ug )
{
#ifdef DEBUGVARARR
cerr << "[-] - ogneu<_ug, Feld soll freigegeben werden"
<< endl;
#endif /* DEBUGVARARR */
// Feld soll freigegeben werden:
loesche();
}
else
{
#ifdef DEBUGVARARR
cerr << "[-] - ogneu>=_ug, Feld soll am oberen"
<< " Ende angepasst werden" << endl;
#endif /* DEBUGVARARR */
// Feld soll am oberen Ende angepaßt werden:
resize( ogneu );
_og = ogneu;
_l = _og - _ug + 1;
}
#ifdef DEBUGVARARR
cerr << "[-] - _ug ist jetzt " << _ug << endl;
cerr << "[-] - _og ist jetzt " << _og << endl;
cerr << "[-] _l ist jetzt " << _l << endl;
#endif /* DEBUGVARARR */
return _og;
}
// setzt den Defaultwert, mit dem neue Feldbereiche gefüllt
// werden sollen
void
SetDefault( const T &Default )
{
if( _default )
{
delete _default;
}
_default = new T( Default );
}
void
SetNoDefault()
{
if( _default )
{
delete _default;
_default = (T*)NULL;
}
}
}; // { Ende von template<class T> class VarArr }
// vergleicht zwei VarArr<T> nach Länge und Inhalt.
// true, wenn beide gleich sind.
// Benötigt für die Klasse T den operator==().
template <class T> static bool
CmpVarArr( VarArr<T> &a1, VarArr<T> &a2 )
{
if( a1.ug()!=a2.ug() || a1.og()!=a2.og() )
{
return false;
}
else
{
for( int i=a1.ug(); i<=a1.og(); i++ )
{
if( !(a1[i]==a2[i]) )
{
return false;
}
}
}
return true;
}
#endif /* _VARARR */
Hier das zugehörige Testprogramm:
// Time-stamp: "09.09.02 19:43 test.cpp klaus@wachtler.de"
//
// Kleines Demoprogramm für VarArr
#define NDEBUG // um diverse assert() in vararr.h stillzulegen
#include "vararr.h" // oder <vararr.h>
#include <iostream>
#include <string>
/////////////////////////////////////////////////////////////////////////////
// demonstriert ein einfaches Feld:
void demo_simple_int()
{
// Feld vereinbaren:
VarArr<int> feld;
// Beliebige Elemente initialisieren und verwenden:
feld[1] = 11;
feld[0] = 10;
feld[-5] = 15;
std::cout << "\ndemo_simple_int:" << std::endl;
std::cout << "feld[-5] = " << feld[-5] <<std::endl;
std::cout << "feld[0] = " << feld[0] <<std::endl;
std::cout << "feld[1] = " << feld[1] << std::endl;
}
/////////////////////////////////////////////////////////////////////////////
// demonstriert ein einfaches Feld:
void demo_simple_double()
{
// Feld vereinbaren:
VarArr<double> feld;
// Beliebige Elemente initialisieren und verwenden:
feld[1] = 11.11;
feld[0] = 10.00;
feld[-5] = 15.55;
std::cout << "\ndemo_simple_double:" << std::endl;
std::cout << "feld[-5] = " << feld[-5] <<std::endl;
std::cout << "feld[0] = " << feld[0] <<std::endl;
std::cout << "feld[1] = " << feld[1] << std::endl;
}
/////////////////////////////////////////////////////////////////////////////
// demonstriert ein einfaches Feld mit einem default-Wert für nicht
// definierte Elemente:
void demo_default_int()
{
// Feld vereinbaren:
VarArr<int> feld;
// einen Wert als Standardwert setzen:
feld.SetDefault( 12 );
// Beliebige Elemente initialisieren und verwenden:
feld[1] = 11;
feld[0] = 10;
feld[-5] = 15;
std::cout << "\ndemo_default_int:" << std::endl;
// Alle Elemente vom kleinsten benutzten bis zum höchsten benutzten
// ausgeben (obwohl nicht alle explizit initialisiert wurden!):
for( int i=feld.ug(); i<=feld.og(); i++ )
{
std::cout << "feld[" << i << "] = " << feld[i] <<std::endl;
}
}
/////////////////////////////////////////////////////////////////////////////
// demonstriert ein Feld einer eigenen Klasse:
class Student
{
friend std::ostream & operator<<( std::ostream &os, const Student &obj );
public:
Student( std::string name = "", int iq = 30 )
: name(name), iq(iq) {}
std::string getName() { return name; }
int getIQ() { return iq; }
private:
std::string name;
int iq;
};
std::ostream & operator<<( std::ostream &os, const Student &obj )
{
return (os<<obj.name<<","<<obj.iq);
}
void demo_student()
{
VarArr<Student> feld;
std::cout << "\ndemo_student:" << std::endl;
feld[3] = Student( "Hans-Peter", 12 );
feld[5] = Student( "Birgit", 103 );
// Alle Elemente vom kleinsten benutzten bis zum höchsten benutzten
// ausgeben (obwohl nicht alle explizit initialisiert wurden!):
for( int i=feld.ug(); i<=feld.og(); i++ )
{
std::cout << "feld[" << i << "] = " << feld[i] <<std::endl;
}
}
/////////////////////////////////////////////////////////////////////////////
// vergleicht anhand einer Mischung aus lesenden und schreibenden
// Zugriffen die Laufzeiten für echte Felder, VarArr<> und vector<>
// aus der STL.
//
// Auf meinem Laptop (PIII, 1.1GHz) ergibt das mit dem g++ 2.95.3 (Linux):
// klaus@lap2:~/vararr > g++ -Wall test.cpp -O0 && a.out
// demo_zeit:
// belegen echtes Feld: 0.03500000 usec/Element
// verwenden echtes Feld: 0.05725000 usec/Zugriff
// belegen var. Feld: 0.20700000 usec/Element
// verwenden var. Feld: 0.06125000 usec/Zugriff
// verwenden var. Feld: 0.06700000 usec/Zugriff (const)
// belegen vector-Feld: 0.13700000 usec/Element
// verwenden vector-Feld: 0.06800000 usec/Zugriff (ungeprüft)
// klaus@lap2:~/vararr > g++ -Wall test.cpp -O3 && a.out
// demo_zeit:
// belegen echtes Feld: 0.03000000 usec/Element
// verwenden echtes Feld: 0.01530000 usec/Zugriff
// belegen var. Feld: 0.13200000 usec/Element
// verwenden var. Feld: 0.02635000 usec/Zugriff
// verwenden var. Feld: 0.02335000 usec/Zugriff (const)
// belegen vector-Feld: 0.08700000 usec/Element
// verwenden vector-Feld: 0.01555000 usec/Zugriff (ungeprüft)
// bzw. unter W2k mit VC++ 6.0:
// Y:\>cl /GX test.cpp & .\test
// demo_zeit:
// belegen echtes Feld: 0.02800000 usec/Element
// verwenden echtes Feld: 0.04226000 usec/Zugriff
// belegen var. Feld: 0.18930000 usec/Element
// verwenden var. Feld: 0.05382500 usec/Zugriff
// verwenden var. Feld: 0.05308000 usec/Zugriff (const)
// belegen vector-Feld: 0.37950000 usec/Element
// verwenden vector-Feld: 0.05518000 usec/Zugriff (ungeprüft)
// Y:\>cl /Ox /GX test.cpp & .\test
// demo_zeit:
// belegen echtes Feld: 0.02800000 usec/Element
// verwenden echtes Feld: 0.03675500 usec/Zugriff
// belegen var. Feld: 0.15120000 usec/Element
// verwenden var. Feld: 0.03560000 usec/Zugriff
// verwenden var. Feld: 0.03900500 usec/Zugriff (const)
// belegen vector-Feld: 0.16730000 usec/Element
// verwenden vector-Feld: 0.03675000 usec/Zugriff (ungeprüft)
// Anzahl der Durchläufe der verschiedenen Varianten (um die
// Genauigkeit von clock() zu erhöhen); je nach Rechner müssen die
// Werte ggf. angepaßt werden:
#define NDURCHLAUF_ARRAY 100000000
#define NDURCHLAUF_VARARR 100000000
#define NDURCHLAUF_VECTOR 100000000
// gewünschte Feldlänge:
#define N_ELEMENTE 10000000
#include <ctime>
#include <vector>
void demo_zeit()
{
clock_t start, ende;
size_t i;
std::cout << "\ndemo_zeit:" << std::endl;
//
// "echtes" Feld:
//
// erstmals belegen (static, weil unter VC++ sonst der Stack nicht
// reicht):
static int echtes_feld[N_ELEMENTE];
start = clock();
for( i=0; i<N_ELEMENTE; i++ )
{
echtes_feld[i] = (int)i;
}
ende = clock();
printf( "belegen echtes Feld: %12.8f usec/Element\n",
(double)( ende - start ) // clock ticks
/CLOCKS_PER_SEC // Umrechnen auf sec
/N_ELEMENTE // Zeit je Element
*1.E6 // Umrechnen auf mikro sec
);
// verwenden:
start = clock();
for( i=0; i<NDURCHLAUF_ARRAY; i++ )
{
echtes_feld[i%N_ELEMENTE] = (int)i + echtes_feld[(i-55)%N_ELEMENTE];
}
ende = clock();
printf( "verwenden echtes Feld: %12.8f usec/Zugriff\n",
(double)( ende - start ) // clock ticks
/CLOCKS_PER_SEC // Umrechnen auf sec
/NDURCHLAUF_ARRAY // Zeit je Element
/2.0 // zwei Feldzugriffe je Durchlauf
*1.E6 // Umrechnen auf mikro sec
);
//
// VarArr:
//
// erstmals belegen:
VarArr<int> vararr_feld;
start = clock();
for( i=0; i<N_ELEMENTE; i++ )
{
vararr_feld[i] = (int)i;
}
ende = clock();
printf( "belegen var. Feld: %12.8f usec/Element\n",
(double)( ende - start ) // clock ticks
/CLOCKS_PER_SEC // Umrechnen auf sec
/N_ELEMENTE // Zeit je Element
*1.E6 // Umrechnen auf mikro sec
);
// verwenden (normales VarArr):
start = clock();
for( i=0; i<NDURCHLAUF_VARARR; i++ )
{
vararr_feld[i%N_ELEMENTE] = (int)i + vararr_feld[(i-55)%N_ELEMENTE];
}
ende = clock();
printf( "verwenden var. Feld: %12.8f usec/Zugriff\n",
(double)( ende - start ) // clock ticks
/CLOCKS_PER_SEC // Umrechnen auf sec
/NDURCHLAUF_VARARR // Zeit je Element
/2.0 // zwei Feldzugriffe je Durchlauf
*1.E6 // Umrechnen auf mikro sec
);
// verwenden (const VarArr):
const VarArr<int> &vararr_feld_const = vararr_feld;
start = clock();
for( i=0; i<NDURCHLAUF_VARARR; i++ )
{
vararr_feld_const[i%N_ELEMENTE]
= (int)i + vararr_feld_const[(i-55)%N_ELEMENTE];
}
ende = clock();
printf( "verwenden var. Feld: %12.8f usec/Zugriff (const)\n",
(double)( ende - start ) // clock ticks
/CLOCKS_PER_SEC // Umrechnen auf sec
/NDURCHLAUF_VARARR // Zeit je Element
/2.0 // zwei Feldzugriffe je Durchlauf
*1.E6 // Umrechnen auf mikro sec
);
//
// vector aus der STL:
//
// erstmals belegen:
std::vector<int> vector_feld; // Anm.: Man könnte hier auch gleich die
// vermutliche Länge angeben, um
// späteres teures Allokieren vermeiden
// zu helfen.
// Um aber wirklich dynamisches
// Verhalten zu simulieren, stellen wir
// uns dumm und wissen die Länge nicht.
start = clock();
for( i=0; i<N_ELEMENTE; i++ )
{
vector_feld.push_back( (int)i );
}
ende = clock();
printf( "belegen vector-Feld: %12.8f usec/Element\n",
(double)( ende - start ) // clock ticks
/CLOCKS_PER_SEC // Umrechnen auf sec
/N_ELEMENTE // Zeit je Element
*1.E6 // Umrechnen auf mikro sec
);
// verwenden (ohne Feldgrenzenüberprüfung):
start = clock();
for( i=0; i<NDURCHLAUF_VECTOR; i++ )
{
vector_feld[i%N_ELEMENTE] = (int)i + vector_feld[(i-55)%N_ELEMENTE];
}
ende = clock();
printf( "verwenden vector-Feld: %12.8f usec/Zugriff (ungeprüft)\n",
(double)( ende - start ) // clock ticks
/CLOCKS_PER_SEC // Umrechnen auf sec
/NDURCHLAUF_VECTOR // Zeit je Element
/2.0 // zwei Feldzugriffe je Durchlauf
*1.E6 // Umrechnen auf mikro sec
);
}
/////////////////////////////////////////////////////////////////////////////
// demonstriert ein zweidimensionales Feld:
void demo_2dim_int()
{
// Feld von Feld vereinbaren:
VarArr< VarArr<int> > feld;
// Leerzeichen hier^ wichtig!
// Beliebige Elemente initialisieren und verwenden:
feld[1][-1] = 11;
feld[1][0] = 10;
feld[1][1] = 11;
feld[0][3] = 3;
feld[0][4] = 4;
feld[0][5] = 5;
feld[0][6] = 6;
feld[0][8] = 8;
feld[0][9] = 9;
feld[-5][10] = -510;
feld[-5][11] = -511;
feld[-5][12] = -512;
feld[-5][13] = -513;
// alle Werte ausgeben:
std::cout << "\ndemo_2dim_int:" << std::endl;
for( int i=feld.ug(); i<=feld.og(); i++ )
{
for( int j=feld[i].ug(); j<=feld[i].og(); j++ )
{
std::cout << "feld[" << i << "][" << j << "] = "
<< feld[i][j]
<< std::endl;
}
}
}
/////////////////////////////////////////////////////////////////////////////
int main( int nargs, char **args )
{
demo_simple_int(); // einfaches Feld
demo_simple_double(); // einfaches Feld
demo_default_int(); // Feld mit default-Wert
demo_student(); // Feld eigene class für Elemente
demo_zeit(); // Zeitvergleich C-Array, VarArr, vector
demo_2dim_int(); // 2-dimensionales Feld
return 0;
}
/////////////////////////////////////////////////////////////////////////////