Algorithmen

Die STL bietet einen Satz von Funktionen um verschiedene Algorithmen auf Container anzuwenden. Vielen dieser Funktionen ist gemein, das sie auf Sequenzen ausgeführt werden, d.h. der Funktion wird jeweils Beginn und Ende einer Sequenz (z.b. eines Containers) gegeben, so das der Algorithmus auf allen Elementen der Sequenz ausgeführt wird.

Ein Beispiel mit verschiedenen STL Algorithmen:

 

std::vector<int> vec;// 1
std::list<int> ilist;
for(int i=0; i < 20; ++i)
    vec.push_back(i);
std::copy(vec.begin(),vec.end(),std::back_inserter(ilist));// 2
std::cout << std::count_if(vec.begin(),vec.end(),iseven) << " gerade Zahlen" << std::endl; // 3
ilist.erase(
            std::remove_if(ilist.begin(),ilist.end(),iseven), // 4
            ilist.end());
std::cout << std::count_if(ilist.begin(),ilist.end(),iseven) << " gerade Zahlen" << std::endl;
std::copy(ilist.begin(),ilist.end(),std::ostream_iterator<int>(std::cout," ")); // 5
std::cout << std::endl;
ilist.clear();
std::remove_copy_if(vec.begin(),vec.end(),std::back_inserter(ilist),iseven); // 6
std::copy(ilist.begin(),ilist.end(),std::ostream_iterator<int>(std::cout," "));
  1. Es wird erst mal ein vector<int> und eine list<int> erstellt, um schließlich den Vector mit Zahlen von 0 – 20 zu füllen.

  2. Der erste STL Algorithmus: copy. Der Inhalt von vec wird nach ilist kopiert.

  3. Mit count_if können wir bestimmte Elemente in einer Sequenz zählen. Die Funktion iseven gibt true zurück, wenn das Element eine gerade Zahl ist.

  4. remove_if ist ein Sonderfall. Man könnte glauben, die Methode würde alle geraden Zahlen entfernen, das ist aber nicht korrekt. remove_if überschreibt jede gerade zahl mit einer nachfolgenden ungeraden, und gibt den Iterator auf die letzte Position der zurück. So das vom Anfang der Squenz bis zu diesem alle Werte korrekt entfernt wurden. Der Aufruf von erase bewirkt, das die nun nicht mehr gebrauchten Elemente wieder freigegen werden.

  5. Wieder std::copy, aber hier wird mit Hilfe eines ostream_iterators der Inhalt der Liste nach std::cout geschrieben.

  6. Dies bewirkt das gleiche wie 4, kombiniert aber 2 und 4, und kopiert direkt nur die ungeraden Zahlen.

 

For Each

For Each ist weiterer Algorithmus, welcher für jedes Element in einer Sequenz eine übergebene Funktion mit dem Element als Argument aufruft. Dies kann auch ein Funktionsobjekt sein, welches den entsprechenden operator() überladen hat:

 

class sum
{
    int val;
public:
    sum():val(0){}
    void operator()(const int& i)
    {
        val += i;
    }
    int getSum()const
    {
        return val;
    }
};
 

Die Klasse sum soll die Summe aller an den operator() übergebenen Zahlen berechnen. Die Implementation ist relativ einfach gehalten, ein solches Objekt könnte aber auch z.b. Statistiken für eine bestimmte Sequenz generieren. Der Aufruf von std::for_each ist dann relativ einfach:

 

sum s;
s = std::for_each(vec.begin(),vec.end(),s);
std::cout << "Summe aller Elemente ist " << s.getSum() << std::endl;
 

Wichtig hierbei ist, das std::for_each das übergene Funktionsobjekt kopiert, und am schluss diese Kopie wieder zurückgibt. Man muss also den Rückgabewert von for_each in einer Variablen speichern, wenn man nach dem Aufruf noch darauf zugreifen möchte. Das übergebene Objekt wird nicht verändert. Mit C++11 wird es auch möglich in for_each und anderen STL Algorithmen Lambdas zu nutzen. Ausserdem ist die neue Range-based for Schleife eine gute Alternative zu std::for_each.