• De afgelopen dagen zijn er meerdere fora waarop bestaande accounts worden overgenomen door spammers. De gebruikersnamen en wachtwoorden zijn via een hack of een lek via andere sites buitgemaakt. Via have i been pwned? kan je controleren of jouw gegeven ook zijn buitgemaakt. Wijzig bij twijfel jouw wachtwoord of schakel de twee-staps-verificatie in.

[C++] Linked list (m.b.v. OOP)

Status
Niet open voor verdere reacties.

D Drmmr

Heeft veel posts
Lid geworden
5 jul 2005
Berichten
13.482
Waarderingsscore
151
[hand]
Inleiding
Deze tutorial laat zien hoe een aantal programmeerconcepten in C++ gebruikt kunnen worden. Het is een goede oefening voor mensen die al redelijk kunnen programmeren in C++, maar ook voor de verder gevorderden. De concepten die aan bod komen zijn: object georinteerd programmeren, const correctness en templates. Dit zijn allemaal dingen waarvan ik de waarde heb leren kennen in mijn werk als C++ programmeur. Het zijn dus dingen waar je echt iets aan hebt.

Alles wordt behandeld binnen het thema 'linked list', een bekende en veel gebruikte datastructuur. Voor de (relatieve) beginners is het een goede oefening om iets vrij abstracts als een datastructuur op te zetten en te implementeren. Voor degenen die deze datastructuur al kennen, is het alleen nodig om even door het eerste deel heen te 'scimmen' om verder te kunnen met de meer geavanceerde delen.
De code is op zich niet echt nuttig voor hergebruik, aangezien het beter is om gewoon de STL (Standard Template Library) klassen (specifiek std::vector, std::deque en std::list) te gebruiken, maar je kunt wel veel leren van de oefening en de ideen in deze tutorial.

Overzicht
[/hand]
 
[hand]
1. Een linked list (met behulp van objectgerinteerd programmeren)

Inhoud
  • [linkje]Vereiste voorkennis[/linkje]
  • [linkje]Wat is een linked list?[/linkje]
  • [linkje]Wat moet een linked list allemaal kunnen?[/linkje]
  • [linkje]Achtergrond[/linkje]
  • [linkje]Opzet van de implementatie[/linkje]
    • [linkje]De lijst[/linkje]
    • [linkje]Itereren[/linkje]
    • [linkje]Terug naar de lijst[/linkje]
  • [linkje]Het controleren van de geschreven code[/linkje]
Opdrachten
  • [linkje]Opdracht 1.1[/linkje]
  • [linkje]Opdracht 1.2[/linkje]
  • [linkje]Opdracht 1.3[/linkje]
  • [linkje]Opdracht 1.4[/linkje]
  • [linkje]Opdracht 1.5[/linkje]
  • [linkje]Opdracht 1.6[/linkje]
  • [linkje]Opdracht 1.7[/linkje]
  • [linkje]Opdracht 1.8[/linkje]

In deze handleiding zullen we een datastructuur maken in C++ die het makkelijk maakt om de elementen van een lijst bij te houden. Deze structuur is met name makkelijk als we vaak ergens een element moeten toevoegen of verwijderen. Het is minder geschikt om een element uit de lijst op een willekeurige positie in de lijst op te zoeken.

In de tutorial staan een aantal opdrachten. Deze komen er in feite op neer dat je de precieze implementatie van wat we hebben besproken moet uitvoeren. Dit houdt dus in dat je niet alles voorgekauwd krijgt, maar het wel duidelijk zal zijn wat je zelf nog moet doen. Mocht je er niet uitkomen (wat overigens helemaal niet gek is) of wil je commentaar op de code die je hebt geschreven, maak dan even een postje in het Programmeren deelforum (http://www.nationaalcomputerforum.nl/forumdisplay.php?f=37).

[kopje]Vereiste voorkennis[/kopje]

Om deze handleiding goed te kunnen volgen, moet je het volgende al kennen:
  • Je moet weten wat objectgerinteerd programmeren (OOP) inhoudt. (Zie http://nl.wikipedia.org/wiki/OOP)
  • Je moet kunnen omgaan met pointers. Dit moet je eigenlijk redelijk goed beheersen. Dat is, je moet goed begrijpen wat een pointer precies is, hoe je bij de data waarnaar de pointer verwijst komt en waar je bij pointers op moet letten (op 0 initialiseren, enz.). We zullen geen gebruik maken van operaties op pointers, zoals verhogen of verlagen van pointers of het verschil van twee pointers nemen.
  • Je moet om kunnen gaan met het dynamisch alloceren van geheugen (new en delete).
  • Je moet weten hoe een klasse (class) werkt en wat friends zijn. We zullen geen overerving (inheritance), oftewel afgeleide klassen gebruiken.
  • Je moet zelf een programma kunnen maken in C++. Dat houdt in dat ik je niet precies ga vertellen wat je moet intypen of aanklikken. De code die we maken, kun je allemaal in 1 .h bestand zetten, dan is het makkelijker om het later aan te passen naar een template versie. Je mag natuurlijk ook eigenwijs zijn en de implementatie in een .cpp bestand zetten. :p

[kopje]Wat is een linked list?[/kopje]

Een linked list is een lijst (duh!) die op een speciale manier is gemaakt, zodat je snel een element aan de lijst kunt toevoegen op een willekeurige plek en snel een element uit de lijst kunt verwijderen. Verder is het mogelijk om snel over de elementen van de lijst te lopen (in volgorde), maar het is niet mogelijk om snel een willekeurig element van de lijst te benaderen.
Het principe is dat we bij ieder element dat we in de lijst opslaan een verwijzing opslaan naar het volgende element. Op die manier kunnen we over alle elementen van de lijst 'lopen' als we het eerste element kennen. Zie ook http://nl.wikipedia.org/wiki/Linked_list tot en met het stuk over enkelvoudig gelinkte lijsten.

[kopje]Wat moet een linked list allemaal kunnen?[/kopje]

Het is natuurlijk allemaal leuk en aardig om een datastructuur te verzinnen, maar het is wel zo prettig als we die vervolgens ook kunnen gebruiken. Laten we dus even heel precies bedenken wat we allemaal met die datastructuur willen doen.
  • We willen een lijst van elementen van hetzelfde type bijhouden (bijvoorbeeld een lijst van getallen). De volgorde waarin we de getallen zetten moet behouden blijven.
  • We willen elementen kunnen toevoegen aan het begin of het einde van de lijst.
  • We willen het eerste element van de lijst kunnen opvragen en verwijderen. Samen met de vereiste hierboven kunnen we dan een FIFO of LIFO systeem maken (de vakkenvullers weten waar ik het over heb ;), voor de rest http://nl.wikipedia.org/wiki/Fifo en http://nl.wikipedia.org/wiki/Lifo).
  • We willen het aantal elementen in de lijst kunnen opvragen.
  • We willen over de elementen van de lijst kunnen itereren ('lopen').

[kopje]Achtergrond[/kopje]

Het idee van een linked list is al behoorlijk oud. Het werd ook al in C gebruikt, maar in die tijd was het idee van OOP nog niet zo ver doorgedrongen (en de taal staat het niet zo goed toe), dus wat je meestal zag was dat mensen de datastructuur telkens opnieuw implementeerden als ze die nodig hadden. Het is natuurlijk makkelijker als je de algemene operaties maar 1 keer hoeft te (laten) implementeren en ze dan telkens kunt gebruiken.
In veel C++ programma's zie je nog sporen van C programmeerstijlen. Zo ook bij linked lists. Je kunt bijvoorbeeld hier (klikbaar) zien dat de abstractie en OO te wensen overlaat (een element van de lijst (Node) is tegelijk de lijst zelf :blink: wat gebeurt er dan als ik een Node kopieer; kopieer ik dan het element of de hele lijst?). Bovendien is de implementatie onveilig, ingewikkeld en inefficient door het gebruik van pointers naar de data. Verder is de gebruikte naamgeving dubbelzinnig en de implementatie inefficient (met name de functie addNode(...)).
Kortom, dit kan (veel) beter.

[kopje]Opzet van de implementatie[/kopje]

We maken dus een lijst die de bovengenoemde operaties moet kunnen uitvoeren. Maar wat slaat die lijst dan op? Elementen (what's in a name? ;)). Een element is gewoon een object van een bepaald vooraf gedefinieerd type. Laten we er even vanuit gaan dat we een lijst van integers gaan opslaan (we kunnen dit type later veranderen).
Code:
typedef int elemType; // het type van een element in de lijst

Een element slaat dus een int op, maar vanwege de structuur van een linked list, moet bij die int een verwijzing naar het volgende element in de lijst worden opgeslagen. Omdat de int en verwijzing bij elkaar moeten worden opgeslagen, maken we er een apart object van. Dit object vormt dan een 'schakel' in de lijst, dus laten we het een Link noemen.
De gebruiker van de list hoeft echter niks van dit object af te weten, omdat die alleen genteresseerd is in wat de lijst kan doen, niet hoe het gemplementeerd is. Dus is het een goed idee om alleen het list object toegang te geven tot het element.
Code:
class Link
{
	friend class List; // alleen de list mag dit element gebruiken
private:
	Link(elemType data, Link* pNext); // kan alleen door een list gemaakt worden

	elemType m_Element;
	Link* m_pNext;
};
Aangezien alleen de lijst van het bestaan van een link hoeft te weten, is het het beste om de klassedefinitie van Link (straks) in het protected gedeelte van de List klasse (die we nog moeten maken) te zetten.
[kopje]Opdracht 1.1[/kopje]: Implementeer de constructor van Link, die de opgegeven argumenten in de member variabelen opslaat.

[kopje]De lijst[/kopje]

Onze lijst is dus opgebouwd uit allemaal links die naar elkaar verwijzen. Als we dus bij de eerste link zijn, kunnen we via die verwijzingen naar iedere link in de lijst 'lopen' en dus ieder element van de lijst benaderen. Dat betekent dus dat we alleen maar een verwijzing naar de eerste link hoeven bij te houden, om bij alle elementen te kunnen komen. Laten we deze variabele de kop van de lijst (head) noemen.
Code:
class List
{
public:
	List();
	~List();
	List(const List& that); // copy constructor
	List& operator =(const List& that); // assignment operator

private:
	Link* m_pHead; // owned; begin van de lijst
};
Achter de definitie van m_pHead zie je het commentaar 'owned' staan. Dit is om te verduidelijken dat m_pHead verwijst naar een dynamisch gealloceerd object en dat de klasse List verantwoordelijk is voor het vrijgeven van de gealloceerde geheugenruimte (delete m_pHead; ). De Link objecten die we gebruiken om de elementen van de lijst op te slaan worden dus dynamisch gealloceerd.
Omdat m_pHead een dynamisch gealloceerd object is, moeten we de destructor, copy constructor en assignment operator van de klasse List zelf implementeren (de default implementatie kopieert alleen de waarde van de pointer). We zullen dit later doen. Laten we eerst even kijken naar hoe we over de lijst kunnen itereren, dan wordt het waarschijnlijk wat duidelijker hoe de datastructuur precies in elkaar zit.

[kopje]Itereren[/kopje]

De lijst heeft een verwijzing naar de eerste link in de lijst en iedere link heeft een verwijzing naar de volgende link in de lijst. Dat betekent dus dat de laatste link in de lijst naar niets verwijst. Dit kunnen we aangeven door de pointer m_pNext in die link de waarde 0 te geven (goed onthouden!).
Als we een verwijzing naar een link hebben, kunnen we bij het element dat in die link wordt opgeslagen komen. Herinner je dat we eerder al hebben gezegd dat de gebruiker van de klasse niet van het bestaan van de klasse Link hoeft te weten, omdat die daar niet in is genteresseerd. Wel moet het mogelijk zijn om over de elementen van de lijst te 'lopen'. We noemen dit itereren en dit doen we met een iterator. Een iterator is een object waarmee we over de elementen van de lijst kunnen lopen en toegang hebben tot het element waar we 'op staan'. Het moge duidelijk zijn dat een iterator dus in feite neerkomt op een verwijzing naar een Link object. Echter, omdat het iterator object door de gebruiker van de List klasse gebruikt zal worden, moeten we er een aparte klasse van maken, die de vereiste functionaliteit biedt.

Wat is die functionaliteit dan precies? Wat willen we precies allemaal kunnen doen, als we over de lijst willen itereren.
  • We willen bij het eerste element in de lijst kunnen beginnen.
  • We willen naar het volgende element in de lijst kunnen gaan, als we op een element staan.
  • We willen weten wanneer we moeten ophouden met itereren, dat is, wanneer we bij het einde van de lijst zijn aangekomen.
  • We willen het element waar we op staan kunnen benaderen.
We hebben het in deze vereisten telkens over 'de lijst'. Dat betekent dus dat een iterator moet weten over welke lijst we het hebben, oftewel de klasse Iterator moet een verwijzing hebben naar een List object. Nu zouden we voor die verwijzing een pointer naar een List kunnen nemen, maar wat zou het dan betekenen als de waarde van die pointer 0 is? Dan zou de iterator naar geen lijst verwijzen, dus zouden we het in de vereisten hierboven telkens hebben over een lijst die helemaal niet bestaat.
We kunnen dus beter een reference gebruiken voor de verwijzing naar de lijst, want die verwijst altijd naar een valide object.

Verder hebben we al eerder gezien dat een iterator dus in feite een verwijzing naar een Link is. Ook hier kunnen we ons weer afvragen of we een pointer of een reference willen gebruiken. Daarvoor stellen we weer de vraag: is het zinnig als een iterator naar geen Link verwijst? (dit is geen simpele vraag, neem er gerust ff de tijd voor)

Het antwoord op de vraag zal wat duidelijker worden door een andere vraag te stellen: Naar welk Link object verwijst een iterator van een lijst die leeg is (dus geen elementen bevat)?
Kijk nu ff in de spiegel. Als je zoiets ziet :wacko:, geeft niks, gewoon later nog een keer lezen. ;)
Voor de verwijzing naar een link nemen we dus een pointer. Onze klasse definitie komt er dan ongeveer zo uit te zien:
Code:
class Iterator
{
public:
	Iterator(List& rList);

	// assignment operator kan alleen worden uitgevoerd als de iterators naar dezelfde lijst verwijzen
	Iterator& operator =(const Iterator& that);

	void GotoBegin(); // gaat naar het begin van de lijst
	void GotoNext(); // gaat naar het volgende element; alleen aanroepen als AtEnd() false teruggeeft
	bool AtEnd() const; // geeft aan of we klaar zijn met itereren (voorbij het einde van de lijst zijn)

	elemType& GetElement() const;

private:
	List& m_rList;
	Link* m_pLink;
};
De functie AtEnd() is een zogenaamde const functie. Dit houdt in dat de functie de member variabelen van het object niet kan veranderen. Het is goed om bij het programmeren alle dingen die constant kunnen zijn, ook constant te maken (dit heet 'const correctness').

Omdat het misschien nog niet helemaal duidelijk is hoe het itereren in zijn werk gaat, zullen we de implementatie van de functie AtEnd() alvast geven.
Code:
bool Iterator::AtEnd() const
{
	return (m_pLink == 0);
}
We zijn dus bij het einde van de lijst beland, als de verwijzing naar de link 0 is. Dit komt overeen met wat we eerder hebben gezegd: de verwijzing naar de volgende Link in het Link object is 0 voor de laatste link in de lijst. Het werkt ook prima als we itereren over een lege lijst (ga dit na!).

[kopje]Opdracht 1.2[/kopje]: Implementeer de overige functies van de klasse Iterator, behalve de assignment operator. De implementatie van de assignment operator krijg je cadeau. Deze is wellicht wat te ingewikkeld, als je het goed wilt doen.
Code:
Iterator& Iterator::operator =(const Iterator& that)
{
	if (this != &that) {
		if (&m_rList != &that.m_rList)
		{
			assert(false); // kan geen iterator van een andere lijst kopiren
			throw("Iterator assignment operator failed.");
		}
		m_pLink = that.m_pLink;
	}
	return *this;
}
Om de functie assert(...) te kunnen gebruiken moet je de STL header 'cassert' includeren. Na die assertion wordt een exceptie gegooit met throw. Dit zorgt ervoor dat de executie van het programma stopt en teruggaat naar een bepaald punt (waar een 'catch' staat). Het is niet nodig om dit precies te begrijpen om verder te kunnen. Het gaat erom dat we hier controleren dat de twee Iterator objecten (this en that) naar dezelfde lijst verwijzen.

Omdat we van Iterator een apart object hebben gemaakt en de functionaliteit niet direct in de lijst hebben gestopt, is het mogelijk om met meer dan 1 iterator tegelijk door de lijst te lopen. Dit is bijvoorbeeld nodig om naar alle paren van elementen in de lijst te kijken. Bijv.:
Code:
List myList;
Iterator it1(myList);
for (it1.GotoBegin(); !it1.AtEnd(); it1.GotoNext())
{
	Iterator it2(myList);
	for (it2.GotoBegin(); !it2.AtEnd(); it2.GotoNext())
	{
		std::cout << "(" << it1.GetElement() << ", " << it2.GetElement() << ")" << std::endl;
	}
}
Hier kun je vrij goed zien wat het nut is van OOP.

[kopje]Terug naar de lijst[/kopje]

Ok, hopelijk heeft het implementeren van de Iterator wat meer inzicht gegeven in hoe de lijst werkt. Zo niet, vraag dan gerust om meer uitleg van de dingen die je niet snapt in het deelforum Programmeren.

We hebben al een klassedefinitie van de klasse List. We hebben ook al gezien dat de Link objecten die we daarin opslaan dynamisch gealloceerde objecten zullen zijn. Daardoor kunnen we niet met de default impelementatie van destructor, copy constructor en assignment operator volstaan. We zullen deze dus nog moeten implementeren. Maar laten we eerst naar het wat leukere deel gaan; het implementeren van de functionaliteit die we bovenaan hebben genoemd. Hiervoor kunnen we de volgende functiedeclaraties aan de klasse List toevoegen (public natuurlijk).
Code:
void AddAtBegin(elemType data);
void AddAtEnd(elemType data);
elemType RemoveFirst();

int GetSize() const;
All deze operaties moeten we in O(1) (constante) tijd kunnen uitvoeren. Dat houdt in dat we in de implementatie niet mogen itereren over de links van de lijst. Dit betekent dus dat we wat member variabelen zullen moeten toevoegen voor de functies AddAtEnd(...) en GetSize(). Voor de functie GetSize() is dit simpel; we slaan gewoon in de lijst op hoeveel elementen erin zitten.
[kopje]Opdracht 1.3[/kopje]: Implementeer de functie GetSize().

Als de lijst leeg is, is er geen eerste element waarnaar m_pHead kan verwijzen. In dat geval moet de waarde van m_pHead dus 0 zijn. Dit kunnen we alvast in de contructor van de klasse List implementeren.
[kopje]Opdracht 1.4[/kopje]: Implementeer de constructor van de klasse List. Zorg ervoor dat de functie GetSize() het juiste aantal elementen teruggeeft, nadat een List object is gecreerd.

In de functie AddAtBegin(...) moeten we een link maken waarin we het opgegeven element opslaan (onthoud dat de Link objecten dynamisch gealloceerd moeten worden). Deze link wordt het nieuwe begin van de lijst en de verwijzing naar het volgende element zal dus verwijzen naar het oude begin van de lijst.
[kopje]Opdracht 1.5[/kopje]: Implementeer de functie AddAtBegin(...). Zorg ervoor dat de functie GetSize() nog altijd het juiste aantal elementen teruggeeft.

De functie RemoveFirst() verwijdert de eerste link uit de lijst en retourneert een kopie van het element dat in die link zat. De functie mag alleen aangeroepen worden als de lijst niet leeg is, dus is het makkelijk om een functie te maken die dat controleert, laten we zeggen de functie IsEmpty.
[kopje]Opdracht 1.6[/kopje]: Voeg de functie IsEmpty toe aan de klasse List en implementeer de functie RemoveFirst(). Let erop dat gealloceerd geheugen ook weer wordt vrijgegeven.

We hebben eerder al gezegd dat we niet willen dat de functie AddAtEnd(...) over alle elementen van de lijst moet itereren. Als we direct iets aan het einde van de lijst willen toevoegen, moeten we dus een verwijzing naar het laatste element bijhouden. We moeten dan ook in de andere functies erop letten dat die verwijzing naar het juiste element blijft verwijzen.
[kopje]Opdracht 1.7[/kopje]: Voeg de verwijzing naar het laatste element in de lijst toe aan de klasse List en noem dit m_pTail (de staart van de lijst). Pas de reeds gemplementeerde functies aan. Implementeer de functie AddAtEnd(...). Hiervoor kun je veel spieken van de functie AddAtBegin(...).

Nu we alle vereiste functionaliteit hebben gemplementeerd, kunnen we schematisch weergeven hoe de lijst werkt. Zo'n tekening kan erg behulpzaam zijn bij het controleren van de implementatie en het implementeren van extra functionaliteit. Zo'n schema kan er bijvoorbeeld zo uitzien:

List.bmp

Bovenaan zie je de verschillende links van de lijst (in dit geval 3). De pijltjes zijn de verwijzingen naar de volgende link in de link. De laatste link in de lijst verwijst niet naar een volgende link, maar naar 0. De lijst heeft 2 verwijzingen naar een link, namelijk m_pHead en m_pTail. De eerste verwijst naar het eerste element van de lijst en de tweede naar het laatste element.


Dan rest ons alleen nog de implementatie van de destructor, copy constructor en assignment operator. Hierbij is het van belang dat we goed omgaan met het dynamisch gealloceerde geheugen. De klasse List is in dit geval verantwoordelijk voor het verwijderen van alle aangemaakte objecten, aangezien die ook in de klasse List dynamisch worden gealloceerd. We kunnen dit controleren door na te gaan dat voor iedere aanroep van new precies 1 keer delete wordt aangeroepen.
Als je niet al het gealloceerde geheugen vrijgeeft in een stuk code (dit heet een memory leak), kan dat grote gevolgen hebben: je applicatie zal belachelijk veel geheugen nodig hebben, waardoor je pc zal gaan swappen (en het programma ontzettend langzaam wordt) en uiteindelijk zal het programma gaan klagen dat er niet genoeg geheugen is en crashen. Tegelijk is het opsporen van memory leaks erg moeilijk als je er niet de juiste tools voor hebt. Het is dus raadzaam om op het web op zoek te gaan naar dergelijke tools. Anderzijds is het gebruiken van je eigen verstand ook een goed hulpmiddel.

Het implementeren van deze drie functies kunnen we een stuk vergemakkelijken door gebruik te maken van de functies die we al hebben.
[kopje]Opdracht 1.8[/kopje]: Implementeer deze functies.

[kopje]Het controleren van de geschreven code[/kopje]

De code die we nu hebben geschreven, moeten we natuurlijk eerst nog eens grondig testen om enige zekerheid te krijgen dat ie daadwerkelijk doet wat die moet doen. We kunnen dit het makkelijkst doen met een zogenaamd driver programmaatje. Dat is een simpel zelfgemaakt programma wat je uitsluitend gebruikt om te controleren of de code die je hebt geschreven correct werkt.

Een voorbeeldje:
Code:
#include "list.h"
#include &lt;iostream&gt;

void DisplayList(List& l)
{
	std::cout << "List size: " << l.GetSize() << std::endl;
	Iterator it(l);
	for (it.GotoBegin(); !it.AtEnd(); it.GotoNext()) {
		std::cout << it.GetElement() << ", ";
	}
	std::cout << std::endl;
}

int main()
{
	List l;
	for (int i = 0; i < 10; ++i) {
		l.AddAtBegin(i);
	}
	DisplayList(l);

	int n;
	for (int i = 0; i < 3; ++i) {
		n = l.RemoveFirst();
		l.AddAtEnd(n);
	}
	DisplayList(l);

	return 0;
}
Controleer of je code goed werkt en, zo niet, gebruik dan de debugger om na te gaan waar het fout gaat. Kom je ergens niet uit, vraag het dan gerust.

[/hand]
 
[hand]
2. Extra functionaliteit toevoegen

Opdrachten
  • [linkje]Opdracht 2.1[/linkje]
  • [linkje]Opdracht 2.2[/linkje]
  • [linkje]Opdracht 2.3[/linkje]

In het vorige deel hebben we een linked list gemaakt die gebruikt kan worden voor zogenaamde lifo en fifo systemen. Het kan echter voorkomen dat je in sommige toepassingen een linked list wilt gebruiken waar je ook ergens midden in de lijst een element kunt toevoegen of weghalen. De vraag is hoe we deze functionaliteit kunnen toevoegen aan de lijst die we gemaakt hebben.

Als we een element ergens in de lijst willen toevoegen of weghalen, zullen we moeten kunnen aangeven waar in de lijst (bij welk element) we dat willen doen. We hebben hiervoor al een goed object, namelijk de iterator. Met de iterator kunnen we een element in de lijst opzoeken en aangeven. Bij het verwijderen van een element uit de lijst, kunnen we met de iterator dus precies aangeven welk element we willen verwijderen. Maar bij het toevoegen van een element hebben we de keuze om het toegevoegde element voor of achter het element waar de iterator naar verwijst te zetten. Als we kijken naar de uiteinden van de lijst, wordt duidelijk dat er maar 1 logische keuze is.
Als we iets aan het begin van de lijst willen toevoegen (m.b.v. een iterator) dan zal die iterator naar het eerste element moeten verwijzen en zullen we het toe te voegen element dus voor het element waar de iterator naar verwijst moeten zetten. Als we een element aan het einde van de lijst willen toevoegen, kunnen we met de iterator tot aan het einde van de lijst gaan. De iterator staat dan in feite 1 element 'voorbij' het laatste element van de lijst. Als we het toe te voegen element daarvoor toevoegen, komt het dus na het laatste element van de lijst te staan; precies wat we wilden.

We kunnen nu de volgende functiedeclaraties aan de List klasse toevoegen.
Code:
void InsertBefore(Iterator& it, elemType data);
void Remove(Iterator& it);
De iterator wordt by reference doorgegeven, zodat we ervoor kunnen zorgen dat deze na de operatie weer naar een valide element verwijst. Als we bijvoorbeeld een element verwijderen, kunnen we de iterator niet naderhand naar hetzelfde element laten verwijzen, omdat dat niet meer bestaat. Het logischte is dat de iterator naderhand verwijst naar het volgende element in de lijst. Ook bij de andere functie moeten we ervoor zorgen dat de iterator valide blijft.

Laten we eerst eens kijken naar de functie Remove(...). Ter verduidelijking van wat er precies moet gebeuren, nemen we het plaatje van het vorige deel erbij.

List.bmp

Allereerst zullen we moeten controleren dat de iterator die we meekrijgen valide is, dat is, dat hij naar deze lijst verwijst (dit kan met een assertion) en dat hij naar een element in de lijst verwijst (zo niet dan hoeven we niks te doen). Vervolgens kunnen we kijken naar wat er werkelijk moet gebeuren. De link waarnaar de iterator verwijst, moeten we uit de lijst halen, dus moet de pointer m_pNext van het (eventuele) vorige element worden veranderd, zodat die wijst naar het volgende element. Daarna kunnen we de lijst updaten (m_pHead en m_pTail) en de iterator naar de volgende link in de lijst laten verwijzen. Tot slot moeten we de gealloceerde geheugenruimte van het gealloceerde element vrijgeven.
Er is echter een probleem: hoe komen we bij de vorige link in de lijst? We zouden de hele lijst kunnen doorlopen totdat we zien dat de volgende link dezelfde is als de link waar de iterator naar verwijst, maar dat zou erg inefficient zijn, omdat we mogelijk de hele lijst moeten doorlopen om 1 link te verwijderen. Beter is het om in de iterator de vorige link bij te houden.
[kopje]Opdracht 2.1[/kopje]: Voeg een pointer naar een link m_pPrev toe aan de Iterator klasse en zorg ervoor dat die altijd naar de vorige link verwijst (of 0 als er geen vorige link is).

[kopje]Opdracht 2.2[/kopje]: Implementeer nu de functie Remove(...). Gebruik het plaatje om te controleren of je alle pointers goed hebt aangepast. Let er ook op dat je alle verschillende gevallen onderscheidt; verwijst de iterator naar de eerste link, de laatste of ...? Controleer ook of je functie goed werkt door het te testen met een driver programmaatje.

In de functie InsertBefore(...) kunnen we hetzelfde onderscheidt maken als in de functie Remove(...). Als de iterator naar de eerste of laatste link in de lijst verwijst, kunnen we de functie AddAtBegin(...) of AddAtEnd(...) respectievelijk aanroepen. We moeten er dan nog wel voor zorgen dat de iterator valide blijft. In het andere geval kun je het plaatje gebruiken om na te gaan wat je allemaal moet doen.
[kopje]Opdracht 2.3[/kopje]: Implementeer de functie InsertBefore(...) door deze drie gevallen te onderscheiden. Controleer weer of je functie goed werkt, ook samen met de functie Remove(...).

C'est tout. :clapping:
[/hand]
 
[hand]
3. Const-correcte iteratoren

Inhoud
  • [linkje]Const correctness[/linkje]
  • [linkje]Een iterator voor een const List[/linkje]
Opdrachten
  • [linkje]Opdracht 3.1[/linkje]

In dit deel maken we een iterator die je kunt gebruiken met een const List. Dit is nodig om de List klasse goed te kunnen gebruiken in const correcte code. We zullen eerst maar eens uitleggen wat daarmee wordt bedoeld.

[kopje]Const correctness[/kopje]

Const correctness is een programmeerstijl waarbij zoveel mogelijk gebruik wordt gemaakt van het const sleutelwoord in C++. Dat houdt in dat je alle variabelen en member functies die constant zijn ook als const declareerd worden. Bijvoorbeeld als we over de waarden in een vector willen itereren met een random access operator ([]).
Code:
std::vector<int> v;
// ... vector vullen
const int size = v.size();
for (int i = 0; i < size; ++i) {
	std::cout << v[i] << ' ';
}
Als we geen elementen toevoegen of verwijderen binnen de for-loop, blijft de grootte van de vector gelijk, dus kunnen we deze opslaan in een constante variabele. Zouden we deze code in een aparte functie zetten, dan kunnen we de hele vector zelfs als const reference meegeven.
Code:
void DisplayValues(const std::vector<int>& v)
{
	const int size = v.size();
	for (int i = 0; i < size; ++i)
		std::cout << v[i] << ' ';
	std::cout << std::endl;
}
De functie verandert de vector niet, dus geven we die als const reference mee, zodat de vector niet helemaal gekopieerd hoeft te worden alleen maar om de waarden te tonen, maar we toch zeker zijn dat er niks aan verandert door het aanroepen van de functie.

Het voordeel van const correctness is dat code een stuk duidelijker wordt en (in de meeste gevallen) ook beter geoptimaliseerd kan worden door de compiler, waardoor je programma sneller zal draaien (je kunt dit testen met het itereren over de waarden van een vector).
Verder kun je er sommige programmeerfouten mee voorkomen. Bijv:
Code:
int a = 1;
const int b = 0;
if (a = 0) // compileert
	std::cout << "a is gelijk aan 0";
if (b = 0) // compiler error
	std::cout << "b is gelijk aan 0";
In beide if's hebben we een = gezet, terwijl we een == bedoelen. In het eerste geval krijgen we geen compiler error en zullen we de fout alleen kunnen ontdekken door onverwacht gedrag van het programma. In het tweede geval krijg je een compiler error, omdat je een waarde probeert toe te kennen aan een constante variabele. Erg handig. :)

Overigens moet je er goed op letten dat, als je een const reference naar een object hebt of een pointer naar een const object, je dat object daarmee niet kunt veranderen, maar het object wel veranderd kan worden (door iets anders). Bijvoorbeeld:
Code:
int i = 1;
const int& r = i;
r = 0; // mag niet
std::cout << "waarde van r: " << r << std::endl;
++i;
std::cout << "waarde van r: " << r << std::endl;
// output:
// waarde van r: 1
// waarde van r: 2

[kopje]Een iterator voor een const List[/kopje]

De normale Iterator die we hebben gemaakt kan niet gebruikt worden als we een const List (of een referentie daarnaar) hebben. In de constructor van Iterator moeten we namelijk een referentie naar een List meegeven. Je zou bijvoorbeeld in je programma de volgende functie kunnen hebben.
Code:
void DisplayList(const List& rList)
{
	Iterator it(rList);
	for (it.GotoBegin(); !it.AtEnd(); it.GotoNext())
		std::cout << it.GetElement() << ", ";
	std::cout << std::endl;
}
Als je deze functie aanroept, wil je niet dat de hele lijst gekopieerd wordt, dus geef je die by reference mee. Maar omdat de lijst door de functie niet gewijzigd wordt, geef je hem als const reference mee. Het probleem is echter dat de Iterator een referentie naar een List (niet const List) verwacht, waardoor je een compiler error krijgt.

We hebben dus een iterator nodig die met een const List overweg kan, een ConstIterator. Als de lijst constant is, zijn de links die erin zitten ook constant en de elementen die in de links zitten dus ook. We krijgen dan dus de volgende klasse definitie voor de ConstIterator.
Code:
class ConstIterator
{
public:
	ConstIterator(const List& rList);

	// assignment operator kan alleen worden uitgevoerd als de iterators naar dezelfde lijst verwijzen
	ConstIterator& operator =(const ConstIterator& that);

	void GotoBegin(); // gaat naar het begin van de lijst
	void GotoNext(); // gaat naar het volgende element; alleen aanroepen als AtEnd() false teruggeeft
	bool AtEnd() const; // geeft aan of we klaar zijn met itereren (voorbij het einde van de lijst zijn)

	const elemType& GetElement() const;

private:
	const List& m_rList;
	const Link* m_pLink;
};
De lijst, de links en de elementen zijn dus allemaal constant. De ConstIterator zelf is echter niet constant, daarom zijn de functies GotoBegin() en AtEnd() geen const functies.
[kopje]Opdracht 3.1[/kopje]: Implementeer de klasse ConstIterator.

Als je goed hebt opgelet, zul je gemerkt hebben dat de code van de ConstIterator klasse precies gelijk is aan die van de Iterator klasse. De twee klassen verschillen alleen in de declaratie van de member functies en variabelen. In het volgende deel zullen we hiervan gebruik maken m.b.v. templates.
[/hand]
 
[hand]
4. Het gemak van templates

Inhoud
  • [linkje]Een template gebasseerde basis klasse[/linkje]
Opdrachten
  • [linkje]Opdracht 4.1[/linkje]

In dit deel zullen we templates gebruiken om de implementatie van een ConstIterator uit het vorige deel te verbeteren. In het vorige deel hebben we gezien dat de implementatie van de Iterator en de ConstIterator alleen verschilde in de declaraties van de member functies en variabelen van de iterator klasse. In dit deel zorgen we ervoor dat alles wat hetzelfde is ook maar 1 keer wordt gemplementeerd. Het voordeel hiervan is dat we ook maar op 1 plek code hoeven te wijzigen als er wat veranderd moet worden. Daardoor kunnen we voorkomen dat we de code op de ene plek wel updaten en op de andere niet.

[kopje]Een template gebasseerde basis klasse[/kopje]

De klassen Iterator en ConstIterator verschillen eigenlijk maar in 1 ding: de eerste klasse gebruikt een List, een Link en een elemType; de tweede gebruikt een const List, een const Link en een const elemType. Voor de rest zijn de klasses helemaal gelijk (behalve de naam).

Als we die drie verschillende types die gebruikt worden nu in een template zetten, dan kunnen we dus de hele klasse implementeren voor zowel de Iterator als de ConstIterator. We kunnen vervolgens die twee klassen implementeren als een specialisatie van de template klasse die we gemaakt hebben.
Code:
template &lt;class TList, class TLink, class TElem&gt;
class IteratorBase
{
protected:
	typedef TList listType;
	IteratorBase(listType& rList) : m_rList(rList), m_pLink(0), m_pPrev(0) {}

public:
	// assignment operator kan alleen als de iterators naar dezelfde lijst verwijzen
	inline IteratorBase& operator =(const IteratorBase& that);

	inline void GotoBegin(); // gaat naar het begin van de lijst
	inline void GotoNext(); // gaat naar het volgende element; alleen aanroepen als AtEnd() false teruggeeft
	inline bool AtEnd() const; // geeft aan of we klaar zijn met itereren (voorbij het einde van de lijst zijn)

	inline TElem& GetElement() const;

private:
	listType& m_rList;
	TLink* m_pLink;
	TLink* m_pPrev;
};

class Iterator : public IteratorBase&lt;List, Link, elemType&gt;
{
public:
	Iterator(listType& rList) : IteratorBase(rList) {};
};

class ConstIterator : public IteratorBase&lt;const List, const Link, const elemType&gt;
{
public:
	ConstIterator(listType& rList) : IteratorBase(rList) {};
};
Omdat de klasse IteratorBase een template klasse is, moeten we de definitie van de member functies in het header bestand (.h) zetten. Het makkelijkste is om ze meteen bij de functiedeclaraties in de klassedefinitie te zetten. Bijv:
Code:
template &lt;class TList, class TLink, class TElem&gt;
class IteratorBase
{
//...
	inline bool AtEnd() const { return (m_pLink == 0); } // geeft aan of we klaar zijn met itereren (voorbij het einde van de lijst zijn)
//...
};
[kopje]Opdracht 4.1[/kopje]: Implementeer het spul hierboven en test het met een driver programmaatje.
[/hand]
 
[hand]
5. De lijst templatiseren

Inhoud
  • [linkje]Wat is een template?[/linkje]
  • [linkje]Een template klasse maken van List[/linkje]
  • [linkje]Testen[/linkje]
Opdrachten
  • [linkje]Opdracht 5.1[/linkje]
  • [linkje]Opdracht 5.2[/linkje]
  • [linkje]Opdracht 5.3[/linkje]

In het eerste deel hebben we een lijst gemaakt die elementen van een bepaald vooraf gedefinieerd type kan opslaan. We hebben dat type toen in een typedef gezet om het makkelijk te maken om dit te veranderen.
Code:
typedef int elemType; // het type van een element in de lijst

Maar wat nu als we een lijst willen hebben die integers opslaat en een lijst die doubles opslaat? Met deze implementatie zou dat niet kunnen. Gelukkig kunnen we hiervoor gebruik maken van templates.
[kopje]Wat is een template?[/kopje]
Met een template kunnen we een stuk C++ code toepassen op meerdere types (ingebouwde types, zoals int, char, float e.d. of zelfgemaakte structs of klassen). We doen dit door het type in de template te zetten (het type wordt dan het template argument genoemd). In plaats van te spreken over bijv. een int, hebben we het dan over het type T (of welke naam je eraan wilt geven). Als we de code willen gebruiken, moeten we zeggen welk type we voor T willen nemen.
De syntax voor een template ziet er als volgt uit:
Code:
template &lt;class [i]type_naam[/i]&gt; [i]functie_of_klasse_declaratie[/i];
template &lt;typename [i]type_naam[/i]&gt; [i]functie_of_klasse_declaratie[/i];
De beide regels zijn gelijkwaardig. Voor type_naam moet je een naam invullen die je voor het template argument wilt gebruiken; vaak wordt T gebruikt. Voor functie_of_klasse_declaratie moet je de (normale) declaratie van een functie of klasse invullen. Een voorbeeld van een template functie om een getal om te zetten naar een string is:
Code:
#include &lt;sstream&gt;

// Zet het meegegeven getal om in een std::string
template &lt;class T&gt; std::string ToStr(const T value) {
	std::ostringstream oss;
	oss &lt;&lt; value;
	return oss.str();
}
Compilers gaan anders om met template functies en template klassen dan met normale functies en klassen. Een template functie wordt helemaal niet gecompileerd, totdat deze ergens wordt aangeroepen. Als we in de functie hierboven voor de return statement "syntax error!;" toevoegen, compileert de code waarschijnlijk prima, zolang we de functie nergens aanroepen (dit kan per compiler verschillen).
Op het moment dat een template functie wordt aangeroepen, wordt de functie gemplementeerd met het opgegeven type. Voor de functie hierboven doe je dat als volgt:
Code:
std::string str1 = ToStr&lt;int&gt;(1. / 3);
std::string str2 = ToStr(1. / 3);
// output:
// str1 = "0"
// str2 = "0.333333"
In het eerste geval geven we expliciet op welk type er moet worden genomen bij de implementatie van de template functie. Het argument dat we aan de functie meegeven wordt dan dus automatisch gecast naar een int. Daarom is de output bij deze functie "0". In het tweede geval kan de compiler het type dat moet worden genomen zelf bepalen, aan de hand van het type van het argument dat we meegeven (in dit geval een double).
[kopje]Een template klasse maken van List[/kopje]
De lijst die we gemaakt hebben, bestaat uit verschillende klassen, dus zellen we eerst eens goed moeten kijken waar we allemaal een template van moeten maken. Om te beginnen moeten we een template klasse maken van alle klassen die een element bevatten van het type elemType. Dat is dus de klasse Link. We doen dat als volgt.
Code:
template &lt;class T&gt;
class Link
{
	friend class List; // alleen de list mag dit element gebruiken
private:
	Link(T data, Link&lt;T&gt;* pNext); // kan alleen door een list gemaakt worden

	T m_Element;
	Link&lt;T&gt;* m_pNext;
};
Door 'template &lt;class T&gt;' voor de klasse definitie te zetten, vertellen we de compiler dat de klasse definitie afhankelijk is van het type dat we voor T nemen. Overal waar we elemType hadden staan, zetten we nu T. We hadden ook in plaats van T elemType kunnen nemen, maar op deze manier is het verschil wat duidelijker.

Je ziet dat de Link pointers ook zijn aangepast. De klasse Link bestaat niet meer, omdat dat nu een template klasse is. Als we het dus over de klasse Link willen hebben, moeten we opgeven welk type er voor het template argument (T dus) moet worden genomen. In dit geval hebben we een pointer naar een instantie van de klasse Link met hetzelfde template argument, dus kunnen we Link&lt;T&gt;* zetten. De T refereert hier dus naar het template argument T van de klasse Link dat we in de eerste regel gespecificeerd hebben.

De constructor van de klasse Link&lt;T&gt; is het enige wat we nog moeten implementeren voor die klasse. Normaal zouden we dit in een .cpp bestand zetten. Maar, zoals eerder gezegd, wordt een template klasse pas gecompileerd als we ernaar verwijzen, omdat we het type dat voor de implementatie gebruikt moet worden eerder nog niet weten. Als we de constructor dan in een .cpp bestand definiren, kan de compiler die definitie niet meer terug vinden. Daarom is het gebruikelijk om bij template klassen alle functiedefinities in het .h bestand te zetten. Dit kunnen we op twee manieren doen.

Allereerst kunnen we de body van de constructor direct in de klassedefinitie zetten.
Code:
template &lt;class T&gt; class Link
{
private:
	Link(T data, Link&lt;T&gt;* pNext) // kan alleen door een list gemaakt worden
		: m_Element(data), m_pNext(pNext)
	{
	}
// ...
};
We kunnen de functie echter ook definiren na de klasse definitie. Dan zetten we dus het stuk dat we normaal in het .cpp bestand zetten onderaan het .h bestand. Omdat het hier om een template klasse gaat, moeten we de compiler hier nogmaals aan herinneren, anders weet die niet over welke T we het hebben.
Code:
template &lt;class T&gt;
Link::Link(T data, Link&lt;T&gt;* pNext)
: m_Element(data), m_pNext(pNext)
{
}

Als je dit gedaan hebt en het hele spul compileert, zul je merken dat je compiler fouten geeft in je List klasse, omdat daar een pointer naar een Link wordt opgeslagen. De klasse Link bestaat niet meer, omdat we daar een template klasse van gemaakt hebben. We zullen Link* dus moeten vervangen door Link&lt;T&gt;*. Maar hoe weet de compiler dan welk type hij voor die T moet nemen? Dat kan ie alleen maar weten als we ook van List een template klasse maken.
[kopje]Opdracht 5.1[/kopje]: Maak van de List klasse een template klasse en pas alle pointers naar een Link aan.

Ook de Iterator klasse heeft een pointer naar een Link en een reference naar een List. Deze klassen zullen we ook weer moeten vervangen door de template klassen.
[kopje]Opdracht 5.2[/kopje]: Maak van de Iterator klasse een template klasse en pas alle pointers naar een Link en references naar een List aan.
[kopje]Testen[/kopje]
Een template klasse testen is wel even wat lastiger dan een normale klasse testen. Zoals al eerder gezegd, wordt niet altijd alle template code gecompileerd. Daar komt bij dat de code alleen wordt gecompileerd voor het type waarvoor we de code aanroepen. Dat betekent dus dat we de template code zullen moeten uitproberen met meerdere verschillende types.

Bijvoorbeeld:
Code:
template &lt;class T&gt;
T multiplyByFour(const T value)
{
	return (value &lt;&lt; 2);
}

int main()
{
	multiplyByFour&lt;int&gt;(10); // werkt prima
	multiplyByFour&lt;double&gt;(10); // compiler error

	return 0;
}
In dergelijke gevallen is het goed om duidelijk te documenteren aan welke voorwaarden het type dat je in de template functie of klasse wilt gebruiken, moet voldoen. In dit geval moet de "operator <<(int)" (oftewel de left shift operator) gedeclareerd zijn voor het type dat we willen gebruiken. Het beste kun je op de plek waar je de eerste compiler error krijgt een comment plaatsen, waarin je verwijst naar die documentatie.

Er zijn ook manieren om een duidelijker foutmelding van de compiler te krijgen. Bjarne Stroustrup heeft daar een mooi stukje over geschreven.
http://www.research.att.com/~bs/bs_faq2.html#constraints
Dit werkt echter niet op alle compilers en het vergt een goede beheersing van C++ om te kunnen begrijpen wat er gedaan wordt en het zelf toe te kunnen passen.

[kopje]Opdracht 5.3[/kopje]: Test je code. :wink:
[/hand]
 
Laatst bewerkt door een moderator:
Status
Niet open voor verdere reacties.
Steun Ons

Nieuwste berichten

Terug
Bovenaan