Intranet: Algoritmen I

Bekijk fakeint.h. Objecten van het type FakeInt gedragen zich als gewone ints, maar het aantal operaties (constructoren en operatoren) wordt bijgehouden (static, dus bij het type zelf). Bv.

	FakeInt i = 10;  // equivalent met FakeInt i(10)
	cout << FakeInt::counter.n_int_ctor <<endl; // geeft 1 
	cout << FakeInt::counter.n_assign   <<endl; // geeft 0
	FakeInt::report(); 

	FakeInt::reset();
	i = 20;
	cout << FakeInt::counter.n_int_ctor <<endl; // geeft 0
	cout << FakeInt::counter.n_assign   <<endl; // geeft 1

De bedoeling is nu om algoritmen te testen op collecties (vectoren) van FakeInt en zodoende het aantal operaties te tellen. Dit kan interessant zijn om:

cache-effecten en invloed van andere processen uit te sluiten

geheugendeallocatie te testen (evenveel afgebroken als gemaakt?)

na te gaan welke operaties door een bepaald algoritme gebruikt worden (bv. enkel < en ==)

door te vergelijken met de werkelijke tijd (bv. gemeten met clock()) de tijd nodig voor bepaalde operaties te schatten, (verborgen) constanten te bepalen, ...

Oefening: Tel het aantal operaties bij het opvullen van een vector. Maak versies met/zonder push_back() en met/zonder reserve(). Vergelijk met het opvullen van een gelinkte lijst.

Tel het aantal operaties bij sorteren, bv. met std::sort en met je eigen insertion-sort. Welke operatoren gebruiken deze algoritmen?

Sorteercriterium

Maak een klasse Persoon met attributen naam, voornaam en leeftijd. Overlaad de operator< zodat personen alfabetisch gesorteerd worden op naam + voornaam, maar zonder spaties en speciale tekens en zonder met hoofdletters rekening te houden.

Test met std::sort op een aantal dummy-personen.

Stel nu dat je personen wil kunnen sorteren op leeftijd of op naam en stijgend of dalend. De klasse zelf kan slechts één operator< definiëren. We kunnen echter het sorteeralgoritme zo aanpassen dat we het sorteercriterium kunnen meegeven. Dat criterium is een functie f(a,b) die true geeft als a kleiner is dan b. In plaats van een functie kan men ook een functie-object of functor gebruiken, dat is een klasse die de gepaste operator() overlaadt. Omdat je het type niet precies weet kun je hier best een template-parameter gebruiken.

Breng de nodige aanpassingen in je insertion-sort algoritme aan:

	template <typename T, typename CRIT>
	void insertion_sort(vector<T> &v, CRIT &crit);

Om te testen:

Maak een gewone functie om personen volgens dalende leeftijd de sorteren.

Doe hetzelfde met een functie-klasse

Extra: kun je een lidfunctie als criterium gebruiken???

R. Stoop 12/09/2003