De standard C++ vector

De standard vector is een soort "slimme" tabel of array. Men kan een vector gewoon gebruiken zoals een tabel, maar de klasse biedt veel extra faciliteiten. De belangrijkste eigenschappen zijn de dynamische groeimogelijkheid en het oplossen van vervelende allocatieproblemen.

Allocatieproblemen bij de traditionele tabel

Indien een tabel (array) van lengte N gedefinieerd wordt, bv.

  const int N=100;
  int tabel[N];
 

Een gelinkte lijst is beter omdat ze onbeperkt kan groeien, maar dit vraagt mee geheugen (voor de linken tussen de knopen) en indexeren is inefficient. Deze problemen worden opgelost door vector.

Indien het precieze aantal elementen wel gekend is kan men precies voldoende plaats voorzien. Als dit aantal pas tijdens de uitvoer van het programma ("at runtime") bekend is, moet men dynamisch alloceren. Bijvoorbeeld:

   int aantal;
   cin >> aantal;
   int* tab = new int[aantal];
 

   delete [] tab;
 

std::vector

De klasse vector wordt gedefinieerd in de header <vector> (niet <vector.h> !!).

De klasse zit in namespace std. De volledige naam is dus std::vector. Om de namespaceprefix niet elke keer te moeten typen kan men een using-constructie toevoegen. In een programma dat standard vectoren wenst te gebruiken vindt men typisch

   #include <vector>       // geen .h !
   using namespace std;
 

   vector<int>    v; // elk element is een int
   vector<double> w; // elk element is een double
 

   typedef vector<char> mystring;
 

Indexeren

Vectoren zijn vrij eenvoudig en intuïtief te gebruiken. Men kan een vector indexeren zoals een tabel: v[i] is het i-de element van een vector v. Zoals bij tabellen start is een index een positief geheel getal, en start de nummering aan nul.

   const int N=10;
   vector<int> v(N);      // maak vector van N int's (elk element default 0)
   for (int i = 0; i < N; i++)
      v[i] = i;                 // gedraagt zich als tabel
 

Het aantal karakters in een string verkrijgt men door de lidfunctie size().
De lidfunctie empty() geeft een bool terug die aangeeft of de vector leeg is.

Voorbeeld: volgend fragment berekent de som van de elementen van vector<int> v:

   int som = 0;
   for (int i = 0; i < v.size(); i++)
      som += v[i];
   cout << "De som is " << som << endl;
 

Opmerking: eigenlijk is het beter het type size_t te gebruiken voor de index i in plaats van int. Dit komt op de meeste machines neer op een unsigned int. Ook size() geeft eigenlijk een size_t terug.

Elementen toevoegen, dynamisch groeien

   vector<double> v;     // lege vector (nul elementen)
   cout << "Geef getallen, eindig met nul : ";
   double x;
   cin >> x;
   while (x != 0) {
      v.push_back(x);       // voeg achteraan toe
      cin >> x;
   }
   cout << "Aantal : " << v.size() << endl;

Men moet een onderscheid maken tussen de size (grootte) en de capacity (capaciteit) van een vector.
Intern houdt een vector een tabel (array) elementen bij. De grootte van die tabel is de capacity. Er wordt in het algemeen slechts een deel van deze tabel gebruikt, namelijk de eerste size elementen. In dat geval is er nog plaats vrij voor capacity-size elementen.

Wanneer men een nieuw element x toevoegt door push_back(x) en er is nog plaats vrij, dan wordt het element gekopieerd op de eerste vrije plaats van de tabel, en wordt de size verhoogd. Deze operatie is O(1).
Wanneer de tabel echter vol is (d.w.z. size==capacity), dan gebeurt het volgende:

1. er wordt een nieuwe tabel gealloceerd die dubbel zo groot is als de huidige tabel (dubbele capacity, zelfde size)
2. de oorspronkelijke elementen worden gekopieerd naar de nieuwe tabel
3. de oude tabel wordt gedealloceerd (delete)
4. het nieuwe element x wordt toegevoegd

Je kunt de capaciteit van een vector opvragen d.m.v. de methode capacity(), de grootte door size(). Je kunt een capaciteit opgeven d.m.v. reserve(n), en de effectieve grootte wijzigen door resize(n).

Vooraan toevoegen of tussenvoegen van een element in een vector is een dure operatie (O(N)), omdat de rest van de tabel verschoven moet worden. Indien je dit frequent gebruikt, is een gelinkte lijst misschien een beter alternatief [zie ...]
Indien het toch moet: v.insert(pos, x) voegt x toe aan vector v, voor iterator pos (opm. pos is dus geen index!!). Voorbeeld: v.insert(v.begin, x) voegt x vooraan toe.

Er bestaan ook andere varianten van de methode insert die toelaten meerdere elementen ineens toe te voegen.

Constructie, kopie en toekenning

Constructoren:

   vector<double> v1;          // leeg
   vector<double> v2(10);      // 10 doubles, elk = 0.0
   vector<double> v3(20, 0.1); // 10 doubles, elk = 0.1
 

Copy constructor:

   vector<double> v4(v2);      // kopieert alle elementen
 

Toekenning:

   v1 = v2;                          // kopieert alle elementen
 

Initialisatie d.m.v. tabel:

    int tabel[100];
    //...
    vector<int> v5(tabel, tabel+100);
 

   vector<int> v6(a, b);
 

Input/output

Opgelet: zoals bij tabellen (uitgezonderd char-tabellen kan men een vector niet in zijn geheel uitschrijven (naar cout of een andere ostream) of inlezen (uit cin of een andere istream). Dit moet element per element.

vector als functie-argument

Wanneer een vector als argument meegegeven wordt, dan wordt eigenlijk de copy-constructor opgeroepen, die alle elementen kopieert! Behalve voor heel korte vectoren is dit een dure operatie. Men vermijdt best het kopiëren door references naar vectoren mee te geven.
Om aan te geven dat een functie niet van plan is de elementen te wijzigen kan men best een const reference meegeven.
Voorbeeld 1: deze procedure drukt alle elementen van een int-vector af:

   void print(const vector<int> &v) {
      for (int i = 0; i < v.size(); i++)
         cout << v[i] << " ";
   }
 

   void verdubbel(vector<int> &v) {
      for (int i = 0; i < v.size(); i++)
         v[i] *= 2;
   }
 

Ook het retourneren (teruggeven) van een vector door een functie is een "dure" operatie, die vermeden moet worden. Oplossing: vorm de functie om tot een procedure met uitvoerparameter. Bijvoorbeeld: een functie vector<int> keerom(const vector<int> &v) die een vector teruggeeft met dezelfde elementen als v maar in omgekeerde volgorde, kan men beter vervangen door een procedure void keerom(const vector<int> &v, vector<int> &res).

Iteratoren

Net als alle andere STL containers voorziet std::vector een iteratorklasse om de elementen te overlopen: Voorbeeld:

	print(vector<double>& v) {
		for (vector<double>::iterator it = v.begin(); it != v.end(); it++) 
			cout << *it << endl;
	}

Deze iteratoren zijn vooral handig om standard algoritmes te gebruiken; deze verwachten immers iteratorargumenten. Voorbeeld:

	void kopieer(vector<>& bron, vector<>& doel) {
		copy(bron.begin(), bron.end(), doel.begin());
	}

Een vector opvullen

Voorbeeld: Stel dat we 100 gehele getallen willen inlezen van de console (toetsenbord) en bewaren. Er zijn verschillend oplossingen:

1.

	vector<int> v(100);		// alle elementen 0
	for (int i=0; i<100; i++)
		cin >> v[i];

2.

	vector<int> v;  // size==0, capacity==0
	int x;
	for (int i=0; i<100; i++) {
		cin >> x;
		v.push_back(x);
	}

3. verbetering

	vector<int> v;  // size==0, capacity==0
	v.reserve(100);       // size==0, capacity==100
	int x;
	for (int i=0; i<100; i++) {
		cin >> x;
		v.push_back(x);
	}

Verwijderen

De hele vector leeg maken kan door v.erase(v.begin(), v.end()) of door v.clear()

Vergelijking met andere containers

Vergeleken met de traditionele tabel (array) is de vector veel versatieler en handiger. Op constructie en doorgeven als parameter na, kun je je oude tabel-code ongewijzigd hergebruiken: code zoals

   for (int i=0; i<; i++)
      cout << sin(t[i]) << endl;

• houdt eigen lengte bij (size())
• past in STL-framework, o.a. door iteratoren begin() en end(), en door interne typedefs
• kan dynamisch groeien
• stack-operaties push_back() ...
• ...

Let wel dat als je aan de constructor een aantal meegeeft, dat al die elementen geïnitializeerd worden (O(N)), wat bij een tabel niet het geval is.

Vector van pointers

Merk op dat de vector eigenlijk kopieën van de toegevoegde elementen bevat: Bij operaties zoals v[0] = x of v.push_back(x) wordt een kopie van x opgeslagen.
Indien de elementen "grote" datatypes zijn kan men deze kopie vermijden door een vector van pointers te gebruiken:

   class Groot {   // neemt veel plaats in beslag
      public:
         Groot();
         void lees();
         void schrijf();
   };

   vector<Groot*> v;     // lege vector van Groot-pointers (nul elementen)

   for (...) {
      Groot *g = new Groot;        // default constructor
      g->lees();
      v.push_back(g);              // voeg pointer toe
   }
   for (size_t i=0; i<v.size(); i++) {
      v[i]->schrijf();
      delete v[i];
   }

   cout << "Aantal : " << v.size() << endl;

[W. Schepens sept. 2003]