Tags:    c++

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 <algorithm>, derimod har en list sin egen sort()-metode:

// Fig. 5.0.
#include <list>
#include <string>
#include <algorithm>
#include <iostream>
#include <iterator>

using namespace std;

int main()
{
  list<string> 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<string>(cout, "\\n"));

  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 <utility>. 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 <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <utility>

using namespace std;

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

int main(int argc, char** argv)
{
  if (argc % 2 == 0 || argc < 3)
    {
      cerr << "Usage: " << argv[0] << " [element value]..." << endl;
      return 1;
    }

  vector<pair<string, int> > elem_vec;

  for (int p = 1; p < argc-1; p+=2)
    elem_vec.push_back(make_pair(argv[p], atoi(argv[p+1])));
 
  for(vector<pair<string, int> >::const_iterator it = elem_vec.begin();
      it != elem_vec.end();
      it++)
    cout << it->first << " " << it->second << endl;

  cout << "vector is being sorted..." << endl;

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

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

  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 <<-operatoren), sorterer denne vector, og udskriver indholdet. Programmet bruger make_pair() til at oprette pair-objekterne, en funktion der tager to parametre, og returnerer et pair objekt indeholdende disse parametre. Jeg bruger atoi() for at konvertere et tal i en char*-string til et heltal, idet vores vector indeholder pair-objekter af typen pair<string, int>. C++'s standard library rummer ikke en standardfunktion der kan sammenligne to pair<string, int>-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 <map>. 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<string, int>, frem for en vector<pair<string, int>. 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<K, V, P> 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<K, V>, 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<map<K, V>::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 <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <utility>
#include <map>

using namespace std;

int main(int argc, char** argv)
{
  if (argc % 2 == 0 || argc < 3)
    {
      cerr << "Usage: " << argv[0] << " [element value]..." << endl;
      return 1;
    }

  map<string, int> elem_map;

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

  for (int p = 1; p < argc-1; p+=2)
    elem_map.insert(make_pair(argv[p], atoi(argv[p+1])));
 
  for(map<string, int>::const_iterator it = elem_map.begin();
      it != elem_map.end();
      it++)
    cout << it->first << " " << it->second << endl;

  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.

Konklusion

Det var det. Som jeg skrev i indledningen er dette på ingen måde en komplet guide. Faktisk mener jeg selv at den er meget ufærdig, men den burde indeholde den information der skal til for at man kan bruge containere i sine C++-programmer. Der er mange ting jeg ikke fik dækket, bl.a. flere detaljer om iteratorer, algoritmer, flere containerfunktioner, hvordan containere implementeres, flere forskellige containere, og mere. Dette vil muligvis blive dækket i en senere artikel. Få jer en bog som Accelerated C++ (http://www.acceleratedcpp.com/ -- min ene store inspiration til denne artikel) eller The C++ Programming Language (http://www.research.att.com/~bs/C++.html -- min anden store inspiration til denne artikel).

Templates, containers og generiske algoritmer styrer. Brug dem.

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:  

Karma barometer (30 dage)

IT jobs | Kontakt | Om Udvikleren.dk | Om karma | IT nyheds arkiv | Annoncering

X