Vectorklasse, Probleme

Hallo Leute,

ich hab mich mal an einer Vectorklasse versucht, und stoße auf 2 Probleme (die markeire ich im Code)

bitte nicht an der form stören..

const int GROW=10;
class StackAsVector
{
 public:
  StackAsVector(int size){data = new int[size];TopIndex=-1;vsize=size;}
  StackAsVector(const StackAsVector& sav)           //copy konstruktor
  {
   vsize = sav.vsize;
   data = new int[vsize];
   TopIndex=sav.TopIndex;
   for(int i=0;i<vsize;i++)
    data[i]=sav.data[i];
  }

  void Pop()
   {
    if(TopIndex==-1)
     cout<<"Stack bereits leer";
    else
     {
      data[TopIndex]=0;
      TopIndex--;
     }
   }

  int Top(){return data[TopIndex];}

  int Size(){return TopIndex+1;}

  int Capacity(){return vsize;}

  void Push(int number)
  {
   TopIndex++;
   if(TopIndex==vsize)
    Grow();

   data[TopIndex]=number;
  }

  bool isEmpty(){return TopIndex==-1;}

  int ElementAt(int at){return data[at];}

  void InsertAt(int at,int number)     //hier habe ich probleme, wie könnte ich diese funktion am besten programmieren??? Wenn ichdie in main aufrufe, bleibt er in endlosschleife
  {
   TopIndex++;
   if(TopIndex==vsize)
    Grow();
   if(at>vsize)
    Grow();
   if(at>TopIndex)
    {
    data[at]=number;
    }
    else
    {
     int rest = Size()-(at+1);
     int* temp1 = new int[at-1];
     int* temp2 = new int[rest];
     for(int i=0;i<at;i++)
      temp1[i]=data[i];
     for(int i=at;i<rest;i++)
      temp2[i]=data[i];

     data=new int[vsize];
     for(int i=0;i<at;i++)
      data[i]=temp1[i];

     data[at]=number;

     for(int i=at;i<rest;i++)
      data[i]=temp2[i];

     delete[] temp1;
     delete[] temp2;
    }

  }

  void DeleteAt(int at);

  void Empty()
  {

   delete[] data;

   vsize=GROW;
   data = new int[vsize];
   for(int i=0;i<vsize;i++)
    data[i]=0;
   TopIndex=-1;
  }

  void PrintData(int start,int end,int mode=0)
  {
   if(mode>1||mode<0)
    mode=0;

   if(mode==0)
   {
    for(int i=start;i<=end;i++)
    {
     cout<<"Element an Position: "<<i<<" ist: "<<data[i]<<endl;
    }
   }
   else
   {
    for(int i=end;i>=start;i--)
    {
     cout<<"Element an Position: "<<i<<" ist: "<<data[i]<<endl;
    }
   }
  }

  void operator=(const StackAsVector& sav)
  {

  }
  void operator=(const int number)
  {
    Push(number);
  }

  ~StackAsVector(){delete[] data;}
 private:

  int vsize;
  int* data;
  int TopIndex;

  void Grow()
  {
   int* temp = data;  //altes array sichern
   vsize+=GROW;       //Größe erhöhen
   delete[] data;     //speicher freigeben
   data = new int[vsize];

   for (int i=0;i<TopIndex;i++)             //daten umkopieren
   {
    data[i]=temp[i];
   }

   delete[] temp;     //temporären speicher freigeben
  }
};
//---------------------------------------------------------------------------

#pragma argsused
int main(int argc, char* argv[])
{
 typedef StackAsVector SAV;
 SAV t(10);
 SAV t2(t);
 /*cout<<"Alte groesse: "<<t.Size()<<endl;
 cout<<"Alte Kapazitaet: "<<t.Capacity()<<endl;
 cout<<"Alte groesse copy: "<<t2.Size()<<endl;
 cout<<"Alte Kapazitaet copy: "<<t2.Capacity()<<endl;
 for(int i=0;i<10;i++)
 {
  t.Push(i);
 }
 cout<<"Neue groesse: "<<t.Size()<<endl;
 cout<<"Neue Kapazitaet: "<<t.Capacity()<<endl;
 cout<<"AUSGABE:"<<endl;
 for (int i=0;i<11;i++)
 {
  if(t.isEmpty())
   {
   cout<<"Ende erreicht"<<endl;
   break;
   }
  cout<<t.Top()<<endl;
  t.Pop();
 }
 for(int i=0;i<12;i++)
 {
  t.Push(i);
 }
 t.PrintData(3,7,1);
 cout<<"Neue groesse: "<<t.Size()<<endl;
 cout<<"Neue Kapazitaet: "<<t.Capacity()<<endl;
 cout<<"Element an Position 2: "<<t.ElementAt(2)<<endl;
 t.Empty();
 cout<<"Stack geloescht"<<endl;
 cout<<"Neue groesse: "<<t.Size()<<endl;
 cout<<"Neue Kapazitaet: "<<t.Capacity()<<endl;
 t=23;                                */
 cout<<t.Top()<<endl;
 cout<<"Groesse:"<<t.Size()<<endl;
 t.Push(1);
 cout<<"Groesse:"<<t.Size()<<endl;
 t.Push(1);
 cout<<"Groesse:"<<t.Size();  //hier gibt er plötzlich völlig falsche werte aus, wieso??
 cout<<t.ElementAt(2)<<endl;
 //t.InsertAt(2,20);
 cout<<t.ElementAt(2)<<endl;
 cout<<t.ElementAt(3)<<endl;
 getch();       return 0;
}
//---------------------------------------------------------------------------

CStoll

Wahlwiederholung schrieb:

void Grow()
  {
   int* temp = data;  //altes array sichern
   vsize+=GROW;       //Größe erhöhen
   delete[] data;     //speicher freigeben //<-FEHLER
   data = new int[vsize];

   for (int i=0;i<TopIndex;i++)             //daten umkopieren
   {
    data=temp[i];
   }

   delete[] temp;     //temporären speicher freigeben
  }
};

Also das kann so nicht funktionieren - mit dem "delete[] data;" löschst du die Daten deines Stacks und versuchst [i]anschließend, diese Daten zu kopieren. Lass mal diese Zeile weg, dann solltest du eigentlich sinnvollere Werte bekommen.

wieso kann das nicht gehen?
Hab doch vorher schon data in temp gespeichert, und kopiere dann in das neue data die alten werte rein....

PS: in der for schleife heißt eigentlich data[i]=temp[i]

LordJaxom

Du sicherst höchstens die Adresse des ersten Feldelementes, nicht das Ursprungsfeld. Dazu musst Du erstmal ein Feld für die Kopie erzeugen.

Aber Vorschlag: Baue doch erstmal das neue Array komplett auf und lösch dann das alte...

Und das delete[] temp ist auch übel:

int *temp = data; // temp und data zeigen nun auf das selbe Feld
delete[] data; // das Feld wird gelöscht
... /* Hier wird es sogar benutzt!! */
delete[] temp; // das Feld wird nochmal gelöscht

hm...wenn ich das delete[] wegmache, geht es trotzdem nicht

und wenn ich in der main das obere auskommentierte wieder reinmache geht es da oben:

int main(int argc, char* argv[])
{
 typedef StackAsVector SAV;
 SAV t(10);
 SAV t2(t);
 cout<<"Alte groesse: "<<t.Size()<<endl;
 cout<<"Alte Kapazitaet: "<<t.Capacity()<<endl;
 cout<<"Alte groesse copy: "<<t2.Size()<<endl;
 cout<<"Alte Kapazitaet copy: "<<t2.Capacity()<<endl;
 for(int i=0;i<10;i++)
 {
  t.Push(i);
 }
 cout<<"Neue groesse: "<<t.Size()<<endl;   //das geht, richtiger wert 10
 cout<<"Neue Kapazitaet: "<<t.Capacity()<<endl;
 cout<<"AUSGABE:"<<endl;    /*
 for (int i=0;i<11;i++)
 {
  if(t.isEmpty())
   {
   cout<<"Ende erreicht"<<endl;
   break;
   }
  cout<<t.Top()<<endl;
  t.Pop();
 }
 for(int i=0;i<12;i++)
 {
  t.Push(i);
 }
 t.PrintData(3,7,1);
 cout<<"Neue groesse: "<<t.Size()<<endl;
 cout<<"Neue Kapazitaet: "<<t.Capacity()<<endl;
 cout<<"Element an Position 2: "<<t.ElementAt(2)<<endl;
 t.Empty();
 cout<<"Stack geloescht"<<endl;
 cout<<"Neue groesse: "<<t.Size()<<endl;
 cout<<"Neue Kapazitaet: "<<t.Capacity()<<endl;
 t=23;                                */
 cout<<t.Top()<<endl;
 cout<<"Groesse:"<<t.Size()<<endl;
 t.Push(1);
 cout<<"Groesse:"<<t.Size()<<endl;
 t.Push(1);
 cout<<"Groesse:"<<t.Size();
 cout<<t.ElementAt(2)<<endl;
 //t.InsertAt(2,20);
 cout<<t.ElementAt(2)<<endl;
 cout<<t.ElementAt(3)<<endl;
 getch();       return 0;
}

hm...weiß keiner was??

Wie müsste denn die Grow() und InsertAT() funktion richtig aussehen?

Braunstein

Mal ein Beispiel für Grow

void Grow()
{
   int* temp = new int[vsize+GROW];  // Speicher für neue Größe allozieren
   for (int i=0;i<TopIndex;++i)      // Daten umkopieren
   {
    temp[i] = data[i];
   }
   vsize += GROW;                    // Größe erhöhen
   std::swap(temp,data);             // Pointer tauschen
   delete[] temp;                    // Speicher freigeben
}

Statt der for-Schleife könnte man auch memcpy einsetzen. Desweiteren würde ich nicht um GROW erhöhen, sondern hier eher einen Multiplikator einsetzen (üblich ist hier 2).

ok, aber in Volkards Tut bei StackAsVector bei der Lösung ist aber die das erhöhen des Stacks so wie ich es gemacht habe!!!

was genau passiert hier durch das swap?

Und wie könnte ich das mit dem InsertAt() lösen?

Braunstein

Das Erhöhen kann man letztlich machen wie man will. In zwei mir bekannten Implementationen von vector (stl) wird mit Faktor 2 multipliziert. Deswegen die Bemerkung.
Der Kommentar hinter swap sagt doch eigentlich alles. Ansonsten schau mal in die Hilfe zu swap.
Zu InsertAt.
Da will ich erstmal keinen Quellcode angeben. Nur ein paar Hinweise.
Das mit dem Grow am Anfang ist erstmal richtig.
Du brauchst dann aber keine temporären Arrays mehr.
Kopiere einfach ab der Einfügeposition alle Elemente eins nach hinten (von hinten anfangen).
Füge dann das Element an der gewünschten Position ein.
Dann sollte es gehen.

nein mir geht es hier drum:

int* temp = new int[vsize+GROW];  // Speicher für neue Größe allozieren 
   for (int i=0;i<TopIndex;++i)      // Daten umkopieren 
   { 
    temp[i] = data[i]; 
   }

da in volkards tut das kopieren in ein anderes array so steht:

int* temp = data;

ja swap is eigentl klar!

CStoll

int* temp=data;

kopiert überhaupt keine Daten, sondern setzt nur einen Ersatzzeiger auf deine vorhandenen Daten - danach kannst du data einen neuen Bereich zuweisen und die Daten aus dem alten Bereich (auf den temp immer noch zeigt) dorthin verschieben.

Braunstein

Das geht natürlich auch so, hat aber den Nachteil, dass wenn bei der Allozierung neuen Speichers etwas schief geht, der Status deiner Instanz gestört ist und du nicht mehr an deine Daten kommst.

ser1al

hm...weiß nich ob das so geht, hab mal grad was ausgedacht (ohne zu testen)

int insertElementAt(int _number, int _position)
  {
   TopIndex=TopIndex+1;
   if(TopIndex==size)
    Grow();

   int* temp = new int[TopIndex];    //um daten ab/inkl _position zu sichern

   for(int i=_position-1;i<TopIndex+1;i++)
   {
    temp[i]=data[i];
   }

   data[_position]=_number;         //nummer einfügen an gewünschter position

   for(int i=_position+1;i<TopIndex+1;i++)
   {
    data[i]=temp[i-1];               //gesicherten daten nach position wieder einfügen
   }

   delete[] temp;
  }

gibt wohl aber sicher bessere lösungen?!