View
240
Download
0
Category
Preview:
Citation preview
17.12.2007 C++ Standard Template Library (STL) 46
FB InformatikProf. Dr. R.Nitsch
STL Algorithm Übersicht
• Die C++ STL enthält mehrere typparametrisierte Algorithmen (ca. 70 verschiedene ) die hinsichtlich Laufzeiteffizienz optimiert sind.
• Die STL Algorithmen sind generisch: Jeder Algorithmus arbeitet mit mehreren (einige sogar mit allen) Containern und C-Arrays zusammen. Beispiele folgen.
• Dies wird ermöglicht, indem Iteratoren als gemeinsames Konzeptvon Algorithmen und Containern verwendet werden: STL Container erzeugen Iteratoren, STL Algorithmen nutzen sie!
• Die Anforderungen an den Funktionsumfang der Iteratoren sind unterschiedlich.
– Algorithmen unterscheiden sich in den Anforderungen, die sie an die verwendeten Iteratoren stellen.
– Bei einzelnen Containern können bestimmte Iterator-Funktionen nur mit nicht vertretbaren Laufzeiteffizienz-einbußen implementiert werden und werden deshalb weggelassen.
Deshalb wurde eine Iteratorenhierarchie definiert:– Input-Iterator , Output-Iterator– Forward-Iterator– Bidirectional Iterator– Random Access Iterator
Container Container
Algorithm
Container
Iterator
Iterator
Iterator
Input-Iteratoren
Output-Iteratoren
17.12.2007 C++ Standard Template Library (STL) 47
FB InformatikProf. Dr. R.Nitsch
Iterator-Kategorien der STL
• Hinweis: Der Begriff "Input Iterator" ist kein Datentyp sondern ein Sammelbegriff für eine Familie von Iteratortypen, die allesamt das Anforderungsprofil für den "Input Iterator" erfüllen.
template< class InputIterator , class T >InputIterator std::find( InputIterator first , InputIterator last , const T& value ) {
while( first!=last && !(*first==value) )++first;
return first;}
find benutzt die Methoden operator!= , operator++ , und operator* (nur lesend) des übergebenen Iterators.
Der Funktionsumfang der Kategorie "Input Iterator" reicht also aus.
Der Typparametername InputIterarator bringt dies dem Anwender gegenüber (an Stelle eines Kommentars) zum Ausdruck.
template< class InputIterator , class OutputIterator >OutputIterator std::copy( InputIterator first , InputIterator last , OutputIterator result ) {
while( first!=last ) {*result = *first;++first;++result;
} //whilereturn result;
}
copy benutzt die Iterator-Methoden operator!= , operator++, und operator* (nur lesend für first und nur schreibend für result) des übergebenen Iterators
Der Funktionsumfang der Kategorie "Input Iterator" für first und "Output Iterator" für result reicht also ausDie Stellvertretertypen InputIterarator für first und OutputIterator für result bringen dies dem Anwender gegenüber (an Stelle eines Kommentars) zum Ausdruck
• Input Iterator ++ (post&pre) , * (R-value ausreichend), ==, != O(1) O(1) • Output Iterator ++ (post&pre) , * (L-value ausreichend), ==, !=
Returns: The first iterator i in the range [first ,last ) for which the condition *i == value holds. Returns last if no such iterator is found. Complexity: At most last - first applications of the binary predicate T::operator== [Quelle: C++-Standard].
Copies elements in the range [first ,last ) into the range [result ,result + (last - first )) starting from first and proceeding to last . Returns: result + (last - first ). // T::operator= wird benötigt!
InputIteratorTyp T& Typ const T&
Für den T muss T::operator!= definiert sein!
17.12.2007 C++ Standard Template Library (STL) 48
FB InformatikProf. Dr. R.Nitsch
Iteratoren-Kategorien der STL
template< class ForwardIterator , class T >void std::replace( ForwardIterator first , ForwardIterator last ,
const T& old_value , const T& new_value ){
while( first!=last ) {if( *first==x ) *first = y;++first;
}}
• Bidirectional Iterator wie Forward Iterator; zusätzlich operator-- (post- und prefix) O(1) Mit einfach verketteten Listen ist das nicht möglich!
• Random Access Iterator wie Bidirectional Iterator; zusätzlich Iterator-Arithmetik, d.h. r+n , n+r , r-nIndex-Operator r[n]Bidirectionale "big jumps" r+=n und r-=nIterator Subtraktion r-s (Ergebnistyp long)Vergleiche r<s , r>s , r<=s , r>=s (Ergebnistyp bool)
alles O(1)
r und s sind Iteratorenn ist eine Ganzzahl
Requires: The expression *first = new_value must be valid.Effects: Substitutes elements referred by the iterator i in the range [first ,last ) with new_value , when the condition *i == old_value holds.Complexity: Exactly last - first applications of the corresponding predicate.[Quelle: C++ Standard]
Zugriff
lesender schreibender
wie InputIterator und OutputIterator d.h. operator* musslesenden und schreibenden Zugriff auf Containerelemente bieten; zusätzlich operator= , d.h. Iteratoren können gespeichert werden. Dies ist zum Beispiel in multipass-Algorithmen notwendig.
• Forward Iterator O(1)
17.12.2007 C++ Standard Template Library (STL) 49
FB InformatikProf. Dr. R.Nitsch
Hierarchie der STL Iterator-Kategorien
• Ein ForwardIterator ist auch ein InputIterator und ein OutputIterator
• Ein BidirectionalIterator ist auch ein ForwarIterator und somit auch ein InputIterator und ein OutputIterator.
• Ein RandomAccessIterator ist auch ein BidirectionalIterator und somit auch ein ForwarIterator und somit auch ein InputIterator und ein OutputIterator
RandomAccessIterator
BidirectionalIteratorForwardIterator
InputIterator
OutputIterator
Konsequenzen dieser Hierarchie:• Ein Algorithmus der einen Input-Iterator oder Output-Iterator benötigt kann auch mit einem
Forward-Iterator oder Bidirectional-Iterator oder Random-Access-Iterator arbeiten.• Ein Algorithmus der einen Forward-Iterator benötigt kann auch mit einem Bidirectional-
Iterator oder Random-Access-Iterator arbeiten.• Ein Algorithmus der einen Bidirectional-Iterator benötigt kann auch mit einem Random-Access-
Iterator arbeiten.• Ein Algorithmus der einen Random-Access-Iterator benötigt kann mit keinem anderen Iterator
arbeiten.
Einen Überblick über alle STL Algorithmen und die Anforderungen an die Iteratoren findet man hier:http://msdn.microsoft.com/library/default.asp?url=/library/en-us/vclang98/html/ALGORITH.asp
Welchen Iteratortyp stellt die class Liste aus der Vorlesung zur Verfügung?
17.12.2007 C++ Standard Template Library (STL) 50
FB InformatikProf. Dr. R.Nitsch
Beispiel 3: Anwendung des generischen reverse Algorithmus#include <algorithm> // für reverseusing namespace std;
void main(){
// reverse Algorithmus mit stringstring s("leben retten");reverse( s.begin() , s.end() );assert( s == "netter nebel" );copy( s.begin(), s.end(), ostream_iterator<char>( cout ) );
// reverse Algorithmus mit vectorvector<char> v( s.begin() , s.end() );reverse( v.begin(), v.end() );assert( v == "netter nebel" );assert( v == vector<char>( s.rbegin(), s.rend() ) );copy( v.begin(), v.end(), ostream_iterator<char>( cout ) );
// reverse Algorithmus mit listlist<char> l( s.begin() , s.end() );reverse( l.begin(), l.end() );assert( l == list<char>( s.rbegin(), s.rend() ) );copy( l.begin(), l.end(), ostream_iterator<char>( cout ) );
// reverse Algorithmus mit C-Arraychar a[] = "leben retten";reverse(&a[0], &a[strlen(a)]);assert( a == "netter nebel" );assert( string(a) == "netter nebel" );
}
Außerdem müssen <iostream>, <cassert>, <string> und <vector> includiert werden!
Effects: For each non-negative integer i <= (last - first )/2, applies iter_swap to all pairs of iterators first + i, (last - i) - 1.Requires: The type of *first must be CopyConstructable and Assignable.Complexity: Exactly (last - first )/2 swaps. [Quelle: C++ Standard]
OK: Diesen Konstruktor gibt'sVergleichsoperator der vector Klasse
template < class BidirectionalIterator >void reverse ( BidirectionalIterator first, BidirectionalIterator last );
17.12.2007 C++ Standard Template Library (STL) 51
FB InformatikProf. Dr. R.Nitsch
Übungsaufgabe 1
• Erweitern Sie das vorherige Beispiel um die Anwendung des reverse Algorithmus in Verbindung mit dem deque Container
// reverse Algorithmus mit listdeque<char> d( s.begin() , s.end() );std::reverse( );assert( );
17.12.2007 C++ Standard Template Library (STL) 52
FB InformatikProf. Dr. R.Nitsch
Algorithmen mit Funktionsparametern oder Funktionsobjekten
• Viele generische Algorithmen haben eine Version, die ein Funktionsobjekt und (wenn der Parameter typparametrisiert ist) / oder eine Funktion als Parameter akzeptiert.
• In den meisten Fällen haben diese Funktionsobjekte die Bedeutung eines Prädikats (predicates). Predicates sind Funktionen oder wie Funktionen aufrufbare Objekte, die einen (unary predicate) oder zwei (binary predicate) Parameter übernehmen und ein Ergebnis vom Typ bool liefern.
• Beispiel: Die Algorithmen mit Sortieraufgaben akzeptieren einen binären predicate-Parameter, der das Sortierkriterium festlegt.
#include <algorithm> // für sort und merge#include <functional> // für greater<T>
using namespace std;
struct GanzZahl {int w;GanzZahl( int i = 0 ) { w = i; }bool operator>( const GanzZahl& z ) const { return w > z.w; }
};
bool greaterFunc( const GanzZahl& z1 , const GanzZahl& z2 ) { return z1.w > z2.w; }
ostream& operator<<( ostream& os, const GanzZahl& z) {os << z.w;return os;
}
Außerdem müssen <iostream>, <deque>, <vector> und <list> inkludiert werden!
Einfache Klasse mit minimaler Funktionalität für nachfolgende Anwendung
// Standardkonstruktor
unäre predicate-Memberfkt.
Wird bei der Dereferenzierung eines ostream_iterator benötigt
STL-Beispiel 4:
globale binäre predicate Fkt
17.12.2007 C++ Standard Template Library (STL) 53
FB InformatikProf. Dr. R.Nitsch
STL Beispiel 4: Algorithmen sort und merge mit binärer predicate-Fkt.
void main() {const int N = 5;int i;
deque<GanzZahl> d;list<GanzZahl> l;for ( i = 0; i < N; ++i ) d.push_front(2*i);for ( i = 0; i < N; ++i ) l.push_back(2*i+1);
std::copy( d.begin() , d.end() , ostream_iterator<GanzZahl>(cout," ") ); cout << endl;ostream_iterator<GanzZahl> out(cout," ");std::copy( l.begin() , l.end() , out ); cout << endl << endl;
std::random_shuffle( d.begin() , d.end() ); std::random_shuffle( l.begin() , l.end() );
std::copy( d.begin() , d.end() , out ); cout << endl << endl;
// 2 leere Sequenz-Container werden erzeugt …
// … und aufgefüllt
// Ausgabe über cout mit Trennzeichen
Erzeugen eines benannten ostream_iterator-Objekts (Konstruktoraufruf)
//Objekte werden gemischt
template < class RandomAccessIterator >void random_shuffle(RandomAccessIterator first, RandomAccessIterator last);1 Effects: Shuffles the elements in the range [first ,last ) with uniform distribution.2 Requires: The type of *first shall be CopyContructable and Assignable.3 Complexity: Exactly (last - first ) - 1 swaps. [Quelle: C++ Standard]
8 6 4 2 01 3 5 7 9
Ausgabe:
0 2 8 4 6Ausgabe:
12.01.06
17.12.2007 C++ Standard Template Library (STL) 54
FB InformatikProf. Dr. R.Nitsch
STL Beispiel 4a: Algorithmus sort mit binärer predicate-Fkt.
std::sort( d.begin() , d.end() , greaterFunc ); std::sort( l.begin() , l.end() , greaterFunc );
l.sort( std::greater<GanzZahl>() );
std::copy( d.begin() , d.end() , out ); cout << endl;std::copy( l.begin() , l.end() , out ); cout << endl;
// deque d im Bereich [d.begin(), d.end()) sortieren
8 6 4 2 09 7 5 3 1
Ausgabe:
void sort(); // T::operator<; stable; O(N log N)template<class Pred> void sort(Pred pr);
1) // MS Visual C++ kann nur void sort( greater<T> pr );
template<class _Ty>struct greater /* … */ {
bool operator() (const _Ty& _X, const _Ty& _Y) const{ return (_X > _Y); }
};
Quellcode aus Header "functional"template<class RanIt> // Prototyp; ≈O(N log N)void sort(RanIt first, RanIt last);template<class RanIt, class Pred>
void sort(RanIt first, RanIt last, Pred pr);Requires: The type of *first shall be CopyContructable and Assignable
// class list hat 2 eigene sort-Memberfunktionen// list::sort() verwendet T::operator< als Sortierkriterium // list::sort( Pred pr ) Optionaler predicate-Parameter muss eine binäre // Predicate-Funktion sein oder ein Funktionsobjekt mit dem binären Funktionsoperator // bool Pred::operator()(const T& , const T& )
17.12.2007 C++ Standard Template Library (STL) 55
FB InformatikProf. Dr. R.Nitsch
STL Beispiel 4b: Algorithmus merge mit binärer predicate-Fkt.
vector<GanzZahl> v(2*N);
std::merge( d.begin(), d.end(), l.begin(), l.end(), v.begin() , GreaterFunc );
std::merge( d.begin(), d.end(), l.begin(), l.end(), v.begin() , std::greater<GanzZahl>() );
std::copy( v.begin() , v.end() , out ); cout << endl << endl;}
// vector-Container erzeugen und auffüllen mit 2N identischen Objekten GanzZahl()// für den nachfolgenden merge-Vorgang muss der vector-Container ausreichend groß sein. // Er wächst bei der nachfolgenden Operation nicht dynamisch!
// Funktions-Pointer als predicate
// zur Funktion des merge-Algorithmus:// merge ohne predicate setzt mit operator<() sortierte// Teilsequenzen voraus (also aufsteigend sortiert)// Die merge-Sequenz (hier ab V.begin) enthält alle Elemente in sortierter Reihenfolge// Bei nicht aufsteigend sortierten Sequenzen muss merge mit predicate verwendet werden.
0 1 2 3 4 5 6 7 8 9v
0 2 4 6 8
1 3 5 7 9
d
l
9 8 7 6 5 4 3 2 1 0Ausgabe:
// Funktions-Objekt der Klasse // greater<GanzZahl> als predicate
template< class InIt1, class InIt2, class OutIt > // Prototyp; O(N)OutIt merge(InIt1 first1, InIt1 last1, InIt2 first2, InIt2 last2, OutIt x);template< class InIt1, class InIt2, class OutIt, class Pred > OutIt merge(InIt1 first1, InIt1 last1, InIt2 first2, InIt2 last2, OutIt x, Pred pr);
im WS05 ausgeblendet
17.12.2007 C++ Standard Template Library (STL) 56
FB InformatikProf. Dr. R.Nitsch
Sortier-Alternativen: sort und stable_sort
0.41 1.67 0.34 1.00 2.69 1.24 0.78 2.58 2.62 1.64 0.05 2.45 1.81 0.27 0.61 1.91 2.95
0.41 0.34 0.78 0.61 0.05 0.27 1.67 1.00 1.24 1.91 1.64 1.81 2.95 2.45 2.62 2.58 2.690.41 0.34 0.78 0.05 0.27 0.61 1.67 1.00 1.24 1.64 1.81 1.91 2.69 2.58 2.62 2.45 2.95
class Integer_Less { public:
bool operator() ( double x, double y ) const { return long(x) < long(y); }};void main() {
double d[17] = { 0.41, 1.67, 0.34, 1.00, 2.69, 1.24, 0.78, 2.58, 2.62, 1.64, 0.05, 2.45, 1.81, 0.27, 0.61, 1.91, 2.95 };
vector<double> Vu( &d[0] , &d[17] );std::copy( Vu.begin() , Vu.end() , ostream_iterator<double>(cout," ") ); cout << endl;
std::sort( Vu.begin() , Vu.end() , Integer_Less() );std::copy( Vu.begin() , Vu.end() , ostream_iterator<double>(cout," ") ); cout << endl;
vector<double> Vs( &d[0] , &d[17] );std::stable_sort( Vs.begin() , Vs.end() , Integer_Less() ); std::copy( Vs.begin() , Vs.end() , ostream_iterator<double>(cout," ") ); cout << endl;
}
Eigenschaften von sort:sort arbeitet mit quicksort
→ O(N log N) im Mittel→ O(N2) worst case (wc)→ nicht stabil
Alternative zu sort: stable_sortarbeitet mit merge-sort Algorithmus
→ O(N log N) im Mittel und im worst case→ stabil→ 40% langsamer als sort
Ausgabe
Ergebnis von sortErgebnis von stable_sort
// Vergleich ohne Nachkommastellen
Funktionsobjekt-Klasse als Predicate
im WS05 ausgeblendet
17.12.2007 C++ Standard Template Library (STL) 57
FB InformatikProf. Dr. R.Nitsch
Insert Iteratoren
• Nachteilig im vorigen Beispiel zu "merge" war, daß die Größe des Ziel-Containers ausreichend bemessen sein mußte, um beide Quell-Container-Inhalte aufzunehmen. Gleiches gilt für den Ziel-Container beim copy-Algorithmus. Beim Lesen von Dateien ist dies z.B. problematisch, wenn ihre Größe im Voraus unbekannt ist.
• Abhilfe: Insert-Itertoren - Ein Insert-Iterator i bewirkt in der Anweisung *i= nicht ein Überschreiben des adressierten Objekts sondern ein Einfügen vor dieser Stelle durch Aufruf einer insert-Memberfunktion.
• STL bietet 3 insert-Iterator Typen–back_insert_iterator<ContTyp>(ContName) // benutzt push_back Memberfunktion–front_insert_iterator<ContTyp>(ContName) // benutzt push_front Memberfunktion (nicht bei vector)–insert_iterator<ContTyp>(ContName, pos) // fügt mittels insert Memberfunktion vor Iterator pos ein
void main() {ifstream fin1("intFile1.txt"), fin2("intFile2.txt");vector<int> intVec;copy( istream_iterator<int>(fin1) , istream_iterator<int>(),
back_insert_iterator< vector<int> >(intVec) );copy( intVec.begin(), intVec.end(), ostream_iterator<int>( cout, " " ) );set<int> intSet;merge( intVec.begin(), intVec.end(),
istream_iterator<int>(fin2), istream_iterator<int>(),insert_iterator< set<int> >(intSet, intSet.begin() ) );
copy( intSet.begin(), intSet.end(), ostream_iterator<int>( cout, " ") );}
// … und speichert mittels push_back in intvec
// liest ints aus Datei bis zum Dateiende
9 7 5 3 1 8 6 4 2 0
// leeres Set// Input-Iterator-Range 1
// Input-Iterator-Range 2// Ziel-Container und Einfügestelle
9 7 5 3 1
0 1 2 3 4 5 6 7 8 9
im WS05 ausgeblendet
17.12.2007 C++ Standard Template Library (STL) 58
FB InformatikProf. Dr. R.Nitsch
STL Beispiel 5: Algorithmus generate
• A 'Generator gen' in the std::generate algorithm is a function object or a function which is called without parameters and whose returns are assigned (=) one by one to the elements of the sequence.
template <class FwdIt, class Generator> // Prototyp; O(N)void generate(FwdIt first, FwIt last, Generator gen);
#include <cstdlib> // rand()#include <algorithm>#include <vector>#include <iostream>using namespace std;class Random {public:
Random(long b) : range(b) { }// returns random number between 0 and range -1long operator()() {
return rand() % range;}
private:long range;
};
int powerOfTwo() { // double value; begin with 1static int value = 1;return ( value=value<<1 ) >> 1;
}
void main() {vector<int> v(6);Random lotto(49);ostream_iterator<int> out( cout, " " );std::generate( v.begin(), v.end(), lotto );copy( v.begin(), v.end(), out );cout << endl;generate_n( v.begin(), 5, powerOfTwo );std::copy( v.begin(), v.end(), out );v.resize( 0 ); // size()==0!generate_n( v.begin(), 5, powerOfTwo );back_insert_iterator< vector<int> > v_iter( v );generate_n( v_iter, 5, powerOfTwo );std::copy( v.begin(), v.end(), out );v.assign( 5, 0 ); generate_n( v_iter, 5, powerOfTwo );std::copy( v.begin(), v.end(), out );
}
// 41 43 13 40 10 44
// 1 2 4 8 16 44
Konstruktor
// no parameters!
template<class OutputIterator, class Size, class Generator> // Prototypvoid generate_n( OutputIterator _First, Size _Count, Generator _Gen );
// 1 2 4 8 16 44
// 1 2 4 8 16 44// v.erase(); v.insert( v.begin(), 5, 0 );
// gen takes no arguments
// Fehlerursache?Fehler: v wächst nicht!
17.12.2007 C++ Standard Template Library (STL) 59
FB InformatikProf. Dr. R.Nitsch
STL Beispiel 6: Algorithmus next_permutation
• Der Algorithmus permutiert die Sequenz in [first,last) in ihren Nachfolger bei lexikografischer Sortierung.
• return true, wenn ein Nachfolger existiert. Falls nicht wird die lexikografisch kleinste Permutation erzeugt und false zurück gegeben.
• benötigt value_type::operator<
// Finde alle Worte, die aus den Buchstaben 'n', 'i' und 'e' gebildet werden könnenvoid main() {
cout << boolalpha << left ;string s = "ein"; bool b = false;for ( int i=0; i<7; ++i ) {copy( s.begin(), s.end(), ostream_iterator<char>( cout, " " ) );cout << " : " << b << endl;b = next_permutation( s.begin(), s.end() );
}}
false e i ntrue e n itrue i e ntrue i n etrue n e itrue n i efalse e i n
Beispiel:Permutationen der Zeichen 'e', 'i' und 'n'
17.12.2007 C++ Standard Template Library (STL) 60
FB InformatikProf. Dr. R.Nitsch
Grundsätzliches zu Containern
• Container und Vererbung– Behälterklassen werden in C++ üblicherweise als Template realisiert (siehe STL)– Beachte:
• Oberklassen-Objekte können nicht in Containern für ihre Unterklassen gespeichert werden.
• Aber: Unterklassen-Objekte können in Containern für ihre Oberklassen gespeichert werden ☺
– Achtung: Beim Speichern von Objekten abgeleiteter Klassen in Containernfür Objekte der Oberklasse wird das Unterklassen-Objekt auf den Typ des Oberklassen-Objekts reduziert.
– Deshalb: Container für Oberklassen-Objekte, die auch Objekte aller abgeleiteten Klassen aufnehmen sollen, müssen Zeiger oder Referenzen auf die Objekte speichern (Ausnutzung der is-a-Beziehung für Objekt-Referenzen).
– Solche Container haben eine Wert-Semantik bezüglich der gespeicherten Referenzen, aber eine Referenzsemantik bezüglich der "gespeicherten" und meist dynamisch erzeugten Objekte (Beispiel: siehe Übung 3 "Smart House")
17.12.2007 C++ Standard Template Library (STL) 61
FB InformatikProf. Dr. R.Nitsch
Nocheinmal: Fallstudie "Personal- und Lohnbuchhaltung"
// includes // using Anweisungen …
int main() {// Voreinstellung Zahlenausgabe im Gleitpunktformatcout << fixed << setprecision( 2 );// Firma gründenvector < Personal* > beschaeftigte( 4, 0 );// Personal einstellenbeschaeftigte[0] = new Angestellter( "Hans", "Fleissig", "111", 800.00 );beschaeftigte[1] = new Verkaeufer( "Klaus", "Wirbelwind", "222", 10000, .06 );beschaeftigte[2] = new LeitenderAngestellter( "Bernd", "Schlau", "333",300, 5000,.04 );beschaeftigte[3] = new Arbeiter( "Karl", "Machtalles", "444", 16.75, 40 );// Gehaltsmitteilungen erstellen// Personaldaten elementweise verarbeitenfor ( int i = 0; i < beschaeftigte.size(); i++ ) {
//Personalstammdaten druckenbeschaeftigte[i]->drucke();// hier Gehaltserhöhungen verarbeiten …(ausgeblendet) und nun ausgeben:cout << "Gehalt: Euro " << beschaeftigte[i]->Gehalt() << endl;
} // end for}
Angestellter: Hans FleissigPersonalNummer: 111Gehalt: Euro 800.00
Verkaeufer: Klaus WirbelwindPersonalNummer: 222Gehalt: Euro 600.00
…
Ausgabe:
Alle von Basisklasse "Personal" abgeleitet
Im Container werden 4 Basisklassen-Pointer gespeichert und mit 0 initialisiert.
Pointer auslesen und polymorph dereferenzieren!
Aufgabe:• Personal und Lohnbuchhaltung mit Container "list"• Verwendung von Iteratoren und STL Algorithmen
17.12.2007 C++ Standard Template Library (STL) 62
FB InformatikProf. Dr. R.Nitsch
Fallstudie "Personal- und Lohnbuchhaltung" mit STL
/* include und using Anweisungen */int main() {
// Voreinstellung Zahlenausgabe im Gleitpunktformatcout << fixed << setprecision( 2 );// Firma gründentypedef list<Personal*> PERSONALKARTEI;PERSONALKARTEI beschaeftigte;// Personal einstellenbeschaeftigte.push_back( new Angestellter( "John", "Smith", "111", 800.00 ) );beschaeftigte.push_back( new Verkaeufer( "Sue", "Jones", "222", 10000, .06 ) );beschaeftigte.push_back( new LeitenderAngestellter( "Bob", "Lewis", "333", 300, 5000, .06 ) );beschaeftigte.push_back( new Arbeiter( "Karen", "Price", "444", 16.75, 40 ) );// Gehaltsanpassungen verarbeiten
Tarif dezember( 300.f*1.1f, 800.00f, 0.06f, 16.75f );std::for_each( beschaeftigte.begin(), beschaeftigte.end(), dezember );// Gehaltsmitteilungen druckenGehaltsmitteilungToStream druckeGM( "01/06" , cout );std::for_each( beschaeftigte.begin(), beschaeftigte.end(), druckeGM ); cout << endl;// Alle Beschäftigten entlassenPERSONALKARTEI::iterator iter = beschaeftigte.begin(); while( iter != beschaeftigte.end() ) {
delete *iter;iter = beschaeftigte.erase(iter);
}cout << endl;return 0;
} // end main
// Destruktor der Klasse Personal gibt Kündigungsschreiben aus// iter zeigt danach auf das Element hinter dem gelöschten!
// Funktionsobjekt das Gehaltsmitteilungen ausgibt
// Funktionsobjekt das Gehaltserhöhungen kennt
Leitender Angestellter +10% Angestellter 0% Verkäufer 0% Arbeiter 0%
17.12.2007 C++ Standard Template Library (STL) 63
FB InformatikProf. Dr. R.Nitsch
Fallstudie "Personal- und Lohnbuchhaltung" mit STL
class Tarif {private:
float ltdAngGG, angMG, arbStdL, verkProv;public:
Tarif( float ltdAngGG , float angMG, float verkProv, float arbStdL ): ltdAngGG(ltdAngGG), angMG(angMG), verkProv(verkProv), arbStdL(arbStdL) { }
void operator()( Personal* p ) { if(p!=0) p->tarifAendern( *this );
}
float getAngMG() { return angMG; }float getArbStdL() { return arbStdL; }float getVerkProv() { return verkProv; }float getLtdAngGG() { return ltdAngGG; }
};
Hier ist Referenzsemantik erforderlich: for_each liest nacheinander die Objekte aus dem Container (hier vom Typ Personal* ) und übergibt sie dem Funktionsobjekt zur Bearbeitung. Dieser Typ muß vom Funktionsobjekt erwartet werden.
17.12.2007 C++ Standard Template Library (STL) 64
FB InformatikProf. Dr. R.Nitsch
Fallstudie "Personal- und Lohnbuchhaltung" mit STL
class Tarif;
class Personal {public:virtual void tarifAendern( Tarif& tarif ) = 0;// Rest ausgelassen
};
// pure virtual
//Gehaltserhöhung verarbeitenvoid LeitenderAngestellter::tarifAendern( Tarif& tarif ){
float neuesGrundgehalt = tarif.getLtdAngGG();if ( grundGehalt!=neuesGrundgehalt ) { // Gehaltsänderungcout << "Mitteilung zur Gehaltserhoehung";drucke(cout);cout << "Grundgehalt (alt): " << grundGehalt << endl
<< "Grundgehalt (neu): " << neuesGrundgehalt << endl;grundGehalt = neuesGrundgehalt;
} // end if}
// Vorwärtsdeklaration
17.12.2007 C++ Standard Template Library (STL) 65
FB InformatikProf. Dr. R.Nitsch
Fallstudie "Personal- und Lohnbuchhaltung" mit STL
class GehaltsmitteilungToStream {private:
ostream* pStream; string monat;
public:GehaltsmitteilungToStream( const string& m, const ostream& ostr = cout )
: pStream(&ostr), monat(m) { }
void operator() ( Personal* p ) {p->drucke(os);os << "Gehalt fuer Monat " << monat << " (Euro): " << p->gibGehalt() << endl;
} // end operator()};
Hier ist Referenzsemantik erforderlich: for_each entnimmt nacheinander die Objekte aus dem Container ( hier vom Typ Personal* ) und übergibt sie dem Funktionsobjekt zur Bearbeitung. Dieser Typ muß vom Funktionsobjekt erwartet werden.
17.12.2007 C++ Standard Template Library (STL) 72
FB InformatikProf. Dr. R.Nitsch
Memberfunktionen, die in allen Container-Klassen implementiert sind
C();
C u(a);~C();
a < b;a <= b;
a > b;a >= b;a == b;
a != b;a.begin();
a.end();a.rbegin(); nur in reversiblen Containern (list, vector, deque, map, set)a.rend(); nur in reversiblen Containern (list, vector, deque, map, set)a.erase();a.empty(); true, wenn keine Elemente gespeichert sinda.max_size(); size() des größten möglichen Containersa.size(); Anzahl gespeicherter Objekte im Containerr = a; Zuweisungsoperator für Containera.swap(b); Tauscht Inhalte von Containern gleichen Typs
Annahmen:C ist eine Containerklasse mit Objekten vom Typ Ta, b, r und u sind Objekte vom Typ C
Recommended