TDDC69 Objektorienterad prog. och Java

Labb 3: Introduktion till C++

Introduktion

Syftet med den här laborationen är att gå genom vissa grunder i objektorienterad programmering i C++ och några av de viktigaste skillnaderna som finns jämfört med Java.

Observera: C++ är ett stort och jämförelsevis komplext språk. Det är uttryckligen designat för att stödja många olika stilar och för att ge programmeraren möjlighet att välja, "även om detta gör det möjligt att välja fel". Det är också designat för att ge hög prestanda även om detta leder till ökad komplexitet. Detta i kombination med manuell minneshantering gör t.ex. att allokering, kopiering och radering av objekt på många sätt är mer komplicerat än i Java.

Detta betyder inte att C++ är ett dåligt språk. Den största anledningen till att det är komplicerat är just att det ger så många alternativ och så många möjligheter till "detaljstyrning". Däremot betyder det att vi på den tid som finns tillgänglig i denna kurs kan skrapa lite på ytan, men inte på något sätt bli fullfjädrade C++-programmerare.

Förkunskaper

Du förutsätts ha kunskaper i grundläggande programmering i den icke objektorienterade delen av C++, motsvarande kursen TDDC68 Imperativ programmering i Ada för C1 och D1.

Utvecklingsmiljö för C++: Kommandoradsverktyg

En kompilator för C++ brukar ingå i alla Linux/Unixsystem. Detta och en lämplig texteditor (t.ex. Emacs) är egentligen allt som behövs för den här kursen, speciellt med tanke på att andelen C++-programmering är ganska liten. Rekommenderad kompilator för IDA:s Sun-system är g++ (ingår i GNU GCC). För att få tillgång till den används kommandot

    module add prog/gcc/4.7.2

För större program används normalt make för att hålla reda på vad som behöver kompileras. I denna labb skapar vi ett väldigt litet program och nöjer oss därför med en enkel kommandorad:

    g++ -std=c++98 -pedantic -Wall -Wextra list.cpp -o list

Denna checklista för grundläggande klassdesign, innehåller på slutet information om tänkbara kompileringsfel. Se även mer om kompilatorer för C++ på IDA:s Sun-system.

Om du vill laborera hemma ingår g++ i de flesta Linuxdistributioner. Under Windows har tidigare kursledning rekommenderat MinGW, Minimalist GNU for Windows, som är en portning av GCC (GNU Compiler Collection) och stödjer både C, C++, Fortran och Ada. Vi kan inte ge support för dessa alternativ – har du problem måste vi tyvärr hänvisa till labbsalarna.

Utvecklingsmiljö för C++: Integrerade miljöer

Vill man ha en integrerad utvecklingsmiljö kan man använda t.ex. Eclipse. Tiden för att lära sig en utvecklingsmiljö kan dock vara lite för lång för att det ska löna sig för en så här liten labb, och då kod skriven i C++ är svårare att analysera automatiskt kan utvecklingsmiljöerna typiskt inte heller ge lika bra navigering, kodkomplettering eller kodanalys i C++ som de kan för Java. Vi kan inte heller ge support för detta alternativ.

För att använda C++ i Eclipse kan det krävas att du laddar ner en plug-in till Eclipse som heter CDT (C/C++ Development Toolkit) – se t.ex. IBMs sidor om att komma igång med CDT.

Labbuppgift: Sorterade länkade listor

Under den här labbens gång kommer vi att utforska hur olika objektorienterade begrepp appliceras i C++. Detta kommer återigen att ske till stor del i tutorialform med vägledning steg för steg, så att vi relativt snabbt kan gå genom de nödvändiga begreppen och därefter gå tillbaka till projektprogrammeringen i vårt huvudsakliga språk Java.

Uppgiften går ut på att implementera en länkad lista för heltal som lagrar sina värden i sorterad ordning. Själva listan kommer att representeras av klassen List, medan en enskild länkad nod i listan representeras av den abstrakta klassen List_Node. Att klassen är abstrakt beror på att vi har två distinkta fall att hålla reda på. De flesta noder i en lista kommer att vara av undertypen Int_Node, som innehåller dels ett heltal, dels en pekare till nästa nod. För att denna pekare aldrig ska behöva vara NULL, och för att vi ska kunna använda polymorfism för att ta hand om vissa specialfall relaterade till slutet av en lista, avslutas varje länkad nodsekvens med en nod av typen End_Node. Denna typ av nod innehåller varken ett heltal eller en pekare till nästa nod. Därmed har alltså tomma listan exakt en nod i sin sekvens – mer generellt har en lista med n element exakt n+1 noder.

En stor del av koden och kommentarerna är ursprungligen tagna från ett exempel av Tommy Olsson.

1. Headerfil och kodfil

För att skapa vår listimplementation börjar vi med följande enkla skelett som ska placeras i headerfilen list.h. Notera att vi här deklarerar flera klasser i samma fil, vilket är en skillnad mot det vanliga tillvägagångssättet i Java.

class List
{
    public:
        List();                    // defaultkonstruktor
        List(const List& other);   // kopieringskonstruktor
        ~List();                   // destruktor
        List& operator=(List& rhs);// kopieringstilldelningsoperator
        void insert_sorted(const int value);
        void swap(List& other);
        int len() const;
        int get(const int pos) const;
    private:
        class List_Node* first_node;
        int length;
        class List_Node* copy(const class List_Node* p) const;
};

class List_Node
{
    public:
        virtual ~List_Node();
        virtual List_Node* insert_sorted(const int value) = 0;
        virtual List_Node* clone() const = 0;
        virtual int get(const int pos) const = 0;
    protected:
        List_Node();
    private:
        // Annan kopiering än med clone() är ej tillåten,
        // så vi deklarerar en privat kopieringskonstruktor
        // och kopieringstilldelningsoperator utan att
        // ge dem någon implementation.
        List_Node(const List_Node&);
        List_Node& operator=(const List_Node&);
};

class Int_Node : public List_Node
{
    public:
        Int_Node(const int value, List_Node* next);
        ~Int_Node();
        virtual Int_Node* insert_sorted(const int value);
        virtual Int_Node* clone() const;
        virtual int get(const int pos) const;
    private:
        // Annan kopiering än med clone() är ej tillåten
        // (som för List_Node)
        Int_Node(const Int_Node&);
        Int_Node& operator=(const Int_Node&);

        // Medlemsvariablerna är privata
        int node_value;
        List_Node* next_node;
};

class End_Node : public List_Node
{
    public:
        End_Node();
        virtual Int_Node* insert_sorted(const int value);
        virtual End_Node* clone() const;
        virtual int get(const int pos) const;
    private:
        // Annan kopiering än med clone() är ej tillåten
        // (som för List_Node)
        End_Node(const End_Node&);
        End_Node& operator=(const End_Node&);
};

Vi behöver också skapa en kodfil, list.cpp. Filen ska börja så här:

// Vi behöver klassdeklarationerna...
#include "list.h"
// ...och standardfunktioner för I/O med mera
#include <iostream>
#include <algorithm>

// Vi behöver använda saker från namnrymden std
using namespace std;

2. Konstruktion av listelement och tomma listor

Listklassen ska ha en defaultkonstruktor, dvs. en konstruktor som kan anropas utan argument. Denna konstruktor är redan deklarerad i list.h och är publik, tillgänglig för alla, men den måste också få en implementation som passar till den representation vi har tänkt oss. I den representationen ska varje lista innehålla en pekare till dess första listnod, och varje sekvens av noder slutar med en End_Node. När vi skapar en ny tom lista ska vi därför peka på ett nytt End_Node-objekt. Det kan vi göra genom att lägga in följande kod i list.cpp, där vi använder C++-syntaxen för initializer lists för att ge ett initialvärde till first_node.

List::List() :
    first_node(new End_Node()), length(0)
{}

Vi måste också implementera konstruktorer för de tre nodklasserna. Vi börjar med List_Node, vars konstruktor inte ska göra något. Den är deklarerad protected för att se till att den enbart kan användas för subklasserna – klassen ska ändå bli abstrakt och ska inte instansieras direkt. I list.cpp lägger vi därför till följande tomma implementation:

List_Node::List_Node() {}

Skriv nu en liknande implementation av defaultkonstruktorn för End_Node (som är public!), med en tom metodkropp.

Fortsätt sedan med konstruktorn för Int_Node. Denna konstruktor är också publik och behöver ta två parametrar: Ett heltal som lagras i noden och en pekare till nästa nod i listan. Nedan visar vi hur själva implementationen i list.cpp ska se ut.

Int_Node::Int_Node(const int value, List_Node* next) : 
    node_value(value), next_node(next)
{}

3. Stoppa in element i listor

Nu behöver vi se till att det går att stoppa in element i en lista. Vi antar att listan redan är sorterad i växande (eller strikt sett "icke avtagande") ordning – det gäller ju trivialt för den tomma listan. Vi har därför en metod i List som vi kallar insert_sorted(), och som ska lägga till ett angivet värde på rätt plats så att listan fortfarande är sorterad.

Vi kan åstadkomma detta genom att List::insert_sorted() själv går genom sekvensen av listnoder och hittar rätt plats för det element som ska adderas, men vi väljer istället ett annat alternativ där vi delegerar sökningen efter rätt plats till listnoderna. Eftersom det kan hända att elementet ska sättas in först i listan måste sökningen returnera den nya (eller gamla) första noden. Lägg in följande kod på lämplig plats i list.cpp och lägg till en motsvarande publik deklaration på lämplig plats i list.h.

void List::insert_sorted(const int value)
{
    first_node = first_node->insert_sorted(value);
    length++;
}

Allt vi vet om first_node när ovanstående funktion anropas är att den pekar på någon sorts List_Node – det kan vara antingen en End_Node eller en Int_Node. Dessa klasser måste alltså också ha en insert_sorted-metod, och dynamisk bindning måste användas för att slå upp vilken implementation av insert_sorted som används.

Vi börjar med List_Node-klassen. Notera att den redan har denna deklaration under "public":

virtual List_Node* insert_sorted(const int value) = 0;

Att metoden är "virtual" innebär att dynamisk bindning ska användas och att den dessutom deklareras "= 0" innebär att den är "pure virtual", ungefär motsvarande en abstrakt metod i Java. Vi vill inte ge denna metod en implementation i den här klassen, så för List_Node:s del är vi klara.

Vi behöver däremot skapa konkreta implementationer av denna metod i Int_Node och End_Node. Det kan vi göra på följande sätt. Lägg till denna kod på lämplig plats i list.cpp – men läs först genom den och se till att ni förstår allt som koden illustrerar! Ni kan bli tillfrågade om vad koden betyder när ni demonstrerar.

List_Node* Int_Node::insert_sorted(const int value)
{
    // Om värdet är mindre än denna nods värde
    // ska det stoppas in före denna nod i listan
    if (value < node_value) {
        // Här allokerar vi minne för en ny nod som ska placeras
        // före denna.  Om minnesallokeringen misslyckas vill vi
        // inte förstöra datastrukturen, vilket vi inte gör
        // eftersom vi inte har gjort några ändringar innan
        // allokeringen.
        return new Int_Node(value, this);
    } else {
        // Värdet ska stoppas in efter denna nod.  Det kan hända
        // att den stoppas in *direkt* efter denna nod.  I så
        // fall returnerar det rekursiva anropet till
        // insert_sorted en ny nod som vi får som vår nya "nästa"
        // nod.
        next_node = next_node->insert_sorted(value);
        return this;
    }
}

List_Node* End_Node::insert_sorted(const int value)
{
    // Vi har nått slutet på listan.  Elementet vi skulle
    // lägga till var större än alla existerande element i
    // listan.  Den nya noden ska vara omedelbart före denna
    // End_Node.

    // Om allokering misslyckas backar vi bara ur rekursionen,
    // som i Int_Node ovan.
    return new Int_Node(value, this);
}

4. Destruering av listor

Vi kan nu skapa tomma listor och stoppa in element i dem. I båda fall allokeras minne dynamiskt med new-operatorn, och varje klass som allokerar minne behöver ha en destruktor. För listnoderna har vi dessutom en polymorf klasshierarki, vilket kräver virtuella destruktorer för att destruering ska ske på korrekt sätt – annars är det pekartypen istället för objektets verkliga typ som anger vilken destruktor som anropas av delete.

Läs genom och placera in följande kod på lämplig plats i list.cpp. Se till att du förstår vad som händer.

// Vi måste deklarera en virtuell destruktor i List_Node även om
// den inte gör något -- annars kommer inte destruering att
// fungera korrekt när vi gör delete på en List_Node-pekare!
// Vi kan inte förlita oss på standarddestruktorn som används om
// vi inte själva deklarerar en destruktor, eftersom denna INTE
// är virtuell.
List_Node::~List_Node() {}

// När vi destruerar en Int_Node ska vi även rekursivt destruera
// den nod den pekar på (vilket då fortsätter ända till kedjan
// "tar slut").  Här behöver vi inte säga att destruktorn ska
// vara virtual -- det blir den automatiskt eftersom
// superklassens destruktor är virtual.
Int_Node::~Int_Node() { delete next_node; }

// Notera att vi inte själva skapar en destruktor för End_Node!
// Kompilatorn kommer därför att skapa en defaultimplementation
// för oss, vilket fungerar i detta fall eftersom just End_Node
// inte allokerar minne eller andra resurser.

// Slutligen behöver vi kunna destruera en hel lista.  Vi
// destruerar då dess första nod, vilket rekursivt går genom hela
// listan och destruerar alla noder fram till och med den sista
// End_Node-noden.
List::~List()
{
    delete first_node;
}

5. Kopiering av listor

Eftersom våra klasser använder dynamiskt allokerat minne duger inte heller de kompilatorgenererade kopieringskonstruktorerna. Även här måste vi alltså skriva egen kod. Vi börjar med en kloningsfunktion för listnoder, som måste vara polymorfisk och därför inte kan implementeras enbart med hjälp av t.ex. kopieringskonstruktorer – konstruktorer är aldrig polymorfiska, vare sig i C++ eller i Java. Vi har därför följande publika pure-virtual-funktion i List_Node i list.h:

virtual List_Node::List_Node* clone() const = 0;

Metoden måste implementeras i Int_Node. Använd följande kod.

Int_Node* Int_Node::clone() const
{
    // Försök först att kopiera resten av listan.  Om detta
    // misslyckas returnerar funktionen (ett undantag kastas),
    // men det är OK för vi har inte allokerat några resurser
    // eller "förstört" denna datastruktur på något sätt.
    List_Node* p = next_node->clone();

    try {
        // Försök sedan att allokera minne för en ny Int_Node som
        // har samma värde som denna, men pekar på den nya
        // kopierade "svansen".  Om *detta* misslyckas kan vi
        // inte bara returnera som vi gjorde ovan -- vi måste
        // städa upp det minne vi faktiskt lyckades allokera (p)!
        return new Int_Node(node_value, p);
    } catch (...) {
        // Konstruktionen ovan är en "catch-all" som fångar ALLA
        // fel som kan uppstå.
        // Städa upp:  Frigör det minne vi lyckades allokera
        delete p;
        // Kasta vidare det fel som uppstod
        throw;
    }
}

Metoden måste också implementeras i End_Node. Eftersom End_Node inte har några medlemsvariabler är detta enkelt: Skriv en motsvarande implementation som helt enkelt returnerar (en pekare till) en ny End_Node, enligt den metodprototyp som angavs först i labben.

Till slut är det dags att implementera kopieringskonstruktorn i List-klassen: List::List(const List& other). Den nya listans nodpekare ska peka på en kopia av den gamla listans nodsekvens, skapad med clone()-metoden ovan, och den nya listans längd ska vara lika med den gamlas. Skriv en egen kopieringskonstruktor på detta sätt!

6. Kopieringstilldelning

Utöver kopieringskonstruktorn måste vi också implementera en kopieringstilldelningsoperator (copy assignment operator). Detta gör vi i två steg. Först implementeras metoden List::swap(List& other), som byter innehåll på två listor. Sedan implementeras själva kopieringstilldelningsoperatorn, List& List::operator=(List& rhs), som utför tre steg: Skapa en klon av rhs, byt innehåll mellan klonen och det aktuella objektet (*this), och returnera det aktuella objektet (*this). Se föreläsningsanteckningarna för utförliga förklaringar!

7. Hämta element i listor

Vi vill kunna hämta elementet på en viss position i en lista, där första elementet antas vara på position 0. Denna typ av sökning liknar funktionaliteten för att stoppa in nya värden på så sätt att listan "delegerar" till nodsekvensen att rekursivt ta sig fram till rätt position. Att hämta element är dock betydligt enklare än att stoppa in, eftersom listan inte behöver modifieras.

Följande implementation kan användas för List-klassen. Notera att metoden deklareras const för att indikera att den inte kan ändra på innehållet i listan.

int List::get(const int pos) const
{
      return first_node->get(pos);
}

Skriv nu motsvarande implementationer av get() för Int_Node och End_Node. Tips: För nodernas get()-metod är positionen angiven relativt den nuvarande noden. Positionen måste alltså räknas ned i varje rekursivt anrop.

Om en felaktig position anges (mindre än 0 alternativt större än längden) borde man egentligen kasta ett undantag för att signalera fel. Detta är något vi inte går genom i den här kursen och därför kan ni i stället t.ex. returnera värdet -1.

8. Returnera listans längd

Vi har nu kommit till det sista och enklaste steget i själva listklassen: Implementera listans len()-metod. Notera att metoden inte kan heta length(), eftersom vi har en medlemsvariabel (ett fält) med det namnet. Java förstår vad man menar i det fallet, men inte C++.

Testprogram

För att avsluta labben ska ni nu skriva ett testprogram – en vanlig main()-funktion i list.cpp, på samma sätt som ni lärde er i TDDC68 – som:

Skapar två listor, list1 och list2.
Lägger till ett antal heltal i var och en av listorna. Heltalen ska läggas till i "osorterad" ordning, så att insert_sorted() får "sortera" dem.
Skriver ut båda listorna med hjälp av print(), så ni kan se att heltalen har placerats i korrekt sorterad ordning. Detta innebär att print() måste implementeras. Eftersom print() tar en referensparameter kopieras inte listan vid anropet.
Skriver ut båda listorna med hjälp av printcopy(). Eftersom printcopy() tar en icke-referensparameter kopieras listan vid anropet vilket även testar kopieringskonstruktorn.
Gör list2 = list1; och skriver ut elementen i list2 igen, så att ni ser att kopieringstilldelningsoperatorn fungerar.

// Vi använder inga kommandoradsargument, så vi behöver inte ha
// några parametrar till main()...
int main() {
    // ...

    return 0;
}

// Skriver ut en lista.  Parametern är en referens, så den behöver
// inte kopieras.
void print(const List& list) {
    // Här behöver ni skriva ut alla element, från index 0 till
    // index length-1.  Detta blir lite ineffektivt eftersom
    // listans get()-metod alltid börjar söka från början.
    // Egentligen borde vi istället ha en iterator som kan iterera
    // effektivt över listan, men det är överkurs för denna
    // introduktion.
    ...
    cout << ... << endl;
    ...
}

// Skriver ut en lista.  Parametern är varken referens eller
// pekare, så hela listan kopieras automatiskt.  Sedan skickar vi
// den kopian till den ursprungliga print-funktionen så att vi
// slipper skriva samma kod en gång till...
void printcopy(const List list) {
    print(list);
}

Kompilera programmet enligt tidigare instruktioner och testa det genom att köra ./list

Några möjliga kompileringsfel

list.h: I kopieringskonstuerare "List::List(const List&)":
list.h:14:13: varning: "List::length" kommer initieras efter [-Wreorder]
list.h:13:26: varning:   "List_Node* List::first_node" [-Wreorder]
list.cpp:122:1: varning:   vid initiering här [-Wreorder]

Medlemsvariabler som initialiseras i en konstruktors initialiseringlista kommer inte att ges sina värden i den ordning de skrivs i initialiseringslistan utan i den ordning variablerna först angavs i klassdeklarationen i .h-filen. Om variablerna har angivits i olika ordning på de två ställena får ni en varning enligt ovan.

list.cpp: I global räckvidd:
list.cpp:147:5: varning: oanvänd parameter "pos" [-Wunused-parameter]

Denna typ av varning kan ni få om en metod inte använder en eller flera av sina parametrar. Detta indikerar ibland ett fel i koden men kan också bero på att en metod är implementerad i flera klasser och att den i vissa av sina implementationer inte behöver alla parametrar. Så kan t.ex. vara fallet för End_Node::get(). Varningen kan undvikas genom att man låter bli att ge parametern ett namn i de metoder där den inte behövs, t.ex. genom att definiera int End_Node::get(const int) const instället för int End_Node::get(const int pos) const.

Examination

Gruppen ska demonstrera det slutgiltiga programmet för labbhandledaren, visa att man förstår vad som händer, och lämna in koden enligt de vanliga instruktionerna.

Sidansvarig: Jonas Kvarnström
Senast uppdaterad: 2012-10-08

Institutionen för datavetenskap