Achtung : Skript gibt den mündlichen Vortrag nur teilweise wieder !!! 
	Achtung : Skript noch nicht abgeschlossen !!!
                        

1. Einführung

Im bisherigen Verlauf der Lehrveranstaltung wurde in stark vereinfachter Form verdeutlicht, was unter einem Softwareprojekt im Rahmen des MDA-Ansatzes der OMG zu verstehen ist. Das allgemeine Konzept wurde am Beispiel einer konkreten Problemstellung konkretisiert und illustriert. In diesem Zusammenhang sind auch erste Grundelemente der Programmiersprache C++ eingeführt worden. Insbesondere wurden neben dem Grundbegriff Klasse die Begriffe Referenz, Konstruktor, Dekonstruktor sowie Template erläutert. Auch wurde das Konzept der Ausnahmebehandlung schon besprochen sowie die Behandlung von Input und Output.

In den Vorlesunen 10+11g wird jetzt das Grundkonzept der Standard Library (STL) vorgestellt. Im Mittelpunkt stehen die Konzepte Container, Iterator sowie Algorithmus.

START

2. Container, Iteratoren, Algorithmen

Das Grundgerüst der STL kann man in den Begriffen Container, Iterator und Algorithmus fassen (vgl. Schaubild).

Wechselspiel zwischen Container, Iteratoren und Algorithmen

START

3. Container

Container sind jene Klassen, in denen man die unterschiedlichsten Daten sammelt und sie nach unterschiedlichen Gesichtspunkten ordnet. Man unterscheidet zwei Basistypen bei Containern: (i) solche, bei denen die Werte sequentiell angeordnet sind, und solche (ii) bei denen die Werte nach Schlüsseln (keys) angeordnet sind. Container mit sequentiell angeordneten Daten nennt man Sequenz-Container und solche, in denen nach Schlüsseln geordnet wird Assoziative Container (vgl. Schaubild).

Typen von Containern

• vector

• deque

• list

Die Kurzcharakteristik eines Assozitiven Containers lautet: "An Associative Container is a variable-sized Container that supports efficient retrieval of elements (values) based on keys. It supports insertion and removal of elements, but differs from a Sequence in that it does not provide a mechanism for inserting an element at a specific position."

Konkrete Beispiele (Instanzen, Modelle) von Assoziativen Containern sind die folgenden:

• set

• multiset

• map

• multimap

Weiterführende Beschreibungen findet man unter folgender Klassifizierung:

• Simple Associative Container

• Pair Associative Container

• Unique Associative Container

• Multiple Associative Container

• Sorted Associative Container

• Unique Sorted Associative Container

• Multiple Sorted Associative Container

START

Vector

Beispiel fuer einen sequentiellen Container mit der Klasse vector nach Josuttis (Für Details siehe: vector)

/* The following code example is taken from the book
 * "The C++ Standard Library - A Tutorial and Reference"
 * by Nicolai M. Josuttis, Addison-Wesley, 1999
 *
 * (C) Copyright Nicolai M. Josuttis 1999.
 * Permission to copy, use, modify, sell and distribute this software
 * is granted provided this copyright notice appears in all copies.
 * This software is provided "as is" without express or implied
 * warranty, and with no claim as to its suitability for any purpose.
 */
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <iterator>

using namespace std;

int main()
{
    // create empty vector for strings
    vector<string> sentence;

    // reserve memory for five elements to avoid reallocation
    sentence.reserve(5);

    // append some elements
    sentence.push_back("Hello,");
    sentence.push_back("how");
    sentence.push_back("are");
    sentence.push_back("you");
    sentence.push_back("?");

    // print elements separated with spaces
    copy (sentence.begin(), sentence.end(),
          ostream_iterator<string>(cout," "));
    cout << endl;

    // print ``technical data''
    cout << "  max_size(): " << sentence.max_size() << endl;
    cout << "  size():     " << sentence.size()     << endl;
    cout << "  capacity(): " << sentence.capacity() << endl;

    // swap second and fourth element
    swap (sentence[1], sentence[3]);

    // insert element "always" before element "?"
    sentence.insert (find(sentence.begin(),sentence.end(),"?"),
                     "always");

    // assign "!" to the last element
    sentence.back() = "!";
    
    // print elements separated with spaces
    copy (sentence.begin(), sentence.end(),
          ostream_iterator<string>(cout," "));
    cout << endl;

    // print ``technical data'' again
    cout << "  max_size(): " << sentence.max_size() << endl;
    cout << "  size():     " << sentence.size()     << endl;
    cout << "  capacity(): " << sentence.capacity() << endl;
}

gerd@kant:~/public_html/fh/II-PPmP/VL/VL10> ./vector2
Hello, how are you ?
  max_size(): 1073741823
  size():     5
  capacity(): 5
Hello, you are how always !
  max_size(): 1073741823
  size():     6
  capacity(): 10

START

Liste

Beispiel fuer einen sequentiellen Container mit der Klasse list nach Josuttis (Für Details siehe: list)

/* The following code example is taken from the book
 * "The C++ Standard Library - A Tutorial and Reference"
 * by Nicolai M. Josuttis, Addison-Wesley, 1999
 *
 * (C) Copyright Nicolai M. Josuttis 1999.
 * Permission to copy, use, modify, sell and distribute this software
 * is granted provided this copyright notice appears in all copies.
 * This software is provided "as is" without express or implied
 * warranty, and with no claim as to its suitability for any purpose.
 */
#include <iostream>
#include <list>
#include <algorithm>
#include <iterator>

using namespace std;

void printLists (const list<int>& l1, const list<int>& l2)
{
    cout << "list1: ";
    copy (l1.begin(), l1.end(), ostream_iterator<int>(cout," "));
    cout << endl << "list2: ";
    copy (l2.begin(), l2.end(), ostream_iterator<int>(cout," "));
    cout << endl << endl;
}

int main()
{
    // create two empty lists
    list<int> list1, list2;

    // fill both lists with elements
    for (int i=0; i<6; ++i) {
        list1.push_back(i);
        list2.push_front(i);
    }
    printLists(list1, list2);

    // insert all elements of list1 before the first element with value 3 of list2
    // - find() returns an iterator to the first element with value 3
    list2.splice(find(list2.begin(),list2.end(),  // destination position
                      3),
                 list1);                          // source list
    printLists(list1, list2);

    // move first element to the end
    list2.splice(list2.end(),        // destination position
                 list2,              // source list
                 list2.begin());     // source position
    printLists(list1, list2);

    // sort second list, assign to list1 and remove duplicates
    list2.sort();
    list1 = list2;
    list2.unique();
    printLists(list1, list2);

    // merge both sorted lists into the first list
    list1.merge(list2);
    printLists(list1, list2);
}

gerd@kant:~/public_html/fh/II-PPmP/VL/VL10> ./list1
list1: 0 1 2 3 4 5
list2: 5 4 3 2 1 0

list1:
list2: 5 4 0 1 2 3 4 5 3 2 1 0

list1:
list2: 4 0 1 2 3 4 5 3 2 1 0 5

list1: 0 0 1 1 2 2 3 3 4 4 5 5
list2: 0 1 2 3 4 5

list1: 0 0 0 1 1 1 2 2 2 3 3 3 4 4 4 5 5 5
list2:

In beiden Beispielen werden Iteratoren benutzt. Diese werden jetzt erläutert.

START

4. Iterator; Iterator Adaptor

Ein Iterator ist ein Objekt, das auf Elemente in einem Container zeigen kann und zusätzlich mögliche Vorgänger oder Nachfolger findet.M an unterscheidet die folgenden Typen von Iteratoren (vgl. Schaubild). Ein Iterator Adaptor ist eine Klasse, die sich formal wie ein Iterator verhält, aber zusätzloiche Eigenschaften besitzt (siehe unten).

Typen von Iteratoren

• Trivial Iterator

• Input Iterator

• Output Iterator

• Forward Iterator

• Bidirectional Iterator

• Random Access Iterator

Folgende Iterator Adaptoren werden in der STL unterschieden:

• Insert Iteratoren

• Stream Iteratoren

• Reverse Interatoren

Beispiele für Insert Iteratoren:

Das folgende kleine Programm von Josuttis zeigt alle drei Typen von Insert Iterator Adaptoren im Einsatz

/* The following code example is taken from the book
 * "The C++ Standard Library - A Tutorial and Reference"
 * by Nicolai M. Josuttis, Addison-Wesley, 1999
 *
 * (C) Copyright Nicolai M. Josuttis 1999.
 * Permission to copy, use, modify, sell and distribute this software
 * is granted provided this copyright notice appears in all copies.
 * This software is provided "as is" without express or implied
 * warranty, and with no claim as to its suitability for any purpose.
 */
/**************************************************************
 *
*  Minor Modifications for printouts by gerd d-h
*
****************************************************************/


#include <iostream>
#include <vector>
#include <list>
#include <deque>
#include <set>
#include <algorithm>
#include <iterator>

using namespace std;

int main()
{
    list<int> coll1;

    // insert elements from 1 to 9 into the first collection
    for (int i=1; i<=9; ++i) {
        coll1.push_back(i);
    }
  copy (coll1.begin(), coll1.end(),      // source
	ostream_iterator<int>(cout," "));           // destination

  cout << endl;


    // copy the elements of coll1 into coll2 by appending them
    vector<int> coll2;
    copy (coll1.begin(), coll1.end(),      // source
          back_inserter(coll2));           // destination

  copy (coll2.begin(), coll2.end(),      // source
	ostream_iterator<int>(cout," "));           // destination

  cout << endl;

    // copy the elements of coll1 into coll3 by inserting them at the front
    // - reverses the order of the elements
    deque<int> coll3;
    copy (coll1.begin(), coll1.end(),      // source
          front_inserter(coll3));          // destination

  copy (coll3.begin(), coll3.end(),      // source
	ostream_iterator<int>(cout," "));           // destination

  cout << endl;


    // copy elements of coll1 into coll4
    // - only inserter that works for associative collections
    set<int> coll4;
    copy (coll1.begin(), coll1.end(),      // source
          inserter(coll4,coll4.begin()));  // destination


  copy (coll4.begin(), coll4.end(),      // source
	ostream_iterator<int>(cout," "));           // destination

  cout << endl;

}

gerd@kant:~/public_html/fh/II-PPmP/VL/VL11> g++ -o copy3b copy3b.cpp
gerd@kant:~/public_html/fh/II-PPmP/VL/VL11> ./copy3b
1 2 3 4 5 6 7 8 9
1 2 3 4 5 6 7 8 9
9 8 7 6 5 4 3 2 1
1 2 3 4 5 6 7 8 9

Das folgende kleine Programm von Josuttis zeigt, wie ein Iterator auf einen Container vom Typ Liste zugreift.

/* The following code example is taken from the book
 * "The C++ Standard Library - A Tutorial and Reference"
 * by Nicolai M. Josuttis, Addison-Wesley, 1999
 *
 * (C) Copyright Nicolai M. Josuttis 1999.
 * Permission to copy, use, modify, sell and distribute this software
 * is granted provided this copyright notice appears in all copies.
 * This software is provided "as is" without express or implied
 * warranty, and with no claim as to its suitability for any purpose.
 */

#include <iostream>
#include <list>
#include <iterator>

using namespace std;

int main()
{
    list<char> coll;      // list container for character elements

    // append elements from 'a' to 'z'
    for (char c='a'; c<='z'; ++c) {
        coll.push_back(c);
    }

    /* print all elements
     * - iterate over all elements
     */
    list<char>::const_iterator pos;
    for (pos = coll.begin(); pos != coll.end(); ++pos) {
        cout << *pos << ' ';
    }
    cout << endl;
}

gerd@linux:~/public_html/fh/II-PPmP/VL/VL10> g++ -o list2 list2.cpp
gerd@linux:~/public_html/fh/II-PPmP/VL/VL10> ./list2
a b c d e f g h i j k l m n o p q r s t u v w x y z

START

Set

Beispiel eines assoziativen Containers set in Verbindung mit Input-Iteratoren saowie einem Result-Iterator (fürv Details siehe Set)

//---------------------
//
// set3.cpp
//
// This example is taken from the public STL-site of SGI
// See: http://www.sgi.com/tech/stl/
//------------------------------

#include <iostream>
#include <set>
#include <iterator>


using namespace std;

// Hilfsfunktion lt := less-than, kleiner als
// Vergleicht zwei Zeichenketten

struct ltstr
{
  bool operator()(const char* s1, const char* s2) const
  {
    return strcmp(s1, s2) < 0;
  }
};

int main()
{
  // Bereitstellung von zwei gewoehnlichen Arrays vom Typ char:

  const int N = 6;
  const char* a[N] = {"isomer", "ephemeral", "prosaic", 
                      "nugatory", "artichoke", "serif"};
  const char* b[N] = {"flat", "this", "artichoke",
                      "frigate", "prosaic", "isomer"};

  // Es werden jetzt drei Mengen-Objekte angelegt: A, B und C.
  // In allen drei Faellen wird der Typ des Schluessels (= Key) auf char* festgelegt,
  // d.h. die Elemente dieser Mengen sind vom Typ Pointer auf Zeichenkette.
  // Ferner wird eine Vergleichsfunktion ltstr angegeben.Diese Vergleichsfunktion kann 
  // zwei beliebige Elemente in der Menge vergleichen. Sie liefert true (=1)  zurueck, wenn das 
  // erste Argument nicht mit dem zweiten Argument uebereinstimmt, sonst false (=0).

  set<const char*, ltstr> A(a, a + N);
  set<const char*, ltstr> B(b, b + N);
  set<const char*, ltstr> C;

  cout << "Set A: ";
  copy(A.begin(), A.end(), ostream_iterator<const char*>(cout, " "));
  cout << endl;
  cout << "Set B: ";
  copy(B.begin(), B.end(), ostream_iterator<const char*>(cout, " "));   
  cout << endl;

  cout << "Union: ";
  set_union(A.begin(), A.end(), B.begin(), B.end(),
            ostream_iterator<const char*>(cout, " "),
            ltstr());   
  cout << endl;

  cout << "Intersection: ";
  set_intersection(A.begin(), A.end(), B.begin(), B.end(),
                   ostream_iterator<const char*>(cout, " "),
                   ltstr());    
  cout << endl;

  set_difference(A.begin(), A.end(), B.begin(), B.end(),
                 inserter(C, C.begin()),
                 ltstr());
  cout << "Set C (difference of A and B): ";
  copy(C.begin(), C.end(), ostream_iterator<const char*>(cout, " "));
  cout << endl;
}

gerd@kant:~/public_html/fh/II-PPmP/VL/VL10> ./set3
Set A: artichoke ephemeral isomer nugatory prosaic serif
Set B: artichoke flat frigate isomer prosaic this
Union: artichoke ephemeral flat frigate isomer nugatory prosaic serif this
Intersection: artichoke isomer prosaic
Set C (difference of A and B): ephemeral nugatory serif

START

Map

(Für Details siehe Map)

/* The following code example is taken from the book
 * "The C++ Standard Library - A Tutorial and Reference"
 * by Nicolai M. Josuttis, Addison-Wesley, 1999
 *
 * (C) Copyright Nicolai M. Josuttis 1999.
 * Permission to copy, use, modify, sell and distribute this software
 * is granted provided this copyright notice appears in all copies.
 * This software is provided "as is" without express or implied
 * warranty, and with no claim as to its suitability for any purpose.
 */
#include <iostream>
#include <map>
#include <string>
#include<iterator>


using namespace std;

int main()
{
    /* create map / associative array
     * - keys are strings
     * - values are floats
     */
    typedef map<string,float> StringFloatMap;

    StringFloatMap stocks;      // create empty container

    // insert some elements
    stocks["BASF"] = 369.50;
    stocks["VW"] = 413.50;
    stocks["Daimler"] = 819.00;
    stocks["BMW"] = 834.00;
    stocks["Siemens"] = 842.20;

    // print all elements
    StringFloatMap::iterator pos;
    for (pos = stocks.begin(); pos != stocks.end(); ++pos) {
        cout << "stock: " << pos->first << "\t"
             << "price: " << pos->second << endl;
    }
    cout << endl;

    // boom (all prices doubled)
    for (pos = stocks.begin(); pos != stocks.end(); ++pos) {
        pos->second *= 2;
    }

    // print all elements
    for (pos = stocks.begin(); pos != stocks.end(); ++pos) {
        cout << "stock: " << pos->first << "\t"
             << "price: " << pos->second << endl;
    }
    cout << endl;

    /* rename key from "VW" to "Volkswagen"
     * - only provided by exchanging element
     */
    stocks["Volkswagen"] = stocks["VW"];
    stocks.erase("VW");

    // print all elements
    for (pos = stocks.begin(); pos != stocks.end(); ++pos) {
        cout << "stock: " << pos->first << "\t"
             << "price: " << pos->second << endl;
    }
}

gerd@kant:~/public_html/fh/II-PPmP/VL/VL11> g++ -o map1 map1.cpp
gerd@kant:~/public_html/fh/II-PPmP/VL/VL11> ./map1
stock: BASF     price: 369.5
stock: BMW      price: 834
stock: Daimler  price: 819
stock: Siemens  price: 842.2
stock: VW       price: 413.5

stock: BASF     price: 739
stock: BMW      price: 1668
stock: Daimler  price: 1638
stock: Siemens  price: 1684.4
stock: VW       price: 827

stock: BASF     price: 739
stock: BMW      price: 1668
stock: Daimler  price: 1638
stock: Siemens  price: 1684.4
stock: Volkswagen       price: 827

START

Multimap

(Für Details siehe Multimap )

Das nachfolgende Beispiel von Josuttis benutzt Formattierungsanweisungen für cout.Für eine ausführliche Auflistung und Besprechung sei auf den C++-Standard verwiesen sowie auf das hervorragende STL-Buch von Josuttis.

/* The following code example is taken from the book
 * "The C++ Standard Library - A Tutorial and Reference"
 * by Nicolai M. Josuttis, Addison-Wesley, 1999
 *
 * (C) Copyright Nicolai M. Josuttis 1999.
 * Permission to copy, use, modify, sell and distribute this software
 * is granted provided this copyright notice appears in all copies.
 * This software is provided "as is" without express or implied
 * warranty, and with no claim as to its suitability for any purpose.
 *****************************************************************
 *
 * some minor changes for output by gerd d-h
 *
 ***********************************************************/

#include <iostream>
#include <map>
#include <string>
#include <iomanip>
#include<iterator>

using namespace std;

int main()
{
    // define multimap type as string/string dictionary
    typedef multimap<string,string> StrStrMMap;

    // create empty dictionary
    StrStrMMap dict;

    // insert some elements in random order
    dict.insert(make_pair("day","Tag"));
    dict.insert(make_pair("strange","fremd"));
    dict.insert(make_pair("car","Auto"));
    dict.insert(make_pair("smart","elegant"));
    dict.insert(make_pair("trait","Merkmal"));
    dict.insert(make_pair("strange","seltsam"));
    dict.insert(make_pair("smart","raffiniert"));
    dict.insert(make_pair("smart","klug"));
    dict.insert(make_pair("clever","raffiniert"));

    // print all elements
    StrStrMMap::iterator pos;
    cout.setf (ios::left, ios::adjustfield);
    cout << ' ' << setw(10) << "english "
         << "german " << endl;
    cout << setfill('-') << setw(20) << ""
         << setfill(' ') << endl;
    for (pos = dict.begin(); pos != dict.end(); ++pos) {
        cout << ' ' << setw(10) << pos->first.c_str()
             << pos->second << endl;
    }
    cout << endl;

    // print all values for key "smart"
    string word("smart");
    cout << word << ": " << endl;
    for (pos = dict.lower_bound(word);
         pos != dict.upper_bound(word); ++pos) {
      cout << left << setw(12) << setfill('_') <<  pos->second << endl;
    }

    // print all keys for value "raffiniert"
    word = ("raffiniert");
    cout << word << ": " << endl;
    for (pos = dict.begin(); pos != dict.end(); ++pos) {
        if (pos->second == word) {
	  cout <<  right << setw(12) << setfill('_') << pos->first << endl;
        }
    }

    cout << oct << cout.flags() << endl;
}

gerd@kant:~/public_html/fh/II-PPmP/VL/VL11> g++ -o mmap1b mmap1b.cpp
gerd@kant:~/public_html/fh/II-PPmP/VL/VL11> ./mmap1b
 english   german
--------------------
 car       Auto
 clever    raffiniert
 day       Tag
 smart     elegant
 smart     raffiniert
 smart     klug
 strange   fremd
 strange   seltsam
 trait     Merkmal

smart:
elegant_____
raffiniert__
klug________
raffiniert:
______clever
_______smart
10202

START

5. Algorithmen

In den vorausgehenden Beispielen wurde schon verschiedentlich die copy()-Funktion benutzt. De copy()-Funktion wie auch andere funktionen wie z.B. sort(), set_intersection() usw. sind Algorithmen, die mit Hilfe von Iteratoren auf Container zugreifen. einige Beispiele für solche Algorithmen sind die folgenden:

• copy()-Algorithmus

• sort()-Algorithmus

• set_union()-Algorithmus

• set__intersection()-Algorithmus

• set_difference()-Algorithmus

Ein einfaches Beispiel für den sort()-Algorithmus findet sich im folgenden Programm:

//------------------
//
// ioiter0.cpp
//
//---------------------------

#include <iostream>
#include <vector>
#include <algorithm>
#include <iterator>

using namespace std;

int main()
{
   
vector<int> coll;

 copy(istream_iterator<int>(cin),      //source
      istream_iterator<int>(),         // EOF := Ctrl-D
      back_inserter(coll));            //destination

 coll.insert(coll.begin(),100);    

// sort elements
    sort (coll.begin(), coll.end());



copy(coll.begin(), coll.end(),             // source
     ostream_iterator<int>(cout,"\n")); // destination

 return(1);
}

gerd@kant:~/public_html/fh/II-PPmP/VL/VL10> ./ioiter0
22
33
6
7654
4
8768
4
6
22
33
100
7654
8768

START

6. Testfragen

1. Noch zu schreiben....

START