✔ Dynamisches Array oder Vector?

[ACE2xxx]

Hallo,

also, ich habe ein kleines Problem.
Ich müsste eine Liste mit Daten (Zahlen, Zeichen usw.) in einem Vector Speichern, dazu müsste dieser aber irgendwie dynamisch verwaltet werden.

Im endeffekt müsste ich z.B. alle Zahlen die eine 5 am Ende haben im 5-ten "Fach" speichern, alle die eine 3 am Ende haben im 3-ten Fach usw.

Der Hacken ist: Ich weiß zwar immer am Anfang wieviele Fächer ich brauche aber nicht wieviele Werte eingelesen werden und in welcher Reihenfolge diese ankommen.

Gibt es da eine Möglichkeit`?

Ich habe es mir so überlegt:

Man nehme ein Array der dimension n (=Anz. der Fächer) und erzeuge diese dynamisch zur Laufzeit.
In jedes Fach erzeuge ich zur Laufzeit einen Vector den ich dann mit "vector.push_back(i)" vervollständige...

Ich habe aber um Ehrlich zu sein absolut keine Ahnung wie ich das realisieren kann!
Kann mir vielleicht jemand sagen wie ich das gebacken bekomme?

Danke schon mal im Vorraus an alle.

Grüße ACE

 

[deepthroat]

Hi.

Nimm doch einfach eine Map von Listen:

#include <map>
#include <list>

std::map<int, std::list<DATEN> > speicher;

speicher[5].push_back(daten1);
speicher[3].push_back(daten2);
speicher[1].push_back(daten3);

Gruß

 

[ACE2xxx]

wow, das ging ja zügig! Danke für die antwort

Aber wie kann ich jetzt auf die Elemente zugreifen?

Ich habe es eben über den iterator versucht...das geht aber nicht

also so:

list<string>::iterator i;
for(i = speicher.begin(); i !=  speicher.end(); i++)
{
    cout<<*i<<" ";
}

Oder geht der Aufrug etwas anders?

Wie kann ich alle Elemente auf einmal ausgeben, also zuerst alle im Ersten Fach, dann im zweiten usw...?

Ich weiß es sind kleinigkeiten, mit denen ich euch hier aufhalte, aber ich habe noch nie damit gearbeitet und es fällt am Anfang immer am schwersten!

Danke nochmals

ACE!

 

[deepthroat]

list<string>::iterator i;
for(i = speicher.begin(); i !=  speicher.end(); i++)
{
    cout<<*i<<" ";
}

Die Variable speicher ist keine Liste, sie ist eine Map (von Listen)!

typedef map<int, list<string> > speicher_t;

for (speicher_t::const_iterator mi = speicher.begin(), me = speicher.end();
     mi != me; ++mi) 
{
  cout << endl << "Liste für " << mi->first << endl;
  for (speicher_t::mapped_type::const_iterator li = mi->second.begin(), 
       le = mi->second.end();
       li != le; ++li) 
  {
     cout << (*li) << endl;
  }
}

Gruß

 

[ACE2xxx]

Hallo,

Tut mir leid, dass ich jetzt erst antworte, aber ich hatte irgendwie keine Zeit mich damit zu befassen...bis heute!
Also erstmal danke ich für die wunderbare Antwort, geholfen hat es auf jeden Fall!
Damit lässt es sich auch ziemlich bequem arbeiten.

Aber jetzt möchte ich schon einige Modifikationen an dem Programm durchführen,
z.B. soll die Ausgabe beim letzten Element beginnen [gelöst ducht "reverse_iterator" ] oder ich möchte eine Kopie der map anfertigen usw...

Na ja und wie ich eine Kopie davon mache weiß ich auch noch nicht genau...
Habe eigentlich vor gehabt jedes Element mit Hilfe der Schleifen (siehe oben ) in eine andere map zu überführen, also mit

speicher[(mi->first)].puch_back(*li);

dabei stürzt das Programm leider auch ab!
Könnte mir da jemand ein paar Tipps geben!

Danke nochmals an "deepthroat" [Übrigens cooler nick ]

Grüße

ACE

 

[deepthroat]

Hi.

Na ja und wie ich eine Kopie davon mache weiß ich auch noch nicht genau...
Habe eigentlich vor gehabt jedes Element mit Hilfe der Schleifen (siehe oben ) in eine andere map zu überführen

Das ist nicht nötig. Eine Kopie wird automatisch bei der Zuweisung von einem speicher_t Objekt an ein anderes speicher_t Objekt angelegt (oder natürlich bei der Initialisierung durch einen Kopierkonstruktor).

also mit

speicher[(mi->first)].puch_back(*li);

dabei stürzt das Programm leider auch ab!

Kann es sein, das du dort das Objekt veränderst von dem die Iteratoren sind? Die Iteratoren können ungültig werden wenn die zugrundeliegende Datenstruktur geändert wird.

Gruß

 

[ACE2xxx]

Ah, ok, super, jetzt leuchtet es mir auch wieder ein...
Ich habe das Objekt nämlich zuerst ersetzt und dann versucht mit dem "nicht mehr gültigen" Iterator darauf zuzugreifen!


Aber das erste müstest du mir nochmal erklären, weil ich dann den Quellcode nicht verstanden habe den du gepostet hast.
Das könnte dann auch der Grund dafür sein, dass ich ca seit einer Stunde versuche mit dem Inhalt zu arbeiten, was aber nicht klappt.

Miene Idee ist folgende:
falls in einem "Fach" von der Map eine bzw. mehrere Elemente liegen, vergleiche diese mit den nachfolgenden im selben "Fach" UND mit jedem aus dem nächsten "Fach" und dann noch ein paar bedingungen usw... die sind aber machbar soweit!

ich habe versucht auf diese Art und Weise es anzugehen:

void myProgram::vergleiche()
{
 	 for(int i = 0;i<=dim;i++)
 	 {
	  	for(int j = 0, k = vector_temp[i].size();j <= k ; j++)
		{  	 
	  	if(	!vector_temp[i].empty() )
		  {cout << vector_temp[i].front() << endl;
		  	      vector_temp[i].pop_front();	 
				  }
	                       }
	 }
}

ich habe mir meine Struktur als eine Art Vector vorgestellt, daher auch der Name.

Könntest du mir einen Tipp geben wie ich jetzt die Vergleiche in meine Schleife einbauen kann. Also den Part mit: "falls in einem "Fach" von der Map eine bzw. mehrere Elemente liegen, vergleiche diese mit den nachfolgenden im selben "Fach" UND mit jedem aus dem nächsten "Fach" "

Die Schleife an sich macht ja genau das gleiche wie deine, ich wollte nur ein bisschen rumexperementieren...

Ich glaube ich brauche da noch eine Schleife, aber ich habe absolut keinen Plan wie man das machen kann..

Danke schon mal im Vorraus...

Grüße

ACE

 

[deepthroat]

Die Schleife an sich macht ja genau das gleiche wie deine, ich wollte nur ein bisschen rumexperementieren...

Naja, nicht ganz. Falls Elemente in der Map noch nicht existieren, werden sie angelegt. Das passiert bei der Verwendung von Iteratoren nicht.

Wenn allerdings immer alle Elemente von 0 bis dim existieren, oder die Lücken in der Struktur nicht weiter schlimm sind, dann kannst du auch einfach einen vector<list<string> > verwenden. Ich hatte es nur so verstanden, dass du nicht weißt welche Elemente überhaupt vorkommen werden...

Um ein Element in der aktuellen oder in der nächsten Liste zu finden, kannst du den find Algorithmus verwenden:

#include <algorithm>

for(int i = 0;i<=dim;i++) {
  for(int j = 0, k = vector_temp[i].size();j < k ; j++) {  	 
    list<string>::iterator iter = find(vector_temp[i].begin() + j, vector_temp[i].end(), vector_temp[i][j]);
    if (iter != vector_temp[i].end()) {
       // gefunden.
    }
    iter = find(vector_temp[i+1].begin(), vector_temp[i+1].end(), vector_temp[i][j]);
    
    ...
  }
}

Gruß

 

[ACE2xxx]

Arbeiten mit map und list

Hallo nochmals,

erstmal wieder Danke für die Großartige Hilfe...ich bin schon mal um einiges weiter

Du hast es schon richtig verstanden...am anfand weiß ich nciht welche Elemente vorkommen, aber die Dimension habe ich mir mit "size" ausgeben lassen in einer anderen Funktion!

Mit der Map zu arbeiten ist schon angenehm, vor allem, dass man sich nciht um die Verwaltung der Liste kümmern muss!

In den letzten Stunden habe ich mal unter Anderem folgendes zusammengebaut:

void MyProg::auslesen()
{
               //mit dem n kann ich die Differenz zwischen den Spalten errechnen, falls nicht jede Spalte gefüllt ist.
 	 int n;
 	 for(int i = dim ; i>=0 ; i--)
 	 {
	 n=1;
 	   for(list<string>::iterator iter1 = vector_temp[i].begin(); iter1 != vector_temp[i].end(); iter1++)
	    {
	      while ( (vector_temp[i-n].empty()) && ((i-n) >= 0 )) {n++;}
	      
 		  for(list<string>::iterator iter2 = vector_temp[i-n].begin(); iter2 != vector_temp[i-n].end(); iter2++)
		   {
             cout << "Iterator1: " << *iter1 << " Iterator2: " << *iter2 << " Differenz: "<< differenz(*iter1,*iter2) << endl;
// In der Funktion Differenz wird festgestellt, wie weit die Elemente auseinander liegen z.B. 45 und 15, als Return-Wert erhält man 30	 
	       }  
   	 	}
     }
}

Ich habe festgestellt, dass ich überhaupt keine Vergleiche in der gleichen Liste benötige, wenn ich mir eine find Funktion zusammenschraube, die bei der Eingabe schon überprüft, ob es das Element bereits in der Liste gibt, aber ich habe es nicht geschafft zu implementieren, das war mein Versuch:

void MyProg::AddTerm(int stelle, string term)
{	 
              list<string>::iterator doppelte;
              doppelte  = vector[stelle].find(term);
              if(doppelte != vector[stelle].end())
	 vector[stelle].push_back(term);

}

ich weiß, dass da was nicht stimmt, aber ich habe keinen Plan, wie ich drum herrum komme! Hier der Fehler:

'class std::list<std::string, std::allocator<std::string> >' has no member named 'find'

Weißt du vielleicht was da los ist, bzw wie ich das wieder hinbiegen kann?

Danke nochmals für die Mühe und den Zeitaufwand!

Grüße

ACE

 

[deepthroat]

Hi.

Du hast es schon richtig verstanden...am anfand weiß ich nciht welche Elemente vorkommen, aber die Dimension habe ich mir mit "size" ausgeben lassen in einer anderen Funktion!

Mit der Map zu arbeiten ist schon angenehm, vor allem, dass man sich nciht um die Verwaltung der Liste kümmern muss!

Ja, aber das mußt du beim vector auch nicht. Wenn du schon vorher die Dimension kennst, kannst du auch einfach gleich einen vector mit der entsprechenden Größe anlegen:

vector<list<string> > aVector(dim + 1);

// oder falls der vector schon existiert:

aVector.resize(dim + 1);

Dabei werden dann dim + 1 Listen in dem Vektor angelegt, die natürlich erstmal alle leer sind. Je nach dem wie groß dim ist und wie dünn der Vektor dann besetzt ist, kann es sich lohnen oder auch nicht. Die Map ist als Baum implementiert und bei jedem Zugriff muss das Element erstmal im Baum gesucht werden - das ist natürlich nicht sehr effizient. Bei einem Vektor ist das nicht der Fall, da ein Vektor wahlfreien Zugriff bietet.

// In der Funktion Differenz wird festgestellt, wie weit die Elemente auseinander liegen z.B. 45 und 15, als Return-Wert erhält man 30

Es gibt bereits eine Funktion std::distance im Header <iterator> welche den Abstand zwischen 2 Iteratoren berechnet. Der Vorteil ist, das für verschiedene Arten von Iteratoren der Abstand möglichst effizient ermittelt wird.

Ich habe festgestellt, dass ich überhaupt keine Vergleiche in der gleichen Liste benötige, wenn ich mir eine find Funktion zusammenschraube, die bei der Eingabe schon überprüft, ob es das Element bereits in der Liste gibt, aber ich habe es nicht geschafft zu implementieren, das war mein Versuch:

void MyProg::AddTerm(int stelle, string term)
{	 
              list<string>::iterator doppelte;
              doppelte  = vector[stelle].find(term);
              if(doppelte != vector[stelle].end())
	 vector[stelle].push_back(term);

}

ich weiß, dass da was nicht stimmt, aber ich habe keinen Plan, wie ich drum herrum komme! Hier der Fehler:

'class std::list<std::string, std::allocator<std::string> >' has no member named 'find'

Weißt du vielleicht was da los ist, bzw wie ich das wieder hinbiegen kann?

Wie der Compiler schon sagte: eine find Methode gibt es bei einer std::list nicht.

Es gibt einen generischen find Algorithmus für alle Container. Siehe mein Beispiel oben.

Gruß