Containers, templates og standard algoritmer i C++

Containers, templates og standard algoritmer i C++

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:

// Fig. 1.0.
#include <iostream>
#include <string>

using namespace std;

template<typename T>
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 << " = " << add<int>(ix, iy) << endl;
  cout << dx << " + " << dy << " = " << add<double>(dx, dy) << endl;
  cout << sx << " + " << sy << " = " << add<string>(sx, sy) << endl;
  return 0;
}

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.

// Fig. 1.1.
template<typename R, typename T>
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 << sx << " + " << sy << " = " << add(sx, sy) << endl;

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 <iostream>
#include <string>

using namespace std;

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

template<>
string add<string,string> (const string& first, const string& second)
{
  cout << endl << "---" << endl;
  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 << " = " << add<int,int>(ix, iy) << endl;
  cout << dx << " + " << dy << " = " << add<double,double>(dx, dy) << endl;
  cout << sx << " + " << sy << " = " << add(sx, sy) << endl;
  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 <iostream>
#include <string>

using namespace std;

template<typename K, typename V>
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<typename K, typename V>
kv_pair<K,V>::kv_pair(const K& n_key, const V& n_value)
{
  m_key = n_key;
  m_value = n_value;
}

template<typename K, typename V>
K kv_pair<K,V>::key()
{
  return m_key;
}

template<typename K, typename V>
V kv_pair<K,V>::value()
{
  return m_value;
}


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

  cout << one.key() << " er " << one.value() << endl;
  cout << another.key() << " er " << another.value() << endl;

  return 0;
}

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:

// Fig. 1.5.
#include <iostream>
#include <string>

using namespace std;

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

  void foo_print()
  {
    cout << m_obj << endl;
  }
  
protected:
  C m_obj;
};

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

  void bar_print()
  {
    foo_print();
    cout << m_k << endl;
  }

protected:
  K m_k;
};

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

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:

// Fig. 1.5.
#include <iostream>
#include <string>

using namespace std;

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

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

int main(int argc, char** argv)
{
  default_tester<> t("Templates er godt.");
  default_tester<int> 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.

<< < Side 1 af 3 > >>