12. Dynamisk minnesallokering

 

1.       Minnesallokering.

2.       New - delete.

3.       Pekare.

4.       Länkade listor.

 

1. Minnesallokering.

 

Ibland vet man inte hur mycket minne man behöver när ett program skrivs. Ta t.ex. ett program som ska hantera en lista på medlemmar i en klubb, och man vill ha alla medlemmar i en listvariabel av en egendefinierad strukturtyp. Om man då definierar variabeln så här:

 

struct medlem Medlemmar[10];

 

...så rymmer den 10 medlemmar, inte mer. Blir det fler medlemmar måste man ändra i programmet, och kompilera/länka igen. Har man dessutom strukturerat programmet med samma begränsningar kan det hända att man måste skriva om större delar av programkoden också.

 

Varför inte dra till ordentligt då? För det första måste vi tänka på att datorns min­ne är en begränsad resurs. Egentligen har vi inte råd att reservera större mäng­der utrymme som inte används. Förr eller senare behövs utrymmet till an­nat, som vi då tycker är viktigt. Vi kanske har reserverat för 100 medlemmar i vår lilla lokala kattklubb (det är vi och grannen och deras bekanta samt några till och deras svåger, så vi har gott om plats för flera medlemmar) med resultat att vi måste stänga medlemsegistret varje gång vi vill köra Word eller Excel. Det­ta kan inte accepteras, eftersom vi köpt in dessa program för dyra pengar och klubbkassan är liten.

 

Om vi inte drar till fullt så mycket då? Vad vet vi om framtiden? Alltför ofta väx­er det fortare än man tänkt sig. Om ett par år kanske vår kattklubb växt i par­itet med Svenska Kennelklubben (det finns ju faktiskt många fler katter än hun­d­ar i sverige). De fantasifulla 100 medlemmarna räckte inte.

 

Lösningen på ovanstående dilemma är att programmet ber operativsystemet om mer utrymme efterhand som det behövs. Programmet tar då inte upp oanvänt ut­rymme, och när väl den lilla klubben växt sig till Svenska Kisseklubben och man ändå inte får plats med allt i minnet räcker det med att köpa mer minne, ing­a förändringar behöver göras i programmet.

 

Hur ber man då om minne? Det ska vi titta på i nästa avsnitt.

 

2. new - delete.

 

I C++ kan man använda ‘new’ för att be om mera minne. Allmän syntax:

 

pekare = new typ;

 

Detta betyder att vi använder operatorn 'new' till att reservera minnesutrymme anpassat att innehålla data av typen typ, samt tilldelar pekaren pekare adressen till det reserverade utrymmet. Man kan tro att 'new' är en funktion, eftersom den returnerar ett värde, men i själva verket är det en operator. Utan att gå längre in på tekniska detaljer kan man konstatera att operatorerna i C++ faktiskt är funk­tioner, och detta beror av att alla datatyper är klasser. Vi ska titta litet på klasser i kommande kapitel.

 

Vanligt är att man passar på att deklarera även pekaren i samma sats. Då behöv­er vi naturligtvis ange samma datatyp på två ställen:

 

typ *pekare = new typ;

 

Observera att ovanstående syntax inte betyder att returvärdet lagras där pekare pekar, vilket stjärnan antyder. Stjärnan ingår i pekarens typdeklaration och har ingen inverkan på tilldelningen i detta fall. Annat vore ologiskt eftersom pekar­en deklareras här och naturligtvis inte pekar på någonting före tilldelningen.

 

Här nedan följer diverse exempel:

 

int *ip = new int;                     // Ett heltal, 2 bytes.

double *dp = new double;              // Dubbel precision.

struct person *sp = new struct person;      // En hel struktur!

int *ip10 = new int[10];              // Även listor!

char *cp = new char[81];              // Textsträng.

 

Observera att dessa programinstruktioner reserverar utrymme när programmet körs, inte vid kompilering. Om en programsats inte utförs kommer minne inte att reserveras (en besparing). Om en programsats utförs flera gånger kommer min­ne att reserveras flera gånger. Man reserverar alltså utrymme efterhand som det behövs, och aldrig i onödan.

 

När man sedan är klar med minnet ska man lämna tillbaka det med hjälp av 'delete'. Här följer syntaxen:

 

delete pekare;

 

Om vi tillexempel ska frigöra det vi allokerade tidigare:

 

delete ip;

delete dp;

delete sp;

delete ip10;

delete cp;

 

En fördel med new och delete är att man bara behöver frigöra minnet om man tänker låta programmet fortsätta med någonting. Om programmet ändå avslutas när man inte längre behöver minnet, behöver man inte använda delete, minnet frigörs automatiskt när programmet avslutas. Detta kan vara en sanning med mo­difikation. Det är operativsystemet som återtar reserverat minne vid pro­gram­slut, och om inte operativsystemet klarar detta så måste man ändå själv göra det. Det tillhör god programmeringssed att man ändå frigör minnet själv.

 

Definition: Minne kan reserveras med hjälp av operatorn new. Man måste sedan använda pekare för att utnyttja det reserverade minnet. Man frigör minnet med hjälp av delete när man inte behöver det längre.

 

? new, delete.

 

3. Pekare.

 

Eftersom vi inte har någon egentlig variabel deklarerad kan vi inte nå vårt data på vanligt sätt. Det vanliga sättet är ju att använda variabelnamnet:

 

iTal = 5; // Här används namnet iTal vid tilldelning.

 

I stället använder vi pekare:

 

*piTal = 5; // Här används heltalspekaren ipTal för att lagra

            // talet 5 på den position i minnet som piTal pekar

            // på.

 

Åter till vår medlemslista. Nu skulle vi kunna ha en lista med pekare i stället. Denna kan innehålla till exempel 10000 pekare:

 

struct medlem *pMedlem[10000];

 

Varje gång man begär utrymmet till en ny 'medlemspost' tar man en av dessa pek­are och tilldelar den adressen till den nya posten. Men vänta nu, nu har vi återigen begränsat oss till ett antal poster, vi har ju bara 10.000 pekare! Ja, det är sant, men dessa tar bara 40.000 bytes i minnet. Har vi en lista med medlems­poster som innehåller till exempel 120 bytes per post, så tar dessa tillsammans 1.200.000 bytes i minnet. Vi har alltså inte löst problemet hundraprocentigt, men vi har kommit en bra bit på vägen.

 

Kom ihåg att man kan använda indexerade pekare. Det fungerar naturligtvis äv­en här. Vi har ju redan gjort detta i ett tidigare kapitel.

 

Övningsuppgift 12.3.1:

·      Öppna projektet Medlem om det inte redan är öppet.

·      Ändra deklarationen av listan Medlem på följande sätt:

·      Deklarera en pekare pMedlem av typen 'struct person'.

·      Reservera minnesutrymme för medlemsposterna med hjälp av 'new'.

·      Tilldela pMedlem den adress som 'new' returnerar.

·      Ovanstående steg kan utföras som en programsats.

·      Använd 'delete' sist i programmet för att frigöra minnesutrymmet.

·      Testa programmet, det ska fungera som tidigare.

 

4. Länkade listor.

 

Man kan även skapa pekarna dynamiskt, det vill säga med hjälp av new. Detta kräver att man skapar en struktur med ett par pekare, och skapar nya variabler från den strukturen när det behövs mer minne. Varje sådan variabel kan då in­nehålla information om var nästa respektive första variabel finns, samt var själ­va posten finns. Denna teknik kallas länkad lista. Vi ska inte fördjupa oss i tek­niken, men den som är intresserad kan prova att 'knappa in' nedanstående exem­pel:

 

#include <iostream.h>

#include <string.h>

 

void main()

{

   struct person {

                   char cNamn[31];

                   struct person *next;

                 };

 

   struct person *pCurrent = new struct person;

   struct person *pStart;

   pStart = pCurrent;

 

   cout << "Skriv in så många namn du har lust till!\n";

   cout << "Avsluta med 'slut'.\n";

   cin >> pCurrent->cNamn;

 

   while(strcmp(pCurrent->cNamn,"slut"))

   {

      pCurrent->next = new struct person;

      pCurrent = pCurrent->next;

      cin >> pCurrent->cNamn;

   }             

 

   cout << "Detta var vad du skrev:\n";

 

   while(pStart != pCurrent)

   {

      cout << pStart->cNamn << "\n";

      pStart = pStart->next;

   }

}

 

Efterhand som man matar in nya uppgifter i strukturen (namn) lägger program­met in pekare till nästa förekomst av strukturen i minnet. Adressen till första fö­r­e­komsten av strukturen sparas i pekaren pStart. När användaren skriver ‘slut’ av­bryts inmatningen. Därefter skriver programmet ut allt som matats in.

 

Vi kommer att behöva detta när vi sysslar med klasser och objekt.