Programerring

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:

// Fig. 1.0.
#include
#include

using namespace std;

template
T add(const T& first, const T& second)
{
return first + second;
}

int main(int argc, char** argv)
{
int ix = 5, iy = 8;
double dx = 4.54, dy = 89.333;
string sx = "Første.", sy = "Anden.";

cout (ix, iy)
cout (dx, dy)
cout (sx, sy)
return 0;
}


Det spændende i dette program er add()-funktionen. Via template 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). 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.

// Fig. 1.1.
template
R add(const R& first, const T& second)
{
return first + second;
}


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:

// Fig. 1.2.
cout


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:

// Fig. 1.3.
#include
#include

using namespace std;

template
R add(const R& first, const T& second)
{
return first + second;
}

template<>
string add (const string& first, const string& second)
{
cout
return "Hej du gamle!";
}

int main(int argc, char** argv)
{
int ix = 5, iy = 8;
double dx = 4.54, dy = 89.333;
string sx = "Første.", sy = "Anden.";

cout (ix, iy)
cout (dx, dy)
cout
return 0;
}


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:

// Fig. 1.4.
#include
#include

using namespace std;

template
class kv_pair
{
public:
kv_pair(const K& n_key, const V& n_value);

K key();
V value();

private:
K m_key;
V m_value;
};

template
kv_pair::kv_pair(const K& n_key, const V& n_value)
{
m_key = n_key;
m_value = n_value;
}

template
K kv_pair::key()
{
return m_key;
}

template
V kv_pair::value()
{
return m_value;
}


int main(int argc, char** argv)
{
kv_pair one("Bjarnes alder", 15);
kv_pair another("Peters alder", "otteogtredive");

cout
cout

return 0;
}


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

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

// Fig. 1.5.
#include
#include

using namespace std;

template
class foo
{
public:
foo(const C& n_obj)
{
m_obj = n_obj;
}

void foo_print()
{
cout
}

protected:
C m_obj;
};

template
class bar : public foo
{
public:
bar(const K& n_k, const C& n_c):
foo(n_c)
{
m_k = n_k;
}

void bar_print()
{
foo_print();
cout
}

protected:
K m_k;
};

int main(int argc, char** argv)
{
bar my_object(666, "C# er en syntaksfejl. :-)");
my_object.bar_print();
return 0;
}


Bemærk hvor mange steder typen for foo 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:

// Fig. 1.5.
#include
#include

using namespace std;

template
class default_tester
{
public:
default_tester(C n_obj = C())
{
m_obj = n_obj;
}

void print()
{
cout
}
private:
C m_obj;
};

int main(int argc, char** argv)
{
default_tester<> t("Templates er godt.");
default_tester i(17);
t.print();
i.print();
return 0;
}


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.


Lad Os Komme I Gang


Teori er godt, men man lærer nu også ved at læse kode. Her er et simpelt program der benytter sig af en speciel container fra STL -- en vector:

// Fig. 2.0.
#include
#include

using namespace std;
// Ellers skulle vi skrive std::vector -- alle STL's containers er i std-namespacet.

int main(int argc, char* argv[]) {
vector Vec;

for (int p = 1; p
{
Vec.push_back(argv[p]);
// Placér en kopi af argv[p] i slutningen af Vec.
}
cout

vector::iterator it = Vec.begin();
// Initialisering af iteratoren til begyndelsen af containeren.

while ( it != Vec.end() )
{
std::cout
it++;
}

std::cout
return 0;
}


(Dette program løser ikke noget problem der ikke kunne klares uden brug af containere, men bær over med mig for eksemplets skyld).

Vi bruger containeren std::vector, en container der er optimeret til hurtig lineær tilføjelse af elementer. En vectors ydelse er meget ringe hvis man forsøger at benytte den til andet end at tilføje elementer i slutningen af den -- på denne måde virker vector meget som den container der minder mest om et traditionelt array, og hvis man bare har brug for en simpel container, er det også denne jeg vil anbefale.

Det første vi gør i vor main()-funktion er at oprette et vector-objekt, og specificere hvilken type objekt det vil indeholde. Dette skal gøres ved oprettelsen, og typen specificeres i vinkel-parenteser efter containerens typenavn, som det ses i koden. Dette er altså templateinstantieringen.

Vi gennemgår alle de parametre programmet er kaldt med, og gemmer dem i vores vector. Dette sker gennem medlemsfunktionen push_back(), der tager et argument af den type som den relevante vector indeholder (i dette tilfælde konverteres char* til string), og tilføjer (en kopi af) argumentet til slutningen af vectoren. Det skal retfærdigvis siges at en vector har en maksimal størrelse, men denne afhænger af den relevante C++-implementation, og er generelt så høj at den ikke er værd at bekymre sig om. Du vil sandsynligvis løbe tør for virtuel hukommelse før du når at fylde en vector op.

Når vi skal printe indholdet af vor vector benytter vi os af iteratorer, som man passende kan tænke på som en pointer til et givent element i vectoren. Læg især mærke til hvordan vi definerer iteratoren -- vi bruger ikke vores instans af en vector, men derimod selve vector-klassen. Vi tildeler iteratoren værdien der bliver returneret fra Vec.begin(), en funktion der returnerer en iterator til det første element i vectoren. Vi derefererer iteratoren ganske som med en pointer og printer det returnerede element på skærmen, hvorefter vi bruger postincrement-operatoren (++) til at flytte iteratoren til det næste element i vectoren. Vec.end() returnerer en iterator til et punkt efter det sidste element i vectoren, derfor kan vi benytte funktionen til at checke om vores loop skal stoppes, uden at vi mangler at printe det sidste element. Denne itereringsteknik er en af de hyppigst benyttede container-teknikker, idet den både er relativt hurtig, sikker og simpel.

Vær dog opmærksom på at ikke alle containere understøtter denne fremgangsmåde. De har hver deres styrker, hvilket vil blive beskrevet senere.

Iteratorer er grundstenen i STL containers, og dem der gør de forskellige containers til mere end arrays med bounds checking. Det er også især ved iteratorerne at de forskellige containers skiller sig ud.

Iteratorer er den abstraktion der gør generiske algoritmer mulige:


Algoritmer og Containere


Ud over selve containerne, definerer STL også en række praktiske algoritmer til brug i forbindelse med behandling af iteratorer (eller rettere, den data iteratorerne refererer til). Algoritmer opererer ikke, som man skulle tro, på en container -- du kalder altså ikke f.eks. sort(Vec), men derimod sort(Vec.begin(), Vec.end()). Derved kan man nøjes med kun at sortere en mindre del af en container, eller endda sortere almindelige arrays -- pointers kan i næsten alle tilfælde bruges som iteratorer. Jeg vil præsentere brugen af udvalgte algoritmer, og vise en mulig måde de kan implementeres på.

Jeg vil nu demonstrere funktionen sort(). For at forstå kravene en sådan funktion stiller, er det nødvendigt først at forstå at der findes forskellige kategorier af iteratorer, alt efter hvilke funktioner de understøtter (basalt set, hvilken adgang de giver til det underliggende objekt). Kategorierne er:

Input iterator

Denne form for iterator kan flytte til det næste element i containeren (men ikke det forrige), kan få adgang til det underliggende objekt (gennem *-operatoren), follow-pointer-operatoren (->) og er-ikke-lig-med-operatoren (!=). Denne iterator giver også kun read-only adgang til det element der peges på. En iterator der udelukkende har disse operatorer defineret vil skabe compile-errors hvis vi forsøger at bruge andre operatorer. Alle containere i C++'s STL understøtter mindst disse operatorer, hvilket vil sige at alle iteratorer er input-iteratorer. De kan også tilhøre andre iteratorkategorier, forudsat at de opfylder de relevante kategoriers krav, men de er i hvert fald input-iteratorer, idet de opfylder input-iterator-gruppens krav. Hvis man tilknytter en iterator til cin er der tale om en input iterator.

Output iterator

Output-iteratorer er som input-iteratorer, bortset fra at de kun tillader at der skrives til det underliggende objekt, ikke at det læses (f.eks. *it = foo). Derudover er de magen til input-iteratorer. Alle iteratorer i C++'s STL er, ganske som med input-iteratorer, output-iteratorer. En output-iterator ses ofte i forbindelse med fil-output. Du kan skrive til en fil, og du kan rykke fremad i filen, men hvis du kun har åbnet filen til output, kan du naturligvis ikke læse fra den.

Forward Iterator

Disse iteratorer fungerer som input-iteratorer, i den forstand at de kun kan flytte til næste objekt, men til gengæld understøtter de både skrivning og læsning af og til det underliggende element. Som med de to foregående typer, understøtter alle iteratorer i C++'s STL disse krav, og er derfor forward iterators.

Bidirectional Iterator

Birectional iterators skal understøtte alle forward-iterator operatorer, men skal derudover også understøtte at gå til forrige element. Alle containere i STL opfylder kravene til bidirectional iterators.

Random Access Iterator

Denne iterator er den mest kraftfulde i C++'s STL, og kun få containere understøtter den. Basalt set kræver den at man kan udførearitmetik med iteratoren. F.eks. trække to iteratorer fra hinanden -- hvis man f.eks. trækker en iterator der peger på det 3. element fra en iterator der peger på det 8. element, skal man få en iterator der peger på det 5. element. I mange containere ville denne iterator slet ikke give mening, idet der ikke er tale om en lineær container, men snarere en "pøl" af data. Containers der har random access iterators, understøtter også []-operatoren, kendt fra arrays. std::string og std::vector opfylder begge random access iteratorens krav (idet begge containere er lineære repræsentationer af data).

Det virker måske absurd at der findes så primitive iteratorer som input-iterators, idet det jo er svært at se hvorfor nogen iterator skulle være så begrænset, og hvad man overhovedet kan bruge den til. En sådan iterator ville være praktisk, hvis man f.eks. havde en kompleks database, hvor man ikke ville være det i stand til at definere at et objekt kommer "efter" et andet, hvilket vil sige at der bliver byttet om på rækkefølgen af data hver gang man opretter en iterator. I et sådant tilfælde ville en input iterator være praktisk (eller nødvendig), idet man ved at inkrementere den nok gange eventuelt ville læse hele databasen (hvis klassen da havde et system der forhindrer iteratoren i at pege på samme data to gange).

sort() kræver random access adgang via random access iteratorer, og compileren vil melde fejl hvis man forsøger at kalde funktionen med iteratorer der ikke er i denne klasse.

Med denne teori i baghovedet burde det være til at forstå hvordan sort() skal bruges:

// Fig. 3.0.
#include
#include // Indeholder de fleste generiske algoritmer.
#include

using namespace std;

int main()
{
vector intVec;
// Opretter en list på samme måde som med vector.
int temp;
cout

while (cin >> temp) // Mens der er input i cin...
{
intVec.push_back(temp);
}
cout

sort(intVec.begin(), intVec.end()); // Sorterer alle elementer fra begin() til end().
for ( vector::const_iterator it = intVec.begin();
it != intVec.end();
it++ )
cout

cout

return 0;

}


Udover sort() selv, er der intet nyt i dette program. Programmet tager EOF (Ctrl-D på de fleste operativsystemer) for at afbryde inputsekveksen. for-loopet er også mere kompakt end i det forrige eksempel, men princippet er det samme (læg dog mærke til at der benyttes en read-only const_iterator -- denne bør altid benyttes, når man ikke vil ændre på iteratorens underliggende objekt, ganske som med traditionel const).

sort() tager to iteratorer som parametre, der definerer hvilken sekvens af objekter der skal sorteres (praktisk, hvis man ikke ønsker at sortere hele containeren). Eftersom vores vector består afints, har compileren ikke svært ved at sammenligne de respektive elementer, men hvis vi havde en vector der indeholdt klasser der ikke kunne sammenlignes med '

// Fig. 3.1.
sort(Vec.begin(), Vec.end(), compare);


Hvor compare() er en funktion der tager to argumenter af samme type som Vec indeholder, og som returnerer true, hvis det andet argument er "større" (hvad dette betyder i denne sammenhæng, afhænger af programmøren) end det første.

F.eks:

// Fig. 3.2.
bool compare(int x, int y)
{
return x % 2 == 0;
}

/* Kode... */

sort(Vec.begin(), Vec.end(), compare);


Dette vil resultere i at alle de tal der kan deles med 2 (alle runde tal), bliver placeret i starten af vectoren.

Man bør altid bruge denne sort() funktion, frem for qsort(), som C++ har arvet fra C.

En anden generisk algoritme er fill(). Den bruges således:

// Fig. 3.3.
fill(begin, end, value)


Denne algoritme vil tildele alle elementer i intervallet [begin;end[ værdien value.

Man kunne forestille sig fill() være implementeret således:

// Fig. 3.4.
template
void fill(B beg, E end, V value)
{
while (beg != end) *beg++ = value;
}


Bemærk at denne algoritme kan benyttes både med pointers og rigtige iteratorer. Betragt:

// Fig. 3.5.
#include
#include
#include

using namespace std;

template
void fill(B beg, E end, V value)
{
while (beg != end) *beg++ = value;
}

template
void print_container(B beg, E end, P padding)
{
while (beg != end) cout
}

int main(int argc, char** argv)
{
int array[] = { 1, 2, 3, 4, 5, 6, 7 };
vector lang_vec;

lang_vec.push_back("Java");
lang_vec.push_back("C");
lang_vec.push_back("Python");
lang_vec.push_back("ECMAScript");
lang_vec.push_back("Pascal");
lang_vec.push_back("C#");

print_container(array, array + 7, "\
");
print_container(lang_vec.begin(), lang_vec.end(), "\
");

cout

fill(array, array + 7, 1337);
fill(lang_vec.begin(), lang_vec.end(), "C++");

cout

print_container(array, array + 7, "\
");
print_container(lang_vec.begin(), lang_vec.end(), "\
");
}


Ganske elegant. Selvom dette program er simpelt, demonstrerer det alligevel de grundlæggende ideer bag generiske algoritmer.

Hvilke iteratorer kræver de to funktioner så? Det er tydeligt at fill() ikke kan klare sig med read-only iteratorer, men eftersom de eneste funktioner der bliver benyttet er operator*, operator= og postfix operator++ burde en output iterator være acceptabel. print_container kan klare sig med en input iterator -- så simpel er funktionen.


Prædikater og Funktionsobjekter


Ovenfor nævnte jeg kort hvorledes man kunne specificere sin egen sammenligningsfunktion i sort(). Jeg brugte der en funktionspointer, men det er langt mere normalt at bruge funktionsobjekter (også kendt som functors). Disse er objekter hvor operator() er defineret:

// Fig. 4.0.
class numfinder
{
public:
numfinder(int x, int y):
m_x(x), m_y(y)
{}

bool operator()(int i)
{
if ( i == m_x || i == m_y )
return true;
return false;
}

private:
int m_x;
int m_y;
};


For at vise hvordan disse fungerer, ser vi på en logisk implementation af find() og find_if(), hvor find_if() bruger et prædikat:

// Fig. 4.1.
#include

using namespace std;

class numfinder
{
public:
numfinder(int x, int y):
m_x(x), m_y(y)
{}

bool operator()(int i)
{
if ( i == m_x || i == m_y )
return true;
return false;
}

private:
int m_x;
int m_y;
};

template
B find(B begin, E end, V value)
{
while (begin != end)
if (*begin++ == value)
return begin;
return end;
}

template
B find_if(B begin, E end, P predicate)
{
while (begin != end)
if (predicate(*begin++))
return begin;
return end;
}

int main(int argc, char** argv)
{
int numarray[] = { 1, 2, 3, 4, 5, 6, 7, 888, 666, 1337, 1987, 3, 2, 1 };

cout



return 0;
}


find() og find_if() returnerer den sidste iterator i sekvensen, hvis den ønskede værdi ikke kan findes, eller iteratoren der refererer til den ønskede værdi i containeren, hvis den kan findes. find_if() bruger blot et simpelt prædikat til dette. Det trick jeg bruger for at finde hvilken plads i sekvensen resultatet har, er noget jeg kan gøre fordi jeg i dette eksempel bruger pointers og arrays. Pointers er effektivt det samme som random-access iterators. Dette eksempel er interessant, fordi det viser at man, uden at udvide selve algoritmen, kan få en find() til at lede efter to forskellige værdier. I princippet er der ingen grænser for hvor kompliceret logik der kan indbygges i et prædikat. Se f.eks. dette, der leder efter to på hinanden følgende værdier:

// Fig. 4.2.
template
class numfinder_seq
{
public:
numfinder_seq(C x, C y):
m_x(x), m_y(y)
{}

bool operator()(C val)
{
if ( m_last == m_x && val == m_y )
return true;
m_last = val;
return false;
}

private:
C m_last;
C m_x;
C m_y;
};


Der er adskillige fordele ved at bruge function objects frem for function pointers. For det første er det trivielt for compileren at inline funktionskaldende, hvorved man sparer den overhead der er associeret med ethvert funktionskald, og ydermere kan funktionen gemme information om sig selv imellem kaldende, uden brug af statisk data.

max_element() og min_element returnerer hver en iterator der refererer til hhv. det største og det mindste element i sekvensen. Disse to algoritmer kunne implementeres, og bruges, således:

// Fig. 4.3.
#include
#include

using namespace std;

template
B max_element(B begin, E end)
{
B* cur_max = begin;

while (++begin != end)
if (*cur_max
cur_max = &begin;
return *cur_max;
}

template
B min_element(B begin, E end)
{
B* cur_min = begin;

while (++begin != end)
if (*cur_min
cur_min = &begin;
return *cur_min;
}

int main()
{
vector num_vec;
num_vec.push_back(5);
num_vec.push_back(3);
num_vec.push_back(1337);
num_vec.push_back(66*72);
num_vec.push_back(2);
num_vec.push_back(3);

cout
cout

return 0;
}


Jeg bruger en pointer til en iterator, for jeg kan ikke være sikker på at en iterator er et letvægtsobjekt, så jeg vil helst undgå dyr initialisering. Det kan også lade sig gøre at lave en max_element_if(), hvor et binært prædikat (en funktion der tager to parametre) benyttes:

// Fig. 4.4.
template
B max_element_if(B begin, E end, P pred = P())
{
B* cur_max = begin;

while (++begin != end)
if (pred(*cur_max, *begin))
cur_max = &begin;
return *cur_max;
}


copy() er en af de mest fleksible algoritmer i STL. Dens mest åbenlyse brug, er kopiering af en sekvens til en ny container:

// Fig. 4.5.
#include
#include
#include
#include

using namespace std;

int main(int argc, char** argv)
{
vector src_vec(5); // vector med 5 elementer.
src_vec[0] = "Chadk";
src_vec[1] = "Frnz";
src_vec[2] = "HyBreeD";
src_vec[3] = "KasperTSW";
src_vec[4] = "Athas";

vector dest_vec(5); // vector med 5 elementer.

copy(src_vec.begin(), src_vec.end(), dest_vec.begin());
src_vec.clear();

for(vector::const_iterator it = dest_vec.begin();
it != dest_vec.end();
it++)
cout

return 0;
}


copy() er en funktion man skal passe på med. Her ses det at jeg opretter to vector-objekter, hver med plads til fem elementer, for derefter at tildele en værdi til elementerne i src_vec. copy() fungerer ved at hvert element i den angivne sekvens (her src_vec.begin(), src_vec.end()) tildeles til destinationen (her dest_vec.begin()), som inkrementeres efter hver værditildeling, med det resultat at iteratoren bevæger sig til det næste element i containeren. Det er her man skal passe på, for copy() kender ikke til destinationens størrelse, og vil uden videre lade destinationsiteratoren vandre ind i hukommelse uden for containeren. Derfor specificerer jeg eksplicit at dest_vec har fem elementer -- så er jeg sikker på at den ikke overflower. Dette holder jo naturligvis ikke, derfor findes der en wrapper-klasse, der fungerer som en iterator, men som kalder push_back på den relevante container, når der tildeles til iteratoren. Deklarationen af dest_vec og kaldet af copy() kan altså erstattes med:

// Fig. 4.6.
vector dest_vec;
copy(src_vec.begin(), src_vec.end(), back_inserter(dest_vec));


Ligeledes findes der front_inserter, der, som navnet antyder, bruger push_front(), frem for push_back().

Jeg bruger i Fig. 4.5 en klassisk for-konstruktion til at printe indholdet af containeren... det virker, men det er ikke synderligt elegant. Her kan copy() og opfindsom brug af wrapper-iteratorer også hjælpe til. Den iteratorwrapper vi her skal bruge hedder ostream_iterator, der er at finde i
// Fig. 4.7.
copy(dest_vec.begin(), dest_vec.end(), ostream_iterator(cout, "\
"));


Her vises en revideret udgave af programmet i Fig. 4.5, der har de to forbedringer jeg nævnte her (og som ikke længere behøver at specificere størrelsen på sine vector-objekter eksplicit):

// Fig. 4.8.
#include
#include
#include
#include
#include

using namespace std;

int main(int argc, char** argv)
{
vector src_vec;
src_vec.push_back("Chadk");
src_vec.push_back("Frnz");
src_vec.push_back("HyBreeD");
src_vec.push_back("KasperTSW");
src_vec.push_back("Athas");

vector dest_vec;

copy(src_vec.begin(), src_vec.end(), back_inserter(dest_vec));
src_vec.clear();

copy(dest_vec.begin(), dest_vec.end(), ostream_iterator(cout, "\
"));

return 0;
}


ostream_iterator skal fungere som en iteratoremulator, men i princippet er der jo ikke meget iterator over den. Der er intet element at rykke videre til, og det ville ikke give mening at rykke tilbage. Alligevel er ostream_iterator en output iterator. operator= for et ostream_iterator objekt er som at kalde operator

back_inserters og ostream_iterators er abstraktioner der kun er mulige pga. C++'s elegante template, stream og iterator-design. Som det sås ovenfor, ved Fig. 4.5 , skal man dog også passe på, for der er grænser for hvor meget de individuelle algoritmer ved om de objekter de behandler, hvilket er årsagen til at wrappere som ostream_iterator og back_inserter eksisterer. Som algoritmeprogrammør kan det dog være nyttigt at kende til visse detaljer omkring iteratorerne, f.eks. hvilke typer de refererer til, og dette klares via iterator_traits-klassen. iterator_traits er en template-klasse indeholdende typedef's. Idéen er at man, når man laver en ny iterator, laver en template specialization, så iterator_traits også fungerer for denne. Via template specialization fungerer klassen også med pointers. Her er definitionen:

// Fig. 4.9.
template
struct iterator_traits
{
typedef typename Iter::iterator_category iterator_category;
typedef typename Iter::value_type value_type;
typedef typename Iter::difference_type difference_type;
typedef typename Iter::pointer pointer;
typedef typename Iter::reference reference;
};

template
struct iterator_traits
{
typedef std::random_access_iterator_tag iterator_category;
typedef T value_type;
typedef ptrdiff_t difference_type;
typedef T* pointer;
typedef T& reference;
};


Hvis en iterator er en klasse i sig selv, vil den, hvis den har defineret de rigtige typer i sin deklaration, automatisk virke i iterator_traits. Hvis ikke, kan man lave template specialization, såsom det kan ses at det er gjort med pointers. random_access_iterator_tag er en "tom" klasse, der udelukkende er beregnet til at blive brugt til template specialization og lignende, og den indikerer at iteratoren er en random access iterator. Ligeså findes der klasserne input_iterator_tag, output_iterator_tag, forward_iterator_tag og bidirectional_iterator_tag. ptrdiff_t er den type man får når man trækker to pointere fra hinanden. Som regel er dette en int.

// Fig. 4.10.
#include
#include
#include
#include
#include

using namespace std;

template
vector::value_type> mkvector(B begin, E end)
{
vector::value_type> ret;

copy(begin, end, back_inserter(ret));

return ret;
}

int main(int argc, char** argv)
{
list src_vec;
typedef list::value_type src_type;

src_vec.push_back(5);
src_vec.push_back(4);

vector dest_vec = mkvector(src_vec.begin(), src_vec.end());

copy(dest_vec.begin(), dest_vec.end(), ostream_iterator(cout, "\
"));

return 0;
}


I Fig. 4.10 er der vist en funktion der kan producere vector-objekter fra input iteratorer. Den type en given vector skal indeholde skal defineres ved templateinstantiering, ved compile-time, så her bruger jeg iterator_traits til at få information om den type iteratorerne refererer til. Jeg bruger eksplicit typename, for at give compileren et hint om at jeg mener en type, og ikke et udtryk. typename er nødvendigt når templateparametre benyttes på en så relativt kompleks måde. Der vises hvordan en container af typen list kan omdannes til en vector, men funktionen burde fungere med enhver gyldig sekvens. list er en container jeg ikke har nævnt før, og den vil blive beskrevet i næste sektion.


Flere Containere


Indtil videre har jeg kun kort beskrevet vector, men STL har et stort antal containers, der hver især er velegnede til visse former for opgaver. Som jeg tidligere sagde, er vector velegnet til indsættelse, og fjernelse, af elementer i slutningen af containeren, samtidigt med at der leveres random access iterators. vector kan dog ikke så meget mere, og ydelsen er utroligt ringe hvis man vil indsætte elementer i midten af den. Der er for mange containers i C++ til at jeg kan beskrive dem alle, men jeg vil forsøge at dække et nyttigt subset.

Der er en række der er understøttet af (næsten) alle containere. Disse, og deres virkning for containeren c, er:

c.begin() -- returnerer en iterator til det første element i c.
c.end() -- returnerer en iterator til det sidste element i c.
c.size() -- returnerer antallet af elementer i c.
c.empty() -- returnerer true hvis c ikke har nogen elementer, ellers false.
c.clear() -- sletter alle elementer i c. Returnerer void.

list

list-typen er STL's pendant til traditionelle linkede lister. Sædvanligvis er list også selv implementeret via en linked list. En list's helt store styrke er dens evne til at indsætte elementer på et vilkårligt sted i containeren, en handling der kan implementeres som en O(1)-algoritme. list har kun bidirectional operators, så subscripting-operatoren ([]) virker ikke -- den kunne nok godt implementeres for en list, men algoritmen ville være O(n) eller værre. Dette betyder også at en list ikke kan sorteres via den sort()-funktion der er defineret i , derimod har en list sin egen sort()-metode:

// Fig. 5.0.
#include
#include
#include
#include
#include

using namespace std;

int main()
{
list grocery_list;

grocery_list.push_back("Orange");
grocery_list.push_back("Apple");
grocery_list.push_back("Banana");
grocery_list.push_back("Pear");
grocery_list.push_back("Pineapple");
grocery_list.push_back("Cucumber");

grocery_list.sort();

copy(grocery_list.begin(), grocery_list.end(), ostream_iterator(cout, "\
"));

return 0;
}


list::sort() kan naturligvis også tage et prædikat som parameter, ganske som den almindelige sort(). list har også en medlemsfunktion ved navn splice. Denne kan bruges til at splejse lister sammen, og er, takket være list's typiske implementation som en linked list, ret hurtig. list::splice() kan bruges på tre forskellige måder. Alle funktionerne returnerer void, og gør alle iteratorer til den indsplejsede liste ugyldige:

// Fig. 5.1.
l.splice(it, l2);


Denne brugsmetode indsætter alle elementer fra listen l2 ind i listen l, før det punkt iteratoren it peger på. Det siger sig selv at it skal være en gyldig iterator til l. Du kan bruge l.end() som it hvis du bare vil tilføje elementerne fra l2 i slutningen af l. Bemærk at alle elementerne i l2 bliver flyttet over i l, og altså fjernet fra l2.

// Fig. 5.2.
l.splice(it, l2, it2);


Dette fungerer som i Fig. 5.1, med den undtagelse at det eneste element der flyttes fra l2 til l, er det it2 refererer til. it2 skal være en gyldig iterator for l2.

// Fig. 5.3.
l.splice(it, l2, b, e);


Dette fungerer som i Fig. 5.3, med den undtagelse at alle elementer i intervallet [b;e] flyttes til l. Disse skal naturligvis være gyldige iteratorer til elementer i l2.

pair

pair er en simpel container der er at finde i . Den tillader en at gruppere to objekter sammen i ét objekt. Simpelt, men nyttigt. pair holder to objekter, der ikke nødvendigvis er af samme type, og disse kan tilgås via pairs first og second members. Der findes også en make_pair() funktion der let kan generere pair-objekter. Her er et fyldestgørende eksempel på hvordan pair kan bruges, og hvilke fordele klassens brug har:

// Fig. 5.4.
#include
#include
#include
#include
#include

using namespace std;

bool sort_elem(const pair& prim, const pair& sec)
{
if ( prim.second > sec.second )
return true;
return false;
}

int main(int argc, char** argv)
{
if (argc % 2 == 0 || argc
{
cerr
return 1;
}

vector > elem_vec;

for (int p = 1; p
elem_vec.push_back(make_pair(argv[p], atoi(argv[p+1])));

for(vector >::const_iterator it = elem_vec.begin();
it != elem_vec.end();
it++)
cout << it->first << " " << it->second

cout

sort(elem_vec.begin(), elem_vec.end(), &sort_elem);

for(vector >::const_iterator it = elem_vec.begin();
it != elem_vec.end();
it++)
cout << it->first << " " << it->second

return 0;
}


Dette program tager en række parametre, mindst 2 og et lige antal, indeler disse parametre i "navn-værdi"-par, indsætter det i en vector (bemærk at der er mellemrum imellem vinkelparanteserne -- dette er nødvendigt, for at compileren ikke fortolker det som . C++'s standard library rummer ikke en standardfunktion der kan sammenligne to pair-objekter, så jeg definerer min egen sort_elem()-funktion, der så benyttes som et funktionspointerparameter til sort(). Dette bevirker at elem_vec bliver sorteret efter faldende værdi for de enkelte elementer. Til sidst udskrives indholdet af elem_vec endnu engang. En typisk session med programmet kunne se således ud:

// Fig. 5.5.
~/code $ ./t10 Bjarne 1337 Athas 666 C++ 4000 Java 2 BASIC -1 Agurk 10
Bjarne 1337
Athas 666
C++ 4000
Java 2
BASIC -1
Agurk 10
vector is being sorted...
C++ 4000
Bjarne 1337
Athas 666
Agurk 10
Java 2
BASIC -1


Programmet er ikke helt robust nok til andet end tutorial-brug, idet der ikke er fejlrapportering hvis et givent parameter ikke kan konverteres til et tal (i så fald returnerer atoi 0).

map

map er en meget nyttig container, der er at finde i . Grundlæggende er det en associativ container, hvor man kan associere et objekt af en given type (key-typen), men et andet objekt af en evt. anden type (value-typen). I Fig. 5.4 kunne man have brugt en map, frem for en vector. map sorterer automatisk elementerne (ved at sammenligne deres key-værdier), så derfor skal en sammenligningsfunktion være tilgængelig for den type der benyttes som key-type. Denne er naturligvis automatisk defineret for alle indbyggede typer, men gør det nødvendigt at specificere et prædikat der kan foretage sammenligningen hvis der benyttes brugerdefinerede typer, for hvilke sammenligningsoperatorerne ikke er definerede.

// Fig. 5.6.
map m(cmp);


Denne linje definerer m som et objekt af typen map, med K som key-type, V som value-type, og et prædikat, cmp, af typen P. Hvis sammenligningsoperatorerne er definerede for typen K kan de prædikatrelaterede parametre udelades. Elementer indsættes i et map via funktionen map::insert(), der tager et parameter af typen pair, hvor K og V er af samme type som de relevante key- og value-værdier i det map der indsættes i. make_pair kan passende bruges til at generere disse pair-objekter:

// Fig. 5.7.
m.insert(make_pair(keyobj,valobj));


Her er keyobj og valobj to objekter af typerne hhv. K og V for map-objektet m. Bemærk at hvis m allerede indeholder et element hvis key-værdi er den samme som keyobj vil et nyt element ikke blive indsat. Der kan altså kun være én instans af en given key-værdi i et map. Dette er meget vigtigt at huske på. map::insert()'s returtype er pair::iterator, bool>, hvor iteratoren peger på elementet, i det map-objekt der er blevet indsat et element, der har en key-værdi der er lig med keyobj, og bool-objektet er true hvis der blev indsat et nyt element (altså, hvis key-værdien ikke fandtes i map-objektet allerede), og false hvis der ikke blev indsat et nyt element.

map har også en find() funktion. map::find() tager et parameter, af samme type som key-værdien for containeren, og returnerer en iterator der refererer til elementet med denne key. Hvis et sådan element ikke findes, returneres map::end().

Bemærk, at når en map-iterator derefereres, fås et pair-objekt, hvor man så kan tilgå first og second.

map tillader brug af subscripting-operatoren ([]), hvor parametren er af samme type som det relevante maps key-værdi. Hvis et element med den givne key-værdi findes, returneres en reference til dette element (ganske som med arrays, eller en vector), hvis ikke, oprettes et nyt element, med den givne key-værdi, og en reference til dette nye element returneres. Eftersom subscripting-operatoren således kan ændre objektet, må det map den benyttes med, ikke være const. Den reference der fås ved brug af subscripting-operatoren, kan tildeles en værdi af samme type som map-objektets value-type.

Her er en omskrevet udgave af Fig. 5.4, der nu bruger map, og altid har værdier for "Athas" og "Bjarne."

// Fig. 5.8.
#include
#include
#include
#include
#include
#include

using namespace std;

int main(int argc, char** argv)
{
if (argc % 2 == 0 || argc
{
cerr
return 1;
}

map elem_map;

elem_map["Bjarne"] = 1337;
elem_map["Athas"] = 666;

for (int p = 1; p
elem_map.insert(make_pair(argv[p], atoi(argv[p+1])));

for(map::const_iterator it = elem_map.begin();
it != elem_map.end();
it++)
cout << it->first << " " << it->second

return 0;
}


Bemærk at outputtet er sorteret efter navn, og ikke tal, i modsætning til det oprindelige program. map sorterer efter sin key.

vector

Denne container er generelt den man skal bruge, med mindre man har eksplicitte krav den ikke kan leve op til (f.eks. indsættelse af mange elementer i midten af containeren). En vector er meget let at have med at gøre. Den har random access iterators, den er lineær og den har et meget lille overhead i forhold til et typisk array. Forskellen i run-time hastighed er så lille at den knapt kan måles, og en vector bruger kun nogle få bytes til at gemme information om sin egen længde. En vector styrer selv sit hukommelsesforbrug, og kan dynamisk ændre sin størrelse for at akkomodere for et større antal elementer. Dette betyder at en push_back pludselig kan tage længere tid end sædvanligt, mens vectoren allokerer hukommelsen og flytter rundt på data, og dette er ikke altid praktisk. vector har derfor to funktioner der kan kontrollere hukommelsesbrug, så man kan placere allokering på strategisk rigtige tidspunkter i programmet. Hvis v er en vector:

v.reserve(n) -- reallokerer v så den kan indeholde mindst (muligvis flere) n elementer. Hvis n er mindre end v.size() vil overskydende elementer ikke blive slettet, og v vil ikke antage en mindre størrelse. Det eneste denne funktion garanterer, er at v kan indeholde n elementer uden yderligere reallokering.
v.resize(n) -- Reallokerer v til at kunne indeholde n elementer. Bevarer de første n elementer i v, men sletter overskydende elementer hvis n er mindre end v.size(). Denne funktion gør alle iteratorer til c ugyldige. At bruge en ugyldig iterator er en meget alvorlig fejl.


Typiske Container-Funktioner


De sekventielle containere (list, vector og string) har en række funktioner der gør dem lettere at arbejde med. Disse, hvis c er en sekventiel container, er beskrevet er:

c.insert(it, t) -- denne funktion indsætter en kopi af objektet t, i containeren c, lige før placeringen refereret til af iteratoren it. Denne iterator skal naturligvis være gyldig for c. Denne funktion returnerer en iterator til det netop indsatte objekt.
c.insert(t, b, e) -- denne funktion indsætter sekvensen [b;e[ i containeren c, lige før den placering der refereres til af it. Denne funktion returnerer void.
c.erase(it) -- denne funktion sletter det element it refererer til. Denne funktion returnerer en iterator der refererer til elementet lige efter det der blev slettet.
c.erase(b, e) -- denne funktion sletter alle elementer i intervallet [b;e[, og returnerer en iterator der refererer til elementet lige efter sekvensen der blev slettet.
c.push_back(t) -- indsætter en kopi af objektet t i slutningen af containeren c. Returnerer void.
c.pop_back() -- sletter cs sidste element og returnerer void. Må ikke benyttes hvis c ikke indeholder elementer.
c.push_front(t) -- indsætter en kopi af objektet t i starten af containeren c. Returnerer void. Er ikke gyldig for string og vector.
c.pop_front() -- sletter cs første element og returnerer void. Må ikke benyttes hvis c ikke indeholder elementer. Er kun gyldig for list.