STL Algoritmen

Behalve containerklassen biedt de STL ook een hele reeks containeralgoritmes aan. De meeste bevinden zich in de header <algorithm> (zonder .h), in de namespace std.

Voorbeelden: zoeken, sorteren, sommeren, kopieren, dubbels wissen etc.

De algoritmes werken niet op een container, maar op een range [b, e) bepaald door twee iteratoren b, e. Zo schrijft men bv. niet sort(mylist) maar wel sort(mylist.begin(), mylist.end()). Alle algoritmes zijn dus ook bruikbaar op delen van containers ("reeksen").

De algoritmen vervangen vaak een (of meerdere) for-lussen. Het voordeel is dat je code dan minder foutgevoelig is, wellicht leesbaarder, en vaak efficiënter.

`find`

Het algoritme find(begin, end, data) retourneert een iterator die wijst naar het gezochte element, ofwel de end-iterator, die voorbij het laatste element wijst.

De implementatie ziet er ongeveer als volgt uit:

	template <class IT, class T>    // IT is iteratortype, T is elementtype
	IT find(IT begin, IT end, T zoek) {
		while (begin != end && *begin != zoek) 
			begin++;
		return begin;
	}

Voorbeeld van gebruik:

	vector<string> namen;
	// ... vul op;
	vector<string>::iterator it = find(namen.begin(), namen.end(), "Jan");
	if (it == namen.end())
		cout << "niet gevonden" << endl;

Nauw verwante algoritmen zijn

find_if: zoekt elementen die aan een bepaalde criterium voldoen
find_first_of: zoekt het eerste element dat ook in een andere reeks voorkomt
adjacent_find: zoekt opeenvolgende identieke elementen

Om reeksen te vergelijken:

equal: test of twee reeksen gelijk zijn
mismatch: zoekt eerste plaats waar twee reeksen van elkaar verschillen

Er zijn ook algoritmen om te tellen:

count: telt elementen in een reeks
count_if: telt elementen die aan een bepaald criterium voldoen.

`copy`

Het algoritme copy kopieert (deel)sequenties:

	void foo(const vector<int> &v, list<int> &l) {
		v.copy(v.begin(), v.end(), l.begin());
	}

Opgelet: als de vector n elementen bevat, dan moet de list minstens n elementen bevatten; de eerste n elementen worden namelijk overschreven.

Als je elementen wil toevoegen i.p.v. te overschrijven kun je gebruik maken van handige hulpklassen:

inserter(container, pos) voegt elementen toe op de positie aangeven door iterator pos.
front_inserter(container) voegt vooraan toe.
back_inserter(container) voegt achteraan toe.

Voorbeeld:

	v.copy(v.begin(), v.end(), front_inserter(l));

voegt elementen vooraan de lijst toe (keert dus de volgorde om!).

Ook interessant is de hulpklasse ostream_iterator. Die gedraagt zich als een iterator gekoppeld aan een uitvoerstroom (operator* schrijft uit, operator++ doet eigenlijk niets). Bij constructie moet je de uitvoerstroom en een scheidingsstring meegeven. Vergeet ook de template-parameter niet:

	v.copy(v.begin(), v.end(), ostream_iterator<int>(cout, "; "));

Hier worden de elementen van v naar cout geschreven, gescheiden door "; ".

Er bestaat ook een istream_iterator waarmee je van een invoerstroom kunt lezen.

`sort`

Met het algoritme sort(a,b) kun je de elementen in een reeks [a, b[ sorteren. Voorbeeld:

	sort(v.begin(), v.end());

Het algoritme is efficiënt: O(N log N), zelfs worst case, maar niet stabiel. Voor stabiele sortering kun je stable_sort gebruiken, maar die is worst case iets minder performant.

De ordening steunt normaal op operator&lgt;, maar je kunt een andere ordening opleggen via een comparator-object:

	sort(v.begin(), v.end(), greater<int>)

sorteert van groot naar klein. Voor meer voorbeelden van comparatoren: zie priority_queue.

andere

Er bestaan nog tal van andere nuttige algoritmen, bv. om containers op te vullen, om te draaien, te transformeren, "random shuffle", enz.

Meer uitleg vind je oa. in de SGI-documentatie