Programmieren - Standard Template Library (STL)

Transcrição

FB Informatik
Prof. Dr. R.Nitsch
Programmieren - Standard Template Library (STL)
Reiner Nitsch
 [email protected]
Literatur zu STL
FB Informatik
Prof. Dr. R.Nitsch
Ulrich Breymann
Designing Components with the C++ STL
(2000)
ISBN 0 201 67488 2
Free download of the revised and improved edition as a PDFfile for non-commercial purposes:
http://www.ubreymann.de/stlbe.html
David R. Musser, Gillmer J. Derge, Atul Saini.
STL Tutorial and Reference Guide: C++ Programming with the
Standard Template Library, 2nd Edition (2001)
ISBN: 0201379236
Price: ~50$
07.12.2012
C++ Standard Template Library (STL)
2
Begriffsdefinitionen
FB Informatik
Prof. Dr. R.Nitsch
 Behälterklassen (Container)
 Container sind Objekte, die andere Objekte speichern und verwalten (Einfügen,
Lesen, Löschen, Kopieren, Suchen, Sortieren, …)
 Die Container enthalten i.A. Objekte desselben Typs, wobei die Objekte auch Zeiger
sein können.
 Die STL bietet 2 Container-Kategorien an:
 Sequenzcontainer
 Assoziative Container: Die Daten in diesen Containern werden nicht mittels Index
adressiert sondern über einen Schlüsselwert beliebigenTyps.
Beispiel: Deutsch-Englisches Wörterbuch. Die deutschen Wörter bilden den Schlüsselwert zum
Auffinden der gespeicherten Daten (=englische Wörter):
cout << dict_ge_en["Sprache"] << endl;
Ausgabe: language
Andere Bezeichner für Assoziative Container sind Dictionary (Smalltalk, Python, ObjectiveC, PostScript, C#), einer Map (C++, Java), Hash (Perl, Ruby) oder einer Hashtable/Hashmap
(Java, Windows PowerShell)
 Gemeinsamkeiten dieser Container
Konstruktoren, Destruktor, Methoden für Elementzugriff, Einfüge- und Lösch-Operationen
eigene Speicherverwaltung (wachsen, wenn der reservierte Speicher nicht mehr ausreicht)
07.12.2012
3
Grundsätzliches zu Containern
FB Informatik
Prof. Dr. R.Nitsch
 Sequentielles Aufsuchen der Elemente eines Containers
 „Sequentiell“ impliziert, dass eine Reihenfolge definiert und dem Anwender bekannt sein
muss.
 Um die interne Datenstruktur zu verbergen, werden i.A. „Iteratoren“ als Mittel zur
Kontrollabstraktion eingesetzt.
 STL-Iteratoren
 Sind Objekte, die wie Pointer anzuwenden sind
 bieten lesenden und schreibenden Zugriff auf den Containerinhalt
 Können von einem zu einem anderen Containerelement bewegt werden, wobei die Details der
Bewegung verborgen bleiben (Kontrollabstraktion)
 Erlauben die Formulierung von Algorithmen, die Containerinhalte verarbeiten, unabhängig
von der jeweiligen Datenrepräsentation (generische Algorithmen)
07.12.2012
4
FB Informatik
Prof. Dr. R.Nitsch
Was soll ein Container enthalten?
 Bei der Wertsemantik legt der Container von allen zum Einfügen übergebenen
Nutzdaten jeweils eine Kopie an, und speichert die Kopie. Eine danach erfolgte
Änderung der Orginale durch den Aufrufer wirkt sich nicht auf die Kopien im
Container aus.
 Bei der Referenzsemantik werden effektiv nur Referenzen auf die einzufügenden
Objekte gespeichert. Eine Änderung der Orginale durch den Aufrufer wirkt sich
auch nach dem Einfügen noch auf den Inhalt des Containers aus.
 Alle STL-Container arbeiten mit Wert-Semantik. Aber auch Referenzsemantik lässt
sich darstellen, indem den Containern lediglich Pointer mit den Adressen der Daten
übergeben werden.
07.12.2012
5
FB Informatik
Prof. Dr. R.Nitsch
 Wachstum von Behältern
 Jedes Wachsen bedeutet Anfordern (Allokieren) eines größeren Speicherbereichs,
Umkopieren und Löschen des bisherigen Speicherbereichs (Zeitaufwändig)
 Zugriff auf Container-Elemente
 Soll ein Container beim Lesen seiner Elemente vom Typ T Referenzen (T&) zurückgeben?
Kein Kopieraufwand .
Missbrauch möglich: Ändern des Werts eines Elements in einem sortierten Container über die
Referenz .
Bei dynamisch wachsenden Containern können Referenzen und Iteratoren ungültig werden, wenn die
Elemente automatisch in einen größeren zusammenhängenden Speicherbereich umkopiert werden .
 Container, die Referenzen/Zeiger zurück geben, sollten ihre Elemente im
Hauptspeicher möglichst nicht verschieben müssen, also auch nicht
wachsen müssen.
07.12.2012
6
Standard Template Library (STL) Components Overview
FB Informatik
Prof. Dr. R.Nitsch
 Die C++ STL enthält mehrere typparametrisierte
Container Klassen
, Header <vector>
, Header <deque>
, Header <list>
, Header <set>
, Header <map>
07.12.2012
Algorithm
OutputIterator
 Diese Container verwenden die Wert-Semantik, d.h. sie
kopieren intern die einzufügenden Elemente anstatt nur
eine Referenz darauf abzuspeichern.
 Die C++ STL enthält mehrere typparametrisierte
Algorithmen (ca. 70 verschiedene ) im Header
<algorithm>, die hinsichtlich Laufzeiteffizienz optimiert
sind.
 Die STL definiert mehrere Funktionsobjekte im Header
<functional>, um verschiedene Algorithmen an
unterschiedliche Aufgabenstellungen anzupassen.
Container
(list)
Container
(vector)
InputIterator
vector<T>
deque<T>
list<T>
set<T>
map<Key,T>
…
InputIterator






Container
(map)
7
Container - Übersicht
FB Informatik
Prof. Dr. R.Nitsch
Container
unordered_multiset
unordered_set
Sequenz-Container
array
vector
deque
stack
queue
priority queue
set
map
■1 ●1
▲1
Menge von
Unikaten
neu:
unordered_map
Assoziative Container
Sequenz-Adapter
list
unordered_multimap
multiset
■4 ●6
▲13
forward_list
auch Duplikate
■1 ●1
Keys ▲1
multimap
☺☼
3■ ●
3▲ 2
 
(einfach verkettet)
☺ Data
☼
◊

☼
♂
◊
Siehe auch: http://msdn.microsoft.com/library/default.asp?url=/library/en-us/vclang98/html/LIB_CONT.asp
07.12.2012
8
Alle STL-Container: Anforderungen an die Objekte
 Die Objekte (Elemente) eines Containers müssen
kopierbar (copy-constructable) sein und die erzeugte
Kopie muss den gleichen 'Wert' wie das Original besitzen.
Dieses Fähigkeit erhalten Objekte durch den KopierKonstruktor.
 Die Objekte müssen zuweisbar (assignable) sein. Hierzu
muss die Klasse den Zuweisungsoperator definieren, wenn
die Standard-Variante nicht ausreicht.
 Die Objekte müssen zerstörbar (destructable) sein.
Container entfernen ihre Elemente durch den impliziten
Aufruf des Element-Destruktors.
Aber: Wenn der Container Pointer speichert, wird auch
nur der von diesen belegte Speicherplatz freigegeben.
Die Destruktoren der referenzierten Objekte muss also
das Kompositum aufrufen, dessen Komponente der
Container.
 Alle diese Operationen werden implizit durch den
Compiler für jede Klasse generiert. Man muss diese
Operationen also nur für nicht-triviale Klassen (solche,
die z.B. dynamische Daten oder andere Objekte
enthalten) selbst implementieren.
07.12.2012
FB Informatik
Prof. Dr. R.Nitsch
class Any {
... // Private Daten
public:
// Kopierkonstruktor
Any(const Any& src);
...
};
class Any {
public:
// Überladener = Operator
Any & operator=(const Any &rhs);
...
};
class Any {
public:
// Destruktor
~ Any();
...
};
9
Alle STL-Container: Anforderungen an die Objekte
 Einige Algorithmen funktionieren nur,
wenn die Objekte den operator==
implementieren. Beispiel: std::find.
 Algorithmen und Container mit Sortierfunktionen setzen den operator< voraus.
 Weitergehende Anforderungen bezüglich
Vergleichsoperatoren werden STL-intern
durch eine Kombination der Operatoren
„==„ und „<„ erfüllt.
Beispiele:
x>=y das Gleiche wie !(x<y)
und
x>y
das Gleiche wie y<x
und
x!=y das Gleiche wie !(x==y)
07.12.2012
FB Informatik
Prof. Dr. R.Nitsch
class Any
{
public:
// Implementierung == Operator
bool operator==(const Any& rhs) const;
...
};
class Any
{
public:
// Implementierung < Operator
bool operator<(const Any& rhs) const;
...
};
10
Musterklasse Any (wird in Beispielen verwendet)
FB Informatik
Prof. Dr. R.Nitsch
class Any {
int* pa;
public:
Any( int i=0 ) { pa = new int(i); }
Any( const Any& a ) { pa = new int(*a.pa); }
~Any() { delete pa; }
int get() const { return *pa; }
Any& operator= ( const Any& a ) {
this->pa = a->pa;
return *this;
}
bool operator== ( const Any& a ) const { return this->pa == a->pa); }
bool operator< ( const Any& a ) const { return this->pa < a->pa; }
};
ostream& operator<< ( ostream& os , const Any& a )
{
os << a.get();
return os;
}
07.12.2012
11
Alle STL Container bieten Iteratoren
Container-Klasse: X
(z.B. list<int> für X)
X::iterator
X::reverse_iterator
first
Container-Elemente
begin()
rend()
FB Informatik
Prof. Dr. R.Nitsch
--iter
++riter
last
iter
++iter
riter
--riter
end()
rbegin()
 Alle STL-Container stellen Iteratoren zur Verfügung, die sich bezüglich einer
Inkrementierung unterschiedlich verhalten:
 X::iterator:
Normaler Iterator, mit dem beim Inkrementieren ein Container
von vorne nach hinten traversiert werden kann.
 X::reverse_iterator: Ein Iterator, mit dem durch Inkrementieren ein Container von
hinten nach vorne traversiert werden kann; in STL implementiert als
Adapterklasse der normalen Iteratoren
07.12.2012
12
Read-only Iterator Typen
FB Informatik
Prof. Dr. R.Nitsch
 Iteratoren können vom Typ read-write-access und read-only-access sein.
 Der read-write Iterator-Typ iterator liefert bei der Dereferenzierung eine
Referenz auf das Element-Objekt (T&), die auch schreibenden Zugriff erlaubt.
 Der read-only Iterator-Typ const_iterator liefert bei der Dereferenzierung
lediglich eine const-Referenz (const T&) ohne Schreibzugriff auf das Objekt
vector<Konto> kto;
vector<Konto>::iterator iter = kto.begin();
iter->stand = iter->stand + 100; // "stand" muss hier public sein. Container darf nicht leer sein!
vector<Konto>::const_iterator const_iter = kto.begin();
double betrag = const_iter->stand; OK, weil nur lesender Zugriff
Fehler, weil schreibender Zugriff über const_iterator
const_iter->stand = 100;
OK! const bedeutet nicht, daß der Iterator selbst nicht verändert
const_iter++;
werden darf, sondern nur das Element auf das er zeigt!
Achtung: keine Bereichs-Kontrolle für Iteratoren
 Alle STL-Container definieren sowohl die
read-write-access als auch die
read-only-access Iteratorvariante.
Hinweis: MS Visual C++2005ff weicht hier
vom Standard ab und bietet sogenannte
"Checked Iterators": Programmabbruch zur
Laufzeit, wenn Iterator nicht im zulässigen
More on this:Visual C++ 8.0 Hijacks the C++ Standard Bereich.
http://www.informit.com/guides/content.aspx?g=cplusplus&seqNum=259 Gleiches gilt auch für den []-Operator.
http://www.informit.com/guides/content.aspx?g=cplusplus&seqNum=260
07.12.2012
13
Alle STL Container: Gemeinsame Typ-Definitionen
Typ-Definitionen
X::value_type
X::reference
X::const_reference
X::pointer
X::const_pointer
X::iterator
X::const_iterator
Legende
Typ der Werte im Container (i.A: T bei
Sequenzcontainer, Key bei std::set und
pair<Key,T> bei std::map)
entspricht X::value_type&
entspricht const X::value_type&
entspricht X::value_type*
entspricht const X::value_type*
Kontrollabstraktion zum traversieren des
Containers in Vorwärtsrichtung
wie X::iterator aber nur lesender Zugriff auf
ElementWerte
X::reverse_iterator
X::const_reverse_iterator wieX::iterator aber Rückwärtsrichtung
X::difference_type
kann Abstand zweier Iteratoren darstellen
X::size_type
kann Größe eines Containers darstellen.
• Die Container stellen mittels typedef-Anweisungen mehrere
Datentypen zur Verfügung.
• Durch Verwendung dieser Typ-Bezeichner in Anwendungen bzw.
Algorithmen werden diese vom tatsächlichen, aktuellen Datentyp
der Container weitgehend unabhängig.
• Werden zu einem späteren Zeitpunkt, anstelle von Any-Objekten,
Objekte vom Typ Konto im Container abgelegt, so ändert sich
damit auch der Datentyp der Variablen A1::value_type ist dann ein
Alias für den Datentyp Konto.
Konstruktoren
X()
X(a); X b(a);
a.~X()
07.12.2012
FB Informatik
Prof. Dr. R.Nitsch
Standard-Konstruktor; erzeugt leeren Container
Copy-Konstruktor
Destruktor
X
ist eine Container-Klasse für Objekte vom Typ T
a,b sind Variablen/Objekte vom Typ X
r
ist eine Referenz-Variable/-Objekt vom Typ X&
// Typ des Vektors
typedef vector<Any> AnyVect;
// Vektor definieren
AnyVect v;
… // v füllen
// Variable definieren deren Datentyp mit dem
// Datentyp der Vektor-Elemente überein stimmt
Any A1 = v[0];
vector<Any>::value_type A1= v[0];
AnyVect::value_type A1= v[0];
Äquivalente Anweisungen!
// Erzeugt einen leeren Container
list<Any> anyList;
// Dupliziert einen Container
list<Any> myList(anyList)
14
Alle STL Container: Gemeinsame Methoden
iterator X::begin() Gibt Iterator auf das erste Containerelement
iterator X::end() Gibt Iterator, der die Ende-Markierung des
Containers kennt.
reverse_iterator
X::rbegin()
Gibt reverse-Iterator zurück, der das Anfangselement für umgekehrtes Traversieren kennt.
reverse_iterator
X::rend()
Gibt reverse-Iterator, der die Ende-Markierung
für reverses Traversieren kennt.
size_type size()
gibt aktuelle Anzahl Elemente im Container
bool empty()
liefert true, wenn Container leer ist
a==b, a!=b
true bei elementweiser (Un)Gleichheit;
benutzt X::value_type::operator==
a<b
vergleicht 2 Container lexikografisch;
benutzt X::value_type::operator<
a>b
returns true, wenn b<a
a<=b
returns true wenn !(b<a)
a>=b
returns true, wenn !(a<b)
r=a
Zuweisungsoperator für Container
a.swap(b)
Vertauschen der Inhalte 2er Container
gleichen Typs (konstante Komplexität O(1)!).
FB Informatik
Prof. Dr. R.Nitsch
// Any-Vektor definieren
AnyVect v;
// hier Any-Vektor füllen…
AnyVect::iterator iter;
// Kompl. Container ausgeben
for ( iter = v.begin();
iter != v.end(); ++iter )
cout << *iter << endl;
AnyVect v;
// hier Any-Vektor füllen …
// Anzahl der Elemente ausgeben
cout << v.size() << endl;
// Test ob Vektor Elemente enthält
if( v.empty() )
cout << "Keine Elemente im Vektor!\n";
AnyVect anyV1, anyV2;
...
// Container-Inhalte vergleichen
AnyVect anyV1, anyV2;
if( anyV1 == anyV2 )
// Container füllen
cout << "Container enthalten die"
// Container-Inhalte vertauschen (konstante Komplexität)
" gleichen Elemente!\n";
anyV1.swap( anyV2 );
// Vergleich auf kleiner als
// Container zuweisen
if( anyV1 < anyV2 )
anyV2
=
anyV1;
15
07.12.2012
C++ Standard Template Library
cout (STL)
<< "anyV1 ist kleiner anyV2 \n";
STL Sequenzcontainer
FB Informatik
Prof. Dr. R.Nitsch
bietet wahlfreien Zugriff auf Objektsequenzen ( O(1) ) variabler
Länge mit schellem Einfügen und Löschen am Ende der Sequenz
wie vector, aber schnelles Einfügen und Löschen am Anfang und
Ende der Sequenz
kein wahlfreier sondern linearer Zugriff ( O(N) ) auf eine Sequenz
variabler Länge (hier N) aber schnelle Einfüge- und Löschoperationen
an beliebiger Stelle ( O(1) )
 vector<T>
 deque<T>
 list<T>
Einfügen / Löschen
Container
ElementZugriff
Beginn
Mitte
Ende
vector<T>
O(1)
O(N)
O(N)
O(1)
deque<T>
O(1)
O(1)
O(N)
O(1)
list<T>
O(N)
O(1)
O(1)
O(1)
T a[N]
O(1)
O(N)
O(N)
O(1)
07.12.2012
Iterator Typ-Definitionen
Iterator-Kategorie
vector<T>::iterator
mutable random access
vector<T>::const_iterator
constant random access
deque<T>::iterator
deque<T>::const_iterator
list<T>::iterator
mutable bidirectional
list<T>::const_iterator
constant bidirectional
T*
const T*
16
Alle Sequenz-Container: Zusätzliche Konstruktoren
FB Informatik
Prof. Dr. R.Nitsch
Konstruktoren:
Legende
Standard-Konstruktor
Initialisiert Container mit n Kopien vom Typ T
Für Typ T muss der Standard-Konstruktor definiert
sein!
X(n,t); X a(n,t) Erzeugen eine Sequenz mit n Kopien von t.
X(i,j); X a(i,j) Erzeugen eine Sequenz mit gleichem Inhalt wie der
Range [i,j)
X ist eine Container-Klasse für Objekte vom Typ T
a ist eine Variable vom Typ X
i,j Input-Iteratoren und [i,j) ist ein gültiger Bereich
n Variable vom Typ X::size_type
p gültiger Iterator für a
q, q1, q2 gültige dereferenzierbare Iteratoren für a
und [q1,q2) ist ein gültiger Bereich
t Variable vom Typ X::value_type
X(); X a;
X(n); X a(n);
• Jeder Sequenz-Container kann auf
die fünf rechts dargestellten
Arten definiert werden.
• Diese Definitionen gelten generell
auch für die Container deque und
list.
07.12.2012
#include <vector>
using std::vector;
class Any { /*…*/ };
// Leeren Vektor definieren
vector<Any> vect1;
// Vektor mit 5 Elementen definieren
vector<Any> vect2(5);
// Vektor aus 5 Objekten mit Wert Any(10) erzeugen
vector<Any> vect3(5, Any(10));
// Any-Feld definieren/initialisieren
Any array[4] = { Any(1),Any(2),Any(3),Any(4) }
// Vektor mit Feldinhalt initialisieren
vector<Any> vect4( &array[0], &array[4] );
vector<Any> vect5( vect3.begin(), vect3.end() );
17
Alle Sequenz-Container: Zusätzliche Methoden
FB Informatik
Prof. Dr. R.Nitsch
typedef vector<Any> AnyVect;
Fügt eine Kopie von t vor p ein.
AnyVect v, v1;
Gibt Iterator auf eingefügten Wert zurück
// Den Wert Any(i) einf.
void X::insert(p,n,t)
Fügt n Kopien von t vor p ein.
iter = v.end();
void X::insert(p,i,j)
Fügt Kopien der Elemente im Range [i,j)
for( int i=4; i>0; --i )
eines anderen Containers vor p ein.
iter = v.insert( iter, Any(i) );
1234
void X::push_back(t)
Fügt eine Kopie von t am Ende ein
//
Den
Wert
Any()
vor
der
1.
Position
einf.
void X::assign(i,j)
Entspricht { clear(); insert( begin(), i, j); }
01234
v.insert( v.begin(), Any() );
void X::assign(n,t)
Entspricht { clear(); insert( begin(), n, t ); }
// 2x den Wert Any(5) vor der 6. Position einf.
v.insert( v.begin()+5, 2, Any(5) );
Elementzugriff:
// Feld definieren
reference X::front()
Gibt Referenz auf 1.Element
Any array[] = { Any(6), Any(7), Any(8) };
reference X::back()
Gibt Referenz auf letztes Element
// Any-Feld am Ende einfuegen
Beide Rückgaben sind undefiniert, wenn
v.insert(v.end(),&array[0],&array[3]);
der Container leer ist!
// Existierenden Vektor löschen und aus aus array neu befüllen
Löschoperationen:
v1.assign( array, &array[3] );
678
iterator X::erase(q)
Löscht das Element, auf das q verweist.
//
Erstes
Element
auslesen
Der Ergebnis-Iterator verweist auf das
AnyVect::value_type var = v.front();
Element hinter q oder a.end(), wenn das
//
Letztes Element auslesen
letzte Element gelöscht wurde.
cout << var << ' ' << v.back();
08
iterator X::erase(q1,q2) Löscht alle Elemente im Bereich [q1,q2).
// 2. Element entfernen
v: 0 1 2 3 4 5 5 6 7 8
Der Ergebnis-Iterator verweist auf das
cout << *v.erase(v.begin()+1);
2
Element hinter q2 oder a.end(), wenn das
// Letzte 4 Elemente entfernen v: 0 2 3 4 5 5 6 7 8
letzte Element gelöscht wurde.
v.erase( v.end()-4, v.end() );
void X::pop_back()
Löscht letztes Element
// Letztes Element entfernen
v: 0 2 3 4 5
void X::clear()
Löscht alle Elemente im Container
v.pop_back();
v: 0 2 3 4
void X::resize(n,t)
Löscht alle Elemente am Ende oder füllt
//Containergröße verändern
am Ende mit Kopien der Objekte t auf bis
v: 0 2 3 4 7 7
v.resize( 6, Any(7) );
size() == n. Eine Reduzierung des
// Alle Elemente entfernen
allokierten Speichers wird dadurch nicht
v.clear();
erzwungen.
18
07.12.2012
Einfügeoperationen:
iterator X::insert(p,t)
Container vector und deque : Direkter Elementzugriff
Elementzugriff:
… = a[n]
lesender Direktzugriff ohne Indexüberprüfung
a[n]= …
schreibender Direktzugriff ohne Indexüberprüfung
… = a.at(n)
lesender Direktzugriff mit Indexüberprüfung
a.at(n)= …
schreibender Direktzugriff mit Indexüberprüfung;
throw( std::out_of_range )
 Der Zugriff auf die einzelnen Elemente eines
Vektor/Deque-Containers kann, wie bei Feldern
üblich, mit dem Indexoperator [] erfolgen. Es
findet keine Indexüberprüfung statt.
 Über die Memberfunktion at(..) kann
lesend/schreibend mit Indexprüfung
( 0<= index <=size() ) auf die Elemente
zugegriffen werden. Bei Indexfehlern wird eine
out_of_range Exception ausgeworfen.
 Bei list Objekten ist der []-operator nicht
implementiert, da der Zugriffsaufwand mit O(N) zu
ineffizient ist.
07.12.2012
FB Informatik
Prof. Dr. R.Nitsch
// Indizierter Elementzugriff
Any var = v[3]; // lesend
v[4] = var;
// schreibend
// Abgesicherter Elementzugriff
// kann out_of_range Exception auslösen
var = v.at(15); // Fehler
v.at(0) = var;
Hinweis: MS Visual C++ 2005 weicht hier
vom Standard ab und bietet sogenannte
"Checked Iterators": Programmabbruch zur
Laufzeit, wenn Iterator nicht im zulässigen
Bereich. Gleiches gilt auch für den []Operator.
Mehr dazu hier:
http://msdn2.microsoft.com/enus/library/aa985965(VS.80).aspx
19
Container deque und list : Zusätzliche Methoden zum Einfügen von Elementen
FB Informatik
Prof. Dr. R.Nitsch
Einfügen und Löschen von Elementen:
void X::push_front(t) Fügt Objekt t am Listenanfang ein
void X::pop_front() Entfernt erstes Objekt im Container
 Elemente können zusätzlich über die
Memberfunktion void push_front(t) am
Beginn von list- und deque-Containern
eingefügt werden.
 Das erste Element von list- und dequeContainern kann zusätzlich über die
Memberfunktion void pop_front()
entfernt werden.
 Beide Methoden sind beim vectorContainer nicht definiert, weil Einfüge- und
Löschoperationen am Beginn dieses
Containers sehr ineffizient sind (O(N))!
07.12.2012
list<Any> myList;
//Objekt Any(1) am Anfang einfügen
myList.push_front( Any(1) );
// Erstes Listenelement entfernen
myList.pop_front();
20
Zusätzliche Methoden für list-Container
FB Informatik
Prof. Dr. R.Nitsch
Return type method Meaning
void merge(list&)
Merges two sorted lists, using T::operator<(const T&) (time complexity O(n)).
void merge(list&,Compare_object)
Merges two sorted lists, using a Compare_object for the comparison of elements (O(n)).
void push_front(const T& t)
Inserts an element at the beginning.
void pop_front()
Deletes the first element.
void remove(const T& t)
Removes all elements that are equal to the passed element t (O(n)).
void remove_if(Predicate pred)
Removes all elements to which the predicate applies (O(n)).
void reverse()
Reverses the order of elements in the list (O(n)).
void sort()
Sorts the elements in the list. Time complexity is O(~N log N). The sorting criterion is the
T::operator<(const T&) defined for the elements. Remark: Stable
void sort(Compare_object)
as sort(), but with the sorting criterion of the comparison function object.
void splice(iterator p,list&x, iterator i) Inserts element *i of x before p and removes *i from x.
void splice(iterator pos, list& x,
iterator first, iterator last)
Inserts elements in the range [first, last) of x before pos and removes them from x. Calling the
same object (that is, &x == this), takes constant time, otherwise, the cost is of the order O(n). pos
must not lie in the range [first, last).
void splice(iterator pos, list& x)
Inserts the contents of list x before pos. Afterwards, x is empty.
void unique()
Deletes identical consecutive elements except for the first one (cost O(n)). Application to a sorted
list leads to the effect that no element occurs more than once.
void unique(binaryPredicate)
Ditto, only that instead of the identity criterion another binary predicate is used.
07.12.2012
21
Container vector : Größenmanagement
 Memberfunktion vector::capacity()
ermittelt Maximalgröße, bis zu der der VektorContainer erweitert werden kann, ohne dass
hierfür neuer Speicherplatz angefordert
werden muss.
 Memberfunktion vector::reserve(n) legt
die Größe des allokierten Speicherplatzes fest.
Ein Größenreduzierung kann mit reserve(n)
nicht erzwungen werden.
 Sie sind deshalb so interessant, weil nach einer
Anforderung von neuem Speicherplatz für
einen Vektor-Container alle ElementReferenzen und -Zeiger sowie Iteratoren
ungültig werden.
 Für die Container list und deque sind
capacity() und reserve() nicht definiert.
07.12.2012
FB Informatik
Prof. Dr. R.Nitsch
// Feld definieren/initialisieren
int array[] = {1,2,3,4,5};
// Vektor mit Feldinhalt initialisieren
vector<Any> v3(&array[0],&array[5]);
// Kenndaten des Vektors ausgeben
cout << v3.size() << ','
<< v3.capacity() << endl;
5, 5
// Vektor vergroessern
v3.reserve(20);
// Erneut Kenndaten ausgeben
cout << v3.size() << ','
5, 20
<< v3.capacity() << endl;
22
Sortierte Assoziative Container der STL
FB Informatik
Prof. Dr. R.Nitsch
 Elementzugriff O(log2N)
 Speichern die Daten intern in einer Baumstruktur
 Das mathematische Konzept einer Relation oder eine diskrete Abbildung wird mit
map realisiert, das einer Menge mit set
 multimap und multiset erlauben mehrfache identische Schlüssel
Erklärung siehe
STL-Algorithmen
Container
set<T>
Zugriff
O(log N)
Einfügen / Löschen
Beginn Mitte Ende
O(1)
O(1)
O(1)
multiset<T>
O(log N)
O(1)
O(1)
O(1)
map<Key,T>
O(log N)
O(1)
O(1)
O(1)
multimap<Key,T>
O(log N)
O(1)
O(1)
O(1)
Iterator
Iterator-Kategorie
set<T>::iterator
constant bidirectional1)
set<T>::const_iterator
multiset<T>::iterator
constant bidirectional1)
multiset<T>::const_iterator
map<key,T>::iterator
map<key,T>::const_iterator
multimap<Key,T>::const_iterator
multimap<Key,T>::const_iterator
1) Microsoft Visual C++ weicht hier vom Standard ab und realisiert "mutable bidirectional" Iteratoren 
07.12.2012
25
Assoziativer Container map
FB Informatik
Prof. Dr. R.Nitsch
 map speichert Elemente, die aus einem Schlüsselwert "key" und
key_type mapped_type
assoziierten Daten "mapped" bestehen.
 Die Schlüsselwerte sind eindeutig, d.h. es gibt keine 2 Datensätze
MatrikelNr Sudent
mit gleichem Schlüsselwert (keine Duplikate).
 Der Zugriff auf die assoziierten Daten erfolgt über den Schlüsselwert,
TelNr
Name
anstatt über ihre absolute (Index) oder relative (front, back)
Position im Container.
Location
Node
 Eine sortierte Anordnung der Schlüsselwerte ist für den Zugriff nicht
Beispiele assoziierter
erforderlich, reduziert aber den Zugriff auf die Komplexität O(logN)
Daten im map-Element
 Schlüsselwerte und assoziierte Daten werden vom map-Container
gemeinsam in Objekten vom Typ std::pair<const Key, T> aufbewahrt.
 Die Konstanz des Schlüssels gewährleistet, dass er nach dem Einfügen nicht mehr
verändert werden kann. Dies würde die Sortierung zerstören.
 Deklaration der Klasse in der STL
template< class Key,
// Typ von key
class T,
// Typ von mapped
class Compare = std::less<Key> > // Typ des Sortierers
class map { /*…*/ };
// (Key::operator< ist voreingestellt)
Anwendungsbeispiele folgen
07.12.2012
26
1. Beispiel - Wörterbuch
Map_Demo_Anwendung
void main(void) {
map<string,string> dictionary;
FB Informatik
Prof. Dr. R.Nitsch
// Leeres Wörterbuch erzeugen
dictionary.insert(pair<string,string>("Baum","tree"));
// Element aufnehmen
dictionary.insert(pair<string,string>("Auto","car"));
// noch ein Element
cout << dictionary["Baum"] << endl;
// Assoziativer Zugriff
map<string,string>::iterator iter = dictionary.begin();
for( ; iter!=dictionary.end(); ++iter )
cout << (*iter).first << ' ' << iter->second << endl;
// Sortierte Ausgabe
}
tree
Auto car
Baum tree
 Voreingestellt ist, dass der Operator < die interne Reihenfolge der Elemente in
map- bzw- set-Containern bestimmt.
 Falls das unerwünscht ist, muss ein anderes geeignetes Kriterium angeboten
werden: class Compare {
Beispiel:
public: bool operator()(const string& s1, const string& s2) const
{ return s2<s1; }
};
07.12.2012
void main(void) {
Comp compare;
map<string,string,Compare> dictionary(compare);
// weiter wie oben
}
// Sortierte Ausgabe
Buch book
Auto car
27
Container map und multimap : Übersicht und Typdefinitionen
FB Informatik
Prof. Dr. R.Nitsch
Typdefinitionen
 map definiert folgende öffentlichen Datentypen
key_type
mapped_type
Typ Key der Schlüsselwerte
Typ T der zugeordneten Werte
value_type
pointer
reference
X::key_compare
Typ der gespeicherten Werte, pair<const Key,T>
entspricht pair<const Key,T>*
entspricht pair<const Key,T>&
Typ des Funktionsobjekts Compare, das die
Sortierreihenfolge der Schlüssel festlegt
Weitere Typen wie Sequenz-Container
…
Fortsetzung des Beispiels:
map-Element
Key
T
value_type
Typ pair<Key,T>
key_type
mapped_type
typedef dient hier der Abkürzung
void main(void) {
Achtung: Ist die Suche nach dem Schlüssel
// wie bisher
erfolglos, wird ein neues map-Element für
cout << dictionary.size();
2
diesen Schlüssel angelegt. Die assoziierten
typedef map<string,string,Compare> Map
Daten werden mit dem Standardkonstruktor
Map::key_type key = "Ei";
// Typ ist string
T() erzeugt (hier: string() ).
cout << dictionary[key];
3
// Schreibender Zugriff auf assoziierte Daten
dictionary[key] = "egg";
// Typ ist string Weitere Informationen zum Einfügen, Suchen und
Map::mapped_type translation;
translation = dictionary[key];
Löschen von Daten finden Sie hier:
egg
cout << word;
Breymann: C++. S. 756ff
}
http://www.cplusplus.com/reference/stl/map/
07.12.2012
28
1. Beispiel - Duplikate
FB Informatik
Prof. Dr. R.Nitsch
void main(void) {
// wie bisher (siehe vorherige Seite)
3
dictionary.insert(pair<string,string>("Auto","vehicle")); // Versuch Duplikat einzufügen:
// Schlüsselwert "Auto" gibt es schon
3
// Duplikat wurde nicht gespeichert!
Wie kann man dieses Verhalten zuverlässig kontrollieren?
Deklaration von map::insert:
pair<iterator,bool> insert( const value_type& x );
map::insert liefert einen return-value vom Typ std::pair.
1. Member pair::first: Iterator, der auf das neu eingefügte Element oder das Duplikat zeigt
2. Member pair::second: Ist false, wenn der Schlüsselwert bereits enthalten ist, sonst true.
typedef Map::iterator Iterator;
std::pair<Iterator,bool> result;
// 2. Versuch
result = dictionary.insert(Map::value_type("Auto","vehicle"));
cout << result.second << endl;
false // Duplikat wurde nicht gespeichert!
cout << *(result.first) << endl;
Auto car
}
07.12.2012
29
2. Beispiel: Ein Telefonbuch mit class map
FB Informatik
Prof. Dr. R.Nitsch
typedef map<string,long> PhoneMap;
string ist der key_type und long ist der mapped_type
typedef PhoneMap::value_type MapElement;
MapElement entspricht jetzt pair<string,long>
typedef dient hier wieder der Abkürzung
void main() {
// Einfügen mit operator[ ] und insert:
PhoneMap directory;
directory.insert(MapElement("IRedViel",732457));
directory["HauMich"] = 163248;
directory[„DuBiDumm"] = 843756;
directory.insert(MapElement("IRedViel",732458)); // 2. Telefon; wird nicht ausgeführt, weil Schlüssel
// schon existiert
// immer noch kein 2. Telefon. Überschreibt 1. Nummer
directory["IRedViel"] = 732458;
const_iter weil read-only Zugriff ausreicht
PhoneMap::const_iter iter = directory.begin();
for( ; iter!=directory.end(); ++iter)
// Sortierte Ausgabe:
cout << (*iter).first << ' '
DuBiDumm 843756 HauMich 163248 IRedViel 732458
<< iter->second << ' ';
// Suchen im Telefonbuch …
string name = "Bin Laden";
// Suchen mit operator[ ]:
// O( logN )
long number = directory[name];
// number = 0; Achtung: Suchfehler gibt es hier nicht!! Für "BinLaden"
// existiert jetzt ein Eintrag.
iter = directory.find(name);
// Suchen mit Iterator und find
// O( logN )
if( iter!=directory.end() )
// Prüfen, ob Iterator dereferenzierbar ist
cout << (*iter).second;
// O( 1 )
iterator find(k) liefert Iterator
else
auf gefundenen Eintrag oder "past-thecout << name << " hat kein Telefon!" << endl;
end" Iterator wenn nicht gefunden
directory.erase(iter); // Leereintrag "BinLaden" wieder löschen
}
void erase(iter) löscht einzelnes Element an Position iter
07.12.2012
30
Sortierter Assoziativer Container multimap
FB Informatik
Prof. Dr. R.Nitsch
 Unterschiede zu map
 Elemente mit identischem Schlüssel (Duplikate) dürfen mehrfach vorkommen. Die
assoziierten Daten dürfen sich dabei durchaus unterscheiden
Beispiel: mehrere Telefonnummern unter gleichem Namen
 Es gibt keinen Indexoperator T& operator[ ](const key_type& k)
07.12.2012
31
Sortierter Assoziativer Container set
FB Informatik
Prof. Dr. R.Nitsch
 entspricht der Klasse map, mit dem Unterschied, dass nur Schlüsselwerte
gespeichert werden (Elemente = Schlüsselwerte)
 set speichert wie map keine Duplikate
 set hat keinen Indexoperator -> Einfügen nur mit insert(key)
void main(void) {
set<string> names;
// Einfügen mit insert
names.insert("IchSchonWieder");
names.insert(„IbinSchlau");
names.insert(„DuBiDumm");
set<string>::iterator iter = names.begin(); // Sortierte Ausgabe
for( ; iter!=names.end(); ++iter )
DuBiDumm IbinSchlau IchSchonWieder
cout << *iter << endl;
names.insert("IchSchonWieder");
// Duplikat nicht eingefügt. Wie erkennt man erfolgreiches Einfügen?
pair<SetIter,bool> success;
pair<iterator,bool> insert(key)
success = names.insert("IchSchonWieder");
if(success.second==true)
cout << *(success.first) << " eingefuegt";
Duplikat
else cout << "Duplikat";
}
07.12.2012
32
Container set : Übersicht und Typdefinitionen
FB Informatik
Prof. Dr. R.Nitsch
• Deklaration der Klasse in der STL
template< class Key
class Compare = std::less<Key> >
class set { /*…*/ };
// Typ der Schlüssel
// Typ des Sortierers
// (Key::operator< ist voreingestellt)
Definition eines leerenset-Containers: set<Konto> myset;
Typdefinitionen
• set definiert folgende öffentlichen Datentypen
Typ Key der Schlüsselwerte
auch Typ Key, im Gegensatz zu map
entspricht Key*
entspricht Key&
Typ Compare. Funktionsobjekt, das die
Sortierreihenfolge der Schlüssel festlegt
…
Weitere Typen wie Sequenz-Container
Weitere Informationen:
key_type
value_type
pointer
reference
key_compare
set-Element
Key
value_type
key_type
Weitere Informationen zum Einfügen, Suchen und Löschen von Daten finden Sie hier:
http://www.cplusplus.com/reference/stl/set/
Breymann: C++. S. 523
07.12.2012
33

Programmieren - Standard Template Library (STL)

Transcrição

Documentos relacionados

`Container`

Viburnum tinus -- Mittelmeer

Einführung in die STL

anforderungen an die 3-d-druckdatei

Lackschicht schnell montagetrocken

MX-4118 DE Produktdatenblatt

AC5488 Eigenschaften Logistische Daten

Montageanleitung für Container

Sortierkriterien für Wertstoffe

BL-4431 DE Produktdatenblatt