 |
JLI Spieleprogrammierung
|
| Vorheriges Thema anzeigen :: Nächstes Thema anzeigen |
| Autor |
Nachricht |
Dragon
Super JLI'ler
Alter: 38
Anmeldedatum: 24.05.2004
Beiträge: 340
Wohnort: Sachsen
Medaillen: Keine
|
 Verfasst am: 20.08.2005, 21:53 Titel: [C++/STL] Teil 1: Sequentielle Container |
 |
|
Einführung
In diesem Tutorial möchte ich Ihnen die Standard Template Libary (kurz STL) etwas näher bringen. Die STL wurde ursprünglich von HP entwickelt und gehört nun zum Sprachstandard von C++. Die Grundlage dieser Bibliothek sind Templates. Jeder sollte schon mal selber ein paar Template-Klassen geschrieben haben um die STL besser zu verstehen. Alle Klassendefinitionen stehen im Namensbereich std. Ich werde den Namen des Namensbereich immer vor die Klasse schreiben, wer will kann auch „using namespace std;“ vor die main schreiben und brauch das zusätzliche davor schreiben des Namensbreich nicht machen. Alle Headerdateien der STL besitzen kein h als Dateiendung. In diesem Tutorial geht er hauptsächlich um Containerklassen. Ich werde Ihnen zeigen wie man diese benutzt.
Es gibt eine Unterscheidung der Containerklassen. Es gibt einmal die Datencontainer und Container-Adapter die einen Container in sich kapseln (zB. stack). Desweiteren unterscheidet man die Datencontainer in Sequentielle Container und in Assoziative Container.
Folgende Containerklassen gibt es:
Datencontainer
Sequentielle Container
->vector
->deque
->list
Assoziative
->set / multiset
->map / mutlimap
Container-Adapter
->stack
->queue
Allgemeines
Es gibt einige Methoden die alle Container haben. Die Anzahl der Elemente in einem Container kann man mit der Methode size() abfragen.
| CPP: | | std::cout << "Anzahl der Elemente: " << container.size() << std::endl; |
Mit der Methode empty() bekommen wir einen booleschen Wert zurück der uns sagt, ob der Container leer ist oder nicht.
| CPP: | | std::cout << ( container.empty() ? "Container ist leer" : "Container hat Elemente") << std::endl; |
Soll der Container komplett geleert werden, dann nutzt wir die Methode clear()
Sequentielle Container
Die Liste (std::list)
Eine std::list ist eine Datencontainer der im Hintergrund eine doppelt verkettete Liste enthält. Jeder hat bestimmt schon mal eine solche Kette programmiert, wenn nicht, dann sollte es eine schöne Übung sein  . Um Instanzen dieser Containerklasse erzeugen zu können, müssen wir die Headerdatei <list> einfügen.
Als erstes legen wir eine std::list mit unserem Datentyp an. Es können auch Klassen genommen aber zur Demonstration nehme ich hier den Standarddatentyp int. Unsere Liste erhält den Namen "zahlen".
| CPP: | | std::list<int> zahlen; |
Für das hinzufügen von Datensätzen gibt es zwei Möglichkeiten. Wir können unsere Datensätze an den Anfang oder ans Ende setzen. Um einen Datensatz an den Anfang der Liste einzufügen nehmen wir die Methode "push_front()". Soll der Datensatz aber an das Ende eingefügt werden, so nehmen wir die Methode "push_back()". In diesem Beispiel fügen wir 3 Zahlen an das Ende und 3 Zahlen an den Anfang.
| CPP: | zahlen.push_back(911);
zahlen.push_back(4711);
zahlen.push_back(12345);
zahlen.push_front(-2000);
zahlen.push_front(2005);
zahlen.push_front(306);
|
Genau so, wie wir die Daten an den Anfang und ans Ende hinzugefügt haben, können wir sie auch wieder löschen. Dafür gibt es die Methoden pop_front() und pop_back();
| CPP: | zahlen.pop_front(); //löscht das erste Element in der Liste
zahlen.pop_back(); //löscht das letze Element in der Liste
|
Die Anzahl der Einträge der Liste bekommen wir mit der Methode size() heraus.
| CPP: | std::cout << "Anzahl der Einträge: " << zahlen.size() << std::endl;
|
Jetzt wollen wir aber auch wissen, was in der Liste drin steht. Um das erste und das letzte Element anzuzeigen gibt es die Methode "front()" bzw. "back()". Diese geben jeweils eine Referenz zurück.
| CPP: | std::cout << "Das erste Element: " << zahlen.front() << std::endl;
std::cout << "Das letzte Element: " << zahlen.back() << std::endl;
|
Um nun alle Elemente anzuzeigen, müssen wir einen Iterator für unsere Liste erzeugen.
| CPP: | // Iterator erzeugen
std::list<int>::iterator it;
// Die Liste durchgehen
for(it=zahlen.begin(); it!= zahlen.end(); it++)
{
std::cout << *it << std::endl;
}
// Es ist auch möglich den Wert des Iterators zu verändern
for(it=zahlen.begin(); it!= zahlen.end(); it++)
(*it) += 100; |
Das Löschen eines Elements ist eine komplizierte Angelegenheit. Ach Quatsch, das ist genau so leicht wie der Rest . Es gibt aber etwas zu beachten. Wenn wir ein Element löschen dann zeigt unser Iterator noch auf das gelöschte.
Zum Glück gibt es eine Methode zum löschen die uns dann einen neuen gültigen Iterator zurück gibt. Zum löschen oder besser gesagt zum entfernen eines Elements aus einem Container, wird uns die Methode "erase()" zur Verfügung gestellt.
In dem folgendem Beispiel werden alle Zahlen gelöscht die kleiner als 1000 sind. Um zu demonstrieren wie der Iterator reagiert wird der Wert vor dem löschen und nach dem löschen ausgegeben.
| CPP: | for(it = zahlen.begin(); it!= zahlen.end(); it++)
{
if(*it < 1000)
{
std::cout << "Vor dem loeschen: " << *it << std::endl;
it = zahlen.erase(it);
std::cout << "Nach dem loeschen: " << *it << std::endl;
}
}
|
Beispiel mit einer Klasse
Ich möchte Ihnen nun ein Beispiel zeigen, wie man eine Liste mit Objekten füllt und sie ausgibt. Hierzu nehme ich eine kleine Klasse die den Namen und das Geburtsjahr speichert. Mit dem Konstruktor oder der set()-Methode können die Werte geändert werden und mit den beiden get-Methoden bekommen wir die Werte zurück.
| CPP: | class Person
{
public:
Person(const char* n = NULL, int j = 1950) : gebjahr(j)
{
if(n) strcpy(name, n);
}
void set(const char* n, int j)
{
gebjahr = j;
strcpy(name, n);
}
int getGebJahr(){return gebjahr;};
const char* getName(){return name;};
private:
char name[128];
int gebjahr;[b]
};
void testprogramm()
{
// Eine Liste von Personen erzeugen
std::list<Person> personen;
// Das hinzufügen von Objekten über den Konstruktor aufruf
personen.push_back(Person("Sven Burow", 1986));
personen.push_back(Person("Max Mustermann", 1900));
// Wir können auch eine Instanz der Klasse erzeugen und diese dann
// hinzufügen. Dabei werden die Werte aber nur kopiert und in der
// Liste entsteht eine neue Instanz.
Person person1("Das Nek", 1960);
personen.push_back(person1);
Person person2;
person2.set("Bart Simpson", 1988);
personen.push_back(person2);
std::list<Person>::iterator it;
for(it = personen.begin(); it != personen.end(); ++it)
{
std::cout << "Name: " << (*it).getName() << " Geburtsjahr:" <<(*it).getGebJahr() << std::endl;
}
} |
[b]Vector
Ein dynamisches Feld kann zur Laufzeit seine Größe ändern. Wie ein normales Feld können die Datensätze über die eckigen Klammern angesprochen werden. Der std::vector hat eine Besonderheit. Die Datensätze liegen im Speicher direkt hintereinander. Zum Beispiel können wir ganz leicht alle Datensätze in eine Binärdatei schreiben ohne sie einzeln durchgehen zu müssen.
Als erstes müssen wir die Headerdatei <vector> einfügen.
Zur Demonstration werde ich hier auch wieder nur ein Vector mit Datensätzen vom Typ int anlegen. Es sollte aber kein Problem sein, dies auch für Klassen umzusetzen.
| CPP: | | std::vector<int> zahlen(10, 2005); |
Mit dieser Zeile legen wir ein Vector mit 10 Elementen an, die alle als Standardwert 2005 haben. Lassen wir den Konstruktoraufruf weg, so enthält unser Vektor keine Elemente. Wie ein normales Feld können wir nun die Werte verändern.
| CPP: | zahlen[0] = 911;
zahlen[1] = 4711;
zahlen[2] = 3141;
|
Wenn wir nur das letzte und das erste Element ausgeben wollen bieten uns die Methoden „front()“ und „back()“ an. „front()“ gibt eine Referenz auf das erste Element und „back()“ auf das Letzte zurück.
| CPP: | std::cout << "erste Element: " << zahlen.front() << std::endl;
std::cout << "letzes Element: " << zahlen.back() << std::endl;
|
Kommen wir nun zur Ausgabe aller Werte. Das einzigste was wir brauchen ist die Größe des Vektors. Diese bekommen wir über die Methode „size()“ heraus. In einer for-Schleife können wir alle Elemente durchgehen und ausgeben, so wie man es von einem Normalen Feld gewöhnt ist.
| CPP: | for(int i = 0; i < zahlen.size(); ++i)
{
std::cout << "zahlen[" << i << "]=" << zahlen[i] << std::endl;
}
|
Wenn sie dies nun ausführen werden Sie merken, das 10 Datensätze ausgegeben werden. Die ersten drei so wie wir sie geändert haben und die Letzten sieben mit den Standardwert 2005.
Für das Ändern der Größe können wir die Methode resize() benutzen. Wir übergeben ihr die neue Größe und wenn nötig den neuen Standardwert. Wenn wir das Feld verkleinern, dann werden alle Werte die wegfallen gelöscht. Wird das Feld vergrößert, so werden die neuen Werte mit dem Standardwert initialisiert. Doch was passiert, wenn kein Standardwert angegeben wurde? Die Werte der Felder sind nicht definiert.
Es gibt noch eine andere Möglichkeit Werte dem Vektor hinzuzufügen. Mit push_back() wird ein neuer Wert angehängt dann wird der Vektor automatisch mit vergrößert. Folgendes Beispiel sollte es gut zeigen.
| CPP: | void bsp1()
{
// Unser Vektor soll 10 Elemente mit den Wert 2005 bekommen
std::vector<int> zahlen(10, 2005);
// nun fügen wir noch 2 hinten dran
zahlen.push_back(1986);
zahlen.push_back(2002);
// Größe ausgeben
std::cout << "Groesse des Vektors: " << zahlen.size() << std::endl;
// Den kompletten Vektor ausgeben
for(int i=0; i<zahlen.size(); ++i)
{
std::cout << "zahlen[" << i << "]=" << zahlen[i] << std::endl;
}
}
|
Unser Vektor hat nun eine Größe von 12 Elementen und die letzen beiden Werte sind 1986 und 2002. Genau so leicht wie wir jetzt Werte hinzugefügt haben, können wir sie auch wieder entfernen. Mit pop_back() entfernen wir das letzte Element.
zahlen.pop_back();
Es ist auch das durchlaufen der Werte mit Iteratoren möglich. Zu erst muss ein Iterator erzeugt werden.
| CPP: | // Iterator erzeugen
std::vector<int>::iterator it;
// von Anfang bis Ende alles durchgehen ..
for(it = zahlen.begin(); it != zahlen.end(); it++)
{
// und ausgeben
std::cout << *it << std::endl;
} |
Deque
Ein Vektor hat einen Nachteil, er kann nur von hinten erweitert werden. Es gibt keine Möglichkeit an den Anfang einen Wert hinzuzufügen. Möchten Sie einen Vektor der genau diese Eigenschaft besitzt, dann müssen sie den Datencontainer deque nehmen. Es ist ein dynamisches Feld, das nach beiden Seiten wächst. Dieser bietet uns zwei zusätzliche Methoden. Einmal push_front() und pop_front(). Wie bei dem Vektor können wir mit dem []-Operator auf die Elemente zugreifen.
Das kleine Beispiel sollte alles erklären da es im Prinzip „nur“ eine Erweiterung des std::vector ist.
| CPP: | // Einen Datencontainer anlegen
std::deque<int> zahlen(5, 2005);
// das erste Element entfernen
zahlen.pop_front();
// Zahlen an das Ende und an den Anfang einfügen
zahlen.push_back(70999);
zahlen.push_front(1986);
// Alle Zahlen ausgeben
for(int i=0; i<zahlen.size(); i++)
{
std::cout << zahlen[i] << std::endl;
}
|
Iteratoren
Iteratoren sind Containerunabhänging. Sie werden benötigt um die Elemente eines Containers durchzugehen. Mit ihnen kommt man an die Werte des Containers. Ein Iterator wird bei jedem Container gleich erzeugt. Mit den Operator ++ kommen wir zum nächsten Element eines Containers. Um dann den Iterator durch einen Container wandern zu lassen müssen wir ihn als Startwert den Beginn des Containers geben. Dafür gibt es die Methode "begin()". Diese zeigt auf das erste Element. Um zu erfahren wann den z.B. die Liste zu Ende ist, gibt es die Methode "end()". Sie zeigt hinter das letzte Element. Ein Iterator kann man auf Gleichheit (==) oder Ungleichheit(!=) prüfen. Iteratoren lassen sich derefernzieren, d.h. mit dem *-Operator können wir auf den Wert zugreifen. Es gibt kein größer oder kleiner als, darum muss die Laufbedingung einer Schleife !=end() sein. Hier ein Beispiel mit einer Liste.
| CPP: | // Einen Container erzeugen, der Zahlen speichert
std::list<int> container;
// einen Iterator für unseren Container erzeugen
std::list<int>::iterator it;
//Alle werte im Container ausgeben
for(it = container.begin(); it != container.end(); ++it)
{
std::cout << *it << std::endl;
}
|
Wollen wir konstante Iteratoren, sprich wir wollen den Wert nicht verändern dürfen, so müssen wir einen const_iterator anlegen.
| CPP: | std::list<int>::const_iterator it;
for(it=container.begin(); it!= container.end(); it++)
{
std::cout << *it << std::endl;
(*it)++; // hier meldet der Compiler einen Fehler da Konstanten
// nicht geändert werden dürfen
}
|
Ich werde Ihnen nun zeige wie man eine Liste rückwärts durchgeht. Es mag vielleicht leicht klingen, aber es gibt etwas zu beachten. Da "end()" hinter das letzte Element zeigt können wir es nicht als Startwert für unseren Iterator nehmen. Des Rätsels Lösung sind die Methoden "rbegin()" und "rend()". Wir müssen aber einen neuen Iterator erzeugen der Rückwert unterstützt.
| CPP: | // einen Rückwärtsiterator
std::list<int>::reverse_iterator it;
// Wichtig! rbegin() und rend()
for(it = container.rbegin(); it != container.rend(); it++)
{
std::cout << *it << std::endl;
} |
Für Kritik und Verbesserungsvorschlägen bin ich sehr dankbar
svenburow(at)web.de
[Edit]
Rechtschtschreibfehler ausgebessert
AFE-GmdG
_________________
Nur wenn man ein Ziel sieht, kann man es auch treffen.
___________
Mein Leben, Freunde und die Spieleentwicklung
Zuletzt bearbeitet von Dragon am 27.08.2005, 19:19, insgesamt 2-mal bearbeitet |
|
| Nach oben |
|
 |
Jonathan_Klein
Living Legend
Alter: 37
Anmeldedatum: 17.02.2003
Beiträge: 3433
Wohnort: Siegerland
Medaillen: Keine
|
| Verfasst am: 20.08.2005, 22:01 Titel: |
|
|
es ist nicht sehr elegant, Iteratoren die ganze zeit zu benutzen aber erst am Ende zu beschreiben...
_________________
https://jonathank.de/games/ |
|
| Nach oben |
|
|
GreveN
JLI Master
Alter: 38
Anmeldedatum: 08.01.2004
Beiträge: 901
Wohnort: Sachsen - Dresden
Medaillen: Keine
|
| Verfasst am: 21.08.2005, 06:45 Titel: |
|
|
Ich finde insgesamt schon sehr gut gelungen. Kommen die Assoziativen Container und Adapter noch? Wäre wirklich schade wenn nicht...
Potentielle Kandidaten für einen möglichen 2. oder 3. Teil wären auch noch die fstream-Klassen, auto_ptr, strings, usw...
Gefällt mir bis jetzt wirklich gut, auch wenn ich Jonathan recht geben muss, es wäre vlt etwas eleganter, die Iteratoren nach dem ersten Container zu beschreiben.  |
|
| Nach oben |
|
|
AFE-GmdG
JLI MVP
Alter: 45
Anmeldedatum: 19.07.2002
Beiträge: 1374
Wohnort: Irgendwo im Universum...
Medaillen: Keine
|
| Verfasst am: 21.08.2005, 09:21 Titel: |
|
|
Sind ein paar Schreibfehler drin (Im Code kommt öfters dieser Block vor - Im Text ist an zwei oder drei Stellen ein echter Schreibfehler enthalten), ansonsten OK.
Schick wäre es noch zu Zeigen, wie man das ganze anstellt, wenn die Vectoren, Listen usw. selbst Pointer sind, also mit New angelegt wurden, dabei gibt es nämlich noch einiges zu Beachten, vorallem beim Durchlaufen und Löschen...
_________________
| CPP: | float o=0.075,h=1.5,T,r,O,l,I;int _,L=80,s=3200;main(){for(;s%L||
(h-=o,T= -2),s;4 -(r=O*O)<(l=I*I)|++ _==L&&write(1,(--s%L?_<(L)?--_
%6:6:7)+\"World! \\n\",1)&&(O=I=l=_=r=0,T+=o /2))O=I*2*O+h,I=l+T-r;} |
|
|
| Nach oben |
|
|
Dragon
Super JLI'ler
Alter: 38
Anmeldedatum: 24.05.2004
Beiträge: 340
Wohnort: Sachsen
Medaillen: Keine
|
| Verfasst am: 21.08.2005, 13:22 Titel: |
|
|
| GreveN hat Folgendes geschrieben: | Ich finde insgesamt schon sehr gut gelungen. Kommen die Assoziativen Container und Adapter noch? Wäre wirklich schade wenn nicht...
Potentielle Kandidaten für einen möglichen 2. oder 3. Teil wären auch noch die fstream-Klassen, auto_ptr, strings, usw...
Gefällt mir bis jetzt wirklich gut, auch wenn ich Jonathan recht geben muss, es wäre vlt etwas eleganter, die Iteratoren nach dem ersten Container zu beschreiben. |
die Assoziativen Container und Adapter kommen auch noch, vieleicht mach ich noch einen 3. Teil für die <algorithm>
_________________
Nur wenn man ein Ziel sieht, kann man es auch treffen.
___________
Mein Leben, Freunde und die Spieleentwicklung |
|
| Nach oben |
|
|
LeeDiGer
Super JLI'ler
Anmeldedatum: 31.08.2003
Beiträge: 366
Wohnort: Duisburg
Medaillen: Keine
|
| Verfasst am: 30.01.2008, 09:41 Titel: |
|
|
Ist es möglich einen normalen Iterator in einen Reverse-Iterator bzw. umgekehrt zu casten?
_________________
Kein Rückzug! Kein Aufgeben! |
|
| Nach oben |
|
|
GreveN
JLI Master
Alter: 38
Anmeldedatum: 08.01.2004
Beiträge: 901
Wohnort: Sachsen - Dresden
Medaillen: Keine
|
| Verfasst am: 30.01.2008, 11:08 Titel: |
|
|
| Mit einem C++-Standard-Cast? Nein, wie auch. Du kannst aber natürlich selber einen schreiben, bzw. z.B. den =-Operator überladen (eventuell bietet die STL sogar von Haus aus diese Funktionalität, hab ich gerade nicht im Kopf und keine Lust eine Referenz zu bemühen). |
|
| Nach oben |
|
|
Deviloper
Junior JLI'ler
Anmeldedatum: 31.05.2006
Beiträge: 77
Medaillen: Keine
|
| Verfasst am: 31.01.2008, 13:27 Titel: |
|
|
Kommt darauf an ... bei manchen Typen sollte es gehen:
| CPP: | // dein Iterator ... sagen wir mal das 10. Element
std::vector<T>::iterator it(data.begin() + 10);
std::vector<T>::reverse_iterator rit(data.rbegin() + (data.size() - (it - data.begin()))); |
Aber naja .... |
|
| Nach oben |
|
|
DirectXer
Dark JLI'ler
Anmeldedatum: 05.02.2005
Beiträge: 1201
Wohnort: Köln
Medaillen: Keine
|
| Verfasst am: 31.01.2008, 21:54 Titel: |
|
|
natürlich geht das, sogar ganz einfach. baut auf dem Grundkonzept der STL auf: | CPP: | // geht mit allen containern die mindst. bidirectional_iterators spezifizieren
std::list<int>::iterator it = ....;
// it -> rit, wird automatisch convertiert
std::list<int>::reverse_iterator rit( it );
// rit -> it, ebenfalls automatisch
std::list<int>::iterator it2 = rit.base(); |
Falls du das selber implementieren wills, musst du darauf achten, dass dabei immer folgendes gilt: | CPP: | | &*(reverse_iterator(i)) == &*(i - 1) |
Gruß DXer |
|
| Nach oben |
|
|
GreveN
JLI Master
Alter: 38
Anmeldedatum: 08.01.2004
Beiträge: 901
Wohnort: Sachsen - Dresden
Medaillen: Keine
|
| Verfasst am: 01.02.2008, 10:14 Titel: |
|
|
| Ja natürlich klappt das, aber das sind eben keine expliziten Casts im eigentlichen Sinne, á la "static_cast<reverse_iterator>(it)". |
|
| Nach oben |
|
|
DirectXer
Dark JLI'ler
Anmeldedatum: 05.02.2005
Beiträge: 1201
Wohnort: Köln
Medaillen: Keine
|
| Verfasst am: 01.02.2008, 11:57 Titel: |
|
|
| GreveN hat Folgendes geschrieben: | | Ja natürlich klappt das, aber das sind eben keine expliziten Casts im eigentlichen Sinne, á la "static_cast<reverse_iterator>(it)". |
Das hab ich auch nicht gesagt, aber es sollte auf jeden Fall das machen was LeeDiGer meinte. Ich hab mich aber auch eher auf Devilopers Post bezogen.
Allerdings müsste "static_cast<reverse_iterator>(it)" sogar funktionieren, da reverse_iterator einen Konstruktor mit iterator implementiert.
Gruß DXer |
|
| 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
