dt047g Programmeringsmetodik

Laboration:

Dynamisk minneshantering, RAII och merge

Martin Kjellqvist∗

–sourcefile– –revision– –time– –owner–

1

Introduktion

RAII - http://en.wikipedia.org/wiki/Resource_Acquisition_Is_Initialization
¨

ar ett idiom i C++ som g¨

or v˚

ar programkod fri fr˚

an minnesl¨

ackage. Iden ¨

ar enkel, anv¨

and

enkla beh˚

allare som d˚

a de konstrueras ocks˚

a skapar resursen. Vid destruktion frig¨

ors

resursen. Anv¨

and sedan stacken f¨

or att skapa och f¨

orst¨

ora dessa enkla beh˚

allare. Stacken

kommer att garantera att resursen frig¨

ors oavsett vad som h¨

ander i programmet.

Vi str¨

avar efter att f˚

a den dynamiska minneshanteringen transparent och enkel.

Uppgiften till˚

ater oss att sedan implementera en kraftfull sorteringsmetod p˚

a ett enkelt

s¨

att.

2

Syfte

Syftet med denna laborationen ¨

ar

• Fr¨asha upp kunskaperna om filhantering, pekare och referenser.

• Bli v¨albekant med RAII idiomet.

3

L¨

asanvisningar

Detta ¨

ar en inledande laboration. Du anv¨

ander kurslitteraturen som referens tillsammans

med dina tidigare erh˚

allna c++ kunskaper.

∗E-post: martin.kjellqvist@miun.se.

1 (4)

4

Genomf¨

orande

F¨

or varje klass ska du skapa en cpp-fil och en h-fil med include-guards. http://en.

wikipedia.org/wiki/Include_guard. Detta f

¨

or att garantera unika definitioner, http:

//en.wikipedia.org/wiki/One_Definition_Rule.

Genomf¨

or uppgifterna i den ordning de ges.

Ditt program ska l¨

asa filerna som omn¨

amns ifr˚

an ”current directory”. Samtliga filer ¨

ar i

textformat med ’\n’ som radslut.

1. Skapa en klass int buffer som sk¨

oter en minnesresurs av typen int.

Klassen ska ha f¨

oljande gr¨

anssnitt.

c l a s s

i n t b u f f e r {

p u b l i c :

e x p l i c i t

i n t b u f f e r ( s i z e t

s i z e ) ; // s i z e t

i s

d e f i n e d i n

c s t d l i b

i n t b u f f e r ( c o n s t i n t ∗ s o u r c e ,

s i z e t

s i z e ) ;

i n t b u f f e r ( c o n s t i n t b u f f e r& r h s ) ;
i n t b u f f e r & o p e r a t o r =( c o n s t i n t b u f f e r& r h s ) ;
s i z e t

s i z e ( ) c o n s t ;

i n t ∗ b e g i n ( ) ;
i n t ∗ end ( ) ;

c o n s t i n t ∗ b e g i n ( ) c o n s t ;
c o n s t i n t ∗ end ( ) c o n s t ;

˜ i n t b u f f e r ( ) ;

} ;

Att t¨

anka p˚

a: storleksf¨

or¨

andringar sk¨

ots enkelt av konstruerare nummer tv˚

a. Kon-

trollera self-assignment vid tilldelningen.

• Skriv klassdefinitionen med n¨odv¨andiga till¨agg i int buffer.h och implementation

i int buffer.cpp.

• Skriv f¨oljande test i main:

-Anropa en funktion f med argumentet int buffer(10)

v o i d f ( i n t b u f f e r b u f ) ;

och kontrollera med hj¨

alp av breakpoints vilka konstruerare och destruerare som

k¨

ors. Anteckna detta i labbem.

- I funktionen f, skriv tv˚

a forsatser med f¨

oljande form

f o r ( i n t ∗ i = b u f . b e g i n ( ) ;

i != b u f . end ( ) ;

i ++)

och

f o r ( c o n s t i n t ∗ i = b u f . b e g i n ( ) ;

i != b u f . end ( ) ;

i ++)

2 (4)

d¨

ar den f¨

orsta formen tilldelar buffern 1 och upp˚

at. Den andra formen skriver

ut inneh˚

allet i buffern. Kontrollera med debuggern att r¨

att version av begin och

end anropas i de b˚

ada fallen. Anteckna detta i labben.

Detta avslutar testning f¨

or int buffer.

2. Skapa en klass med f¨

oljande gr¨

anssnitt.

c l a s s

i n t s o r t e d {

p u b l i c :

i n t s o r t e d ( c o n s t i n t ∗ s o u r c e ,

s i z e t

s i z e ) ;

s i z e t

s i z e ( ) c o n s t ;

i n t ∗ i n s e r t ( i n t v a l u e ) ; // r e t u r n s t h e i n s e r t i o n p o i n t .

c o n s t i n t ∗ b e g i n ( ) c o n s t ;
c o n s t i n t ∗ end ( ) c o n s t ;

i n t s o r t e d merge ( c o n s t i n t s o r t e d& m e r g e w i t h ) c o n s t ;

} ;

En formell beskrivning av merge finner du i algoritm 2.

Notera att denna klass ska inte hantera n˚

agot dynamiska minne alls. Det sk¨

oter

buffern. Man kan f¨

or f¨

orb¨

attrad prestanda hos klassen ha attribut size och capaci-

ty. D¨

ar capacity ¨

ar storleken p˚

a buffern, size ¨

ar antalet m man l˚

ater capacity vara

tillr¨

ackligt stort kan man undvika st¨

orre prestandaf¨

orluster.

Klassen har minst ett privat attribut av typen int buffer.

Testa klassen genom att g¨

ora insert p˚

a n˚

agot hundratal slumptal och d¨

arefter kon-

trollera att begin() till end() ¨

ar i stigande ordning. Alternativt g¨

or du en medlems-

funktion som returnerar true om den ¨

ar sorterad. Nackdelen med det tillv¨

agag˚

angs-

s¨

attet ¨

ar att den medlemsfunktionen inte ¨

ar meningsfull annat ¨

an i test-h¨

anseende.

Formell beskrivning av en g˚

angbar metod finner du i algoritm 1.

3. Skriv f¨

oljande sortering. Argumenten ¨

ar en array av heltal.

c o n s t i n t s o r t e d& s o r t ( c o n s t i n t ∗ b e g i n , c o n s t i n t ∗ end ) {

i f

( b e g i n == end ) r e t u r n i n t s o r t e d ( ) ;

i f

( b e g i n == end −1 ) r e t u r n i n t s o r t e d ( ∗ b e g i n , 1 ) ;

p t r d i f f t

h a l f = ( end−b e g i n ) / 2 ; // p o i n t e r

d i f f t y p e

i n t ∗ mid = b e g i n + h a l f ;
r e t u r n s o r t ( b e g i n , mid ) . merge ( s o r t ( mid , end ) ) ;

}

V¨

alj en av tv˚

a f¨

oljande uppgifter:

• Implementera en selection sort. G¨or en tidsm¨atning p˚

a hur l˚

ang tid de b˚

ada

metoderna tar att sortera 400000 rand() element. K¨

or n˚

agra g˚

anger s˚

a din tid-

tagning blir tillf¨

orlitlig. Se upp s˚

a att du inte sorterar redan sorterade element.

Det finns ¨

aven en metod sort i standardbiblioteket, header ¡algorithm¿. Kon-

trollera hur l˚

ang tid den tar p˚

a sig. Standard sort anv¨

ander troligtvis en metod

intro-sort som ¨

ar en variant p˚

a quick sort, och b¨

or vara n˚

agot snabbare.

3 (4)

• Beskriv utf¨orligt hur metoden sort fungerar.

5

Examination

Du ska l¨

amna in header och implementation f¨

or varje uppgift, tillsammand med ett

dokument som besvarar fr˚

agorna i texten. Filerna zippas i ett arkiv och l¨

amnas in p˚

a

kurswebbplatsen. Anv¨

and inte icke-standardformat som zipx och liknande.

6

Algoritmer

Algorithm 1 Avg¨

or om A ¨

ar sorterad

Input: A inneh˚

aller numeriska v¨

arden

Output: Filen A ¨

ar sorterad

a ← A.next()
while A.hasN ext() do

b ← A.next()
if a > b then

return false

end if
a ← b

end while
return true

Algorithm 2 Merge med tv˚

a filer

Input: A och B ¨

ar sorterade enligt algoritm 1

Output: C inneh˚

aller samtliga v¨

arden fr˚

an A och B i sorterad ordning

while A.hasN ext() And B.hasN ext() do

Avg¨

or vilket v¨

arde som ska skrivas till C

a ← A.next()
b ← B.next()

if a < b then

Skriv a till C
a ← A.next()

else

Skriv b till C
b ← B.next()

end if

end while

A eller B ¨

ar slut, skriv klart b˚

ada

while A.hasN ext() do

Skriv A.next() till C

end while
while B.hasN ext() do

Skriv B.next() till C

end while

4 (4)