[X] Aufbau der STL - Teil 1: Container

michba

@Mr. B
Bin ja auch noch da...

CStoll

Mr. B schrieb:

scheiße, da kommt ja n haufen arbeit auf mich zu...

Wo du es ansprichst, eine kleine Bitte: In den Artikeln nutzt du aber [kor]-Tags Ich habe nämlich keine Lust, in einem mehrseitigen Text du vergleichen, welche drei Worte sich da geändert haben.

Mr. B

ja, und ich hab kein bock wegen jedem kleinen pisslkommafehler zwei tags zu setzen. hab so schon wenig zeit.
einigen wir uns einfach mal dadrauf, dass ihr keine fehler macht!

Mr. B

Artchi

CStoll! Warum willst du nach der Korrektur deinen Text vergleichen? Es reicht doch, wenn Mr.B ihn fertig korrigiert zurück gibt. Korrektur ist doch eh sozusagen der letzte Step vor Release.

estartu

Ich kann Euch beide ja verstehen...
CStoll geht es vermutlich wie mir: Ich will wissen, was ich falsch hatte, damit ich es irgendwann mal lerne.

Mir würde als Kompromiß einfallen, dass man sich den Unterschied mit BeyondCompare anguckt. Falls man das Drucken kann, würde ich Euch das dann auf Nachfrage vergleichen.

Mr.B: Schon gefragt?

Mr. B

estartu schrieb:

Ich kann Euch beide ja verstehen...
CStoll geht es vermutlich wie mir: Ich will wissen, was ich falsch hatte, damit ich es irgendwann mal lerne.

Mir würde als Kompromiß einfallen, dass man sich den Unterschied mit BeyondCompare anguckt. Falls man das Drucken kann, würde ich Euch das dann auf Nachfrage vergleichen.

Mr.B: Schon gefragt?

Ja, aber erst mal: Was ist denn "BeyondCompare"?

Mr. B schrieb:

Hallo Marc++us!

Wäre es möglich, dass man einen Knopf für das [kor]-Tag nur
für das Forum "Redaktion" machen könnte? Ich persönlich und
auch meine Korrekturleserkollegen finden es ein wenig Zeit
raubend, ständig [kor] eingeben zu müssen.

Falls es nicht mit zu viel Aufwand verbunden ist, wäre das
eine große Erleichterung der Arbeit für uns.

Mr. B

Marc++us schrieb:

Hi,

leider ist das nicht so einfach ein Template speziell für eine Rubrik anzupassen - das kor-Tag wäre dann überall sichtbar, was sicherlich nicht in unserem Interesse ist.

Denn die Templates beherrschen keine Fallunterscheidung, man muss dann im Code die Fallunterscheidung hinterlegen und im Template einen Platzhalter einführen, der nur bei Bedarf gefüllt wird.

Das führt zu Änderungen am Code, die nachher bei Updates nur schwierig aufrollbar sind, vor allem weil es sehr speziell wird - if $forum_id == XY then - das ist extrem unangenehm wartbar.

Ich denke mal darüber nach, verspreche aber lieber nichts.

Viele Grüße

Marcus

estartu

Mr. B schrieb:

Ja, aber erst mal: Was ist denn "BeyondCompare"?

Das ist ein extrem nützliches Programm, was Dateien vergleicht.
http://www.scootersoftware.com/

Man kann auch ganze Verzeichnisse vergleichen lassen und auch abgleichen, das ist für "was hab ich seit der letzten Sicherung geändert, dass es nicht mehr geht?" sehr praktisch.

Für Binärdateien ist es nicht so gut, aber für Quellcodes einfach genial.

estartu

So, da du den Artikel auf [R] stellen willst, hab ich es dann doch mal geschafft, ihn zu lesen.
Meine Fragen:
Was ist eine Allokator-Klasse?

Anmerkungen:
In Kapitel 3.3 hast du die Codetags vertauscht und etwas tiefer funktionieren sie gar nicht.
In 5.1, 5.2, 5.3 hast du je ein # vergessen.

Insgesamt hat mich der Artikel ziemlich erschlagen, aber für eine grobe Ahnung hat es gereicht.

CStoll

estartu schrieb:

Was ist eine Allokator-Klasse?

Das steht in Kapitel 2 als letzter Absatz - der Allokator wird verwendet, um Speicher anzufordern und freizugeben.

Anmerkungen:
In Kapitel 3.3 hast du die Codetags vertauscht und etwas tiefer funktionieren sie gar nicht.
In 5.1, 5.2, 5.3 hast du je ein # vergessen.

Kein Problem, das lässt sich korrigieren (warum mein Programmbeispiel in 3.3 nicht richtig angezeigt wird, bin ich nicht sicher.

CStoll

~**OK, hiermit geht Teil 1 offiziell in Korrekturmodus - ist also frei zum "Abschuss". Bitte achtet auch etwas auf Ausdrucks-Fehler (ich weiß selber, daß ich gelegentlich zu Wortwiederholungen neige) und unpassende Formatierungen.

mfG Carsten

PS: Wer noch inhaltliche Anmerkungen hat, darf sich auch gerne äußern.**~

Inhalt

Teil 1:

Vorbemerkungen
Container
sequentielle Container
assoziative Container
Container-Adapter
Zusammenfassung

1. Vorbemerkungen

Die Standard Template Library (STL) ist ein wesentlicher Bestandteil von ISO C++, der leider häufig unterschätzt oder falsch eingesetzt wird. [...]

Wie der Name schon andeutet, sind die einzelnen Komponenten der STL als Templates aufgebaut. Das hat den Vorteil, daß sie mit beliebigen Datentypen und Erweiterungen zusammenarbeiten können, ohne auf Vererbungshierarchien Rücksicht nehmen zu müssen. Der Anwender der STL muß lediglich darauf achten, daß die benötigten Operationen von seinen Typen unterstützt werden (z.B. benötigt der Schlüsseltyp einer set<> einen <-Operator oder eine äquivalente Vergleichfunktion).

Die STL kann grob in drei Hauptbestandteile untergliedert werden:

Container dienen zur Aufbewahrung und Verwaltung großer Datensammlungen
Iteratoren navigieren in Containern oder anderen Datenstrukturen
Algorithmen führen verschiedene Operationen auf Container-Elementen aus

Außerdem gibt es einige weitere Funktionen und Klassen in der Standard-Bibliothek von C++, die nicht direkt der STL zugeordnet werden.

2. Container

Container werden verwendet, um viele gleichartige Objekte gemeinsam unterzubringen und zu verwalten. Alle Containerklassen der STL haben einige gemeinsame Definitionen und Methoden, so daß sie teilweise gegeneinander ausgetauscht werden können. Die wichtigsten davon sind:

Typdefinitionen:

value_type - der Typ der gespeicherten Daten
iterator und const_iterator - der hauseigene Iteratortyp des Containers (für variable bzw. konstante Container)
size_type - ein Typ zur Angabe von Größenwerten (vorzeichenloser Integer)
allocator_type - der Typ der verwendeten Allokator-Klasse

Memberfunktionen

begin() - liefert einen Iterator auf das erste Element des Containers
end() - liefert einen Iterator hinter das letzte Element des Containers
rbegin() und rend() - liefern Reverse-Iteratoren auf das erste bzw hinter das letzte Element des Containers (rückwärts gerechnet)
size() - liefert die aktuelle Anzahl an Elementen
max_size() - liefert das maximale Fassungsvermögen des Containers
insert(pos,wert) - fügt ein Element an der Stelle 'pos' ein (bei assoziativen Containern ist 'pos' nur ein Hinweis, wo das Element eingefügt werden könnte)
assign(st,en) - weist dem Container den Inhalt des Bereiches [st,en[ zu.
c1.swap(c2) und swap(c1,c2) - vertauscht den Inhalt der Container c1 und c2.
clear() - löscht alle Elemente des Containers
erase(pos) und erase(st,en) - löscht das Element an der Stelle 'pos' bzw. alle Elemente im Bereich [st,en[

Zu den Template-Parametern, die ein Container bekommt, gehört neben dem Wertetyp auch immer ein Allokator-Typ. Dessen Methoden werden verwendet, wenn der Container neuen Speicher anfordern, initialisieren und freigeben will. Der Defaulttyp hierfür ist std::allocator<T> und verwendet die Operatoren new und delete, um den Speicher zu verwalten. Experten können die Speicherverwaltung jedoch auch anders implementieren, indem sie eine eigene Allokator-Klasse schreiben und dem Container mitgeben (z.B. kann eine Datenbank oder ein Garbage Collector verwendet oder zurückgegebene Speicherbereiche für schnelleren Zugriff zwischengelagert werden).

3. sequentielle Container

Sequentielle Container speichern ihre Elemente in der Reihenfolge, in der sie eingefügt wurden. Natürlich ist es auch möglich, diese Reihenfolge manuell anzupassen, indem man ein Element in der Mitte des Containers einfügt oder die vorhandenen Elemente direkt ändert.

3.1. vector

voller Name:

template<typename T,typename A=allocator<T> >
class std::vector;

Header:

include <vector>

Ein Vektor verwendet einen zusammenhängenden Speicherbereich, in dem er seine Elemente unterbringen kann. Dadurch kann er sehr schnell über den Index auf ein Element zugreifen und neue Elemente am Ende der Sequenz anhängen und löschen. Einfüge- und Lösch-Operationen in der Mitte oder gar am Anfang des Containers benötigen jedoch deutlich mehr Zeit, weil alle nachfolgenden Elemente entsprechend verschoben werden müssen.

Ein Beispiel zum Umgang mit Vektoren:

#include <vector>
#include <iostream>//für Ausgaben
using namespace std;

int main()
{
  vector<int> data;
  data.push_back(1);
  data.push_back(2);
  data.push_back(3);

  //Ausgabe aller Elemente:
  for(int i=0;i<data.size();++i)
    cout<<data<<" ";
  cout<<endl;

  data[1]=20;//direkter Elementzugriff
  data.front()=11;
  data.pop_back();

  data.resize(10,4);

  //nochmal Ausgabe:
  for(int i=0;i<data.size();++i)
    cout<<data[i]<<" ";

  return 0;
}

Ein Vektor reserviert sich in der Regel mehr Speicherplatz als für seine aktuelle Größe notwendig ist. Solange diese Kapazität noch nicht erreicht wird, können push_back()-Operationen in konstanter Zeit durchgeführt werden. Bei Überschreitung der Kapazität werden alle vorhandenen Elemente in einen neuen (entsprechend größeren) Speicherbereich umkopiert - dadurch werden erstens alle Referenzen, Zeiger und Iteratoren in den Vektor und zweitens kostet diese Operation recht viel Zeit. Deshalb ist es günstig, vor aufwendigen Operationen mit dem Vektor per reserve() genug Speicher anzufordern.

Achtung: Ein Vektor gibt die einmal reservierte Kapazität erst im Destruktor wieder frei.

Zusätzlich zu den generellen Methoden, seinen Inhalt zu manipulieren, bietet ein Vektor noch einige spezielle Zugriffsfunktionen:
*

** resize(size) und resize(size,val)
Ändert die Größe des Vektors auf 'size', indem am Ende Elemente entfernt oder angefügt werden. Neue Elemente werden mit dem Defaultwert des Elementtyps bzw. mit 'val' belegt.
** [i]vec**[pos]** und at(pos)
Liefern das Element mit dem Index 'pos' zurück. Der Unterschied zwischen beiden Methoden besteht in der Fehlerbehandlung - der Index-Operator liefert undefinierte Werte, wenn er mit einem Index außerhalb des Intervalls [0,vec.size()[ aufgerufen wird, die Methode at() wirft eine out_of_range Ausnahme, die vom Anwender aufgefangen werden muß.

push_back(val)
Hängt das Element 'val' an das Ende des Vektors an.
front() und back()
Liefern den Wert des ersten bzw. letzten Elements im Vektor.
pop_back()
Löscht das letzte Element aus dem Vektor.
capacity()
Liefert die aktuelle Kapazität des Vektors zurück. Dieser Wert gibt an, wieviele Elemente er aufnehmen könnte, ohne neuen Speicher anfordern zu müssen.
reserve(size)
Reserviert genug Speicherplatz für mindestens 'size' Elemente. Der neu angelegte Speicherplatz wird nicht initialisiert.

Die Spezialisierung vector<bool> wurde zur platzsparenden Speicherung von 1-Bit-Werten vorgesehen und bietet ein paar Zusatzmethoden zur Manipulation einzelner Bits:

flip()
Invertiert alle Elemente des Vektors (aus true wird false und umgekehrt)
vec[pos].flip() bzw. at(pos).flip
Invertiert das Element 'pos' des Vektors

3.2. deque

voller Name:

template<typename T,typename A=allocator<T> >
class std::deque;

Header:

#include <deque>

Eine Deque (Double Ended QUEue) hat insofern Ähnlichkeit mit dem Vektor, daß sie ihren Inhalt auch in zusammenhängendem Speicher organisiert. Ind der Regel wird jedoch nicht ein einzelner Speicherblock dafür verwendet, sondern mehrere kleinere Blöcke, die beim Durchlaufen der Deque virtuell zusammengefügt werden. Ihr Vorteil ist, daß sie sowohl am Ende als auch am Anfang problemlos erweitert werden kann. Änderungen in der Mitte des Containers sind wie beim vector langsam und sollten besser vermieden werden.

Wenn eine Deque ihre reservierte Kapazität ausgeschöpft hat, reserviert sie einen neuen Speicherbereich, der vor bzw. hinter den vorhandenen Speicherblöcken in die Kontrollstruktur eingefügt wird. Im Gegensatz zum Vektor werden die einzelnen Speicherblöcke auch wieder freigegeben, wenn sie nicht mehr benötigt werden (wann das geschieht, ist normalerweise von der Implementation abhängig).

Eine Deque bietet - mit Ausnahme von capacity() und reserve() - die selben Methoden wie ein Vektor, zusätzlich ermöglicht sie:

push_front(val)
Hängt das Element 'val' an den Anfang der Schlange an
pop_front()
Löscht das erste Element der Schlange

3.3. list

voller Name:

template<typename T,typename A=allocator<T> >
class std::list;

Header:

#include <list>

Im Gegensatz zu Vektoren wird der Inhalt einer list in Form einer doppelt verketteten Liste gespeichert. Auf diese Weise ist es sehr effizient, Werte an beliebiger Stelle einzufügen und wieder zu entfernen. Im Gegenzug ist es sehr langwierig, ein bestimmtes Element anhand seines Index wiederzufinden.

Eine List bietet keinen direkten Elementzugriff über den Index-Operator bzw. at(), aber unterstützt die meisten anderen Funktionen, die auch von Vektoren und Deques zur Verfügung gestellt werden:

resize()
push_back(), pop_back() und back()
push_front(), pop_front() und front()
splice(pos,list), splice(pos,list,spos) bzw. splice(pos,list,sbeg,send)
Hängt einzelne Elemente aus 'list' aus und fügt sie vor dem Iterator 'pos' in die Liste ein. Je nach Version wird die komplette Liste 'list', das einzelne Element 'spos' bzw. der Bereich [sbeg,send[ umgehängt.
unique(), sort(), merge(list) und reverse()
Diese Methoden entsprechen den gleichnamigen Algorithmen, können jedoch auf der Listenstruktur effizienter umgesetzt werden als mit den Iterator-basierten Algorithmen (z.B. braucht reverse() nur alle Vorgänger- und Nachfolger-Zeiger zu vertauschen anstatt Elemente umzukopieren).

Ein Beispiel zur Anwendung einer Liste:

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

int main()
{
  list<int> data;
  //Liste füllen
  for(int i=1;i<5;++i) data.push_back(i);
  data.push_front(4711);

  //Ausgabe (nicht über Index möglich, deshalb benötigt man Listen-Iteratoren)
  for(list<int>::iterator pos=data.begin();pos!=data.end();++pos)
    cout<<*pos<<" ";
  cout<<endl;

  list<int>::iterator pos1=data.begin();
  ++pos1;//Iterator auf 2. Element
  data.insert(pos1,0x0815);

  //nochmal Ausgabe:
  for(list<int>::iterator pos=data.begin();pos!=data.end();++pos)
    cout<<*pos<<" ";
  cout<<endl;
}

3.4. string

voller Name:

template<typename C,typename Tr=char_traits<T>,typename A=allocator<C> >
class std::basic_string;

typedef basic_string<char> string;
typedef basic_string<wchar_t> wstring;

Header:

#include <string>

Achtung: Der Header <string.h> exisitiert ebenfalls, dieser enhält jedoch die char*-Verarbeitungsfunktionen der C-Standardbibliothek.

Strings sind zwar keine "offiziellen" STL-Container, aber sie bieten genug Unterstützung an, um analog zu den anderen Containern verwendet zu werden. Ihre Hauptverwendung ist die Verwaltung von Zeichenketten, deshalb bieten sie auch Operationen zur Verkettung und zur Zusammenarbeit mit char*-Feldern an.

Mit Strings werde ich mich ausführlicher in einem späteren Artikel beschäftigen.

4. assoziative Container

Assoziative Container sortieren ihre Elemente intern nach ihrer Größe. Dadurch geht es deutlich schneller, einen bestimmten Wert im Container wiederzufinden, allerdings spielt es für die Reihenfolge in der Regel keine Rolle, welches Element zuerst eingefügt wurde.

Im Allgemeinen nutzen alle assoziativen Container die gleiche Grundstruktur (ein balancierter Binärbaum), um ihren Inhalt zu speichern, sie unterscheiden sich lediglich im Typ der eingetragenen Elemente und der Art, wie Duplikate verwaltet werden.

Alle assoziativen Container bieten einige zusätzliche Methoden, um bestimmte Elemente suchen zu können (diese Methoden entsprechen den gleichnamigen Algorithmen, können jedoch in der Baumstruktur effizienter arbeiten als auf einem linear angeordneten Iterator-Bereich):

count(val)
Zählt, wie oft das Element (für Set's) bzw. der Schlüsselwert (für Map's) 'val' im Container enthalten ist
find(val)
Liefert einen Iterator auf ein Containerelement mit dem (Schlüssel-)Wert 'val' oder end(), wenn es nicht existiert
erase(val)
Löscht alle Elemente mit dem (Schlüssel-)Wert 'val' aus dem Container
lower_bound(val), upper_bound(val) und equal_range(val)
Liefern die erste, letzte bzw. beide Position im Container (als pair), an der der (Schlüssel-)Wert 'val' in den Container eingefügt werden kann
key_comp() und value_comp()
Liefern den Functor, mit dem die Schlüsselwerte bzw. Elemente des Containers sortiert werden (bei Set's sind beide identisch, bei Map's vergleicht value_comp() die ersten Elemente eines pair mit Hilfe von key_comp())

Jeder assoziative Container besitzt einen "eingebauten" Vergleichstyp, mit dessen Hilfe die einzelnen Elemente verglichen werden. Dieser wird bei der Definition des Containers als zweiter bzw. dritter Template-Parameter übergeben. Der vorgegebene Typ "less<T>" verwendet < als Vergleichskriterium, sortiert die Elemente also aufsteigend. Aber jeder Funktortyp, der zwei Schlüsselwerte als Parameter akzeptiert und einen bool zurückliefert, kann theoretisch als Vergleichskriterium eingesetzt werden.

Die Vergleichsrelation des Containers wird auch verwendet, um zwei Elemente auf Gleichheit zu testen: x==y gdw !(x<y)&&!(y<x).

Wichtig für die Anwendung von set's und map's ist, daß der verwendete Vergleichstyp eine "strict weak ordering" ~wie kann man das auf Deutsch ausdrücken?~ bildet, andernfalls kommt es zur Laufzeit des Programmes zu undefiniertem Verhalten - und kein Compiler kann kontrollieren, ob eine beliebig gegebene Relation diese Anforderungen erfüllt.

4.1. set und multiset

voller Name:

template<typename K,typename P=less<K>,typename A=allocator<K> >
class std::set;
template<typename K,typename P=less<K>,typename A=allocator<K> >
class std::multiset;

Header:

#include <set>

Set's und Multiset's speichern einzelne Schlüsselwerte. Ihr Unterschied besteht darin, daß eine Set jeden Wert maximal einmal enthält, während eine Multiset auch Duplikate enthalten kann.

map und multimap

voller Name:

template<typename K,typename V,typename P=less<K>,typename A=allocator<pair<const K,V> > >
class std::map;
template<typename K,typename V,typename P=less<K>,typename A=allocator<pair<const K,V> > >
class std::multimap;

Map's und Multimap's speichern Paare aus einem Schlüssel und einem zugeordneten Wert. Auch hier besteht der Unterschied darin, daß eine Map eindeutige Schlüssel enthält, während die Schlüssel in der Multimap mehrfach vorkommen können - sogar mit unterschiedlichen zugeordneten Werten. Die Elemente in einer (Multi-)Map sind Paare aus konstantem Schlüssel und Wert, wodurch die insert-Operationen etwas komplizierter geschrieben werden müssen:

map<string,int> id_liste;

//(1) - exakter Typ:
id_liste.insert(map<string,int>::value_type("Carsten",4711);

//(2) - pair:
id_liste.insert(pair<string,int>("CStoll",0x0815);

//(3) - make_pair:
id_liste.insert(make_pair("Admin",1);

(im ersten Fall wird der Typ exakt so übergeben, wie die map ihn benötigt, im zweiten und dritten Fall ist eine implizite Typumwandlung von pair<string,int> bzw. pair<const char*,int> nach pair<const string,int> notwendig)

Eine Map bietet als besonderes Extra direkten Elementzugriff über den Index-Operator m[ind]. Im Gegensatz zu einem Array oder Vektor wird hierbei der Wert zurückgegeben, der zum Schlüssel 'ind' zugeordnet wurde. Wenn dieser Schlüssel nicht in der Map existiert, wird er angelegt und mit einem Defaultwert verknüpft.
(die Multimap bietet dieses Feature nicht, da sie keine eindeutige Zuordnung zwischen einem Schlüssel und seinem Wert herstellen kann)

5. Container Adapter

Diese Adapter verwenden die Standard-Container, um darauf spezielle Datenstrukturen aufzubauen. Sie bieten ein halbwegs einheitliches Interface zur Verwendung an, unterscheiden sich jedoch in der Definition, welches Element das "erste" ist.

push(val)
fügt das Element "val" in den unterliegenden Container ein
top()
liefert das "erste" Element des Containers
pop()
löscht das "erste" Element des Containers (der Wert muß vorher verarbeitet werden)

Diese Methoden verwenden keinerlei Fehlerkontrolle - wenn versucht wird, das erste Element eines leeren Stacks zu lesen, ergibt sich deshalb undefiniertes Verhalten.

Alle Adapter erwarten, daß der verwendete Containertyp die Operationen bereitstellt, die sie verwenden wollen, andernfalls weigert sich der Compiler, sie zu erzeugen.

5.1. stack

voller Name:

template<typename T,typename C=deque<T> >
class std::stack;

Header:

#include <stack>

Ein Stack nutzt die Memberfunktionen push_back(), back() und pop_back() des unterliegenden Containertyps, um einen LIFO-Speicher zu realisieren - die Elemente werden in der umgekehrten Reihenfolge herausgegeben, in der sie eingefügt wurden.

Als Grundlage für den Stack kann theoretisch jeder sequentielle Container eingesetzt werden - der Standardtyp ist die deque, weil sie im Gegensatz zum Vektor auch wieder Speicher freigeben kann.

5.2. queue

voller Name:

template<typename T,typename C=deque<T> >
class std::queue;

Header:

#include <queue>

Eine Queue (oder Warteschlange) nutzt die Memberfunktionen push_back(), front(), und pop_front() des unterliegenden Conntainertyps, um einen FIFO-Speicher zu realisieren - die Elemente werden in der selben Reihenfolge herausgegeben, in der sie eingefügt wurden.

Als Grundlage für die Warteschlange können entweder deque's oder Listen verwendet werden, da sie als einzige Standard-Container eine pop_front()-Methode definieren.

5.3. priority_queue

voller Name:

template<typename T,typename C=vector<T>,typename P=less<typename C::value_type> >
class std::priority_queue;

Header:

#include <queue>

Eine Priority-Queue implementiert eine Prioritäts-Warteschlange auf dem unterliegenden Containertyp - die Elemente werden entsprechend ihrer Größe umgeordnet, so daß jeweils das größte aus der Warteschlange entnommen werden kann. Der Adapter nutzt die Methoden push_back(), front() und pop_back() sowie die Heap-Algorithmen make_heap(), push_heap() und pop_heap(), um seine Elemente zu organisieren.
Das Prädikat P dient dabei zur Feststellung, welches Element größer ist. Genau wie bei den assoziativen Containern muß die verwendete Vergleichsfunktion eine Ordnungsrelation definieren, sonst funktioniert die Priority-Queue nicht richtig.

Als Grundlage für eine Prioritäts-Schlange können Vektoren, Deque's oder Strings verwendet werden - Listen bieten keine Random-Access-Iteratoren und können deshalb nicht mit den Heap-Algorithmen genutzt werden.

6. Zusammenfassung

Es gibt keine "perfekte" Containerklasse für alle Anwendungsbereiche. Deshalb ist es von Vorteil, wenn man die unterschiedlichen Container der STL kennt und auswählen kann, welcher gerade am günstigsten geeignet ist. Dabei ist es auch mit geringem Aufwand möglich, die Container gegeneinander auszutauschen, wenn man zum Beispiel während der Entwicklung feststellt, daß eine deque<> doch bessere Eigenschaften hat als eine list<>.

Container         Vektor          Deque           Liste           Set             Multiset        Map             Multimap
----------------------------------------------------------------------------------------------------------------------------------

Struktur          dynamisches     Array von       verkettete      Binärbaum       Binärbaum       Binärbaum       Binärbaum
                  Array           Arrays          Liste

Elemente          Wert            Wert            Wert            Wert            Wert            Schlüssel+Wert  Schlüssel+Wert

Duplikate         Ja              Ja              Ja              Nein            Ja              Wert            Ja

Direktzugriff     Ja              Ja              Nein            Nein            Nein            über Schlüssel  Nein

Iteratortyp       Random Access   Random Access   Bidirektional   Bidirektional   Bidirektional   Bidirektional   Bidirektional
                                                                  konstant        konstant        Schl. konstant  Schl. konstant
Suche             langsam         langsam         sehr langsam    schnell         schnell         schnell (Schl.) schnell (Schl.)

Einf./Entf.       Ende            Anfang, Ende    überall

invalidiert       Reallocation    immer           nie             nie             nie             nie             nie
Iteratoren etc.

Speicherfreigabe  nie             manchmal        immer           immer           immer           immer           immer

Reservierung      Ja              Nein

Transaktions-     push/pop        push/pop an     alle außer      alle außer      alle außer      alle außer      alle außer
sicher            am Ende         Anfang, Ende    sort            multi-insert    multi-insert    multi-insert    multi-insert

Ausblick

Container sind ein hilfreiches Werkzeug zur Datenorganisation. Aber ihre volle Stärke entwickeln sie erst in Zusammenarbeit mit den Iteratoren und Algortihmen - deshalb werde ich diese Bestandteile der STL im zweiten Teil der Serie ausführlicher behandeln.

michba

______________________________________________________________________________________

So, bin das ganze mal durchgegangen; es waren zum Glück nur wenige Fehler drin.
Was du aber beachten solltest:
- "daß" und "muß" wird jetzt "dass" und "muss" geschrieben
- in z.b. "deque's" ist das Apostroph fehl am Platz, einfach nur "deques"
- nach den Abschnittsnummern kommt kein Punkt (also z.b. 1.1 statt 1.1.)

Im 4. Abschnitt (assoziative Container) hast du 4.1 (set und multiset), aber nicht 4.2, ich denke, das hast du einfach bei "map und multimap" vergessen. Wenn es anders gedacht ist, kannst du es ja wieder rückgängig machen.

Noch was zum Inhalt/Stil:

Abschnitt 2 schrieb:

rbegin() und rend() - liefern Reverse-Iteratoren auf das erste bzw hinter das letzte Element des Containers (rückwärts gerechnet)

Das ist imho für einen Neuling etwas verwirrend, denn ich denke nicht, dass er schon weiß, was ein Reverse-Iterator ist.
Wie wär's wenn du die zwei einzeln behandelst (wie bei begin und end auch) und für rbegin sowas wie "liefert einen Reverse-Iterator hinter das letzte Element des Containers, d.h. ein Inkrementieren dieses Iterators bewirkt einen Schritt in Richtung Anfang des Containers" und für rend dann einfach "liefert analog zu rbegin() einen Reverse-Iterator auf das erste Element des Containers". Ist natürlich nur ein Vorschlag.

Für "strict weak ordering" fällt mir auch kein deutsches Wort ein, aber du könntest es ja mit dem Verhalten von "Kleiner als" umschreiben, und/oder vielleicht noch einen Link auf http://en.wikipedia.org/wiki/Strict_weak_ordering setzen.

PS: auch von mir noch ein , ist wirklich ein toller Artikel geworden.

PPS: Ist bei euch in dem Beispiel in 3.1 auch die zweite Hälfte des Codes kursiv?
Anscheinend liegt das an dem data[ i] in der Schleife, ich habe das jetzt mit data[j] ersetzt.
Eigentlich war das doch der Grund, warum man die Formatierungstags nicht in Code-Listings aktivieren wollte?!

______________________________________________________________________________________

Inhalt

Teil 1:

Vorbemerkungen
Container
sequentielle Container
assoziative Container
Container-Adapter
Zusammenfassung

1 Vorbemerkungen

Die Standard Template Library (STL) ist ein wesentlicher Bestandteil von ISO C++, der leider häufig unterschätzt oder falsch eingesetzt wird. [...]

Wie der Name schon andeutet, sind die einzelnen Komponenten der STL als Templates aufgebaut. Das hat den Vorteil, dass sie mit beliebigen Datentypen und Erweiterungen zusammenarbeiten können, ohne auf Vererbungshierarchien Rücksicht nehmen zu müssen. Der Anwender der STL muss lediglich darauf achten, dass die benötigten Operationen von seinen Typen unterstützt werden (z.B. benötigt der Schlüsseltyp einer set<> einen <-Operator oder eine äquivalente Vergleichfunktion).

Die STL kann grob in drei Hauptbestandteile untergliedert werden:

Container dienen zur Aufbewahrung und Verwaltung großer Datensammlungen
Iteratoren navigieren in Containern oder anderen Datenstrukturen
Algorithmen führen verschiedene Operationen auf Container-Elementen aus

Außerdem gibt es einige weitere Funktionen und Klassen in der Standard-Bibliothek von C++, die nicht direkt der STL zugeordnet werden.

2 Container

Container werden verwendet, um viele gleichartige Objekte gemeinsam unterzubringen und zu verwalten. Alle Containerklassen der STL haben einige gemeinsame Definitionen und Methoden, so dass sie teilweise gegeneinander ausgetauscht werden können. Die wichtigsten davon sind:

Typdefinitionen:

value_type - der Typ der gespeicherten Daten
iterator und const_iterator - der hauseigene Iteratortyp des Containers (für variable bzw. konstante Container)
size_type - ein Typ zur Angabe von Größenwerten (vorzeichenloser Integer)
allocator_type - der Typ der verwendeten Allokator-Klasse

Memberfunktionen

begin() - liefert einen Iterator auf das erste Element des Containers
end() - liefert einen Iterator hinter das letzte Element des Containers
rbegin() und rend() - liefern Reverse-Iteratoren auf das erste bzw. hinter das letzte Element des Containers (rückwärts gerechnet)
size() - liefert die aktuelle Anzahl an Elementen
max_size() - liefert das maximale Fassungsvermögen des Containers
insert(pos,wert) - fügt ein Element an der Stelle 'pos' ein (bei assoziativen Containern ist 'pos' nur ein Hinweis, wo das Element eingefügt werden könnte)
assign(st,en) - weist dem Container den Inhalt des Bereiches [st,en[ zu.
c1.swap(c2) und swap(c1,c2) - vertauscht den Inhalt der Container c1 und c2.
clear() - löscht alle Elemente des Containers
erase(pos) und erase(st,en) - löscht das Element an der Stelle 'pos' bzw. alle Elemente im Bereich [st,en[

Zu den Template-Parametern, die ein Container bekommt, gehört neben dem Wertetyp auch immer ein Allokator-Typ. Dessen Methoden werden verwendet, wenn der Container neuen Speicher anfordern, initialisieren und freigeben will. Der Defaulttyp hierfür ist std::allocator<T> und verwendet die Operatoren new und delete, um den Speicher zu verwalten. Experten können die Speicherverwaltung jedoch auch anders implementieren, indem sie eine eigene Allokator-Klasse schreiben und dem Container mitgeben (z.B. kann eine Datenbank oder ein Garbage Collector verwendet oder zurückgegebene Speicherbereiche für schnelleren Zugriff zwischengelagert werden).

3 sequentielle Container

Sequentielle Container speichern ihre Elemente in der Reihenfolge, in der sie eingefügt wurden. Natürlich ist es auch möglich, diese Reihenfolge manuell anzupassen, indem man ein Element in der Mitte des Containers einfügt oder die vorhandenen Elemente direkt ändert.

3.1 vector

voller Name:

template<typename T,typename A=allocator<T> >
class std::vector;

Header:

include <vector>

Ein Vektor verwendet einen zusammenhängenden Speicherbereich, in dem er seine Elemente unterbringen kann. Dadurch kann er sehr schnell über den Index auf ein Element zugreifen und neue Elemente am Ende der Sequenz anhängen und löschen. Einfüge- und Lösch-Operationen in der Mitte oder gar am Anfang des Containers benötigen jedoch deutlich mehr Zeit, weil alle nachfolgenden Elemente entsprechend verschoben werden müssen.

Ein Beispiel zum Umgang mit Vektoren:

#include <vector>
#include <iostream>//für Ausgaben
using namespace std;

int main()
{
  vector<int> data;
  data.push_back(1);
  data.push_back(2);
  data.push_back(3);

  //Ausgabe aller Elemente:
  for(int j=0;j<data.size();++j)
    cout<<data[j]<<" ";
  cout<<endl;

  data[1]=20;//direkter Elementzugriff
  data.front()=11;
  data.pop_back();

  data.resize(10,4);

  //noch mal Ausgabe:
  for(int j=0;j<data.size();++j)
    cout<<data[j]<<" ";

  return 0;
}

Ein Vektor reserviert sich in der Regel mehr Speicherplatz als für seine aktuelle Größe notwendig ist. Solange diese Kapazität noch nicht erreicht wird, können push_back()-Operationen in konstanter Zeit durchgeführt werden. Bei Überschreitung der Kapazität werden alle vorhandenen Elemente in einen neuen (entsprechend größeren) Speicherbereich umkopiert - dadurch werden erstens alle Referenzen, Zeiger und Iteratoren in den Vektor und zweitens kostet diese Operation recht viel Zeit. Deshalb ist es günstig, vor aufwendigen Operationen mit dem Vektor per reserve() genug Speicher anzufordern.

Achtung: Ein Vektor gibt die einmal reservierte Kapazität erst im Destruktor wieder frei.

Zusätzlich zu den generellen Methoden, seinen Inhalt zu manipulieren, bietet ein Vektor noch einige spezielle Zugriffsfunktionen:

resize(size) und resize(size,val)
Ändert die Größe des Vektors auf 'size', indem am Ende Elemente entfernt oder angefügt werden. Neue Elemente werden mit dem Defaultwert des Elementtyps bzw. mit 'val' belegt.
vec[pos] und at(pos)
Liefern das Element mit dem Index 'pos' zurück. Der Unterschied zwischen beiden Methoden besteht in der Fehlerbehandlung - der Index-Operator liefert undefinierte Werte, wenn er mit einem Index außerhalb des Intervalls [0,vec.size()[ aufgerufen wird, die Methode at() wirft eine out_of_range Ausnahme, die vom Anwender aufgefangen werden muss.
push_back(val)
Hängt das Element 'val' an das Ende des Vektors an.
front() und back()
Liefern den Wert des ersten bzw. letzten Elements im Vektor.
pop_back()
Löscht das letzte Element aus dem Vektor.
capacity()
Liefert die aktuelle Kapazität des Vektors zurück. Dieser Wert gibt an, wie viele Elemente er aufnehmen könnte, ohne neuen Speicher anfordern zu müssen.
reserve(size)
Reserviert genug Speicherplatz für mindestens 'size' Elemente. Der neu angelegte Speicherplatz wird nicht initialisiert.

Die Spezialisierung vector<bool> wurde zur Platz sparenden Speicherung von 1-Bit-Werten vorgesehen und bietet ein paar Zusatzmethoden zur Manipulation einzelner Bits:

flip()
Invertiert alle Elemente des Vektors (aus true wird false und umgekehrt)
vec[pos].flip() bzw. at(pos).flip
Invertiert das Element 'pos' des Vektors

3.2 deque

voller Name:

template<typename T,typename A=allocator<T> >
class std::deque;

Header:

#include <deque>

Eine Deque (Double Ended QUEue) hat insofern Ähnlichkeit mit dem Vektor, dass sie ihren Inhalt auch in zusammenhängendem Speicher organisiert. In der Regel wird jedoch nicht ein einzelner Speicherblock dafür verwendet, sondern mehrere kleinere Blöcke, die beim Durchlaufen der Deque virtuell zusammengefügt werden. Ihr Vorteil ist, dass sie sowohl am Ende als auch am Anfang problemlos erweitert werden kann. Änderungen in der Mitte des Containers sind wie beim vector langsam und sollten besser vermieden werden.

Wenn eine Deque ihre reservierte Kapazität ausgeschöpft hat, reserviert sie einen neuen Speicherbereich, der vor bzw. hinter den vorhandenen Speicherblöcken in die Kontrollstruktur eingefügt wird. Im Gegensatz zum Vektor werden die einzelnen Speicherblöcke auch wieder freigegeben, wenn sie nicht mehr benötigt werden (wann das geschieht, ist normalerweise von der Implementation abhängig).

Eine Deque bietet - mit Ausnahme von capacity() und reserve() - die gleichen Methoden wie ein Vektor, zusätzlich ermöglicht sie:

push_front(val)
Hängt das Element 'val' an den Anfang der Schlange an
pop_front()
Löscht das erste Element der Schlange

3.3 list

voller Name:

template<typename T,typename A=allocator<T> >
class std::list;

Header:

#include <list>

Im Gegensatz zu Vektoren wird der Inhalt einer list in Form einer doppelt verketteten Liste gespeichert. Auf diese Weise ist es sehr effizient, Werte an beliebiger Stelle einzufügen und wieder zu entfernen. Im Gegenzug ist es sehr langwierig, ein bestimmtes Element anhand seines Index wiederzufinden.

Eine List bietet keinen direkten Elementzugriff über den Index-Operator bzw. at(), aber unterstützt die meisten anderen Funktionen, die auch von Vektoren und Deques zur Verfügung gestellt werden:

resize()
push_back(), pop_back() und back()
push_front(), pop_front() und front()
splice(pos,list), splice(pos,list,spos) bzw. splice(pos,list,sbeg,send)
Hängt einzelne Elemente aus 'list' aus und fügt sie vor dem Iterator 'pos' in die Liste ein. Je nach Version wird die komplette Liste 'list', das einzelne Element 'spos' bzw. der Bereich [sbeg,send[ umgehängt.
unique(), sort(), merge(list) und reverse()
Diese Methoden entsprechen den gleichnamigen Algorithmen, können jedoch auf der Listenstruktur effizienter umgesetzt werden als mit den Iterator-basierten Algorithmen (z.B. braucht reverse() nur alle Vorgänger- und Nachfolger-Zeiger zu vertauschen anstatt Elemente umzukopieren).

Ein Beispiel zur Anwendung einer Liste:

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

int main()
{
  list<int> data;
  //Liste füllen
  for(int i=1;i<5;++i) data.push_back(i);
  data.push_front(4711);

  //Ausgabe (nicht über Index möglich, deshalb benötigt man Listen-Iteratoren)
  for(list<int>::iterator pos=data.begin();pos!=data.end();++pos)
    cout<<*pos<<" ";
  cout<<endl;

  list<int>::iterator pos1=data.begin();
  ++pos1;//Iterator auf 2. Element
  data.insert(pos1,0x0815);

  //noch mal Ausgabe:
  for(list<int>::iterator pos=data.begin();pos!=data.end();++pos)
    cout<<*pos<<" ";
  cout<<endl;
}

3.4 string

voller Name:

template<typename C,typename Tr=char_traits<T>,typename A=allocator<C> >
class std::basic_string;

typedef basic_string<char> string;
typedef basic_string<wchar_t> wstring;

Header:

#include <string>

Achtung: Der Header <string.h> existiert ebenfalls, dieser enthält jedoch die char*-Verarbeitungsfunktionen der C-Standardbibliothek.

Strings sind zwar keine "offiziellen" STL-Container, aber sie bieten genug Unterstützung an, um analog zu den anderen Containern verwendet zu werden. Ihre Hauptverwendung ist die Verwaltung von Zeichenketten, deshalb bieten sie auch Operationen zur Verkettung und zur Zusammenarbeit mit char*-Feldern an.

Mit Strings werde ich mich ausführlicher in einem späteren Artikel beschäftigen.

4 assoziative Container

Assoziative Container sortieren ihre Elemente intern nach ihrer Größe. Dadurch geht es deutlich schneller, einen bestimmten Wert im Container wiederzufinden, allerdings spielt es für die Reihenfolge in der Regel keine Rolle, welches Element zuerst eingefügt wurde.

Im Allgemeinen nutzen alle assoziativen Container die gleiche Grundstruktur (ein balancierter Binärbaum), um ihren Inhalt zu speichern, sie unterscheiden sich lediglich im Typ der eingetragenen Elemente und der Art, wie Duplikate verwaltet werden.

Alle assoziativen Container bieten einige zusätzliche Methoden, um bestimmte Elemente suchen zu können (diese Methoden entsprechen den gleichnamigen Algorithmen, können jedoch in der Baumstruktur effizienter arbeiten als auf einem linear angeordneten Iterator-Bereich):

count(val)
Zählt, wie oft das Element (für Sets) bzw. der Schlüsselwert (für Maps) 'val' im Container enthalten ist
find(val)
Liefert einen Iterator auf ein Containerelement mit dem (Schlüssel-)Wert 'val' oder end(), wenn es nicht existiert
erase(val)
Löscht alle Elemente mit dem (Schlüssel-)Wert 'val' aus dem Container
lower_bound(val), upper_bound(val) und equal_range(val)
Liefern die erste, letzte bzw. beide Position im Container (als pair), an der der (Schlüssel-)Wert 'val' in den Container eingefügt werden kann
key_comp() und value_comp()
Liefern den Functor, mit dem die Schlüsselwerte bzw. Elemente des Containers sortiert werden (bei Sets sind beide identisch, bei Maps vergleicht value_comp() die ersten Elemente eines pair mit Hilfe von key_comp())

Jeder assoziative Container besitzt einen "eingebauten" Vergleichstyp, mit dessen Hilfe die einzelnen Elemente verglichen werden. Dieser wird bei der Definition des Containers als zweiter bzw. dritter Template-Parameter übergeben. Der vorgegebene Typ "less<T>" verwendet < als Vergleichskriterium, sortiert die Elemente also aufsteigend. Aber jeder Funktortyp, der zwei Schlüsselwerte als Parameter akzeptiert und einen bool zurückliefert, kann theoretisch als Vergleichskriterium eingesetzt werden.

Die Vergleichsrelation des Containers wird auch verwendet, um zwei Elemente auf Gleichheit zu testen: x==y ist genau dann wahr, wenn !(x<y)&&!(y<x) gilt.

Wichtig für die Anwendung von sets und maps ist, dass der verwendete Vergleichstyp eine "strict weak ordering" bildet, andernfalls kommt es zur Laufzeit des Programmes zu undefiniertem Verhalten - und kein Compiler kann kontrollieren, ob eine beliebig gegebene Relation diese Anforderungen erfüllt.

4.1 set und multiset

voller Name:

template<typename K,typename P=less<K>,typename A=allocator<K> >
class std::set;
template<typename K,typename P=less<K>,typename A=allocator<K> >
class std::multiset;

Header:

#include <set>

Sets und Multisets speichern einzelne Schlüsselwerte. Ihr Unterschied besteht darin, dass eine Set jeden Wert maximal einmal enthält, während eine Multiset auch Duplikate enthalten kann.

4.2 map und multimap

voller Name:

template<typename K,typename V,typename P=less<K>,typename A=allocator<pair<const K,V> > >
class std::map;
template<typename K,typename V,typename P=less<K>,typename A=allocator<pair<const K,V> > >
class std::multimap;

Maps und Multimaps speichern Paare aus einem Schlüssel und einem zugeordneten Wert. Auch hier besteht der Unterschied darin, dass eine Map eindeutige Schlüssel enthält, während die Schlüssel in der Multimap mehrfach vorkommen können - sogar mit unterschiedlichen zugeordneten Werten. Die Elemente in einer (Multi-)Map sind Paare aus konstantem Schlüssel und Wert, wodurch die insert-Operationen etwas komplizierter geschrieben werden müssen:

map<string,int> id_liste;

//(1) - exakter Typ:
id_liste.insert(map<string,int>::value_type("Carsten",4711);

//(2) - pair:
id_liste.insert(pair<string,int>("CStoll",0x0815);

//(3) - make_pair:
id_liste.insert(make_pair("Admin",1);

(im ersten Fall wird der Typ exakt so übergeben, wie die map ihn benötigt, im zweiten und dritten Fall ist eine implizite Typumwandlung von pair<string,int> bzw. pair<const char*,int> nach pair<const string,int> notwendig)

Eine Map bietet als besonderes Extra direkten Elementzugriff über den Index-Operator m[ind]. Im Gegensatz zu einem Array oder Vektor wird hierbei der Wert zurückgegeben, der zum Schlüssel 'ind' zugeordnet wurde. Wenn dieser Schlüssel nicht in der Map existiert, wird er angelegt und mit einem Defaultwert verknüpft.
(die Multimap bietet dieses Feature nicht, da sie keine eindeutige Zuordnung zwischen einem Schlüssel und seinem Wert herstellen kann)

5 Container-Adapter

Diese Adapter verwenden die Standard-Container, um darauf spezielle Datenstrukturen aufzubauen. Sie bieten ein halbwegs einheitliches Interface zur Verwendung an, unterscheiden sich jedoch in der Definition, welches Element das "erste" ist.

push(val)
fügt das Element "val" in den unterliegenden Container ein
top()
liefert das "erste" Element des Containers
pop()
löscht das "erste" Element des Containers (der Wert muss vorher verarbeitet werden)

Diese Methoden verwenden keinerlei Fehlerkontrolle - wenn versucht wird, das erste Element eines leeren Stacks zu lesen, ergibt sich deshalb undefiniertes Verhalten.

Alle Adapter erwarten, dass der verwendete Containertyp die Operationen bereitstellt, die sie verwenden wollen, andernfalls weigert sich der Compiler, sie zu erzeugen.

5.1 stack

voller Name:

template<typename T,typename C=deque<T> >
class std::stack;

Header:

#include <stack>

Ein Stack nutzt die Memberfunktionen push_back(), back() und pop_back() des unterliegenden Containertyps, um einen LIFO-Speicher zu realisieren - die Elemente werden in der umgekehrten Reihenfolge herausgegeben, in der sie eingefügt wurden.

Als Grundlage für den Stack kann theoretisch jeder sequentielle Container eingesetzt werden - der Standardtyp ist die deque, weil sie im Gegensatz zum Vektor auch wieder Speicher freigeben kann.

5.2 queue

voller Name:

template<typename T,typename C=deque<T> >
class std::queue;

Header:

#include <queue>

Eine Queue (oder Warteschlange) nutzt die Memberfunktionen push_back(), front(), und pop_front() des unterliegenden Containertyps, um einen FIFO-Speicher zu realisieren - die Elemente werden in der selben Reihenfolge herausgegeben, in der sie eingefügt wurden.

Als Grundlage für die Warteschlange können entweder deques oder Listen verwendet werden, da sie als einzige Standard-Container eine pop_front()-Methode definieren.

5.3 priority_queue

voller Name:

template<typename T,typename C=vector<T>,typename P=less<typename C::value_type> >
class std::priority_queue;

Header:

#include <queue>

Eine Priority-Queue implementiert eine Prioritäts-Warteschlange auf dem unterliegenden Containertyp - die Elemente werden entsprechend ihrer Größe umgeordnet, so dass jeweils das größte aus der Warteschlange entnommen werden kann. Der Adapter nutzt die Methoden push_back(), front() und pop_back() sowie die Heap-Algorithmen make_heap(), push_heap() und pop_heap(), um seine Elemente zu organisieren.
Das Prädikat P dient dabei zur Feststellung, welches Element größer ist. Genau wie bei den assoziativen Containern muss die verwendete Vergleichsfunktion eine Ordnungsrelation definieren, sonst funktioniert die Priority-Queue nicht richtig.

Als Grundlage für eine Prioritäts-Schlange können Vektoren, Deques oder Strings verwendet werden - Listen bieten keine Random-Access-Iteratoren und können deshalb nicht mit den Heap-Algorithmen genutzt werden.

6 Zusammenfassung

Es gibt keine "perfekte" Containerklasse für alle Anwendungsbereiche. Deshalb ist es von Vorteil, wenn man die unterschiedlichen Container der STL kennt und auswählen kann, welcher gerade am günstigsten geeignet ist. Dabei ist es auch mit geringem Aufwand möglich, die Container gegeneinander auszutauschen, wenn man zum Beispiel während der Entwicklung feststellt, dass eine deque<> doch bessere Eigenschaften hat als eine list<>.

Container         Vektor          Deque           Liste           Set             Multiset        Map             Multimap
----------------------------------------------------------------------------------------------------------------------------------

Struktur          dynamisches     Array von       verkettete      Binärbaum       Binärbaum       Binärbaum       Binärbaum
                  Array           Arrays          Liste

Elemente          Wert            Wert            Wert            Wert            Wert            Schlüssel+Wert  Schlüssel+Wert

Duplikate         Ja              Ja              Ja              Nein            Ja              Wert            Ja

Direktzugriff     Ja              Ja              Nein            Nein            Nein            über Schlüssel  Nein

Iteratortyp       Random Access   Random Access   Bidirektional   Bidirektional   Bidirektional   Bidirektional   Bidirektional
                                                                  konstant        konstant        Schl. konstant  Schl. konstant
Suche             langsam         langsam         sehr langsam    schnell         schnell         schnell (Schl.) schnell (Schl.)

Einf./Entf.       Ende            Anfang, Ende    überall

invalidiert       Reallocation    immer           nie             nie             nie             nie             nie
Iteratoren etc.

Speicherfreigabe  nie             manchmal        immer           immer           immer           immer           immer

Reservierung      Ja              Nein

Transaktions-     push/pop        push/pop an     alle außer      alle außer      alle außer      alle außer      alle außer
sicher            am Ende         Anfang, Ende    sort            multi-insert    multi-insert    multi-insert    multi-insert

Ausblick

Container sind ein hilfreiches Werkzeug zur Datenorganisation. Aber ihre volle Stärke entwickeln sie erst in Zusammenarbeit mit den Iteratoren und Algorithmen - deshalb werde ich diese Bestandteile der STL im zweiten Teil der Serie ausführlicher behandeln.

CStoll

-predator- schrieb:

So, bin das ganze mal durchgegangen; es waren zum Glück nur wenige Fehler drin.

Das hört man doch gerne.

Im 4. Abschnitt (assoziative Container) hast du 4.1 (set und multiset), aber nicht 4.2, ich denke, das hast du einfach bei "map und multimap" vergessen. Wenn es anders gedacht ist, kannst du es ja wieder rückgängig machen.

Stimmt, das hatte ich wohl unterschlagen, als ich die Kapitel neu numeriert habe.

Noch was zum Inhalt/Stil:

Abschnitt 2 schrieb:

rbegin() und rend() - liefern Reverse-Iteratoren auf das erste bzw hinter das letzte Element des Containers (rückwärts gerechnet)

Das ist imho für einen Neuling etwas verwirrend, denn ich denke nicht, dass er schon weiß, was ein Reverse-Iterator ist.
Wie wär's wenn du die zwei einzeln behandelst (wie bei begin und end auch) und für rbegin sowas wie "liefert einen Reverse-Iterator hinter das letzte Element des Containers, d.h. ein Inkrementieren dieses Iterators bewirkt einen Schritt in Richtung Anfang des Containers" und für rend dann einfach "liefert analog zu rbegin() einen Reverse-Iterator auf das erste Element des Containers". Ist natürlich nur ein Vorschlag.

Lässt sich machen.
Für "strict weak ordering" fällt mir auch kein deutsches Wort ein, aber du könntest es ja mit dem Verhalten von "Kleiner als" umschreiben, und/oder vielleicht noch einen Link auf http://en.wikipedia.org/wiki/Strict_weak_ordering setzen.

PPS: Ist bei euch in dem Beispiel in 3.1 auch die zweite Hälfte des Codes kursiv?
Anscheinend liegt das an dem data[ i] in der Schleife, ich habe das jetzt mit data[j] ersetzt.

Ist mir beim Schreiben gar nicht aufgefallen.

PS: Danke für das Lob

______________________________________________________________________________________

Inhalt

Teil 1:

Vorbemerkungen
Container
sequentielle Container
assoziative Container
Container-Adapter
Zusammenfassung

1 Vorbemerkungen

Die Standard Template Library (STL) ist ein wesentlicher Bestandteil von ISO C++, der leider häufig unterschätzt oder falsch eingesetzt wird. [...]

Wie der Name schon andeutet, sind die einzelnen Komponenten der STL als Templates aufgebaut. Das hat den Vorteil, dass sie mit beliebigen Datentypen und Erweiterungen zusammenarbeiten können, ohne auf Vererbungshierarchien Rücksicht nehmen zu müssen. Der Anwender der STL muss lediglich darauf achten, dass die benötigten Operationen von seinen Typen unterstützt werden (z.B. benötigt der Schlüsseltyp einer set<> einen <-Operator oder eine äquivalente Vergleichfunktion).

Die STL kann grob in drei Hauptbestandteile untergliedert werden:

Container dienen zur Aufbewahrung und Verwaltung großer Datensammlungen
Iteratoren navigieren in Containern oder anderen Datenstrukturen
Algorithmen führen verschiedene Operationen auf Container-Elementen aus

Außerdem gibt es einige weitere Funktionen und Klassen in der Standard-Bibliothek von C++, die nicht direkt der STL zugeordnet werden.

2 Container

Container werden verwendet, um viele gleichartige Objekte gemeinsam unterzubringen und zu verwalten. Alle Containerklassen der STL haben einige gemeinsame Definitionen und Methoden, so dass sie teilweise gegeneinander ausgetauscht werden können. Die wichtigsten davon sind:

Typdefinitionen:

value_type - der Typ der gespeicherten Daten
iterator und const_iterator - der hauseigene Iteratortyp des Containers (für variable bzw. konstante Container)
size_type - ein Typ zur Angabe von Größenwerten (vorzeichenloser Integer)
allocator_type - der Typ der verwendeten Allokator-Klasse

Memberfunktionen

begin() - liefert einen Iterator auf das erste Element des Containers
end() - liefert einen Iterator hinter das letzte Element des Containers
rbegin() - liefert einen Reverse-Iterator auf das letzte Element des Containers (bewegt sich rückwärts über die Elemente)
rend() - liefert Reverse-Iterator vor das erste Element des Containers
size() - liefert die aktuelle Anzahl an Elementen
max_size() - liefert das maximale Fassungsvermögen des Containers
insert(pos,wert) - fügt ein Element an der Stelle 'pos' ein (bei assoziativen Containern ist 'pos' nur ein Hinweis, wo das Element eingefügt werden könnte)
assign(st,en) - weist dem Container den Inhalt des Bereiches [st,en[ zu.
c1.swap(c2) und swap(c1,c2) - vertauscht den Inhalt der Container c1 und c2.
clear() - löscht alle Elemente des Containers
erase(pos) und erase(st,en) - löscht das Element an der Stelle 'pos' bzw. alle Elemente im Bereich [st,en[

Zu den Template-Parametern, die ein Container bekommt, gehört neben dem Wertetyp auch immer ein Allokator-Typ. Dessen Methoden werden verwendet, wenn der Container neuen Speicher anfordern, initialisieren und freigeben will. Der Defaulttyp hierfür ist std::allocator<T> und verwendet die Operatoren new und delete, um den Speicher zu verwalten. Experten können die Speicherverwaltung jedoch auch anders implementieren, indem sie eine eigene Allokator-Klasse schreiben und dem Container mitgeben (z.B. kann eine Datenbank oder ein Garbage Collector verwendet oder zurückgegebene Speicherbereiche für schnelleren Zugriff zwischengelagert werden).

3 sequentielle Container

Sequentielle Container speichern ihre Elemente in der Reihenfolge, in der sie eingefügt wurden. Natürlich ist es auch möglich, diese Reihenfolge manuell anzupassen, indem man ein Element in der Mitte des Containers einfügt oder die vorhandenen Elemente direkt ändert.

3.1 vector

voller Name:

template<typename T,typename A=allocator<T> >
class std::vector;

Header:

include <vector>

Ein Vektor verwendet einen zusammenhängenden Speicherbereich, in dem er seine Elemente unterbringen kann. Dadurch kann er sehr schnell über den Index auf ein Element zugreifen und neue Elemente am Ende der Sequenz anhängen und löschen. Einfüge- und Lösch-Operationen in der Mitte oder gar am Anfang des Containers benötigen jedoch deutlich mehr Zeit, weil alle nachfolgenden Elemente entsprechend verschoben werden müssen.

Ein Beispiel zum Umgang mit Vektoren:

#include <vector>
#include <iostream>//für Ausgaben
using namespace std;

int main()
{
  vector<int> data;
  data.push_back(1);
  data.push_back(2);
  data.push_back(3);

  //Ausgabe aller Elemente:
  for(int j=0;j<data.size();++j)
    cout<<data[j]<<" ";
  cout<<endl;

  data[1]=20;//direkter Elementzugriff
  data.front()=11;
  data.pop_back();

  data.resize(10,4);

  //noch mal Ausgabe:
  for(int j=0;j<data.size();++j)
    cout<<data[j]<<" ";

  return 0;
}

Ein Vektor reserviert sich in der Regel mehr Speicherplatz als für seine aktuelle Größe notwendig ist. Solange diese Kapazität noch nicht erreicht wird, können push_back()-Operationen in konstanter Zeit durchgeführt werden. Bei Überschreitung der Kapazität werden alle vorhandenen Elemente in einen neuen (entsprechend größeren) Speicherbereich umkopiert - dadurch werden erstens alle Referenzen, Zeiger und Iteratoren in den Vektor und zweitens kostet diese Operation recht viel Zeit. Deshalb ist es günstig, vor aufwendigen Operationen mit dem Vektor per reserve() genug Speicher anzufordern.

Achtung: Ein Vektor gibt die einmal reservierte Kapazität erst im Destruktor wieder frei.

Zusätzlich zu den generellen Methoden, seinen Inhalt zu manipulieren, bietet ein Vektor noch einige spezielle Zugriffsfunktionen:

resize(size) und resize(size,val)
Ändert die Größe des Vektors auf 'size', indem am Ende Elemente entfernt oder angefügt werden. Neue Elemente werden mit dem Defaultwert des Elementtyps bzw. mit 'val' belegt.
vec[pos] und at(pos)
Liefern das Element mit dem Index 'pos' zurück. Der Unterschied zwischen beiden Methoden besteht in der Fehlerbehandlung - der Index-Operator liefert undefinierte Werte, wenn er mit einem Index außerhalb des Intervalls [0,vec.size()[ aufgerufen wird, die Methode at() wirft eine out_of_range Ausnahme, die vom Anwender aufgefangen werden muss.
push_back(val)
Hängt das Element 'val' an das Ende des Vektors an.
front() und back()
Liefern den Wert des ersten bzw. letzten Elements im Vektor.
pop_back()
Löscht das letzte Element aus dem Vektor.
capacity()
Liefert die aktuelle Kapazität des Vektors zurück. Dieser Wert gibt an, wie viele Elemente er aufnehmen könnte, ohne neuen Speicher anfordern zu müssen.
reserve(size)
Reserviert genug Speicherplatz für mindestens 'size' Elemente. Der neu angelegte Speicherplatz wird nicht initialisiert.

Die Spezialisierung vector<bool> wurde zur Platz sparenden Speicherung von 1-Bit-Werten vorgesehen und bietet ein paar Zusatzmethoden zur Manipulation einzelner Bits:

flip()
Invertiert alle Elemente des Vektors (aus true wird false und umgekehrt)
vec[pos].flip() bzw. at(pos).flip
Invertiert das Element 'pos' des Vektors

3.2 deque

voller Name:

template<typename T,typename A=allocator<T> >
class std::deque;

Header:

#include <deque>

Eine Deque (Double Ended QUEue) hat insofern Ähnlichkeit mit dem Vektor, dass sie ihren Inhalt auch in zusammenhängendem Speicher organisiert. In der Regel wird jedoch nicht ein einzelner Speicherblock dafür verwendet, sondern mehrere kleinere Blöcke, die beim Durchlaufen der Deque virtuell zusammengefügt werden. Ihr Vorteil ist, dass sie sowohl am Ende als auch am Anfang problemlos erweitert werden kann. Änderungen in der Mitte des Containers sind wie beim vector langsam und sollten besser vermieden werden.

Wenn eine Deque ihre reservierte Kapazität ausgeschöpft hat, reserviert sie einen neuen Speicherbereich, der vor bzw. hinter den vorhandenen Speicherblöcken in die Kontrollstruktur eingefügt wird. Im Gegensatz zum Vektor werden die einzelnen Speicherblöcke auch wieder freigegeben, wenn sie nicht mehr benötigt werden (wann das geschieht, ist normalerweise von der Implementation abhängig).

Eine Deque bietet - mit Ausnahme von capacity() und reserve() - die gleichen Methoden wie ein Vektor, zusätzlich ermöglicht sie:

push_front(val)
Hängt das Element 'val' an den Anfang der Schlange an
pop_front()
Löscht das erste Element der Schlange

3.3 list

voller Name:

template<typename T,typename A=allocator<T> >
class std::list;

Header:

#include <list>

Im Gegensatz zu Vektoren wird der Inhalt einer list in Form einer doppelt verketteten Liste gespeichert. Auf diese Weise ist es sehr effizient, Werte an beliebiger Stelle einzufügen und wieder zu entfernen. Im Gegenzug ist es sehr langwierig, ein bestimmtes Element anhand seines Index wiederzufinden.

Eine List bietet keinen direkten Elementzugriff über den Index-Operator bzw. at(), aber unterstützt die meisten anderen Funktionen, die auch von Vektoren und Deques zur Verfügung gestellt werden:

resize()
push_back(), pop_back() und back()
push_front(), pop_front() und front()
splice(pos,list), splice(pos,list,spos) bzw. splice(pos,list,sbeg,send)
Hängt einzelne Elemente aus 'list' aus und fügt sie vor dem Iterator 'pos' in die Liste ein. Je nach Version wird die komplette Liste 'list', das einzelne Element 'spos' bzw. der Bereich [sbeg,send[ umgehängt.
unique(), sort(), merge(list) und reverse()
Diese Methoden entsprechen den gleichnamigen Algorithmen, können jedoch auf der Listenstruktur effizienter umgesetzt werden als mit den Iterator-basierten Algorithmen (z.B. braucht reverse() nur alle Vorgänger- und Nachfolger-Zeiger zu vertauschen anstatt Elemente umzukopieren).

Ein Beispiel zur Anwendung einer Liste:

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

int main()
{
  list<int> data;
  //Liste füllen
  for(int i=1;i<5;++i) data.push_back(i);
  data.push_front(4711);

  //Ausgabe (nicht über Index möglich, deshalb benötigt man Listen-Iteratoren)
  for(list<int>::iterator pos=data.begin();pos!=data.end();++pos)
    cout<<*pos<<" ";
  cout<<endl;

  list<int>::iterator pos1=data.begin();
  ++pos1;//Iterator auf 2. Element
  data.insert(pos1,0x0815);

  //noch mal Ausgabe:
  for(list<int>::iterator pos=data.begin();pos!=data.end();++pos)
    cout<<*pos<<" ";
  cout<<endl;
}

3.4 string

voller Name:

template<typename C,typename Tr=char_traits<T>,typename A=allocator<C> >
class std::basic_string;

typedef basic_string<char> string;
typedef basic_string<wchar_t> wstring;

Header:

#include <string>

Achtung: Der Header <string.h> existiert ebenfalls, dieser enthält jedoch die char*-Verarbeitungsfunktionen der C-Standardbibliothek.

Strings sind zwar keine "offiziellen" STL-Container, aber sie bieten genug Unterstützung an, um analog zu den anderen Containern verwendet zu werden. Ihre Hauptverwendung ist die Verwaltung von Zeichenketten, deshalb bieten sie auch Operationen zur Verkettung und zur Zusammenarbeit mit char*-Feldern an.

Mit Strings werde ich mich ausführlicher in einem späteren Artikel beschäftigen.

4 assoziative Container

Assoziative Container sortieren ihre Elemente intern nach ihrer Größe. Dadurch geht es deutlich schneller, einen bestimmten Wert im Container wiederzufinden, allerdings spielt es für die Reihenfolge in der Regel keine Rolle, welches Element zuerst eingefügt wurde.

Im Allgemeinen nutzen alle assoziativen Container die gleiche Grundstruktur (ein balancierter Binärbaum), um ihren Inhalt zu speichern, sie unterscheiden sich lediglich im Typ der eingetragenen Elemente und der Art, wie Duplikate verwaltet werden.

Alle assoziativen Container bieten einige zusätzliche Methoden, um bestimmte Elemente suchen zu können (diese Methoden entsprechen den gleichnamigen Algorithmen, können jedoch in der Baumstruktur effizienter arbeiten als auf einem linear angeordneten Iterator-Bereich):

count(val)
Zählt, wie oft das Element (für Sets) bzw. der Schlüsselwert (für Maps) 'val' im Container enthalten ist
find(val)
Liefert einen Iterator auf ein Containerelement mit dem (Schlüssel-)Wert 'val' oder end(), wenn es nicht existiert
erase(val)
Löscht alle Elemente mit dem (Schlüssel-)Wert 'val' aus dem Container
lower_bound(val), upper_bound(val) und equal_range(val)
Liefern die erste, letzte bzw. beide Position im Container (als pair), an der der (Schlüssel-)Wert 'val' in den Container eingefügt werden kann
key_comp() und value_comp()
Liefern den Functor, mit dem die Schlüsselwerte bzw. Elemente des Containers sortiert werden (bei Sets sind beide identisch, bei Maps vergleicht value_comp() die ersten Elemente eines pair mit Hilfe von key_comp())

Jeder assoziative Container besitzt einen "eingebauten" Vergleichstyp, mit dessen Hilfe die einzelnen Elemente verglichen werden. Dieser wird bei der Definition des Containers als zweiter bzw. dritter Template-Parameter übergeben. Der vorgegebene Typ "less<T>" verwendet < als Vergleichskriterium, sortiert die Elemente also aufsteigend. Aber jeder Funktortyp, der zwei Schlüsselwerte als Parameter akzeptiert und einen bool zurückliefert, kann theoretisch als Vergleichskriterium eingesetzt werden.

Die Vergleichsrelation des Containers wird auch verwendet, um zwei Elemente auf Gleichheit zu testen: x==y ist genau dann wahr, wenn !(x<y)&&!(y<x) gilt.

Wichtig für die Anwendung von sets und maps ist, dass der verwendete Vergleichstyp eine "strict weak ordering" (siehe Wikipedia)) bildet, andernfalls kommt es zur Laufzeit des Programmes zu undefiniertem Verhalten - und kein Compiler kann kontrollieren, ob eine beliebig gegebene Relation diese Anforderungen erfüllt.

4.1 set und multiset

voller Name:

template<typename K,typename P=less<K>,typename A=allocator<K> >
class std::set;
template<typename K,typename P=less<K>,typename A=allocator<K> >
class std::multiset;

Header:

#include <set>

Sets und Multisets speichern einzelne Schlüsselwerte. Ihr Unterschied besteht darin, dass eine Set jeden Wert maximal einmal enthält, während eine Multiset auch Duplikate enthalten kann.

4.2 map und multimap

voller Name:

template<typename K,typename V,typename P=less<K>,typename A=allocator<pair<const K,V> > >
class std::map;
template<typename K,typename V,typename P=less<K>,typename A=allocator<pair<const K,V> > >
class std::multimap;

Maps und Multimaps speichern Paare aus einem Schlüssel und einem zugeordneten Wert. Auch hier besteht der Unterschied darin, dass eine Map eindeutige Schlüssel enthält, während die Schlüssel in der Multimap mehrfach vorkommen können - sogar mit unterschiedlichen zugeordneten Werten. Die Elemente in einer (Multi-)Map sind Paare aus konstantem Schlüssel und Wert, wodurch die insert-Operationen etwas komplizierter geschrieben werden müssen:

map<string,int> id_liste;

//(1) - exakter Typ:
id_liste.insert(map<string,int>::value_type("Carsten",4711);

//(2) - pair:
id_liste.insert(pair<string,int>("CStoll",0x0815);

//(3) - make_pair:
id_liste.insert(make_pair("Admin",1);

(im ersten Fall wird der Typ exakt so übergeben, wie die map ihn benötigt, im zweiten und dritten Fall ist eine implizite Typumwandlung von pair<string,int> bzw. pair<const char*,int> nach pair<const string,int> notwendig)

Eine Map bietet als besonderes Extra direkten Elementzugriff über den Index-Operator m[ind]. Im Gegensatz zu einem Array oder Vektor wird hierbei der Wert zurückgegeben, der zum Schlüssel 'ind' zugeordnet wurde. Wenn dieser Schlüssel nicht in der Map existiert, wird er angelegt und mit einem Defaultwert verknüpft.
(die Multimap bietet dieses Feature nicht, da sie keine eindeutige Zuordnung zwischen einem Schlüssel und seinem Wert herstellen kann)

5 Container-Adapter

Diese Adapter verwenden die Standard-Container, um darauf spezielle Datenstrukturen aufzubauen. Sie bieten ein halbwegs einheitliches Interface zur Verwendung an, unterscheiden sich jedoch in der Definition, welches Element das "erste" ist.

push(val)
fügt das Element "val" in den unterliegenden Container ein
top()
liefert das "erste" Element des Containers
pop()
löscht das "erste" Element des Containers (der Wert muss vorher verarbeitet werden)

Diese Methoden verwenden keinerlei Fehlerkontrolle - wenn versucht wird, das erste Element eines leeren Stacks zu lesen, ergibt sich deshalb undefiniertes Verhalten.

Alle Adapter erwarten, dass der verwendete Containertyp die Operationen bereitstellt, die sie verwenden wollen, andernfalls weigert sich der Compiler, sie zu erzeugen.

5.1 stack

voller Name:

template<typename T,typename C=deque<T> >
class std::stack;

Header:

#include <stack>

Ein Stack nutzt die Memberfunktionen push_back(), back() und pop_back() des unterliegenden Containertyps, um einen LIFO-Speicher zu realisieren - die Elemente werden in der umgekehrten Reihenfolge herausgegeben, in der sie eingefügt wurden.

Als Grundlage für den Stack kann theoretisch jeder sequentielle Container eingesetzt werden - der Standardtyp ist die deque, weil sie im Gegensatz zum Vektor auch wieder Speicher freigeben kann.

5.2 queue

voller Name:

template<typename T,typename C=deque<T> >
class std::queue;

Header:

#include <queue>

Eine Queue (oder Warteschlange) nutzt die Memberfunktionen push_back(), front(), und pop_front() des unterliegenden Containertyps, um einen FIFO-Speicher zu realisieren - die Elemente werden in der selben Reihenfolge herausgegeben, in der sie eingefügt wurden.

Als Grundlage für die Warteschlange können entweder deques oder Listen verwendet werden, da sie als einzige Standard-Container eine pop_front()-Methode definieren.

5.3 priority_queue

voller Name:

template<typename T,typename C=vector<T>,typename P=less<typename C::value_type> >
class std::priority_queue;

Header:

#include <queue>

Eine Priority-Queue implementiert eine Prioritäts-Warteschlange auf dem unterliegenden Containertyp - die Elemente werden entsprechend ihrer Größe umgeordnet, so dass jeweils das größte aus der Warteschlange entnommen werden kann. Der Adapter nutzt die Methoden push_back(), front() und pop_back() sowie die Heap-Algorithmen make_heap(), push_heap() und pop_heap(), um seine Elemente zu organisieren.
Das Prädikat P dient dabei zur Feststellung, welches Element größer ist. Genau wie bei den assoziativen Containern muss die verwendete Vergleichsfunktion eine Ordnungsrelation definieren, sonst funktioniert die Priority-Queue nicht richtig.

Als Grundlage für eine Prioritäts-Schlange können Vektoren, Deques oder Strings verwendet werden - Listen bieten keine Random-Access-Iteratoren und können deshalb nicht mit den Heap-Algorithmen genutzt werden.

6 Zusammenfassung

Es gibt keine "perfekte" Containerklasse für alle Anwendungsbereiche. Deshalb ist es von Vorteil, wenn man die unterschiedlichen Container der STL kennt und auswählen kann, welcher gerade am günstigsten geeignet ist. Dabei ist es auch mit geringem Aufwand möglich, die Container gegeneinander auszutauschen, wenn man zum Beispiel während der Entwicklung feststellt, dass eine deque<> doch bessere Eigenschaften hat als eine list<>.

Container         Vektor          Deque           Liste           Set             Multiset        Map             Multimap
----------------------------------------------------------------------------------------------------------------------------------

Struktur          dynamisches     Array von       verkettete      Binärbaum       Binärbaum       Binärbaum       Binärbaum
                  Array           Arrays          Liste

Elemente          Wert            Wert            Wert            Wert            Wert            Schlüssel+Wert  Schlüssel+Wert

Duplikate         Ja              Ja              Ja              Nein            Ja              Wert            Ja

Direktzugriff     Ja              Ja              Nein            Nein            Nein            über Schlüssel  Nein

Iteratortyp       Random Access   Random Access   Bidirektional   Bidirektional   Bidirektional   Bidirektional   Bidirektional
                                                                  konstant        konstant        Schl. konstant  Schl. konstant
Suche             langsam         langsam         sehr langsam    schnell         schnell         schnell (Schl.) schnell (Schl.)

Einf./Entf.       Ende            Anfang, Ende    überall

invalidiert       Reallocation    immer           nie             nie             nie             nie             nie
Iteratoren etc.

Speicherfreigabe  nie             manchmal        immer           immer           immer           immer           immer

Reservierung      Ja              Nein

Transaktions-     push/pop        push/pop an     alle außer      alle außer      alle außer      alle außer      alle außer
sicher            am Ende         Anfang, Ende    sort            multi-insert    multi-insert    multi-insert    multi-insert

Ausblick

Container sind ein hilfreiches Werkzeug zur Datenorganisation. Aber ihre volle Stärke entwickeln sie erst in Zusammenarbeit mit den Iteratoren und Algorithmen - deshalb werde ich diese Bestandteile der STL im zweiten Teil der Serie ausführlicher behandeln.

Mr. B

Inhalt

Teil 1:

Vorbemerkungen
Container
sequenzielle Container
assoziative Container
Container-Adapter
Zusammenfassung

1 Vorbemerkungen

Die Standard Template Library (STL) ist ein wesentlicher Bestandteil von ISO C++, der leider häufig unterschätzt oder falsch eingesetzt wird. [...]

Wie der Name schon andeutet, sind die einzelnen Komponenten der STL als Templates aufgebaut. Das hat den Vorteil, dass sie mit beliebigen Datentypen und Erweiterungen zusammenarbeiten können, ohne auf Vererbungshierarchien Rücksicht nehmen zu müssen. Der Anwender der STL muss lediglich darauf achten, dass die benötigten Operationen von seinen Typen unterstützt werden (z.B. benötigt der Schlüsseltyp einer set<> einen <-Operator oder eine äquivalente Vergleichfunktion).

Die STL kann grob in drei Hauptbestandteile untergliedert werden:

Container dienen zur Aufbewahrung und Verwaltung großer Datensammlungen
Iteratoren navigieren in Containern oder anderen Datenstrukturen
Algorithmen führen verschiedene Operationen auf Container-Elementen aus

Außerdem gibt es einige weitere Funktionen und Klassen in der Standardbibliothek von C++, die nicht direkt der STL zugeordnet werden.

2 Container

Container werden verwendet, um viele gleichartige Objekte gemeinsam unterzubringen und zu verwalten. Alle Containerklassen der STL haben einige gemeinsame Definitionen und Methoden, sodass sie teilweise gegeneinander ausgetauscht werden können. Die wichtigsten davon sind:

Typdefinitionen:

value_type - der Typ der gespeicherten Daten
iterator und const_iterator - der hauseigene Iteratortyp des Containers (für variable bzw. konstante Container)
size_type - ein Typ zur Angabe von Größenwerten (vorzeichenloser Integer)
allocator_type - der Typ der verwendeten Allokator-Klasse

Memberfunktionen

begin() - liefert einen Iterator auf das erste Element des Containers
end() - liefert einen Iterator hinter das letzte Element des Containers
rbegin() - liefert einen Reverse-Iterator auf das letzte Element des Containers (bewegt sich rückwärts über die Elemente)
rend() - liefert Reverse-Iterator vor das erste Element des Containers
size() - liefert die aktuelle Anzahl an Elementen
max_size() - liefert das maximale Fassungsvermögen des Containers
insert(pos,wert) - fügt ein Element an der Stelle 'pos' ein (bei assoziativen Containern ist 'pos' nur ein Hinweis, wo das Element eingefügt werden könnte)
assign(st,en) - weist dem Container den Inhalt des Bereiches [st,en[ zu.
c1.swap(c2) und swap(c1,c2) - vertauscht den Inhalt der Container c1 und c2.
clear() - löscht alle Elemente des Containers
erase(pos) und erase(st,en) - löscht das Element an der Stelle 'pos' bzw. alle Elemente im Bereich [st,en[

Zu den Template-Parametern, die ein Container bekommt, gehört neben dem Wertetyp auch immer ein Allokator-Typ. Dessen Methoden werden verwendet, wenn der Container neuen Speicher anfordern, initialisieren und freigeben will. Der Defaulttyp hierfür ist std::allocator<T> und verwendet die Operatoren new und delete, um den Speicher zu verwalten. Experten können die Speicherverwaltung jedoch auch anders implementieren, indem sie eine eigene Allokator-Klasse schreiben und diese dem Container mitgeben (z.B. kann eine Datenbank oder ein Garbage Collector verwendet oder zurückgegebene Speicherbereiche für schnelleren Zugriff zwischengelagert werden).

3 sequenzielle Container

Sequenzielle Container speichern ihre Elemente in der Reihenfolge, in der sie eingefügt wurden. Natürlich ist es auch möglich, diese Reihenfolge manuell anzupassen, indem man ein Element in der Mitte des Containers einfügt oder die vorhandenen Elemente direkt ändert.

3.1 vector

voller Name:

template<typename T,typename A=allocator<T> >
class std::vector;

Header:

include <vector>

Ein Vektor verwendet einen zusammenhängenden Speicherbereich, in dem er seine Elemente unterbringen kann. Dadurch kann er sehr schnell über den Index auf ein Element zugreifen und neue Elemente am Ende der Sequenz anhängen und löschen. Einfüge- und Lösch-Operationen in der Mitte oder gar am Anfang des Containers benötigen jedoch deutlich mehr Zeit, weil alle nachfolgenden Elemente entsprechend verschoben werden müssen.

Ein Beispiel zum Umgang mit Vektoren:

#include <vector>
#include <iostream>//für Ausgaben
using namespace std;

int main()
{
  vector<int> data;
  data.push_back(1);
  data.push_back(2);
  data.push_back(3);

  //Ausgabe aller Elemente:
  for(int j=0;j<data.size();++j)
    cout<<data[j]<<" ";
  cout<<endl;

  data[1]=20;//direkter Elementzugriff
  data.front()=11;
  data.pop_back();

  data.resize(10,4);

  //noch mal Ausgabe:
  for(int j=0;j<data.size();++j)
    cout<<data[j]<<" ";

  return 0;
}

Ein Vektor reserviert sich in der Regel mehr Speicherplatz als für seine aktuelle Größe notwendig ist. Solange diese Kapazität noch nicht erreicht wird, können push_back()-Operationen in konstanter Zeit durchgeführt werden. Bei Überschreitung der Kapazität werden alle vorhandenen Elemente in einen neuen (entsprechend größeren) Speicherbereich umkopiert - dadurch werden erstens alle Referenzen, Zeiger und Iteratoren in den Vektor ~hier fehlt das verb~ und zweitens kostet diese Operation recht viel Zeit. Deshalb ist es günstig, vor aufwendigen Operationen mit dem Vektor per reserve() genug Speicher anzufordern.

Achtung: Ein Vektor gibt die einmal reservierte Kapazität erst im Destruktor wieder frei.

Zusätzlich zu den generellen Methoden, seinen Inhalt zu manipulieren, bietet ein Vektor noch einige spezielle Zugriffsfunktionen:

resize(size) und resize(size,val)
ändert die Größe des Vektors auf 'size', indem am Ende Elemente entfernt oder angefügt werden. Neue Elemente werden mit dem Defaultwert des Elementtyps bzw. mit 'val' belegt.
vec[pos] und at(pos)
liefern das Element mit dem Index 'pos' zurück. Der Unterschied zwischen beiden Methoden besteht in der Fehlerbehandlung - der Index-Operator liefert undefinierte Werte, wenn er mit einem Index außerhalb des Intervalls [0,vec.size()[ aufgerufen wird, die Methode at() wirft eine out_of_range Ausnahme, die vom Anwender aufgefangen werden muss.
push_back(val)
hängt das Element 'val' an das Ende des Vektors an.
front() und back()
liefern den Wert des ersten bzw. letzten Elements im Vektor.
pop_back()
löscht das letzte Element aus dem Vektor.
capacity()
liefert die aktuelle Kapazität des Vektors zurück. Dieser Wert gibt an, wie viele Elemente er aufnehmen könnte, ohne neuen Speicher anfordern zu müssen.
reserve(size)
reserviert genug Speicherplatz für mindestens 'size' Elemente. Der neu angelegte Speicherplatz wird nicht initialisiert.

Die Spezialisierung vector<bool> wurde zur Platz sparenden Speicherung von 1-Bit-Werten vorgesehen und bietet ein paar Zusatzmethoden zur Manipulation einzelner Bits:

flip()
invertiert alle Elemente des Vektors (aus true wird false und umgekehrt)
vec[pos].flip() bzw. at(pos).flip
invertiert das Element 'pos' des Vektors

3.2 deque

voller Name:

template<typename T,typename A=allocator<T> >
class std::deque;

Header:

#include <deque>

Eine Deque (Double Ended QUEue) hat insofern Ähnlichkeit mit dem Vektor, dass sie ihren Inhalt auch in zusammenhängendem Speicher organisiert. In der Regel wird jedoch nicht ein einzelner Speicherblock dafür verwendet, sondern mehrere kleinere Blöcke, die beim Durchlaufen der Deque virtuell zusammengefügt werden. Ihr Vorteil ist, dass sie sowohl am Ende als auch am Anfang problemlos erweitert werden kann. Änderungen in der Mitte des Containers sind wie beim vector langsam und sollten besser vermieden werden.

Wenn eine Deque ihre reservierte Kapazität ausgeschöpft hat, reserviert sie einen neuen Speicherbereich, der vor bzw. hinter den vorhandenen Speicherblöcken in die Kontrollstruktur eingefügt wird. Im Gegensatz zum Vektor werden die einzelnen Speicherblöcke auch wieder freigegeben, wenn sie nicht mehr benötigt werden (wann das geschieht, ist normalerweise von der Implementation abhängig).

Eine Deque bietet - mit Ausnahme von capacity() und reserve() - die gleichen Methoden wie ein Vektor, zusätzlich ermöglicht sie:

push_front(val)
hängt das Element 'val' an den Anfang der Schlange an
pop_front()
löscht das erste Element der Schlange

3.3 list

voller Name:

template<typename T,typename A=allocator<T> >
class std::list;

Header:

#include <list>

Im Gegensatz zu Vektoren wird der Inhalt einer List in Form einer doppelt verketteten Liste gespeichert. Auf diese Weise ist es sehr effizient, Werte an beliebiger Stelle einzufügen und wieder zu entfernen. Im Gegenzug ist es sehr langwierig, ein bestimmtes Element anhand seines Index wiederzufinden.

Eine List bietet keinen direkten Elementzugriff über den Index-Operator bzw. at(), aber unterstützt die meisten anderen Funktionen, die auch von Vektoren und Deques zur Verfügung gestellt werden:

resize()
push_back(), pop_back() und back()
push_front(), pop_front() und front()
splice(pos,list), splice(pos,list,spos) bzw. splice(pos,list,sbeg,send)
hängt einzelne Elemente aus 'list' aus und fügt sie vor dem Iterator 'pos' in die Liste ein. Je nach Version wird die komplette Liste 'list', das einzelne Element 'spos' bzw. der Bereich [sbeg,send[ umgehängt.
unique(), sort(), merge(list) und reverse()
Diese Methoden entsprechen den gleichnamigen Algorithmen, können jedoch auf der Listenstruktur effizienter umgesetzt werden als mit den Iterator-basierten Algorithmen (z.B. braucht reverse() nur alle Vorgänger- und Nachfolger-Zeiger zu vertauschen anstatt Elemente umzukopieren).

Ein Beispiel zur Anwendung einer Liste:

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

int main()
{
  list<int> data;
  //Liste füllen
  for(int i=1;i<5;++i) data.push_back(i);
  data.push_front(4711);

  //Ausgabe (nicht über Index möglich, deshalb benötigt man Listen-Iteratoren)
  for(list<int>::iterator pos=data.begin();pos!=data.end();++pos)
    cout<<*pos<<" ";
  cout<<endl;

  list<int>::iterator pos1=data.begin();
  ++pos1;//Iterator auf 2. Element
  data.insert(pos1,0x0815);

  //noch mal Ausgabe:
  for(list<int>::iterator pos=data.begin();pos!=data.end();++pos)
    cout<<*pos<<" ";
  cout<<endl;
}

3.4 string

voller Name:

template<typename C,typename Tr=char_traits<T>,typename A=allocator<C> >
class std::basic_string;

typedef basic_string<char> string;
typedef basic_string<wchar_t> wstring;

Header:

#include <string>

Achtung: Der Header <string.h> existiert ebenfalls, dieser enthält jedoch die char*-Verarbeitungsfunktionen der C-Standardbibliothek.

Strings sind zwar keine offiziellen STL-Container, aber sie bieten genug Unterstützung an, um analog zu den anderen Containern verwendet zu werden. Ihre Hauptverwendung ist die Verwaltung von Zeichenketten, deshalb bieten sie auch Operationen zur Verkettung und zur Zusammenarbeit mit char*-Feldern an.

Mit Strings werde ich mich ausführlicher in einem späteren Artikel beschäftigen.

4 assoziative Container

Assoziative Container sortieren ihre Elemente intern nach ihrer Größe. Dadurch geht es deutlich schneller, einen bestimmten Wert im Container wiederzufinden, allerdings spielt es für die Reihenfolge in der Regel keine Rolle, welches Element zuerst eingefügt wurde.

Im Allgemeinen nutzen alle assoziativen Container die gleiche Grundstruktur (ein balancierter Binärbaum), um ihren Inhalt zu speichern, sie unterscheiden sich lediglich im Typ der eingetragenen Elemente und der Art, wie Duplikate verwaltet werden.

Alle assoziativen Container bieten einige zusätzliche Methoden, um bestimmte Elemente suchen zu können (diese Methoden entsprechen den gleichnamigen Algorithmen, können jedoch in der Baumstruktur effizienter arbeiten als auf einem linear angeordneten Iterator-Bereich):

count(val)
zählt, wie oft das Element (für Sets) bzw. der Schlüsselwert (für Maps) 'val' im Container enthalten ist
find(val)
liefert einen Iterator auf ein Containerelement mit dem (Schlüssel-)Wert 'val' oder end(), wenn es nicht existiert
erase(val)
löscht alle Elemente mit dem (Schlüssel-)Wert 'val' aus dem Container
lower_bound(val), upper_bound(val) und equal_range(val)
liefern die erste, letzte bzw. beide Position im Container (als pair), an der der (Schlüssel-)Wert 'val' in den Container eingefügt werden kann
key_comp() und value_comp()
liefern den Funktor, mit dem die Schlüsselwerte bzw. Elemente des Containers sortiert werden (bei Sets sind beide identisch, bei Maps vergleicht value_comp() die ersten Elemente eines pair mit Hilfe von key_comp())

Jeder assoziative Container besitzt einen eingebauten Vergleichstyp, mit dessen Hilfe die einzelnen Elemente verglichen werden. Dieser wird bei der Definition des Containers als zweiter bzw. dritter Template-Parameter übergeben. Der vorgegebene Typ "less<T>" verwendet < als Vergleichskriterium, sortiert die Elemente also aufsteigend. Aber jeder Funktortyp, der zwei Schlüsselwerte als Parameter akzeptiert und einen bool zurückliefert, kann theoretisch als Vergleichskriterium eingesetzt werden.

Die Vergleichsrelation des Containers wird auch verwendet, um zwei Elemente auf Gleichheit zu testen: x==y ist genau dann wahr, wenn !(x<y)&&!(y<x) gilt.

Wichtig für die Anwendung von sets und maps ist, dass der verwendete Vergleichstyp eine "strict weak ordering" (siehe Wikipedia)) bildet, andernfalls kommt es zur Laufzeit des Programmes zu undefiniertem Verhalten - und kein Compiler kann kontrollieren, ob eine beliebig gegebene Relation diese Anforderungen erfüllt.

4.1 set und multiset

voller Name:

template<typename K,typename P=less<K>,typename A=allocator<K> >
class std::set;
template<typename K,typename P=less<K>,typename A=allocator<K> >
class std::multiset;

Header:

#include <set>

Sets und Multisets speichern einzelne Schlüsselwerte. Ihr Unterschied besteht darin, dass eine Set jeden Wert maximal einmal enthält, während eine Multiset auch Duplikate enthalten kann.

4.2 map und multimap

voller Name:

template<typename K,typename V,typename P=less<K>,typename A=allocator<pair<const K,V> > >
class std::map;
template<typename K,typename V,typename P=less<K>,typename A=allocator<pair<const K,V> > >
class std::multimap;

Maps und Multimaps speichern Paare aus einem Schlüssel und einem zugeordneten Wert. Auch hier besteht der Unterschied darin, dass eine Map eindeutige Schlüssel enthält, während die Schlüssel in der Multimap mehrfach vorkommen können - sogar mit unterschiedlich zugeordneten Werten. Die Elemente in einer (Multi-)Map sind Paare aus konstantem Schlüssel und Wert, wodurch die insert-Operationen etwas komplizierter geschrieben werden müssen:

map<string,int> id_liste;

//(1) - exakter Typ:
id_liste.insert(map<string,int>::value_type("Carsten",4711);

//(2) - pair:
id_liste.insert(pair<string,int>("CStoll",0x0815);

//(3) - make_pair:
id_liste.insert(make_pair("Admin",1);

(im ersten Fall wird der Typ exakt so übergeben, wie die map ihn benötigt, im zweiten und dritten Fall ist eine implizite Typumwandlung von pair<string,int> bzw. pair<const char*,int> nach pair<const string,int> notwendig)

Eine Map bietet als besonderes Extra direkten Elementzugriff über den Index-Operator m[ind]. Im Gegensatz zu einem Array oder Vektor wird hierbei der Wert zurückgegeben, der zum Schlüssel 'ind' zugeordnet wurde. Wenn dieser Schlüssel nicht in der Map existiert, wird er angelegt und mit einem Defaultwert verknüpft (die Multimap bietet dieses Feature nicht, da sie keine eindeutige Zuordnung zwischen einem Schlüssel und seinem Wert herstellen kann).

5 Container-Adapter

Diese Adapter verwenden die Standard-Container, um darauf spezielle Datenstrukturen aufzubauen. Sie bieten ein halbwegs einheitliches Interface zur Verwendung an, unterscheiden sich jedoch in der Definition, welches Element das erste ist.

push(val)
fügt das Element "val" in den unterliegenden Container ein
top()
liefert das erste Element des Containers
pop()
löscht das erste Element des Containers (der Wert muss vorher verarbeitet werden)

Diese Methoden verwenden keinerlei Fehlerkontrolle - wenn versucht wird, das erste Element eines leeren Stacks zu lesen, ergibt sich deshalb undefiniertes Verhalten.

Alle Adapter erwarten, dass der verwendete Containertyp die Operationen bereitstellt, die sie verwenden wollen, andernfalls weigert sich der Compiler, sie zu erzeugen.

5.1 stack

voller Name:

template<typename T,typename C=deque<T> >
class std::stack;

Header:

#include <stack>

Ein Stack nutzt die Memberfunktionen push_back(), back() und pop_back() des unterliegenden Containertyps, um einen LIFO-Speicher zu realisieren - die Elemente werden in der umgekehrten Reihenfolge herausgegeben, in der sie eingefügt wurden.

Als Grundlage für den Stack kann theoretisch jeder sequenzielle Container eingesetzt werden - der Standardtyp ist die deque, weil sie im Gegensatz zum Vektor auch wieder Speicher freigeben kann.

5.2 queue

voller Name:

template<typename T,typename C=deque<T> >
class std::queue;

Header:

#include <queue>

Eine Queue (oder Warteschlange) nutzt die Memberfunktionen push_back(), front(), und pop_front() des unterliegenden Containertyps, um einen FIFO-Speicher zu realisieren - die Elemente werden in derselben Reihenfolge herausgegeben, in der sie eingefügt wurden.

Als Grundlage für die Warteschlange können entweder deques oder Listen verwendet werden, da sie als einzige Standard-Container eine pop_front()-Methode definieren.

5.3 priority_queue

voller Name:

template<typename T,typename C=vector<T>,typename P=less<typename C::value_type> >
class std::priority_queue;

Header:

#include <queue>

Eine Priority-Queue implementiert eine Prioritätswarteschlange auf dem unterliegenden Containertyp - die Elemente werden entsprechend ihrer Größe umgeordnet, sodass jeweils das größte aus der Warteschlange entnommen werden kann. Der Adapter nutzt die Methoden push_back(), front() und pop_back() sowie die Heap-Algorithmen make_heap(), push_heap() und pop_heap(), um seine Elemente zu organisieren.
Das Prädikat P dient dabei zur Feststellung, welches Element größer ist. Genau wie bei den assoziativen Containern muss die verwendete Vergleichsfunktion eine Ordnungsrelation definieren, sonst funktioniert die Priority-Queue nicht richtig.

Als Grundlage für eine Prioritätsschlange können Vektoren, Deques oder Strings verwendet werden - Listen bieten keine Random-Access-Iteratoren und können deshalb nicht mit den Heap-Algorithmen genutzt werden.

6 Zusammenfassung

Es gibt keine "perfekte" Containerklasse für alle Anwendungsbereiche. Deshalb ist es von Vorteil, wenn man die unterschiedlichen Container der STL kennt und auswählen kann, welcher gerade am günstigsten geeignet ist. Dabei ist es auch mit geringem Aufwand möglich, die Container gegeneinander auszutauschen, wenn man zum Beispiel während der Entwicklung feststellt, dass eine deque<> doch bessere Eigenschaften hat als eine list<>.

Container         Vektor          Deque           Liste           Set             Multiset        Map             Multimap
----------------------------------------------------------------------------------------------------------------------------------

Struktur          dynamisches     Array von       verkettete      Binärbaum       Binärbaum       Binärbaum       Binärbaum
                  Array           Arrays          Liste

Elemente          Wert            Wert            Wert            Wert            Wert            Schlüssel+Wert  Schlüssel+Wert

Duplikate         Ja              Ja              Ja              Nein            Ja              Wert            Ja

Direktzugriff     Ja              Ja              Nein            Nein            Nein            über Schlüssel  Nein

Iteratortyp       Random Access   Random Access   Bidirektional   Bidirektional   Bidirektional   Bidirektional   Bidirektional
                                                                  konstant        konstant        Schl. konstant  Schl. konstant
Suche             langsam         langsam         sehr langsam    schnell         schnell         schnell (Schl.) schnell (Schl.)

Einf./Entf.       Ende            Anfang, Ende    überall

invalidiert       Reallocation    immer           nie             nie             nie             nie             nie
Iteratoren etc.

Speicherfreigabe  nie             manchmal        immer           immer           immer           immer           immer

Reservierung      Ja              Nein

Transaktions-     push/pop        push/pop an     alle außer      alle außer      alle außer      alle außer      alle außer
sicher            am Ende         Anfang, Ende    sort            multi-insert    multi-insert    multi-insert    multi-insert

Ausblick

Container sind ein hilfreiches Werkzeug zur Datenorganisation. Aber ihre volle Stärke entwickeln sie erst in Zusammenarbeit mit den Iteratoren und Algorithmen - deshalb werde ich diese Bestandteile der STL im zweiten Teil der Serie ausführlicher behandeln.

Mr. B

Mr. B schrieb:

Ein Vektor reserviert sich in der Regel mehr Speicherplatz als für seine aktuelle Größe notwendig ist. Solange diese Kapazität noch nicht erreicht wird, können push_back()-Operationen in konstanter Zeit durchgeführt werden. Bei Überschreitung der Kapazität werden alle vorhandenen Elemente in einen neuen (entsprechend größeren) Speicherbereich umkopiert - dadurch werden erstens alle Referenzen, Zeiger und Iteratoren in den Vektor ~hier fehlt das verb~ und zweitens kostet diese Operation recht viel Zeit. Deshalb ist es günstig, vor aufwendigen Operationen mit dem Vektor per reserve() genug Speicher anzufordern.

man beachte die Anmerkung!!!!!

// EDIT: Mein tausendster Posting!

CStoll

Inhalt

Teil 1:

Vorbemerkungen
Container
sequenzielle Container
assoziative Container
Container-Adapter
Zusammenfassung

1 Vorbemerkungen

Die Standard Template Library (STL) ist ein wesentlicher Bestandteil von ISO C++, der leider häufig unterschätzt oder falsch eingesetzt wird. [...]

Wie der Name schon andeutet, sind die einzelnen Komponenten der STL als Templates aufgebaut. Das hat den Vorteil, dass sie mit beliebigen Datentypen und Erweiterungen zusammenarbeiten können, ohne auf Vererbungshierarchien Rücksicht nehmen zu müssen. Der Anwender der STL muss lediglich darauf achten, dass die benötigten Operationen von seinen Typen unterstützt werden (z.B. benötigt der Schlüsseltyp einer set<> einen <-Operator oder eine äquivalente Vergleichfunktion).

Die STL kann grob in drei Hauptbestandteile untergliedert werden:

Container dienen zur Aufbewahrung und Verwaltung großer Datensammlungen
Iteratoren navigieren in Containern oder anderen Datenstrukturen
Algorithmen führen verschiedene Operationen auf Container-Elementen aus

Außerdem gibt es einige weitere Funktionen und Klassen in der Standardbibliothek von C++, die nicht direkt der STL zugeordnet werden.

2 Container

Container werden verwendet, um viele gleichartige Objekte gemeinsam unterzubringen und zu verwalten. Alle Containerklassen der STL haben einige gemeinsame Definitionen und Methoden, sodass sie teilweise gegeneinander ausgetauscht werden können. Die wichtigsten davon sind:

Typdefinitionen:

value_type - der Typ der gespeicherten Daten
iterator und const_iterator - der hauseigene Iteratortyp des Containers (für variable bzw. konstante Container)
size_type - ein Typ zur Angabe von Größenwerten (vorzeichenloser Integer)
allocator_type - der Typ der verwendeten Allokator-Klasse

Memberfunktionen

begin() - liefert einen Iterator auf das erste Element des Containers
end() - liefert einen Iterator hinter das letzte Element des Containers
rbegin() - liefert einen Reverse-Iterator auf das letzte Element des Containers (bewegt sich rückwärts über die Elemente)
rend() - liefert Reverse-Iterator vor das erste Element des Containers
size() - liefert die aktuelle Anzahl an Elementen
max_size() - liefert das maximale Fassungsvermögen des Containers
insert(pos,wert) - fügt ein Element an der Stelle 'pos' ein (bei assoziativen Containern ist 'pos' nur ein Hinweis, wo das Element eingefügt werden könnte)
assign(st,en) - weist dem Container den Inhalt des Bereiches [st,en[ zu.
c1.swap(c2) und swap(c1,c2) - vertauscht den Inhalt der Container c1 und c2.
clear() - löscht alle Elemente des Containers
erase(pos) und erase(st,en) - löscht das Element an der Stelle 'pos' bzw. alle Elemente im Bereich [st,en[

Zu den Template-Parametern, die ein Container bekommt, gehört neben dem Wertetyp auch immer ein Allokator-Typ. Dessen Methoden werden verwendet, wenn der Container neuen Speicher anfordern, initialisieren und freigeben will. Der Defaulttyp hierfür ist std::allocator<T> und verwendet die Operatoren new und delete, um den Speicher zu verwalten. Experten können die Speicherverwaltung jedoch auch anders implementieren, indem sie eine eigene Allokator-Klasse schreiben und diese dem Container mitgeben (z.B. kann eine Datenbank oder ein Garbage Collector verwendet oder zurückgegebene Speicherbereiche für schnelleren Zugriff zwischengelagert werden).

3 sequenzielle Container

Sequenzielle Container speichern ihre Elemente in der Reihenfolge, in der sie eingefügt wurden. Natürlich ist es auch möglich, diese Reihenfolge manuell anzupassen, indem man ein Element in der Mitte des Containers einfügt oder die vorhandenen Elemente direkt ändert.

3.1 vector

voller Name:

template<typename T,typename A=allocator<T> >
class std::vector;

Header:

include <vector>

Ein Vektor verwendet einen zusammenhängenden Speicherbereich, in dem er seine Elemente unterbringen kann. Dadurch kann er sehr schnell über den Index auf ein Element zugreifen und neue Elemente am Ende der Sequenz anhängen und löschen. Einfüge- und Lösch-Operationen in der Mitte oder gar am Anfang des Containers benötigen jedoch deutlich mehr Zeit, weil alle nachfolgenden Elemente entsprechend verschoben werden müssen.

Ein Beispiel zum Umgang mit Vektoren:

#include <vector>
#include <iostream>//für Ausgaben
using namespace std;

int main()
{
  vector<int> data;
  data.push_back(1);
  data.push_back(2);
  data.push_back(3);

  //Ausgabe aller Elemente:
  for(int j=0;j<data.size();++j)
    cout<<data[j]<<" ";
  cout<<endl;

  data[1]=20;//direkter Elementzugriff
  data.front()=11;
  data.pop_back();

  data.resize(10,4);

  //noch mal Ausgabe:
  for(int j=0;j<data.size();++j)
    cout<<data[j]<<" ";

  return 0;
}

Ein Vektor reserviert sich in der Regel mehr Speicherplatz als für seine aktuelle Größe notwendig ist. Solange diese Kapazität noch nicht erreicht wird, können push_back()-Operationen in konstanter Zeit durchgeführt werden. Bei Überschreitung der Kapazität werden alle vorhandenen Elemente in einen neuen (entsprechend größeren) Speicherbereich umkopiert - dadurch werden erstens alle Referenzen, Zeiger und Iteratoren in den Vektor ungültig gemacht und zweitens kostet diese Operation recht viel Zeit. Deshalb ist es günstig, vor aufwendigen Operationen mit dem Vektor per reserve() genug Speicher anzufordern.

Achtung: Ein Vektor gibt die einmal reservierte Kapazität erst im Destruktor wieder frei.

Zusätzlich zu den generellen Methoden, seinen Inhalt zu manipulieren, bietet ein Vektor noch einige spezielle Zugriffsfunktionen:

resize(size) und resize(size,val)
ändert die Größe des Vektors auf 'size', indem am Ende Elemente entfernt oder angefügt werden. Neue Elemente werden mit dem Defaultwert des Elementtyps bzw. mit 'val' belegt.
vec[pos] und at(pos)
liefern das Element mit dem Index 'pos' zurück. Der Unterschied zwischen beiden Methoden besteht in der Fehlerbehandlung - der Index-Operator liefert undefinierte Werte, wenn er mit einem Index außerhalb des Intervalls [0,vec.size()[ aufgerufen wird, die Methode at() wirft eine out_of_range Ausnahme, die vom Anwender aufgefangen werden muss.
push_back(val)
hängt das Element 'val' an das Ende des Vektors an.
front() und back()
liefern den Wert des ersten bzw. letzten Elements im Vektor.
pop_back()
löscht das letzte Element aus dem Vektor.
capacity()
liefert die aktuelle Kapazität des Vektors zurück. Dieser Wert gibt an, wie viele Elemente er aufnehmen könnte, ohne neuen Speicher anfordern zu müssen.
reserve(size)
reserviert genug Speicherplatz für mindestens 'size' Elemente. Der neu angelegte Speicherplatz wird nicht initialisiert.

Die Spezialisierung vector<bool> wurde zur Platz sparenden Speicherung von 1-Bit-Werten vorgesehen und bietet ein paar Zusatzmethoden zur Manipulation einzelner Bits:

flip()
invertiert alle Elemente des Vektors (aus true wird false und umgekehrt)
vec[pos].flip() bzw. at(pos).flip
invertiert das Element 'pos' des Vektors

3.2 deque

voller Name:

template<typename T,typename A=allocator<T> >
class std::deque;

Header:

#include <deque>

Eine Deque (Double Ended QUEue) hat insofern Ähnlichkeit mit dem Vektor, dass sie ihren Inhalt auch in zusammenhängendem Speicher organisiert. In der Regel wird jedoch nicht ein einzelner Speicherblock dafür verwendet, sondern mehrere kleinere Blöcke, die beim Durchlaufen der Deque virtuell zusammengefügt werden. Ihr Vorteil ist, dass sie sowohl am Ende als auch am Anfang problemlos erweitert werden kann. Änderungen in der Mitte des Containers sind wie beim vector langsam und sollten besser vermieden werden.

Wenn eine Deque ihre reservierte Kapazität ausgeschöpft hat, reserviert sie einen neuen Speicherbereich, der vor bzw. hinter den vorhandenen Speicherblöcken in die Kontrollstruktur eingefügt wird. Im Gegensatz zum Vektor werden die einzelnen Speicherblöcke auch wieder freigegeben, wenn sie nicht mehr benötigt werden (wann das geschieht, ist normalerweise von der Implementation abhängig).

Eine Deque bietet - mit Ausnahme von capacity() und reserve() - die gleichen Methoden wie ein Vektor, zusätzlich ermöglicht sie:

push_front(val)
hängt das Element 'val' an den Anfang der Schlange an
pop_front()
löscht das erste Element der Schlange

3.3 list

voller Name:

template<typename T,typename A=allocator<T> >
class std::list;

Header:

#include <list>

Im Gegensatz zu Vektoren wird der Inhalt einer List in Form einer doppelt verketteten Liste gespeichert. Auf diese Weise ist es sehr effizient, Werte an beliebiger Stelle einzufügen und wieder zu entfernen. Im Gegenzug ist es sehr langwierig, ein bestimmtes Element anhand seines Index wiederzufinden.

Eine List bietet keinen direkten Elementzugriff über den Index-Operator bzw. at(), aber unterstützt die meisten anderen Funktionen, die auch von Vektoren und Deques zur Verfügung gestellt werden:

resize()
push_back(), pop_back() und back()
push_front(), pop_front() und front()
splice(pos,list), splice(pos,list,spos) bzw. splice(pos,list,sbeg,send)
hängt einzelne Elemente aus 'list' aus und fügt sie vor dem Iterator 'pos' in die Liste ein. Je nach Version wird die komplette Liste 'list', das einzelne Element 'spos' bzw. der Bereich [sbeg,send[ umgehängt.
unique(), sort(), merge(list) und reverse()
Diese Methoden entsprechen den gleichnamigen Algorithmen, können jedoch auf der Listenstruktur effizienter umgesetzt werden als mit den Iterator-basierten Algorithmen (z.B. braucht reverse() nur alle Vorgänger- und Nachfolger-Zeiger zu vertauschen anstatt Elemente umzukopieren).

Ein Beispiel zur Anwendung einer Liste:

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

int main()
{
  list<int> data;
  //Liste füllen
  for(int i=1;i<5;++i) data.push_back(i);
  data.push_front(4711);

  //Ausgabe (nicht über Index möglich, deshalb benötigt man Listen-Iteratoren)
  for(list<int>::iterator pos=data.begin();pos!=data.end();++pos)
    cout<<*pos<<" ";
  cout<<endl;

  list<int>::iterator pos1=data.begin();
  ++pos1;//Iterator auf 2. Element
  data.insert(pos1,0x0815);

  //noch mal Ausgabe:
  for(list<int>::iterator pos=data.begin();pos!=data.end();++pos)
    cout<<*pos<<" ";
  cout<<endl;
}

3.4 string

voller Name:

template<typename C,typename Tr=char_traits<T>,typename A=allocator<C> >
class std::basic_string;

typedef basic_string<char> string;
typedef basic_string<wchar_t> wstring;

Header:

#include <string>

Achtung: Der Header <string.h> existiert ebenfalls, dieser enthält jedoch die char*-Verarbeitungsfunktionen der C-Standardbibliothek.

Strings sind zwar keine offiziellen STL-Container, aber sie bieten genug Unterstützung an, um analog zu den anderen Containern verwendet zu werden. Ihre Hauptverwendung ist die Verwaltung von Zeichenketten, deshalb bieten sie auch Operationen zur Verkettung und zur Zusammenarbeit mit char*-Feldern an.

Mit Strings werde ich mich ausführlicher in einem späteren Artikel beschäftigen.

4 assoziative Container

Assoziative Container sortieren ihre Elemente intern nach ihrer Größe. Dadurch geht es deutlich schneller, einen bestimmten Wert im Container wiederzufinden, allerdings spielt es für die Reihenfolge in der Regel keine Rolle, welches Element zuerst eingefügt wurde.

Im Allgemeinen nutzen alle assoziativen Container die gleiche Grundstruktur (ein balancierter Binärbaum), um ihren Inhalt zu speichern, sie unterscheiden sich lediglich im Typ der eingetragenen Elemente und der Art, wie Duplikate verwaltet werden.

Alle assoziativen Container bieten einige zusätzliche Methoden, um bestimmte Elemente suchen zu können (diese Methoden entsprechen den gleichnamigen Algorithmen, können jedoch in der Baumstruktur effizienter arbeiten als auf einem linear angeordneten Iterator-Bereich):

count(val)
zählt, wie oft das Element (für Sets) bzw. der Schlüsselwert (für Maps) 'val' im Container enthalten ist
find(val)
liefert einen Iterator auf ein Containerelement mit dem (Schlüssel-)Wert 'val' oder end(), wenn es nicht existiert
erase(val)
löscht alle Elemente mit dem (Schlüssel-)Wert 'val' aus dem Container
lower_bound(val), upper_bound(val) und equal_range(val)
liefern die erste, letzte bzw. beide Position im Container (als pair), an der der (Schlüssel-)Wert 'val' in den Container eingefügt werden kann
key_comp() und value_comp()
liefern den Funktor, mit dem die Schlüsselwerte bzw. Elemente des Containers sortiert werden (bei Sets sind beide identisch, bei Maps vergleicht value_comp() die ersten Elemente eines pair mit Hilfe von key_comp())

Jeder assoziative Container besitzt einen eingebauten Vergleichstyp, mit dessen Hilfe die einzelnen Elemente verglichen werden. Dieser wird bei der Definition des Containers als zweiter bzw. dritter Template-Parameter übergeben. Der vorgegebene Typ "less<T>" verwendet < als Vergleichskriterium, sortiert die Elemente also aufsteigend. Aber jeder Funktortyp, der zwei Schlüsselwerte als Parameter akzeptiert und einen bool zurückliefert, kann theoretisch als Vergleichskriterium eingesetzt werden.

Die Vergleichsrelation des Containers wird auch verwendet, um zwei Elemente auf Gleichheit zu testen: x==y ist genau dann wahr, wenn !(x<y)&&!(y<x) gilt.

Wichtig für die Anwendung von sets und maps ist, dass der verwendete Vergleichstyp eine "strict weak ordering" (siehe Wikipedia)) bildet, andernfalls kommt es zur Laufzeit des Programmes zu undefiniertem Verhalten - und kein Compiler kann kontrollieren, ob eine beliebig gegebene Relation diese Anforderungen erfüllt.

4.1 set und multiset

voller Name:

template<typename K,typename P=less<K>,typename A=allocator<K> >
class std::set;
template<typename K,typename P=less<K>,typename A=allocator<K> >
class std::multiset;

Header:

#include <set>

Sets und Multisets speichern einzelne Schlüsselwerte. Ihr Unterschied besteht darin, dass eine Set jeden Wert maximal einmal enthält, während eine Multiset auch Duplikate enthalten kann.

4.2 map und multimap

voller Name:

template<typename K,typename V,typename P=less<K>,typename A=allocator<pair<const K,V> > >
class std::map;
template<typename K,typename V,typename P=less<K>,typename A=allocator<pair<const K,V> > >
class std::multimap;

Maps und Multimaps speichern Paare aus einem Schlüssel und einem zugeordneten Wert. Auch hier besteht der Unterschied darin, dass eine Map eindeutige Schlüssel enthält, während die Schlüssel in der Multimap mehrfach vorkommen können - sogar mit unterschiedlich zugeordneten Werten. Die Elemente in einer (Multi-)Map sind Paare aus konstantem Schlüssel und Wert, wodurch die insert-Operationen etwas komplizierter geschrieben werden müssen:

map<string,int> id_liste;

//(1) - exakter Typ:
id_liste.insert(map<string,int>::value_type("Carsten",4711);

//(2) - pair:
id_liste.insert(pair<string,int>("CStoll",0x0815);

//(3) - make_pair:
id_liste.insert(make_pair("Admin",1);

(im ersten Fall wird der Typ exakt so übergeben, wie die map ihn benötigt, im zweiten und dritten Fall ist eine implizite Typumwandlung von pair<string,int> bzw. pair<const char*,int> nach pair<const string,int> notwendig)

Eine Map bietet als besonderes Extra direkten Elementzugriff über den Index-Operator m[ind]. Im Gegensatz zu einem Array oder Vektor wird hierbei der Wert zurückgegeben, der zum Schlüssel 'ind' zugeordnet wurde. Wenn dieser Schlüssel nicht in der Map existiert, wird er angelegt und mit einem Defaultwert verknüpft (die Multimap bietet dieses Feature nicht, da sie keine eindeutige Zuordnung zwischen einem Schlüssel und seinem Wert herstellen kann).

5 Container-Adapter

Diese Adapter verwenden die Standard-Container, um darauf spezielle Datenstrukturen aufzubauen. Sie bieten ein halbwegs einheitliches Interface zur Verwendung an, unterscheiden sich jedoch in der Definition, welches Element das erste ist.

push(val)
fügt das Element "val" in den unterliegenden Container ein
top()
liefert das erste Element des Containers
pop()
löscht das erste Element des Containers (der Wert muss vorher verarbeitet werden)

Diese Methoden verwenden keinerlei Fehlerkontrolle - wenn versucht wird, das erste Element eines leeren Stacks zu lesen, ergibt sich deshalb undefiniertes Verhalten.

Alle Adapter erwarten, dass der verwendete Containertyp die Operationen bereitstellt, die sie verwenden wollen, andernfalls weigert sich der Compiler, sie zu erzeugen.

5.1 stack

voller Name:

template<typename T,typename C=deque<T> >
class std::stack;

Header:

#include <stack>

Ein Stack nutzt die Memberfunktionen push_back(), back() und pop_back() des unterliegenden Containertyps, um einen LIFO-Speicher zu realisieren - die Elemente werden in der umgekehrten Reihenfolge herausgegeben, in der sie eingefügt wurden.

Als Grundlage für den Stack kann theoretisch jeder sequenzielle Container eingesetzt werden - der Standardtyp ist die deque, weil sie im Gegensatz zum Vektor auch wieder Speicher freigeben kann.

5.2 queue

voller Name:

template<typename T,typename C=deque<T> >
class std::queue;

Header:

#include <queue>

Eine Queue (oder Warteschlange) nutzt die Memberfunktionen push_back(), front(), und pop_front() des unterliegenden Containertyps, um einen FIFO-Speicher zu realisieren - die Elemente werden in derselben Reihenfolge herausgegeben, in der sie eingefügt wurden.

Als Grundlage für die Warteschlange können entweder deques oder Listen verwendet werden, da sie als einzige Standard-Container eine pop_front()-Methode definieren.

5.3 priority_queue

voller Name:

template<typename T,typename C=vector<T>,typename P=less<typename C::value_type> >
class std::priority_queue;

Header:

#include <queue>

Eine Priority-Queue implementiert eine Prioritätswarteschlange auf dem unterliegenden Containertyp - die Elemente werden entsprechend ihrer Größe umgeordnet, sodass jeweils das größte aus der Warteschlange entnommen werden kann. Der Adapter nutzt die Methoden push_back(), front() und pop_back() sowie die Heap-Algorithmen make_heap(), push_heap() und pop_heap(), um seine Elemente zu organisieren.
Das Prädikat P dient dabei zur Feststellung, welches Element größer ist. Genau wie bei den assoziativen Containern muss die verwendete Vergleichsfunktion eine Ordnungsrelation definieren, sonst funktioniert die Priority-Queue nicht richtig.

Als Grundlage für eine Prioritätsschlange können Vektoren, Deques oder Strings verwendet werden - Listen bieten keine Random-Access-Iteratoren und können deshalb nicht mit den Heap-Algorithmen genutzt werden.

6 Zusammenfassung

Es gibt keine "perfekte" Containerklasse für alle Anwendungsbereiche. Deshalb ist es von Vorteil, wenn man die unterschiedlichen Container der STL kennt und auswählen kann, welcher gerade am günstigsten geeignet ist. Dabei ist es auch mit geringem Aufwand möglich, die Container gegeneinander auszutauschen, wenn man zum Beispiel während der Entwicklung feststellt, dass eine deque<> doch bessere Eigenschaften hat als eine list<>.

Container         Vektor          Deque           Liste           Set             Multiset        Map             Multimap
----------------------------------------------------------------------------------------------------------------------------------

Struktur          dynamisches     Array von       verkettete      Binärbaum       Binärbaum       Binärbaum       Binärbaum
                  Array           Arrays          Liste

Elemente          Wert            Wert            Wert            Wert            Wert            Schlüssel+Wert  Schlüssel+Wert

Duplikate         Ja              Ja              Ja              Nein            Ja              Wert            Ja

Direktzugriff     Ja              Ja              Nein            Nein            Nein            über Schlüssel  Nein

Iteratortyp       Random Access   Random Access   Bidirektional   Bidirektional   Bidirektional   Bidirektional   Bidirektional
                                                                  konstant        konstant        Schl. konstant  Schl. konstant
Suche             langsam         langsam         sehr langsam    schnell         schnell         schnell (Schl.) schnell (Schl.)

Einf./Entf.       Ende            Anfang, Ende    überall

invalidiert       Reallocation    immer           nie             nie             nie             nie             nie
Iteratoren etc.

Speicherfreigabe  nie             manchmal        immer           immer           immer           immer           immer

Reservierung      Ja              Nein

Transaktions-     push/pop        push/pop an     alle außer      alle außer      alle außer      alle außer      alle außer
sicher            am Ende         Anfang, Ende    sort            multi-insert    multi-insert    multi-insert    multi-insert

Ausblick

Container sind ein hilfreiches Werkzeug zur Datenorganisation. Aber ihre volle Stärke entwickeln sie erst in Zusammenarbeit mit den Iteratoren und Algorithmen - deshalb werde ich diese Bestandteile der STL im zweiten Teil der Serie ausführlicher behandeln.

Mr. B

CStoll schrieb:

Ein Vektor reserviert sich in der Regel mehr Speicherplatz als für seine aktuelle Größe notwendig ist. Solange diese Kapazität noch nicht erreicht wird, können push_back()-Operationen in konstanter Zeit durchgeführt werden. Bei Überschreitung der Kapazität werden alle vorhandenen Elemente in einen neuen (entsprechend größeren) Speicherbereich umkopiert - dadurch werden erstens alle Referenzen, Zeiger und Iteratoren im Vektor ungültig gemacht und zweitens kostet diese Operation recht viel Zeit. Deshalb ist es günstig, vor aufwendigen Operationen mit dem Vektor per reserve() genug Speicher anzufordern.

Jetzt haste da n Kasusfehler reingehauen...

Mr. B

CStoll

Die Pointer etc. stehen außerhalb des Vektors, zeigen aber dort rein - deswegen "in den Vektor". ("im Vektor" sind für mich interne Verwaltungsdaten der Vektor-Klasse - und die kommen problemlos mit einer Reallokierung zurecht)

Vorschlag, bevor wir uns hier gegenseitig den Duden um die Ohren hauen: Was hältst du von der Formulierung "Referenzen, Zeiger und Iteratoren auf Elemente des Vektors"?

estartu

CStoll schrieb:

Was hältst du von der Formulierung "Referenzen, Zeiger und Iteratoren auf Elemente des Vektors"?

Von der halte ICH sehr viel, denn für mich hat sich der komplette Sinn des Satzes geändert und vorher hatte ich das wohl falsch verstanden.

CStoll

Inhalt

Teil 1:

Vorbemerkungen
Container
sequenzielle Container
assoziative Container
Container-Adapter
Zusammenfassung

1 Vorbemerkungen

Die Standard Template Library (STL) ist ein wesentlicher Bestandteil von ISO C++, der leider häufig unterschätzt oder falsch eingesetzt wird. [...]

Wie der Name schon andeutet, sind die einzelnen Komponenten der STL als Templates aufgebaut. Das hat den Vorteil, dass sie mit beliebigen Datentypen und Erweiterungen zusammenarbeiten können, ohne auf Vererbungshierarchien Rücksicht nehmen zu müssen. Der Anwender der STL muss lediglich darauf achten, dass die benötigten Operationen von seinen Typen unterstützt werden (z.B. benötigt der Schlüsseltyp einer set<> einen <-Operator oder eine äquivalente Vergleichfunktion).

Die STL kann grob in drei Hauptbestandteile untergliedert werden:

Container dienen zur Aufbewahrung und Verwaltung großer Datensammlungen
Iteratoren navigieren in Containern oder anderen Datenstrukturen
Algorithmen führen verschiedene Operationen auf Container-Elementen aus

Außerdem gibt es einige weitere Funktionen und Klassen in der Standardbibliothek von C++, die nicht direkt der STL zugeordnet werden.

2 Container

Container werden verwendet, um viele gleichartige Objekte gemeinsam unterzubringen und zu verwalten. Alle Containerklassen der STL haben einige gemeinsame Definitionen und Methoden, sodass sie teilweise gegeneinander ausgetauscht werden können. Die wichtigsten davon sind:

Typdefinitionen:

value_type - der Typ der gespeicherten Daten
iterator und const_iterator - der hauseigene Iteratortyp des Containers (für variable bzw. konstante Container)
size_type - ein Typ zur Angabe von Größenwerten (vorzeichenloser Integer)
allocator_type - der Typ der verwendeten Allokator-Klasse

Memberfunktionen

begin() - liefert einen Iterator auf das erste Element des Containers
end() - liefert einen Iterator hinter das letzte Element des Containers
rbegin() - liefert einen Reverse-Iterator auf das letzte Element des Containers (bewegt sich rückwärts über die Elemente)
rend() - liefert Reverse-Iterator vor das erste Element des Containers
size() - liefert die aktuelle Anzahl an Elementen
max_size() - liefert das maximale Fassungsvermögen des Containers
insert(pos,wert) - fügt ein Element an der Stelle 'pos' ein (bei assoziativen Containern ist 'pos' nur ein Hinweis, wo das Element eingefügt werden könnte)
assign(st,en) - weist dem Container den Inhalt des Bereiches [st,en[ zu.
c1.swap(c2) und swap(c1,c2) - vertauscht den Inhalt der Container c1 und c2.
clear() - löscht alle Elemente des Containers
erase(pos) und erase(st,en) - löscht das Element an der Stelle 'pos' bzw. alle Elemente im Bereich [st,en[

Zu den Template-Parametern, die ein Container bekommt, gehört neben dem Wertetyp auch immer ein Allokator-Typ. Dessen Methoden werden verwendet, wenn der Container neuen Speicher anfordern, initialisieren und freigeben will. Der Defaulttyp hierfür ist std::allocator<T> und verwendet die Operatoren new und delete, um den Speicher zu verwalten. Experten können die Speicherverwaltung jedoch auch anders implementieren, indem sie eine eigene Allokator-Klasse schreiben und diese dem Container mitgeben (z.B. kann eine Datenbank oder ein Garbage Collector verwendet oder zurückgegebene Speicherbereiche für schnelleren Zugriff zwischengelagert werden).

3 sequenzielle Container

Sequenzielle Container speichern ihre Elemente in der Reihenfolge, in der sie eingefügt wurden. Natürlich ist es auch möglich, diese Reihenfolge manuell anzupassen, indem man ein Element in der Mitte des Containers einfügt oder die vorhandenen Elemente direkt ändert.

3.1 vector

voller Name:

template<typename T,typename A=allocator<T> >
class std::vector;

Header:

include <vector>

Ein Vektor verwendet einen zusammenhängenden Speicherbereich, in dem er seine Elemente unterbringen kann. Dadurch kann er sehr schnell über den Index auf ein Element zugreifen und neue Elemente am Ende der Sequenz anhängen und löschen. Einfüge- und Lösch-Operationen in der Mitte oder gar am Anfang des Containers benötigen jedoch deutlich mehr Zeit, weil alle nachfolgenden Elemente entsprechend verschoben werden müssen.

Ein Beispiel zum Umgang mit Vektoren:

#include <vector>
#include <iostream>//für Ausgaben
using namespace std;

int main()
{
  vector<int> data;
  data.push_back(1);
  data.push_back(2);
  data.push_back(3);

  //Ausgabe aller Elemente:
  for(int j=0;j<data.size();++j)
    cout<<data[j]<<" ";
  cout<<endl;

  data[1]=20;//direkter Elementzugriff
  data.front()=11;
  data.pop_back();

  data.resize(10,4);

  //noch mal Ausgabe:
  for(int j=0;j<data.size();++j)
    cout<<data[j]<<" ";

  return 0;
}

Ein Vektor reserviert sich in der Regel mehr Speicherplatz als für seine aktuelle Größe notwendig ist. Solange diese Kapazität noch nicht erreicht wird, können push_back()-Operationen in konstanter Zeit durchgeführt werden. Bei Überschreitung der Kapazität werden alle vorhandenen Elemente in einen neuen (entsprechend größeren) Speicherbereich umkopiert - dadurch werden erstens alle Referenzen, Zeiger und Iteratoren auf Elemente des Vektors ungültig gemacht und zweitens kostet diese Operation recht viel Zeit. Deshalb ist es günstig, vor aufwendigen Operationen mit dem Vektor per reserve() genug Speicher anzufordern.

Achtung: Ein Vektor gibt die einmal reservierte Kapazität erst im Destruktor wieder frei.

Zusätzlich zu den generellen Methoden, seinen Inhalt zu manipulieren, bietet ein Vektor noch einige spezielle Zugriffsfunktionen:

resize(size) und resize(size,val)
ändert die Größe des Vektors auf 'size', indem am Ende Elemente entfernt oder angefügt werden. Neue Elemente werden mit dem Defaultwert des Elementtyps bzw. mit 'val' belegt.
vec[pos] und at(pos)
liefern das Element mit dem Index 'pos' zurück. Der Unterschied zwischen beiden Methoden besteht in der Fehlerbehandlung - der Index-Operator liefert undefinierte Werte, wenn er mit einem Index außerhalb des Intervalls [0,vec.size()[ aufgerufen wird, die Methode at() wirft eine out_of_range Ausnahme, die vom Anwender aufgefangen werden muss.
push_back(val)
hängt das Element 'val' an das Ende des Vektors an.
front() und back()
liefern den Wert des ersten bzw. letzten Elements im Vektor.
pop_back()
löscht das letzte Element aus dem Vektor.
capacity()
liefert die aktuelle Kapazität des Vektors zurück. Dieser Wert gibt an, wie viele Elemente er aufnehmen könnte, ohne neuen Speicher anfordern zu müssen.
reserve(size)
reserviert genug Speicherplatz für mindestens 'size' Elemente. Der neu angelegte Speicherplatz wird nicht initialisiert.

Die Spezialisierung vector<bool> wurde zur Platz sparenden Speicherung von 1-Bit-Werten vorgesehen und bietet ein paar Zusatzmethoden zur Manipulation einzelner Bits:

flip()
invertiert alle Elemente des Vektors (aus true wird false und umgekehrt)
vec[pos].flip() bzw. at(pos).flip
invertiert das Element 'pos' des Vektors

3.2 deque

voller Name:

template<typename T,typename A=allocator<T> >
class std::deque;

Header:

#include <deque>

Eine Deque (Double Ended QUEue) hat insofern Ähnlichkeit mit dem Vektor, dass sie ihren Inhalt auch in zusammenhängendem Speicher organisiert. In der Regel wird jedoch nicht ein einzelner Speicherblock dafür verwendet, sondern mehrere kleinere Blöcke, die beim Durchlaufen der Deque virtuell zusammengefügt werden. Ihr Vorteil ist, dass sie sowohl am Ende als auch am Anfang problemlos erweitert werden kann. Änderungen in der Mitte des Containers sind wie beim vector langsam und sollten besser vermieden werden.

Wenn eine Deque ihre reservierte Kapazität ausgeschöpft hat, reserviert sie einen neuen Speicherbereich, der vor bzw. hinter den vorhandenen Speicherblöcken in die Kontrollstruktur eingefügt wird. Im Gegensatz zum Vektor werden die einzelnen Speicherblöcke auch wieder freigegeben, wenn sie nicht mehr benötigt werden (wann das geschieht, ist normalerweise von der Implementation abhängig).

Eine Deque bietet - mit Ausnahme von capacity() und reserve() - die gleichen Methoden wie ein Vektor, zusätzlich ermöglicht sie:

push_front(val)
hängt das Element 'val' an den Anfang der Schlange an
pop_front()
löscht das erste Element der Schlange

3.3 list

voller Name:

template<typename T,typename A=allocator<T> >
class std::list;

Header:

#include <list>

Im Gegensatz zu Vektoren wird der Inhalt einer List in Form einer doppelt verketteten Liste gespeichert. Auf diese Weise ist es sehr effizient, Werte an beliebiger Stelle einzufügen und wieder zu entfernen. Im Gegenzug ist es sehr langwierig, ein bestimmtes Element anhand seines Index wiederzufinden.

Eine List bietet keinen direkten Elementzugriff über den Index-Operator bzw. at(), aber unterstützt die meisten anderen Funktionen, die auch von Vektoren und Deques zur Verfügung gestellt werden:

resize()
push_back(), pop_back() und back()
push_front(), pop_front() und front()
splice(pos,list), splice(pos,list,spos) bzw. splice(pos,list,sbeg,send)
hängt einzelne Elemente aus 'list' aus und fügt sie vor dem Iterator 'pos' in die Liste ein. Je nach Version wird die komplette Liste 'list', das einzelne Element 'spos' bzw. der Bereich [sbeg,send[ umgehängt.
unique(), sort(), merge(list) und reverse()
Diese Methoden entsprechen den gleichnamigen Algorithmen, können jedoch auf der Listenstruktur effizienter umgesetzt werden als mit den Iterator-basierten Algorithmen (z.B. braucht reverse() nur alle Vorgänger- und Nachfolger-Zeiger zu vertauschen anstatt Elemente umzukopieren).

Ein Beispiel zur Anwendung einer Liste:

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

int main()
{
  list<int> data;
  //Liste füllen
  for(int i=1;i<5;++i) data.push_back(i);
  data.push_front(4711);

  //Ausgabe (nicht über Index möglich, deshalb benötigt man Listen-Iteratoren)
  for(list<int>::iterator pos=data.begin();pos!=data.end();++pos)
    cout<<*pos<<" ";
  cout<<endl;

  list<int>::iterator pos1=data.begin();
  ++pos1;//Iterator auf 2. Element
  data.insert(pos1,0x0815);

  //noch mal Ausgabe:
  for(list<int>::iterator pos=data.begin();pos!=data.end();++pos)
    cout<<*pos<<" ";
  cout<<endl;
}

3.4 string

voller Name:

template<typename C,typename Tr=char_traits<T>,typename A=allocator<C> >
class std::basic_string;

typedef basic_string<char> string;
typedef basic_string<wchar_t> wstring;

Header:

#include <string>

Achtung: Der Header <string.h> existiert ebenfalls, dieser enthält jedoch die char*-Verarbeitungsfunktionen der C-Standardbibliothek.

Strings sind zwar keine offiziellen STL-Container, aber sie bieten genug Unterstützung an, um analog zu den anderen Containern verwendet zu werden. Ihre Hauptverwendung ist die Verwaltung von Zeichenketten, deshalb bieten sie auch Operationen zur Verkettung und zur Zusammenarbeit mit char*-Feldern an.

Mit Strings werde ich mich ausführlicher in einem späteren Artikel beschäftigen.

4 assoziative Container

Assoziative Container sortieren ihre Elemente intern nach ihrer Größe. Dadurch geht es deutlich schneller, einen bestimmten Wert im Container wiederzufinden, allerdings spielt es für die Reihenfolge in der Regel keine Rolle, welches Element zuerst eingefügt wurde.

Im Allgemeinen nutzen alle assoziativen Container die gleiche Grundstruktur (ein balancierter Binärbaum), um ihren Inhalt zu speichern, sie unterscheiden sich lediglich im Typ der eingetragenen Elemente und der Art, wie Duplikate verwaltet werden.

Alle assoziativen Container bieten einige zusätzliche Methoden, um bestimmte Elemente suchen zu können (diese Methoden entsprechen den gleichnamigen Algorithmen, können jedoch in der Baumstruktur effizienter arbeiten als auf einem linear angeordneten Iterator-Bereich):

count(val)
zählt, wie oft das Element (für Sets) bzw. der Schlüsselwert (für Maps) 'val' im Container enthalten ist
find(val)
liefert einen Iterator auf ein Containerelement mit dem (Schlüssel-)Wert 'val' oder end(), wenn es nicht existiert
erase(val)
löscht alle Elemente mit dem (Schlüssel-)Wert 'val' aus dem Container
lower_bound(val), upper_bound(val) und equal_range(val)
liefern die erste, letzte bzw. beide Position im Container (als pair), an der der (Schlüssel-)Wert 'val' in den Container eingefügt werden kann
key_comp() und value_comp()
liefern den Funktor, mit dem die Schlüsselwerte bzw. Elemente des Containers sortiert werden (bei Sets sind beide identisch, bei Maps vergleicht value_comp() die ersten Elemente eines pair mit Hilfe von key_comp())

Jeder assoziative Container besitzt einen eingebauten Vergleichstyp, mit dessen Hilfe die einzelnen Elemente verglichen werden. Dieser wird bei der Definition des Containers als zweiter bzw. dritter Template-Parameter übergeben. Der vorgegebene Typ "less<T>" verwendet < als Vergleichskriterium, sortiert die Elemente also aufsteigend. Aber jeder Funktortyp, der zwei Schlüsselwerte als Parameter akzeptiert und einen bool zurückliefert, kann theoretisch als Vergleichskriterium eingesetzt werden.

Die Vergleichsrelation des Containers wird auch verwendet, um zwei Elemente auf Gleichheit zu testen: x==y ist genau dann wahr, wenn !(x<y)&&!(y<x) gilt.

Wichtig für die Anwendung von sets und maps ist, dass der verwendete Vergleichstyp eine "strict weak ordering" (siehe Wikipedia)) bildet, andernfalls kommt es zur Laufzeit des Programmes zu undefiniertem Verhalten - und kein Compiler kann kontrollieren, ob eine beliebig gegebene Relation diese Anforderungen erfüllt.

4.1 set und multiset

voller Name:

template<typename K,typename P=less<K>,typename A=allocator<K> >
class std::set;
template<typename K,typename P=less<K>,typename A=allocator<K> >
class std::multiset;

Header:

#include <set>

Sets und Multisets speichern einzelne Schlüsselwerte. Ihr Unterschied besteht darin, dass eine Set jeden Wert maximal einmal enthält, während eine Multiset auch Duplikate enthalten kann.

4.2 map und multimap

voller Name:

template<typename K,typename V,typename P=less<K>,typename A=allocator<pair<const K,V> > >
class std::map;
template<typename K,typename V,typename P=less<K>,typename A=allocator<pair<const K,V> > >
class std::multimap;

Maps und Multimaps speichern Paare aus einem Schlüssel und einem zugeordneten Wert. Auch hier besteht der Unterschied darin, dass eine Map eindeutige Schlüssel enthält, während die Schlüssel in der Multimap mehrfach vorkommen können - sogar mit unterschiedlich zugeordneten Werten. Die Elemente in einer (Multi-)Map sind Paare aus konstantem Schlüssel und Wert, wodurch die insert-Operationen etwas komplizierter geschrieben werden müssen:

map<string,int> id_liste;

//(1) - exakter Typ:
id_liste.insert(map<string,int>::value_type("Carsten",4711);

//(2) - pair:
id_liste.insert(pair<string,int>("CStoll",0x0815);

//(3) - make_pair:
id_liste.insert(make_pair("Admin",1);

(im ersten Fall wird der Typ exakt so übergeben, wie die map ihn benötigt, im zweiten und dritten Fall ist eine implizite Typumwandlung von pair<string,int> bzw. pair<const char*,int> nach pair<const string,int> notwendig)

Eine Map bietet als besonderes Extra direkten Elementzugriff über den Index-Operator m[ind]. Im Gegensatz zu einem Array oder Vektor wird hierbei der Wert zurückgegeben, der zum Schlüssel 'ind' zugeordnet wurde. Wenn dieser Schlüssel nicht in der Map existiert, wird er angelegt und mit einem Defaultwert verknüpft (die Multimap bietet dieses Feature nicht, da sie keine eindeutige Zuordnung zwischen einem Schlüssel und seinem Wert herstellen kann).

5 Container-Adapter

Diese Adapter verwenden die Standard-Container, um darauf spezielle Datenstrukturen aufzubauen. Sie bieten ein halbwegs einheitliches Interface zur Verwendung an, unterscheiden sich jedoch in der Definition, welches Element das erste ist.

push(val)
fügt das Element "val" in den unterliegenden Container ein
top()
liefert das erste Element des Containers
pop()
löscht das erste Element des Containers (der Wert muss vorher verarbeitet werden)

Diese Methoden verwenden keinerlei Fehlerkontrolle - wenn versucht wird, das erste Element eines leeren Stacks zu lesen, ergibt sich deshalb undefiniertes Verhalten.

Alle Adapter erwarten, dass der verwendete Containertyp die Operationen bereitstellt, die sie verwenden wollen, andernfalls weigert sich der Compiler, sie zu erzeugen.

5.1 stack

voller Name:

template<typename T,typename C=deque<T> >
class std::stack;

Header:

#include <stack>

Ein Stack nutzt die Memberfunktionen push_back(), back() und pop_back() des unterliegenden Containertyps, um einen LIFO-Speicher zu realisieren - die Elemente werden in der umgekehrten Reihenfolge herausgegeben, in der sie eingefügt wurden.

Als Grundlage für den Stack kann theoretisch jeder sequenzielle Container eingesetzt werden - der Standardtyp ist die deque, weil sie im Gegensatz zum Vektor auch wieder Speicher freigeben kann.

5.2 queue

voller Name:

template<typename T,typename C=deque<T> >
class std::queue;

Header:

#include <queue>

Eine Queue (oder Warteschlange) nutzt die Memberfunktionen push_back(), front(), und pop_front() des unterliegenden Containertyps, um einen FIFO-Speicher zu realisieren - die Elemente werden in derselben Reihenfolge herausgegeben, in der sie eingefügt wurden.

Als Grundlage für die Warteschlange können entweder deques oder Listen verwendet werden, da sie als einzige Standard-Container eine pop_front()-Methode definieren.

5.3 priority_queue

voller Name:

template<typename T,typename C=vector<T>,typename P=less<typename C::value_type> >
class std::priority_queue;

Header:

#include <queue>

Eine Priority-Queue implementiert eine Prioritätswarteschlange auf dem unterliegenden Containertyp - die Elemente werden entsprechend ihrer Größe umgeordnet, sodass jeweils das größte aus der Warteschlange entnommen werden kann. Der Adapter nutzt die Methoden push_back(), front() und pop_back() sowie die Heap-Algorithmen make_heap(), push_heap() und pop_heap(), um seine Elemente zu organisieren.
Das Prädikat P dient dabei zur Feststellung, welches Element größer ist. Genau wie bei den assoziativen Containern muss die verwendete Vergleichsfunktion eine Ordnungsrelation definieren, sonst funktioniert die Priority-Queue nicht richtig.

Als Grundlage für eine Prioritätsschlange können Vektoren, Deques oder Strings verwendet werden - Listen bieten keine Random-Access-Iteratoren und können deshalb nicht mit den Heap-Algorithmen genutzt werden.

6 Zusammenfassung

Es gibt keine "perfekte" Containerklasse für alle Anwendungsbereiche. Deshalb ist es von Vorteil, wenn man die unterschiedlichen Container der STL kennt und auswählen kann, welcher gerade am günstigsten geeignet ist. Dabei ist es auch mit geringem Aufwand möglich, die Container gegeneinander auszutauschen, wenn man zum Beispiel während der Entwicklung feststellt, dass eine deque<> doch bessere Eigenschaften hat als eine list<>.

Container         Vektor          Deque           Liste           Set             Multiset        Map             Multimap
----------------------------------------------------------------------------------------------------------------------------------

Struktur          dynamisches     Array von       verkettete      Binärbaum       Binärbaum       Binärbaum       Binärbaum
                  Array           Arrays          Liste

Elemente          Wert            Wert            Wert            Wert            Wert            Schlüssel+Wert  Schlüssel+Wert

Duplikate         Ja              Ja              Ja              Nein            Ja              Wert            Ja

Direktzugriff     Ja              Ja              Nein            Nein            Nein            über Schlüssel  Nein

Iteratortyp       Random Access   Random Access   Bidirektional   Bidirektional   Bidirektional   Bidirektional   Bidirektional
                                                                  konstant        konstant        Schl. konstant  Schl. konstant
Suche             langsam         langsam         sehr langsam    schnell         schnell         schnell (Schl.) schnell (Schl.)

Einf./Entf.       Ende            Anfang, Ende    überall

invalidiert       Reallocation    immer           nie             nie             nie             nie             nie
Iteratoren etc.

Speicherfreigabe  nie             manchmal        immer           immer           immer           immer           immer

Reservierung      Ja              Nein

Transaktions-     push/pop        push/pop an     alle außer      alle außer      alle außer      alle außer      alle außer
sicher            am Ende         Anfang, Ende    sort            multi-insert    multi-insert    multi-insert    multi-insert

Ausblick

Container sind ein hilfreiches Werkzeug zur Datenorganisation. Aber ihre volle Stärke entwickeln sie erst in Zusammenarbeit mit den Iteratoren und Algorithmen - deshalb werde ich diese Bestandteile der STL im zweiten Teil der Serie ausführlicher behandeln.[/quote]

Mr. B

CStoll schrieb:

Die Pointer etc. stehen außerhalb des Vektors, zeigen aber dort rein - deswegen "in den Vektor". ("im Vektor" sind für mich interne Verwaltungsdaten der Vektor-Klasse - und die kommen problemlos mit einer Reallokierung zurecht)

Vorschlag, bevor wir uns hier gegenseitig den Duden um die Ohren hauen: Was hältst du von der Formulierung "Referenzen, Zeiger und Iteratoren auf Elemente des Vektors"?

Was du damit ausdrücken willst, weiß ich nicht, denn spätestens nach der Hälfte der Artikel kann ich sowieso nicht mehr folgen, weil ich mich einfach zu wenig mit der Programmierung beschäftige, weil ich keine Zeit habe.
Was du damit also ausdrücken willst, ist mir so gesehen egal, nur kann man etwas nicht in etwas ungültig machen. Rein grammatikalisch gesehen ist mir so etwas noch nie begegnet. Kann natürlich sein, dass das n Ausdruck in der Programmierung ist. Dann nehme ich alles zurück und behaupte dasselbige nochmal

Nein, ernsthaft; wenn man das so sagt in der Fachsprache, dann isses okay. Müsst ihr entscheiden. mir ist es jedenfalls noch nie begegnet.

Mr. B