Standard Template Library

oder Wie man das Strategy Pattern mit Templates umsetzt.

Die Konfiguration von Algorithmen mittels Objekten bezeichnet man gerne als Strategy, hingegen die Konfiguration von Typen mittels Subtypen als Traits. Die STL basiert im Wesentlichen auf drei Komponenten, den Algorithmen, den Datencontainern und den Iteratoren.
Die generischen Algorithmen wirken auf den Elementen der Datencontainer durch die Iteratoren.
Die Iteratoren stellen das verbindende Elemente zwischen den Datencontainern und den Algorithmen dar.

Im Gegensatz zur objektorientierten Orientierung, in der die Daten und Algorithmen in einer Klasse gekapselt sind, sind in der STL die Algorithmen von den Datenstrukturen getrennt.

Abgerundet wird die STL einerseits durch Funktionspointer bzw. Funktoren, um die Algorithmen zu konfigurieren und andererseits durch Iteratoradaptoren, um die Iteratoren universeller einzusetzten.
Durch den Erweiterung des C++ Standards um anonyme Funktionen, bzw. lambda Funktionen, unterstützt die STL neben dem generischen auch insbesondere das funktionaleProgrammieren.

Beispiel

Den STL Algorithmus accumulate gibt es ein zwei Variationen:

T accumulate( InputIterator beg, InputIterator end, T initValue ):
T accumulate( InputIterator beg, InputIterator end, T initValue , BinaryFunc op):

Beide Algorithmen erwarten

zwei Iteratoren beg und end
ein Initialisierungswert initValue, der dem Returntyp entsprechen muß

Die zweite Variation kann über einen binären Funktor parametrisiert werden.

Als Ergebnis erzeugt die erste Variante für die Elemente a1 a2 a3 ...

(((initValue + a1 ) + a2 ) + a3 ) + ..

und die zweite Variante

(((initValue op a1 ) op a2 ) op a3 ) op ..

Das folgende Beispiel soll den generischen Ansatz der STL mittels Templates hervorheben, denn es variiert in drei Aspekten:

Elemente der Container
Typ des Containers
Verhalten des Algorithmus

#include <functional>
#include <iostream>
#include <numeric>

#include <string>

#include <set>
#include <vector>

#include "functor.hpp"

#include "IntSequence.h"

int main(){

        std::vector<int> intsInVector;

        std::generate_n( std::back_inserter( intsInVector ), 10, IntSequence (0));

        std::cout << "intsInVector :";
        std::copy ( intsInVector.begin(), intsInVector.end(),

                std::ostream_iterator < int > ( std::cout, " "));

        std::vector< std::string > stringsInVector;
        stringsInVector.push_back("one");

        stringsInVector.push_back("two");
        stringsInVector.push_back("two");
        stringsInVector.push_back("three");

        stringsInVector.push_back("four");
        stringsInVector.push_back("five");
        stringsInVector.push_back("six");

        stringsInVector.push_back("seven");
        stringsInVector.push_back("eight");
        stringsInVector.push_back("nine");

        stringsInVector.push_back("ten");

        std::cout << "\n" << "stringsInVector :";

        std::copy ( stringsInVector.begin(), stringsInVector.end(),

                std::ostream_iterator < std::string> ( std::cout, " "));

        std::cout << "\n\n\n---------- Variation der Elemente: ----";

        std::cout << "\n" << "intsInVector sum:   " ;

        std::cout << std::accumulate( intsInVector.begin(), intsInVector.end(),0 ) ;

        std::cout <<"\n" <<  "stringsInVector sum: ";
        std::cout << std::accumulate( stringsInVector.begin(), stringsInVector.end()  ,std::string("") );

        std::cout << "\n\n\n----------- Variation des Containers: ----" << std::endl;

        std::set<int> intsInSet ( intsInVector. begin(), intsInVector.end() );

        std::cout <<  "intsInSet sum: ";
        std::cout<< std::accumulate( intsInSet.begin(), intsInSet.end()  ,0 );

        std::set< std::string > stringsInSet( stringsInVector. begin(), stringsInVector.end() );

        std::cout <<"\n" <<  "stringsInSet sum: ";
        std::cout << std::accumulate( stringsInSet.begin(), stringsInSet.end(),std::string("") );

        std::cout << "\n\n\n----------- Variation des Algorithmus: ----" << std::endl;

        std::cout <<"\n" <<  "10 Faktultät :";
        std::cout << std::accumulate( intsInVector.begin(), intsInVector.end(),1, std::multiplies< int > ()  ) ;

        std::cout <<"\n" <<  "Norm :";
        std::cout << std::sqrt( static_cast<double> ( std::accumulate( intsInVector.begin(), intsInVector.end(), 0, addQuad< int > ()  ) ) ) ;

        std::cout << std::accumulate( stringsInVector.begin(), stringsInVector.end()  ,std::string("\nPurify    "),addSep<std::string> (std::string(" : " )));

        std::cout << std::accumulate( stringsInVector.begin(), stringsInVector.end() ,std::string("\nPurify title     "),  addSepAndTitle<std::string> (std::string(" : " )) );

};

Hierzu die entsprechende Ausgabe.

intsInVector :1 2 3 4 5 6 7 8 9 10 
stringsInVector :one two two three four five six seven eight nine ten 


---------- Variation der Elemente: ----
intsInVector sum:   55
 stringsInVector sum: onetwotwothreefourfivesixseveneightnineten


----------- Variation des Containers: ----
intsInSet sum: 55
 stringsInSet sum: eightfivefournineonesevensixtenthreetwo


----------- Variation des Algorithmus: ----

10 Faktultät :3628800
 Norm :19.6214
 Purify     : one : two : two : three : four : five : six : seven : eight : nine : ten
 Purify title      : One : Two : Two : Three : Four : Five : Six : Seven : Eight : Nine : Ten

Container

Die Container sind Template, die über ihren Datentyp parametrisiert werden.

std::vector<int> myInt;
std::map< std::string, int > myTelbook

es gibt zwei Typen von Containern
- sequentielle
  - vector
    - kontinuierlicher Speicherbereich
    - für schnelles löschen und hinzufügen am Vektorende optimiert
    - _intelligentes Array_
    - erlaubt wahlfreien Zugriff
  - deque
    - double ended queue
    - für schnelle Manipulation am Containeranfang optimiert
    - erlaubt wahlfreien Zugriff
  - list
    - doppelt verkettete Liste
    - für schnellen Manipulation im Containerkörper optimiert
    - kein wahlfreien Zugrff
- assoziative
  - map, multimap
    - assoziatives Array mit geordnente Schlüsseln
    - unterstützt das Interface eines Dictionary
    - als binärer Suchbaum implementiert
    - Zugriffsgeschwindigkeit im Gegensatz zum Dictionary ist logarithmisch
    - multimaps erlauben mehrfahre Werte zu einem key
  - set, multiset
    - wie map bzw. multimap ohne values
die Typen std::string und das klassische C-Array sind weitere, klassische Container

Iteratoren

jeder Containertyp stellt den richtigen Iterator in zwei Versionen zur Verfügung

std::vector<int> :: itertor myIntIterator;

std::vector<int> :: const_itertor myConstIntIterator;
std::map<std::string, int > :: iterator myTelbookIterator;

std::map<std::string, int > :: const_iterator myConstTelbookIterator;

Iteratoren bietet zum iterieren das gleiche Interface wie Pointer an
- Operator * , ++ , == , != und =
sie sind in dem Sinne intelligent, daß sie das Iterieren über deutlich komplexere Strukturen erlauben
mittels begin() und end() erhält man die Position des ersten Elements des Containers bzw. die hinter des letzten Elements des Containers
der folgende Ausdruck iteriert über alle Element einschließlich stringsInVector.begin() und ausschließlich stringsInVector.end()

std::copy ( stringsInVector.begin(), stringsInVector.end(),

            std::ostream_iterator < std::string > ( std::cout, " "));

die Mächtigkeit des Iterators ist abhängig vom Containertyp
- die Iteratoren der assoziativen und sequentiellen Container sind zumindestens bidirektionale Iteratoren
- die Container vector und deque erlauben darüber hinaus den wahlfreien Zugriff; sie werden als random access Iteratoren bezeichnet
folgende Bild soll die Mächtigkeit der Iteratoren abhängig vom Iteratortyp verdeutlichen

Algorithmen

Im Gegensatz zu dem objektorientierten Paradigma, in dem Daten und Algorithmen gekapselt sind, sind die Algorithmen in der STL von ihren zu verarbeitenden Datenstrukturen getrennt. generische Programmierung
Algorithmen sind in C++ das Mittel das Wahl um Daten unter vorgegebenen Aspekten zu manipulieren.
Sie lassen sich grob durch ihre Wirkung auf die Containern und insbesondere deren Elemente klassifizieren.

Typen

nonmodifying
- equal, count, min_element, find ...
modifying
- copy, transform, merge, fill, generate, replace ...
removing
- remove, unique ...
mutating
- reverse, rotate, next_permutation, random_shuffle ...
sorting
- sort, stable_sort, partial_sort, nth_element
on sorted ranges
- binary_serach, includes, lower_bound, upper_bound, set_union ...
numeric
- accumulate, partial_sum, inner_product ...

Charakteristika

wirken auf halboffenen Intervallen: [Anfangsiterator,Enditerator[

// vec= 10 8 9 0 -1
int maxElement= *max_element( vec.begin(), vec.end() );

// maxElement= 10

stellen ihre Ergebnisse mittels Iteratoren zur Verfügung

das gesuchte Element wird mittels Iterator zurückgegeben
der Zielcontainer wird ab einer Iteratorpostion geschrieben

// vec= 1 2 3 4 5 6 7 
// add 10 to each element of vec
transform( vec.begin(), vec.end(),       // source

           vec.begin(),                  // destination
           bind2nd( plus<int>(),10 ));   // operation

// vec= 11 12 13 14 15 16 17

da Algorithmen sowohl bei der Eingabe wie auch bei der Ausgabe auf Iteratoren wirken, können die Algorithmen ineinander geschachtelt werden

sind durch Funktoren bzw. Funktionen konfigurierbar

falls die Funktoren bzw. Funktionen ein boolschen Wert zurückgeben, werden sie Prädikate genannt
Prädikate kann man in vielen Kontexten verwenden

unäres Prädikat

Suchkriterium für Elemente

// vec= -10 9 1 3 101 8
// find first element greater than 100
int first= *find_if(vec.begin(), vec.end(),              // source
                    bind2nd( greater <int> (), 100 ));   // criterion
// first= 101

Anwendungskriterium des Algorithmus auf die Elemente

//  vec= 0 1 2 3 4 5 6  // count all odd numbers
int numOdd= count_if( vec.begin(), vec.end(),            // source
                       bind2nd( modulus <int> (), 2 ));  // criterion
// int= 3

binäres Prädikat

als Vergleichskriterium für Elemente

vec= 1 2 3 6 9 12 13 14

// find four consecutive elements divisible by 3 
int ele= *search_n_if ( vec.begin, vec.end() ,               // source

                   4 ,                                        // count
                   not1( bind2nd( modululs <int>(),3 )));    // criterion 

// ele= 3

als Verarbeitungskriterium für Elemente

// vec= 101 100 3 4 1000 
bool lessLength (const string& s1, const string& s2){
    return s1.length() < s2.length();
}   
// function as sorting criterium

sort (vec.begin(), vec.end(),                         // source
      lessLength);                                    // criterion

// not stable // vec= 4 3 1001 100 1000

lassen sich mit Iteratoradapter universeller einsetzen

std::ostream_iterator, std::back_inserter

Algorithmen,

die konfiguriert werden könnnen, enhalten das Anhängsel _if

using namespace std;
// Anzahl aller Elemente mit dem Wert 4

int num= count(vec.begin(),vec.end(), 
           4 );

// zähle alle, die größer als 4 sind 
num= count_if( vec.begin(),vec.end(),

               bind2nd( greater<int>(),4));

die, die Elemente nicht in place modifizieren, enhalten das Anhängsel _copy

using namespace std;
// invertiere die Reihenfolge der ersten 3 Elemente 
reverse(deque.begin(), deque.begin()+3 );

// gib die invertierten Elemente lediglich aus
reverse_copy ( deque.begin(),deque.end() ,
               ostream_iterator<int>( cout ));

Konfiguration über Strategien

Die Algorithmen bieten Schnittstellen an, um sie über Strategien zu konfigurieren.

Funktionenpointer

Genügt die Signatur und der Returnwert der Funktion den Anforderungen des Algorithmus, kann die Funktion dazu verwendet werden

Elemente zu modifizieren

double quad( double first, int second ){

  return pow( first ,second ); 
} 

// cont1= 1.0 2.0 3.0 4.0 5.0 6.0
// cont2=  2 2 2 2 2 2 

transform( cont1.begin(), cont1.end(),     // first range
           cont2.begin(),                   // second range
           cont1.begin(),                  // destination range
           quad)                           // operation
// cont1= 1.0 4.0 9.0 16.0 25.0 36.0

Elemente zu bewerten

bool isPrime( int number ){

  if ( number == 0 || number == 1 ) return true;

  int divisor;
  for ( divisor = number/2 ; number%divisor = 0 ; --divisor ){;}

  return divisor == 1;
}
// cont= 910 .. 920
// remove each prime number from cont and print it 
remove_copy_if( cont.begin(), cont.end(),              // source
                ostream_iterator<int>( cout, ", " ),   // destination
                isPrime );                             // unary predicate

// output: 907, 911, 919

Funktoren

sind Objekte, die sich wie Funktionen verhalten
durch das Überladen des Klammeroperators unterstützen diese Objekte die Aufrufsyntax von Funktionen
ein minimal implementierte Funktor besitzt folgende Form

class X{
  public:
    return_value operator() (arguments) const;

    ...

und implementiert

class PrintInt {

  public: 
    void operator()( int element ) const{
       cout << ", " << ;
   }
}
// cont= 1 2 3 4 5 6 
for_each( cont.begin(), cont.end(),     // range

          PrintInt () );                // operation
// output:, 1, 2, 3, 4, 5, 6,

Funktoren besitzen zwei wesentliche Vorteile gegenüber Funktionenpointer.

sie sind in der Regel schneller als gewöhnliche Funktionen
sie besitzen einen Zustand, so daß der Aufruf des Funktors parametrisiert werden kann

void add10( int& elem ){ elem += 10; }

class AddValue ( 
  private:
    int val;
  public:

    AddValue ( int v) val(v){}
    void operator()( int& elem ) { elem += val; }

}
// cont= 1 2 3 4 5 6 
for_each( cont.begin(), cont.end(),    // range

          add10 );                     // operation
// cont= 11 12 13 14 15 16
 for_each( cont.begin(), cont.end(),    // range

          AddValue (10) );              // operation
// cont= 21 22 23 24 25 26
 for_each( cont.begin(), cont.end(),    // range

          AddValue (100) );             // operation
// cont= 121 122 123 124 125 126

STL Erweiterung - boost

Mit Hilfe von boost::bind, boost::function und boost::lambda unterstützt die STL das funktionale Programmieren.

Durch Komposition von Functoren/Funktionenpointer können mächtigere Ausdrücke zusammengebaut werden

logische Verknüpfung

// cont= 1 2 3 4 5 6 7 8 9 10 12
// entferne jedes Element, das durch 2 und 3 teilbar ist
remove_copy_if( cont.begin(), cont.end(),                   // source

                ostream_iterator<int>( cout, ", " ),        // destination
                boost::bind(                                // predicate: ( i%2== 0 and i%3 == 0 ) 

                  logical_and<bool>(),                      // 
                  boost::bind( modululs <int>(),_1,2 ),     // each value must be divisible by 2

                  boost::bind( modululs <int>(),_1,3 )));   // each value must be divisibel by 3

// output: 6, 12

sequentielle Verknüpfung

// cont= 10.0 100.0 1000.0
// addiere zu jedem Wert 10 Prozent hinzu und ziehe wieder 10 Prozen ab
transform( cont.begin(),cont.end(),                 // source

           ostream_iterator<int>( cout, ", " ),        // destination
           boost::bind(

             multiplies<double>(),0.90,             // substract 10 percent
             boost::bind<double> (

               multiplies<double>(),_1,1.10)));     // add 10 percent
                          
// cont= 9.9 99 99

Mit Hilfe von lambda Expressions kann die Datenmanipulation im Algorithmus definiert werden

logische Verknüpfungen

// cont= 1 2 3 4 5 6 7 8 9 10 12
// entferne jedes Element, das durch 2 und 3 teilbar ist
 remove_copy_if( cont.begin(), cont.end(),                   // source

                ostream_iterator<int>( cout, ", " ),         // destination
                ( _1%2== 0 && _1%3== 0 ));                   // predicate: ( i%2== 0 and i%3 == 0 ) 

// output: 6, 12

sequentielle Verknüpfung

// cont= 10.0 100.0 1000.0
// addiere zu jedem Wert 10 Prozent hinzu und ziehe wieder 10 Prozen ab
transform( cont.begin(),cont.end(),                 // source

           ostream_iterator<int>( cout, ", " ),     // destination
           _1 = (_1 * 1.1)*0.9 );                   // operation

// cont= 9.9 99 99