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 dieser Vorlesung 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

Beispiel fuer einen sequentiellen Container mit der Klasse vector nach 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.
 */
#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

Beispiel fuer einen sequentiellen Container mit der Klasse list nach 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.
 */
#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. Iteratoren

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):

Typen von Iteratoren

• Trivial Iterator

• Input Iterator

• Output Iterator

• Forward Iterator

• Bidirectional Iterator

• Random Access Iterator

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) {
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



    
Beispiel eines assoziativen Containers set in Verbindung mit Input-Iteratoren saowie einem Result-Iterator: 

//---------------------
//
// 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 
 




 
 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


  

    
Noch zu schreiben....
  


 
 

 START