Verbesserung an Template Klasse gegen Array Überlauf

[Gast]

Hallo,
habe mir ne EINFACHE Template-Klasse geschrieben um den Array-Überlauf zu verhindern.

Hier erstmal die Klasse:

#include <iostream>
#include <new>
using namespace std;

template<class typ> class MyArray {

               typ *array;
               int aktSize,altSize;
    public:
               MyArray(int size);
               ~MyArray();
               typ &operator[](int i);
               void copynew(int size);
};

template<class typ> MyArray<typ>::MyArray(int size)
{
               aktSize=size;

               try {
                   array=new typ[size];
               } 
               catch(bad_alloc xa) {

                   cout <<"Fehler";
                   cin.get();
                   exit(1);
               }
}

template<class typ> MyArray<typ>::~MyArray()
{
               delete [] array;
}

template <class typ> typ &MyArray<typ>::operator[](int i) // Frage 1
{
         if(i>aktSize) copynew(i);
         return array[i];
}

template <class typ> void MyArray<typ>::copynew(int size)
{
         typ temparray[aktSize];

         for(int i=0;i<aktSize;i++)
                 temparray[i]=array[i];

         altSize=aktSize;
         while (aktSize<size) aktSize+=aktSize; //Frage 2

         delete [] array;

         try {
             array=new typ [aktSize];
         }
         catch (bad_alloc xa) {

               cout <<"Fehler";
               cin.get();
               exit(1);
         }

         for(int i=0;i<aktSize;i++)
                 array[i]=temparray[i];
}

Nun zu den Fragen(Funktionspunkte siehe Code):
-----------------------------------------------

1.) Sollte ich in dieser Funktion auch überprüfen ob als Index ne
negative Zahl eingebene wurde?
Wenn ja wie solch in dann am besten darauf reagieren.

2.) Gibt es hier ne optimalere Möglichkeit um das Array zu
vergrössern?

3.) Noch irgendwelchen anderen Verbesserungvorschläge???

[audacia]

Freak_Coder schrieb:

3.) Noch irgendwelchen anderen Verbesserungvorschläge???

Nimm boost.array .

[Gast]

audacia schrieb:

Nimm boost.array .

Tolle Antwort
Was lerne ich dann daraus???? NICHTS

Ich will ja erfahrung sammeln deswegen code ich sowas halt lieber selber!

[audacia]

Freak_Coder schrieb:

1.) Sollte ich in dieser Funktion auch überprüfen ob als Index ne
negative Zahl eingebene wurde?
Wenn ja wie solch in dann am besten darauf reagieren.

Überprüfe einfach den Index auf Gültigkeit. Ist dieser negativ, so muß der Test natürlich fehlschlagen.
Vielleicht wäre es gut, wenn du die Option bietest, die Indexüberprüfung per define abzuschalten.

Moritz

[finix]

Freak_Coder schrieb:

1.) Sollte ich in dieser Funktion auch überprüfen ob als Index ne
negative Zahl eingebene wurde?
Wenn ja wie solch in dann am besten darauf reagieren.

std::size_t bzw. unsigned int?

Freak_Coder schrieb:

2.) Gibt es hier ne optimalere Möglichkeit um das Array zu
vergrössern?

Was meinst du mit "optimaler"?

Freak_Coder schrieb:

3.) Noch irgendwelchen anderen Verbesserungvorschläge???

1. nimm std::vector.

2. in Bezug auf

Freak_Coder schrieb:

audacia schrieb:

Nimm boost.array .

Tolle Antwort
Was lerne ich dann daraus???? NICHTS

Ich will ja erfahrung sammeln deswegen code ich sowas halt lieber selber!

Hättest du auch ruhig erwähnen können
Wie soll das irgendjemand wissen?

int aktSize,altSize;

Wofür das altSize?

typ &operator[](int i);

Wie wär's mit einer const Überladung?

void copynew(int size);

Spätestens wenn die Methode wirklich public sein soll würde ich sie geschickter benennnen.

catch(bad_alloc xa) {
  cout <<"Fehler"; // std::cerr? "Fehler"? Welcher?
  cin.get();       // keine gute Idee
  exit(1);         // dto
}

typ temparray[aktSize];

for(int i=0;i<aktSize;i++)
  temparray[i]=array[i];

Wozu das temparray?

for(int i=0;i<aktSize;i++)
  array[i]=temparray[i];

temparray war wie groß genau?

[groovemaster]

Freak_Coder schrieb:

1.) Sollte ich in dieser Funktion auch überprüfen ob als Index ne
negative Zahl eingebene wurde?

Nein. Besser du nimmst für den index einen unsigned Typen (std::size_t).

Freak_Coder schrieb:

2.) Gibt es hier ne optimalere Möglichkeit um das Array zu
vergrössern?

Ja, indem die neue Grösse size multipliziert mit irgendeinem Faktor (zB 2 oder 3/2) ist. Der Faktor bestimmt dann sozusagen die Ausgewogenheit zwischen Laufzeitgeschwindigkeit und Speicherverbrauch.

[template]

Also wenn ich mich auch die schnelle nicht verguckt habe, dann hast du einen unnötigen kopiervorgang sowie ein lesen über die Array Grezen hinaus.

for(int i=0;i<aktSize;i++)
  temparray[i]=array[i];

+

for(int i=0;i<aktSize;i++)
  array[i]=temparray[i];

und der fehler

typ temparray[aktSize];

while (aktSize<size) aktSize+=aktSize; // aktsize wird vergrößert

for(int i=0;i<aktSize;i++) // zu wenig platz für temparray reserviert...
  array[i]=temparray[i];

[volkard]

#include <new>

das brauchst nicht, um new zu benutzen. haste placement new oder sowas benutzt? hab ich gerade gar nicht gesehen. also weg damit.

#include <iostream> 
using namespace std;

auch weg. eine benutz-mich-ganz-unten-klasse darf keine ausgaben machen. willst die ja auch verwenden konnen, wenn du ein windows-prog machst.

try { 
                   array=new typ[size]; 
               } 
               catch(bad_alloc xa) { 

                   cout <<"Fehler"; 
                   cin.get(); 
                   exit(1); 
               }

ganz übel. lass doch den benutzer der klasse die exception fangen!

normalerweise einfach in der main

try{
tuwas();
}
catch(std::exception& e){
cout<<"aua! "<<e.why()<<'\n';
}

oder so.

typ temparray[aktSize];

das ist aber nicht standard.
und brauchst ja kein zwischen-array. kannst gleich vom alten ins neue kopieren.

copynew wird normalerweise wohl grow genannt.

template <class typ> void MyArray<typ>::grow(int size) 
{ 
	int oldSize=aktSize;
	while (aktSize<size) 
		aktSize+=aktSize;
	typ* temp=new typ[aktSize]; 

	for(int i=0;i<oldSize;i++) 
		temp[i]=array[i]; 

	delete [] array; 
	array=tmp;
}

aber das ist nicht c++. mach besser assert oder meinetwegen throw bei ner indexgrenzenüberschreitung. und wenn sie passiert, war das ein programmierfehler, der aufgezeigt werden muss und nicht vertuscht.

mach außerdem auch so ein array für ohne new (und ohne wachsen natütlich).

template<class typ,size_t size> class MyStaticArray {
typ array[size];
public:
typ &operator[](int i);
};

das überprüft dann nur, aber man braucht's auch sehr häufig.

dann noch den op[] für const überladen, effektiv c++ lesen, kopierkonstruktor und zuweisungsoperator anbieten, die zweite size als attribut wegschmeißen.

die schleife

while (aktSize<size) 
	aktSize+=aktSize;

ist sehr gut. denn normalerweise wird sie genau einmal aufgerufen. wenn sogar garantiert ist, daß grow nur aufgerufen wird, wenn es was zu growen gibt, tut's eine do-schleife. aber vorher ausrechnen, wie oft verdoppelt werden müßte und << nehmen, wäre viel lahmer, weil wie gesagt, die schleife normalerweise (sagen wir mal deutlich häufiger als zu 99%) nur einmal durchläuft.

[groovemaster]

volkard schrieb:

die schleife

while (aktSize<size) 
	aktSize+=aktSize;

ist sehr gut. denn normalerweise wird sie genau einmal aufgerufen.

Ich verstehe trotzdem nicht, warum das nun besser sein soll, als eine simple Multiplikation.

Unter dieser Vorraussetzung

volkard schrieb:

die schleife normalerweise (sagen wir mal deutlich häufiger als zu 99%) nur einmal durchläuft

gilt $\frac{size}{2}<=aktSize<size$. Mit ein bisschen Algebra und Wahrscheinlichkeitsrechnung ergibt sich daraus, dass aktSize im Durchschnitt $\frac{3}{4}size$ ist. Und mit aktSize+=aktSize wird daraus $\frac{3}{2}size$. Was ist also an der Schleife besser, als ein

aktSize = size * 3 / 2;

[volkard]

groovemaster schrieb:

Was ist also an der Schleife besser, als ein

aktSize = size * 3 / 2;

die laufzeit.
aber hast recht,

aktSize = size * 2;

wäre nicht schrecklich schlecht.

ob man *3/2 oder *2 haben mag, ist geschmckssache. *2 garantiert, daß für 1e10 einfügungen nur 2e10 elementare kopiervorgänge stattfinden. und bei *3/2 schätze ich mal, daß man auf 3e10 kopiervorgänge kommt.

deine wahrscheinlichkeitsrechnung in allen ehren, aber fast immer macht man einfach push_back, und dann ist size==aktSize+1.

ob man auf size aufsetzt oder auf aktSize ist auch geschmckssache. ich gehe davon aus, daß ich nen buddy allocator drunter habe und daß die initial size eine zweierpotenz ist. wenn ich auf aktSize aufsetze, habe ich keinen verschnitt vom allokator aus, da immer ein recht voller buddy verwendet werden kann. die mehrkosten des einen sprungs wegen der schleife zahle ich dafür sehr gerne.
anderenfalls hätte ich verschnitt vom allocator bis zu 50% und darauf nochmal bis zu 50% verschnitt durch das eigene array, das macht mich leicht unglücklich.

[Gast]

OK! Sorry das ich so spät schreibe. War den ganzen Tag nicht zuhause...

Danke an ALLE für die ganzen Tips. Werde sie umsetzten.
Bis zur const-Überladung in meinem Buch bin ich noch nicht gekommen.(Werde aber mal schnell paar Seiten vorblättern )

@Volkard:
Das mit dem Fehler bei der Allozierung wollte ich ja auch noch mal nachfragen, wie ich genau drauf reagieren soll. Aber das weiß ich ja nun.

Und std und iostream habe ich nur drin, weil ich das Prog in main() direkt testen wollte

---> Werde jetzt mal eure ganzen Tips umsetzen (nachdem ich gegessen habe ) und dann den neuen Code posten

--------------
EDIT

[Gast]

Ach, habe gerade nen Fehler endeckt im code in copynew() sollte die letzte Bedingug in der Schleif i<altSize heißen :p ---> Thx to template

[Gast]

volkard schrieb:

typ temparray[aktSize];

das ist aber nicht standard.

Das finde ich aber jetzt auch komisch, das dürfte doch auch garnicht gehen.
aktSize muss doch ne Konstante sein, oda???

Dev-Cpp und Borland spucken keine Fehler aus...

[Gast]

So, hier der neue Code. Bitte wegen dem exit(EXIT_FAILURE) nicht schimpfen.
Ich weiß nämlich nicht genau was ich sonst machen soll.

template<class typ> class MyArray {

               typ* array;
               int aktSize,altSize,t;
               void grow(int size);
    public:
               MyArray(int size);
               MyArray(const MyArray &Array_kopie);
               ~MyArray();
               typ &operator[](const int i);
};

template<class typ> MyArray<typ>::MyArray(int size)
{
               aktSize=size;
               try {
                   array=new typ[size];
               }
               catch (std::bad_alloc xa)
               {
                     std::cout<<"Konnte Speicherplatz nicht reservieren";
                     exit(EXIT_FAILURE);
               }
}

template<class typ> MyArray<typ>::MyArray(const MyArray &Array_kopie)
{
              try {
                   array=new typ[Array_kopie.size];
               }
               catch (std::bad_alloc xa)
               {
                     std::cout<<"Konnte Speicherplatz nicht reservieren";
                     exit(EXIT_FAILURE);
               }

               for(int i=0;i<Array_kopie.size;i++)
                       array[i]=Array_kopie.array[i];                
}

template<class typ> MyArray<typ>::~MyArray()
{
              delete [] array;
}

template <class typ> typ &MyArray<typ>::operator[](const int i)  
{
         std::cout<<"const\n";     
         if(i>aktSize) grow(i);
         return array[i];
}

template <class typ> void MyArray<typ>::grow(int size)
{
         typ* temparray;

         altSize=aktSize;
         aktSize=size * 2;

         try {
             temparray=new typ [aktSize];
         }
         catch (std::bad_alloc xa)
         {
               std::cout<<"Konnte Speicherplatz nicht reservieren";
               exit(EXIT_FAILURE);
         }

         for(int i=0;i<aktSize;i++)
                 temparray[i]=array[i];

         delete [] array;
         array=temparray;

}

volkard schrieb:

dann noch den op[] für const überladen, effektiv c++ lesen, kopierkonstruktor und zuweisungsoperator anbieten, die zweite size als attribut wegschmeißen.

Effektiv C++ wird definitiv mein nächstes Buch
Und wieso soll ich denn den zuweisungsoperator überladen.
Wenn ich:

MyArray<int> z1(10);
MyArray<int> z2(10);

for (int i=0;i<10;i++) z1[i]=i+2;

z2=z1;

dann wird doch ne "schöne"(?) 1 zu 1 Kopie erstellt. Oder verstehe ich wieder was falsch

Und welches zweite size wegschmeißen

Und reicht das auch nicht aus:

typ &operator[](const int i);

Brauche ich den auch noch:

typ &operator[](int i);

Freak_coder schrieb:

Bis zur const-Überladung in meinem Buch bin ich noch nicht gekommen.(Werde aber mal schnell paar Seiten vorblättern )

---> Sorry mein ich doch gar nicht so Habe es mit Elementfunktion die const deklariert sind verwechselt (*schäm*)

Ich weiß, viele viele Fragen -> Will halt C++ perfekt beherrchen
Aber bis dahin ist es noch ein steiler weg

[otze]

Freak_Coder schrieb:

MyArray<int> z1(10);
MyArray<int> z2(10);

for (int i=0;i<10;i++) z1[i]=i+2;

z2=z1;

dann wird doch ne "schöne"(?) 1 zu 1 Kopie erstellt. Oder verstehe ich wieder was falsch

es wird bitweise kopiert, dh der compiler macht dann irgendwie sowas :

z2.array=z1.array;

was ist daran schlimm?
es werden nur die zeiger kopiert, nicht die arrays die du vorher mit new angelegt hast. z2 und z1 benutzen dann das gleiche array zum lesen und schreiben, dh veränderungen bei z1 wirken sich auch bei z2 aus. Und das willst du doch nicht, oder?

nun zu der sache:

try {
    array=new typ[size];
}
catch (std::bad_alloc xa)
{
    std::cout<<"Konnte Speicherplatz nicht reservieren";
    exit(EXIT_FAILURE);
}

mach daraus:

array=new typ[size];

wieso du das so machen sollst?
der benutzer dieser Klasse will selber die möglichkeit haben einzugreifen, er muss dafür sorge tragen, dass er sein programm ordnungsgemäß beendet wenns nicht anders geht. durch exit verbaust du ihm diesen weg komplett.
Oder anders ausgedrückt: es ist nicht die aufgabe der Klasse, fehler abzufangen, der benutzer muss das tun.

[volkard]

Freak_Coder schrieb:

Und welches zweite size wegschmeißen

altSize und aktSize brauchste nicht beide als attribute. mach so wenig wie möglich zum attribut, mach so viel wie möglich zu lokalen variablen. siehe mein grow().

Und reicht das auch nicht aus:

typ &operator[](const int i);

brauchst

typ &operator[](int i);

und

const typ &operator[](int i)const;

siehe den nächstes c++-buch. *grins*

Ich weiß, viele viele Fragen -> Will halt C++ perfekt beherrchen

das ist mal fein. die meisten wollen nur schnell 3d-spiele zusammenhacken. immer nett, wenn man wieder einer viel lernen will.

[Gast]

otze schrieb:

es werden nur die zeiger kopiert, nicht die arrays die du vorher mit new angelegt hast. z2 und z1 benutzen dann das gleiche array zum lesen und schreiben, dh veränderungen bei z1 wirken sich auch bei z2 aus. Und das willst du doch nicht, oder?

Achsoooo, stimmt ja

der benutzer dieser Klasse will selber die möglichkeit haben einzugreifen, er muss dafür sorge tragen, dass er sein programm ordnungsgemäß beendet wenns nicht anders geht. durch exit verbaust du ihm diesen weg komplett.
Oder anders ausgedrückt: es ist nicht die aufgabe der Klasse, fehler abzufangen, der benutzer muss das tun.

[Gast]

const typ &operator[](int i)const;

--> Kannst mir wohl nicht auf die schnelle Erklärung wieso ich das auch so machen sollte ???

Und bis ich das Buch mir kaufe dauerts noch was. Muss erstmal mein 2. Buch C++ Entpackt zu Ende lesen.

[ness]

Das bewirkt, dass du die Methode auch von einem Konstanten Objekt aus aufrufen kannst (das const am Ende). Nun haste aber das Problem, dass du bei einem nichtkonstanten Objekt auch nur lesezugriff auf die Elemente bekommst. Dazu wäre dann eine Überladung gut...

[Gast]

ness schrieb:

Das bewirkt, dass du die Methode auch von einem Konstanten Objekt aus aufrufen kannst (das const am Ende).

Aber was bringt mir das dann ???

const MyArray<int> zahl1(10);
zahl1[5]=6;

Da ruft ein Konstantes Objekt die Elemtfunktion auf.
Aber der Compiler mekert, weil ich das Konstante Objekt ja nicht ändern darf...

->Verstehe immer noch nicht genau, was ich damit:

const typ &operator[](unsigned int i) const;

machen soll