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; } /////////////////////////////////////////////////////////////////////////////