Containers, templates og standard algoritmer i C++

Tags:    c++
<< < 123 > >>
Skrevet af Bruger #5688 @ 10.01.2005

Introduktion



Denne artikel omhandler containers, forstået som de template-klasser der er at finde i C++'s STL -- Standard Template Library, der er en del af C++-standarden. Containers er, som navnet antyder, klasser der kan indeholde andre klasser (eller objekter). En given container kan indeholde en hvilken som helst type af objekt (men hvert specifikt containerobjekt kan kun indeholde én type objekter). Du kan f.eks. ikke tilføje en string til en container der indeholder doubles.

Oprindeligt var det meningen at denne artikel udelukkende skulle omhandle brugen af containers, men snart blev det tydeligt at et sådan emne ikke kunne stå alene. Derfor gennemgår jeg først grundlæggende templates, den C++ feature der tillader eksistensen af containers.

Denne artikel vil også gennemgå en række af STL's indbyggede algoritmer, idet de gør containers langt mere praktiske, og tydeligt illustrerer hvor elegant STL er opbygget.

Det forudsættes at du har en smule erfaring med C++ i forvejen (selve sproget vil ikke blive gennemgået -- dette er ikke en C++-tutorial), men det er ikke nødvendigt med mere end et overfladisk kendskab. Det forventes ligeså at du har en C++-compiler og forstår at bruge den. Denne artikels kodeeksempler er kompileret med GNU g++ 3.3.4 på en GNU/Linux maskine (hvis du bruger Windows kan MingW og Dev-C++ hentes gratis), men bør fungere i enhver ISO C++ compliant compiler.

Desværre er jeg ude af stand til at dække disse emner hundrede procent, idet de er alt for komplekse. Denne artikel er allerede meget stor, så har jeg været nødt til at undlade et par emner der ellers er af forholdsvist stor betydning. Denne artikel er således ikke den definitive guide til brug af templates (langtfra), og kan derfor ikke erstatte en god bog. Alligevel håber jeg at den vil være interessant, og være med til at demonstrere nogle af C++'s mest fascinerende kvaliteter.

Grundlæggende Templates



Jeg vil ikke komme ind på de mere raffinerede template-teknikker, men jeg vil forsøge at give et billede af hvordan de fungerer.
Templates er grundlæggende funktioner eller klasser, hvor visse typer ikke er kendte før de bliver instantieret -- en slags skabelon, hvor man kan sætte vilkårlige datatyper ind, når der er brug for dem. Kode siger mere end tusinde ord:

Fold kodeboks ind/udKode 


Det spændende i dette program er add()-funktionen. Via template<typer> syntaksen specificerer vi hvilke "ubekendte" typer vi benytter i funktionen. Derefter kan vi i vores efterfølgende funktionsdefinition bruge T som en almindelig type. Vi skriver typename T for at specificere at der her er tale om et typenavn, og ikke en specifik instans af en variabel. Vi kunne også have brugt class, i stedet for typename, hvilket nok er mere normalt i dette tilfælde. Vi specificerer både T som returtypen, og som værdien for de to parametre (add() tager to referencer som argumenter af performancehensyn). De reelle typer der benyttes i funktionen, bliver ikke specificeret før funktionen benyttes -- den såkaldte templateinstantiering ("instantiering er når template-typerne, i dette tilfælde T, erstattes med den virkelige type"). Når funktionen instantieres, sættes de relevante typenavne ind i stedet for T, og der checkes om de operatorer og funktioner vi kalder på dem er definerede. Eftersom både int, double og string har defineret +-operatoren, instantieres funktionen uden fejl. Hvis vi havde forsøgt at bruge en type der ikke kan lægges sammen med en anden type, f.eks. istream, eller en type vi selv havde defineret, ville compileren have rapporteret en fejl under instantieringen. Funktionen instantieres ved at specificere typenavnene i vinkelparanteser efter navnet på templaten (f.eks. add<int>). Hvis vi ønskede at lægge to forskellige typer sammen, kunne vi have defineret funktionen således:

En template kan acceptere enhver type der er "passende." Passende er defineret som både "understøtter alle funktioner der benyttes i templaten," og "gør det på denne måde." Som vi senere vil se, findes der i C++ template-funktioner, algoritmer, der forventer at deres parametre opfører sig på en ganske specifik måde. Selvom man kunne definere sin egen type, der understøtter alle de operatorer der bruges i algoritmerne, vil de ikke nødvendigvis virke, med mindre ens type opfører sig som algoritmerne forventer. Hvilke krav de enkelte algoritmer stiller, vil blive beskrevet senere.

Fold kodeboks ind/udKode 


Hvilke navne man giver de uspecificerede templatetyper er ligegyldigt, men personligt finder jeg det lettest at læse hvis man bruger enkeltstående store bogstaver (majuskler).
Man behøver ikke at præcisere hvilke typer funktionen skal instantieres med, hvis compileren kan regne det ud baseret på hvilke parametre funktionen bliver givet. F.eks. kunne vi have skrevet linjen hvor to strings lægges sammen, således:

Fold kodeboks ind/udKode 


Template specialization er en teknik, hvor man får en template til at ændre opførsel, afhængigt af hvilke typer den bliver instantieret med. Specializations skal komme efter den almene deklaration. Den reviderede udgave af Fig. 1.0:

Fold kodeboks ind/udKode 


Template specialization bør aldrig benyttes til at ændre en funktion radikalt, sådan som det gøres her. Det er ualmindeligt dårlig programmeringspraksis. I stedet bør template specialization benyttes til at optimere en template, hvis man tilfældigvis kender til nogle ting vedrørende nogle specifikke typer. Det kan være at en given type ikke har operator+ defineret, men at der til gengæld findes en smart add_clumsy_type()-funktion der kan gøre det. I sådanne tilfælde er template specialization meget praktisk.

Templates kan også bruges til klasser -- her et mindre eksempel:

Fold kodeboks ind/udKode 


Bemærk at hver instantiering af en template-klasse med nye typer, er en ny type for sig selv. En kv_pair<string,int> kan derfor ikke benyttes som en kv_pair<string,string>, og omvendt.

Template-klasser kan også nedarves, men templaten skal instantieres (via vinkelparanteser) når det gøres. Eksempelvis:

Fold kodeboks ind/udKode 


Bemærk hvor mange steder typen for foo<C> specificeres. At glemme de mange typespecifikationer er en typisk begynderfejl.

Templates er en af de mest spændende features i C++. Det er et featuresæt der har løftet C++ fra "a better C" til et helt unikt og meget kraftfuldt sprog. Det er utroligt vigtigt at beherske templates hvis man vil skrive større programmer i C++, om ikke andet, så for at forstå hvordan containere fungerer.

Det sidste jeg kort vil beskrive er default template parametre. De virker ligesom default parameters i funktioner, så koden burde være selvdokumenterende:

Fold kodeboks ind/udKode 


Default template parameters er nyttige til at specificere avanceret template-opførsel, f.eks. hvordan den givne template allokerer hukommelse. Standard kunne så være en traditionel allocator.

Hvad Kan Containers Bruges Til?



Som jeg skrev i introduktionen, kan en container indeholde objekter af en hvilken som helst type (denne type skal dog defineres når containeren oprettes). På dette tidspunkt burde det være indlysende at containers er template-klasser. Containers kan delvist ses som arrays, med den forskel, at mens arrays bare er en sekvens af bytes, så er containers fuldt ud kvalificerede højniveauobjekter, hvilket betyder at de er både sikrere og understøtter flere operationer. Containers har simpelthen langt flere funktioner end arrays. Et array kan i sig selv ikke noget, men selv de mest sparsomme containere i C++'s STL har avancerede funktioner til at fjerne objekter, tilføje, søge, iterere igennem alle objekter i containeren og lignende. En anden, og måske den vigtigste, fordel ved containere frem for arrays, er at (visse) containere dynamisk kan ændre størrelse for at akkommodere de objekter der bliver tilføjet. I modsætning til arrays behøver containere ikke have en statisk størrelse der bliver defineret ved oprettelsen, men kan derimod frit ændre størrelse under programmets kørsel. Dette sker ved at definere operator=, og lignende funktioner, så de udfører range checking. Containers har også praktiske egenskaber der gør det let at "iterere" (gennemgå) gennem alle objekterne i containeren -- ikke som med arrays, hvor man skal holde styr på hvor stort arrayet er, for at undgå at komme til at læse, eller skrive, i ikke-allokeret hukommelse.




<< < 123 > >>

Hvad synes du om denne artikel? Giv din mening til kende ved at stemme via pilene til venstre og/eller lægge en kommentar herunder.

Del også gerne artiklen med dine Facebook venner:  

Kommentarer (10)

User
Bruger #4803 @ 10.01.05 22:48
meget lang.. eventuelt split den op i 2? 3? :S
User
Bruger #5688 @ 10.01.05 22:54
Den kan ikke splittes op uden at forstyrre sammenhængen. Det er et meget komplekst emne.
User
Bruger #6649 @ 10.01.05 22:57
En rigtig god artikel... den har fortjent en femmer
User
Bruger #479 @ 11.01.05 16:32
Flot artikel... du får en femmer herfra.

Jeg håber du senere får tid til at skrive lidt mere om templates.
User
Bruger #5779 @ 12.01.05 14:45
god artikel
User
Bruger #5688 @ 16.01.05 21:30
Efterfølgeren bliver ikke nær så stor, men den skal nok komme engang.
User
Bruger #3470 @ 23.01.05 15:00
God artikel, lærte godt nok ikke noget nyt, men håber at andre gjorde ;-)
Selvom jeg ikke lærte noget, så du får skam stadig 5 :-P

Jeg vil opfordre alle andre til at læse meget mere om dette emne, for der er rent faktisk stor ydelsesmæssig forskel på de forskellige containers. Det blev der ikke nævnt særligt meget om i denne artikel, så jeg synes at jeg burde fremhæve det her.
User
Bruger #601 @ 19.03.05 08:48

Dejligt med en artikel som bevæger sig ud over det rene begynder niveau. Eneste minus - som forfatteren ikke kan gøre noget ved - er at man ikke kan hente artiklen i fx. PDF format ;-).

Forsæt endelig det gode arbejde.
User
Bruger #13085 @ 09.01.08 08:40
Jeg er ny bruger

Udemærket artikel.

Jeg har kun skimmet den, da jeg har nogle ret velskrevne, uddybende refs til STL/templates på engelsk. Jeg vil give artiklen 4. Fordi: Indholdet er solidt, men strukturen er lidt forvirrende, og den er måske mere forvirrende for folk, der intet kender til emnet.

Jeg vil som nogle andre skrev ovenfor også klart mene, at det ville være fedt, hvis forfatteren skrev videre på artiklen. MEN Det BEHØVER vel ikke egentlig ikke gøres af den samme person? Måske kunne NOGEN føre artiklen videre, hvis forfatteren ikke har tid. Rigtig "open source"-stil!

Jeg har surfet lidt rundt her på siden og synes, at der mangler en rigtig "børnehave"-C++ tutorial.

Noget kunne jo "for skæg" sende et "manuskript" ind til censur og se, hvad "redaktøren" siger?

Personligt ville jeg sagtens kunne skrive en "lille" tekst, som indtroducerer sproget C/C++ på en MEGET, MEGET pædagogisk måde, så de sidste 10%, der er bange for programmering kan komme med.

Idé?

User
Bruger #8985 @ 20.04.09 23:59
Nicolai Lystner Fersner: Hvad er forskellen på ydelse mellem de forskellige containere? Hvilke containere snakker vi om? God kommentar, lærte godt nok ikke noget nyt, og tvivler andre gjorde.

Stefan E. Nielsen: Du kan jo læse lidt af artiklen, holde pause, arbejde med det, du har lært, og så læse videre. På den måde vil artiklen ikke virke så lang.

Christian Dyrnesli: Hvad holder dig tilbage? Det virker som en god idé, synes jeg.

Troels Henriksen: God artikel! Jeg har arbejdet med templates før, men du har vist mig nogle metoder at anvende dem på, jeg end ikke havde overvejet.
Du skal være logget ind for at skrive en kommentar.
t