 |
JLI Spieleprogrammierung
|
| Vorheriges Thema anzeigen :: Nächstes Thema anzeigen |
| Autor |
Nachricht |
t10ottoo
Senior JLI'ler
Alter: 40
Anmeldedatum: 15.04.2004
Beiträge: 210
Wohnort: Berlin
Medaillen: Keine
|
 Verfasst am: 14.04.2006, 21:12 Titel: STL - Verständnisprobleme mit den Iteratoren |
 |
|
Hi,
ich befasse mich gard mit dem Thema STL. Speziell den Datentyp "vector". Nun bin ich beim Thema Iteratoren. Leider fehlt mir da ein wenig der Sinn. Ich habe hier mal ein kleines Beispielprogramm:
| CPP: | vector<int> v1;
vector<int>::iterator iter1;
int izahl = 0;
do
{
cout << "Welche Zahl soll hinzugefuegt werden?" << endl;
cin >> izahl;
v1.push_back(izahl);
} while (izahl != 0);
// Letztes Element löschen, damit die 0 nicht mit ausgegeben wird.
v1.erase(--v1.end());
cout << endl << endl;
for (int j = 0; j < v1.size(); j++)
{
cout << v1[j] << " ";
}
cout << endl << endl;
for (iter1 = v1.begin(); iter1 != v1.end(); iter1++)
{
cout << *iter1 << " ";
}
getch(); |
Das Programm sollte denk ich klar sein. Liest halt Zahlen ein, bis man eine 0 eingibt. Die Zahlen werden im vector 'v1' gespeichert.
Nun habe ich zwei Möglichkeiten der Ausgabe. Einmal ohne und einmal mit Iterator.
Nun frage ich mich, warum manche die Ausgabe mit Iterator verwenden. Bzw. frage ich mich, ob es wirklich sinnvolle Anwendungen für Iteratoren gibt. Denn die Ausgabe klappt ja auch wunderbar ohne Iteratoren.
Danke schonmal für eure Bemühungen 
Gruß
Otti
_________________
Meine kleine Projekte-Seite |
|
| Nach oben |
|
 |
51m0n
JLI'ler
Alter: 33
Anmeldedatum: 06.01.2006
Beiträge: 167
Wohnort: Erkelenz
Medaillen: Keine
|
| Verfasst am: 14.04.2006, 21:26 Titel: |
|
|
Hi
Bei Vectoren geht die Ausgabe noch ganz gut ohne Iteratoren aber bei einer List sind das schon anders aus  .
Du bracuhst Iteratoren zum Beispiel wenn du ein Element löschen willst. Die Methode erase() braucht einen Iterator, der auf das zu löschende Element zeigt.
MfG 51m0n
_________________
Teigwaren
heißen Teigwaren,
weil sie früher einmal Teig waren |
|
| Nach oben |
|
|
Fallen
JLI MVP
Alter: 40
Anmeldedatum: 08.03.2003
Beiträge: 2860
Wohnort: Münster
Medaillen: 1 (mehr...)
|
| Verfasst am: 14.04.2006, 21:50 Titel: |
|
|
| 51m0n hat Folgendes geschrieben: | Hi
Bei Vectoren geht die Ausgabe noch ganz gut ohne Iteratoren aber bei einer List sind das schon anders aus .
Du bracuhst Iteratoren zum Beispiel wenn du ein Element löschen willst. Die Methode erase() braucht einen Iterator, der auf das zu löschende Element zeigt.
MfG 51m0n |
Wobei ja v1.erase( v1.begin()+i ); auch wunderbar funktioniert läuft wie du sagtest mit iteratoren ab aber der index i kann so auch wudnerbar verwendet werden, gezwungen iteratoren zu benutzen bist du also in diesem fall nicht unbedingt. Afaik sind iteratoren aber etwas fixer da diese nicht wie beim index erst errechnet werden muss, was einige funktionscalls spart.
Einige hier werden dir das sicher besser erklären können.
_________________
"I have a Core2Quad at 3.2GHz, 4GB of RAM at 1066 and an Nvidia 8800 GTS 512 on Vista64 and this game runs like ass whereas everything else I own runs like melted butter over a smokin' hot 18 year old catholic schoolgirl's arse." |
|
| Nach oben |
|
|
51m0n
JLI'ler
Alter: 33
Anmeldedatum: 06.01.2006
Beiträge: 167
Wohnort: Erkelenz
Medaillen: Keine
|
| Verfasst am: 14.04.2006, 22:19 Titel: |
|
|
Ich weis nicht ob es ganz ohne Iterator geht, denn v1.begin() liefert ja einen Iterator zurück den du dann inkrementierst(oder wie man das auch immer schreibt), also arbeitest du genau genommen auch mit Iteratoren . Auch wenn man das nicht auf den ersten Blick sieht.
_________________
Teigwaren
heißen Teigwaren,
weil sie früher einmal Teig waren |
|
| Nach oben |
|
|
Fallen
JLI MVP
Alter: 40
Anmeldedatum: 08.03.2003
Beiträge: 2860
Wohnort: Münster
Medaillen: 1 (mehr...)
|
| Verfasst am: 14.04.2006, 22:31 Titel: |
|
|
Habs ja nicht abgestritten, war wohl nur unleserlich geschrieben von mir
| Zitat: | | Wobei ja v1.erase( v1.begin()+i ); auch wunderbar funktioniert, läuft wie du sagtest mit iteratoren ab, aber der Index i kann so auch wunderbar verwendet werden. |
_________________
"I have a Core2Quad at 3.2GHz, 4GB of RAM at 1066 and an Nvidia 8800 GTS 512 on Vista64 and this game runs like ass whereas everything else I own runs like melted butter over a smokin' hot 18 year old catholic schoolgirl's arse." |
|
| Nach oben |
|
|
The Lord of Programming
Living Legend
Alter: 37
Anmeldedatum: 14.03.2003
Beiträge: 3122
Medaillen: Keine
|
| Verfasst am: 15.04.2006, 13:45 Titel: |
|
|
| 51m0n hat Folgendes geschrieben: | | Ich weis nicht ob es ganz ohne Iterator geht, denn v1.begin() liefert ja einen Iterator zurück den du dann inkrementierst(oder wie man das auch immer schreibt), also arbeitest du genau genommen auch mit Iteratoren . Auch wenn man das nicht auf den ersten Blick sieht. |
Nicht ganz...Da es in der Natur des Vectors liegt, dass immer an einem Stück im Speicher liegt, genügt es, einen Zeiger auf das erste Element zu bekommen(Iterator!=Zeiger) und im Speicher um Index fortzuschreiten. So kommst du bei Vectoren immer auf das richtige Element. Also sollte der Zugriff per Index immer noch am schnellsten sein.
Da brauchst du keine Iteratoren im Speicher verwalten und nur eine Zählervariable zu inkrementieren.
Vorsicht: Wer trotzdem Iteratoren für Vectoren verwendet, muss aufpassen, da Iteratoren beim Hinzufügen eines Elements ungültig werden können. Abhilfe schafft dem eine vorzeitige Reservierung des Speichers durch die Elementfunktion reserve():
| CPP: | std::vector< int > myvector;
//Reserviert Speicher für 20 Elemente
myvector.reserve(20); |
So wird auch der Aufwand umgangen, der beim Hinzufügen eines Elements nötig ist. Sobald im vector noch freier Speicher reserviert ist, kann das Element einfach hinzugefügt werden. Ist dies nicht mehr so, wird 1. der Iterator ungültig, da 2. der gesamte vector zusammenhängend neu in den Speicher geschrieben wird.
Da sind wir genau beim Thema. Ich vermute, dort wo du Iteratoren bei vectoren im Einsatz gesehen hast, mussten sie verwendet werden. Es gibt Elementfunktionen/Algorithmen, die nur Iteratoren (also keine einfache Indexangabe) unterstützen.
Wenn du also deine Liste im Programmablauf sowieso von vorne bis hinten durchlaufen willst und bei einem bestimmten Ereigniss z.B. ein Element löschen willst (oder eben irgendeine andere Aktion, die einen Iterator erfordert), dann bietet es sich an, gleich Iteratoren zu nehmen, anstatt eine normale for-Schleife mit Indexwert, bei der du parallel noch einen Iterator mitlaufen lässt oder ähnliche Verkrampfungen 
_________________
www.visualgamesentertainment.net
Current projects: RDTDC(1), JLI-Vor-Projekt, Tetris(-Tutorial), JLI-Format
(1) Realtime Developer Testing and Debugging Console
Anschlag, Anleitung zum Atombombenbau, Sprengkörper...
Hilf Schäuble! Damit er auch was findet... |
|
| Nach oben |
|
|
Kampfhund
Super JLI'ler
Alter: 42
Anmeldedatum: 20.07.2002
Beiträge: 408
Medaillen: Keine
|
| Verfasst am: 15.04.2006, 14:17 Titel: |
|
|
Ein Vorteil von iteratoren ist Folgendes:
| CPP: | #include <vector>
#include <list>
struct test
{
typedef unsigned int the_type;
typedef std::list<the_type> TypeStorage;
typedef TypeStorage::iterator iter;
void operate_on_s()
{
for(iter i=s.begin();i!=s.end();i++)
{
if(*i == 3)
*i = 4;
}
}
TypeStorage s;
};
|
Willst du in diesem Beispiel nun - warum auch immer - einen anderen container-typ verwenden, so kannst du einfach diese Zeile:
| CPP: | typedef std::list<the_type> TypeStorage;
|
durch diese ersetzen:
| CPP: | typedef std::vector<the_type> TypeStorage;
|
und das Ganze lässt sich ohne weiteren Aufwand kompilieren.
_________________
Kochen ist ein NP-schweres Optimierungsproblem. |
|
| Nach oben |
|
|
51m0n
JLI'ler
Alter: 33
Anmeldedatum: 06.01.2006
Beiträge: 167
Wohnort: Erkelenz
Medaillen: Keine
|
| Verfasst am: 15.04.2006, 14:27 Titel: |
|
|
Liegt der Vector echt immer an einem Stück? Denn der Compiler kann ja nicht ahnen wie groß er einmal wird und kann dementsprechend nicht den Speicher reservieren. Oder hab ich hier nen Denkfehler?
_________________
Teigwaren
heißen Teigwaren,
weil sie früher einmal Teig waren |
|
| Nach oben |
|
|
Kampfhund
Super JLI'ler
Alter: 42
Anmeldedatum: 20.07.2002
Beiträge: 408
Medaillen: Keine
|
| Verfasst am: 15.04.2006, 14:37 Titel: |
|
|
| 51m0n hat Folgendes geschrieben: |
Denn der Compiler kann ja nicht ahnen wie groß er einmal wird und kann dementsprechend nicht den Speicher reservieren.
|
Ist der Speicher des Vectors zu klein, so wird neuer und größerer Speicher reserviert und alle Elemente des alten Vectors werden in den neuen Speicher kopiert. Das ist natürlich zeitaufwändig, weswegen vectoren auch weniger für das einfügen und löschen von Elementen gedacht sind sondern eher für schnellen zugriff (ist ja nur das indizieren in ein array, also konstanter Zeitaufwand).
EDIT: Und ja, meines wissens nach ist der Speicher des vectors immer zusammenhängend.
_________________
Kochen ist ein NP-schweres Optimierungsproblem. |
|
| Nach oben |
|
|
t10ottoo
Senior JLI'ler
Alter: 40
Anmeldedatum: 15.04.2004
Beiträge: 210
Wohnort: Berlin
Medaillen: Keine
|
| Verfasst am: 15.04.2006, 19:30 Titel: |
|
|
Vielen Dank erstmal für die Antworten und sorry, dass ich jetzt erst antworte. Musste aber noch ein paar Ostervorbereitungen treffen
Soweit hab ich das erstmal verstanden.
Nur noch eine Frage:
Kampfhund hat ja geschrieben, dass Vectoren weniger gut fürs Einfügen und Löschen von Elementen sind, weil das eben sehr langsam ist, da oft (wenn der Speicher nicht mehr zusammenhängend sein kann) neuer Speicher reserviert weden muss und alle Elemente rüberkopiert werden.
Nun stellt sich mir die Frage, wo ich den Vector dann überhaupt sinnvoll anwenden kann? Bzw. sollte?
| Zitat: | | Für einen schnellen Zugriff |
Hmm...ok, d.h. am Anfang Werte reinschreiben und nicht mehr großartig erweitern, sondern nur mit diesen Werten arbeiten? Für Einfügen und Löschen von Elementen wäre dann wohl die Liste besser?
Wäre nett, wenn ihr mir diese Fragen noch beantworten könntet.
Gruß und Danke
Otti
_________________
Meine kleine Projekte-Seite |
|
| Nach oben |
|
|
Kampfhund
Super JLI'ler
Alter: 42
Anmeldedatum: 20.07.2002
Beiträge: 408
Medaillen: Keine
|
| Verfasst am: 15.04.2006, 21:43 Titel: |
|
|
| t10ottoo hat Folgendes geschrieben: |
Nun stellt sich mir die Frage, wo ich den Vector dann überhaupt sinnvoll anwenden kann? Bzw. sollte?
| Zitat: | | Für einen schnellen Zugriff |
Hmm...ok, d.h. am Anfang Werte reinschreiben und nicht mehr großartig erweitern, sondern nur mit diesen Werten arbeiten? Für Einfügen und Löschen von Elementen wäre dann wohl die Liste besser?
|
Ja. Bei einer einfach oder doppelt verketteten List müssen beim Einfügen/Löschen nur Pointer "umgebogen" werden. Das kann in konstanter Zeit erledigt werden (allerdings nur wenn man am Anfang oder am Ende einfügt/löscht, ansonsten ist es von der größe der Liste abhängig).
EDIT:
Unter folgender Adresse findet man (bischen unter der mitte des Dokuments) eine Tabelle mit dem Laufzeitverhalten der verschiedenen Container:
http://www.dd.bib.de/~dozric/C++/kennen/stl.htm
_________________
Kochen ist ein NP-schweres Optimierungsproblem. |
|
| Nach oben |
|
|
The Lord of Programming
Living Legend
Alter: 37
Anmeldedatum: 14.03.2003
Beiträge: 3122
Medaillen: Keine
|
| Verfasst am: 16.04.2006, 02:57 Titel: |
|
|
Ja, es gibt ja schließlich auch Situationen, in denen du weniger Elemente hinzufügen musst, aber eher die Struktur oft durchlaufen musst
Aber wie gesagt, man kann auch selbst den Speicher für den Vector reservieren
| The Lord of Programming hat Folgendes geschrieben: | | CPP: | std::vector< int > myvector;
//Reserviert Speicher für 20 Elemente
myvector.reserve(20); |
|
Also wenn es wahrscheinlich ist, dass während dem Programmverlauf der vector eine bestimmte Maximumgröße nicht überschreitet, wäre sowas ein guter Weg, den Aufwand beim Hinzufügen drastisch zu kürzen.
Genauso wäre es möglich, an "unbelasteten" Stellen des Programms/Spiels zu überprüfen, ob mehr Speicher reserviert werden muss, damit du sowas nicht in den Performance-Engpässen machen musst.
| CPP: | // <- liefert die Anzahl der im Speicher reservierten Elemente
unsigned int reserved_elements=myvector.capacity(); |
_________________
www.visualgamesentertainment.net
Current projects: RDTDC(1), JLI-Vor-Projekt, Tetris(-Tutorial), JLI-Format
(1) Realtime Developer Testing and Debugging Console
Anschlag, Anleitung zum Atombombenbau, Sprengkörper...
Hilf Schäuble! Damit er auch was findet... |
|
| Nach oben |
|
|
GreveN
JLI Master
Alter: 38
Anmeldedatum: 08.01.2004
Beiträge: 901
Wohnort: Sachsen - Dresden
Medaillen: Keine
|
| Verfasst am: 16.04.2006, 06:56 Titel: |
|
|
| Was IMHO aber wiederum auch nicht so toll ist, weil du damit im Grunde ein statisches Array hast, bzw. könntest du gleich eins anlegen mit der weitesgehend selben Funktionalität. Der Witz an den STL Vektoren ist ja grade, dass sie dynamische Arrays repräsentieren sollen. |
|
| Nach oben |
|
|
t10ottoo
Senior JLI'ler
Alter: 40
Anmeldedatum: 15.04.2004
Beiträge: 210
Wohnort: Berlin
Medaillen: Keine
|
| Verfasst am: 16.04.2006, 11:33 Titel: |
|
|
@Kampfhund:
Danke für den Link, steht ja auch noch so hilfreiches dabei.
@TLoP:
Wie GreveN schon sagte, wäre das dann denk ich auch ein statisches Array. Ok, man müsste zum Hinzufügen eines Elements immer eine Zählervariable mitlaufen lassen. Aber ich denke, die Funktion "pushback" macht intern auch nichts anderes.
Also Danke nochmals an alle für die sehr gute Hilfe.
Wünsche euch noch zwei restliche schöne Feiertage
Gruß
Otti
_________________
Meine kleine Projekte-Seite |
|
| Nach oben |
|
|
The Lord of Programming
Living Legend
Alter: 37
Anmeldedatum: 14.03.2003
Beiträge: 3122
Medaillen: Keine
|
| Verfasst am: 16.04.2006, 12:04 Titel: |
|
|
Ja...muss man eben genau abwägen.
Natürlich wäre es Blödsinn, am Anfang des Programms festzulegen, dass mein Vector 1.000.000 Elemente hat.
Aber wenn ich z.B. weiß, dass innerhalb der nächsten Frames voraussichtlich mindestens 25 Elemente neu dazukommen und vector::capacity() nicht dafür ausreicht, dann sollte ich mich mal schnell ans Reservieren machen.
Natürlich übernimmt das auch push_back() - aber wesentlich ineffizienter. Das wichtigste bei der Sache ist, dass du den Speicher sinnvoll und zum richtigen Zeitpunkt reservierst, dann hast du auch Chancen, die Geschwindigkeit zu optimieren. Sonst überlässt du dem Computer die (Reservierungs-)Arbeit und der wird hier mehr oder weniger das machen, worauf er Lust hat...
Und das muss ja nicht zwangsweise Geschwindigkeitsoptimierung sein
Wenn ich hier ein statisches (oder gar dynamisches) Array hätte, dann kostet das wesentlich mehr Verwaltungsaufwand und kann wohl deshalb auch fehleranfälliger sein.
_________________
www.visualgamesentertainment.net
Current projects: RDTDC(1), JLI-Vor-Projekt, Tetris(-Tutorial), JLI-Format
(1) Realtime Developer Testing and Debugging Console
Anschlag, Anleitung zum Atombombenbau, Sprengkörper...
Hilf Schäuble! Damit er auch was findet... |
|
| Nach oben |
|
|
|
|
Du kannst keine Beiträge in dieses Forum schreiben.
Du kannst auf Beiträge in diesem Forum nicht antworten.
Du kannst deine Beiträge in diesem Forum nicht bearbeiten.
Du kannst deine Beiträge in diesem Forum nicht löschen.
Du kannst an Umfragen in diesem Forum nicht mitmachen.
|
Powered by phpBB © 2001, 2005 phpBB Group
Deutsche Übersetzung von phpBB.de |
FAQ
Suchen
Mitgliederliste
Benutzergruppen
Medaillen
Registrieren
Profil
Einloggen, um private Nachrichten zu lesen
Login
