Πρόκειται για μία δομή πίνακα του οποίου η χωρητικότητα μεταβάλλεται δυναμικά με βάση τις ανάγκες αποθήκευσης του προγράμματος. Η παρακάτω εικόνα είναι ενδεικτική της υφιστάμενης δομής δεδομένω που περιγράφει ένα vector. Παρατηρήστε ότι η χωρητικότητα ενός vector μπορεί να είναι μεγαλύτερη από τον αριθμό των αποθηκευμένων στοιχείων του.

• Η πράξη της ένθεσης ή της διαγραφής από τον τέλος του πίνακα έχει σταθερό κόστος (O(1)).
• Η πράξη της ένθεσης ή της διαγραφής από το μέσο ή την αρχή του πίνακα συνεπάγεται την μετακίνηση όλων των στοιχείων που βρίσκονται δεξιότερα κατά μία θέση και η επίδοσης της εξαρτάται από την θέση της ένθεσης ή της διαγραφής σε σχέση με το τέλος του πίνακα. Ο επιμερισμένος χρόνος της συγκεκριμένης πράξης είναι γραμμικός στο μέγεθος των αποθηκευμένων στοιχείων του πίνακα (Ο(Ν)).
• Η πράξη της αναζήτησης είναι γραμμική στο μέγεθος των στοιχείων του πίνακα (Ο(Ν)).

Όπως προαναφέρθηκε, η κλάση vector παρέχει την δυνατότητα ένθεσης και διαγραφής στοιχείων, ώστε το μέγεθος των αποθηκευμένων στοιχείων του vector να μεταβάλλεται. Πιο συγκεκριμένα, η ένθεση μπορεί να γίνει μέσω των συναρτήσεων insert (ένθεση σε οποιαδήποτε θέση του πίνακα μέσω ενός iterator) και push_back ένθεση στο τέλος του πίνακα push_back.

vector_insert.cpp

#include <vector>
#include <list>
#include <iostream>
#include <iomanip>
 
using namespace std;
 
template<typename T>
void print(vector<T> v) {
  for(auto it = v.cbegin(); it!=v.cend(); it++) 
    cout << setw(3) << *it;
  cout << endl;
}
 
int main() {
  vector<int> ints;                  // initially zero size
  cout << "size: " << setw(2) << ints.size() ;
  cout << " capacity: " << setw(2) << ints.capacity() << endl;
  for(int i=0; i<10; i++) {
    ints.push_back(i+1);             // insert to the end - very fast
    cout << "size: " << setw(2) << ints.size() ;
    cout << " capacity: " << setw(2) << ints.capacity() << endl;
    ints.insert(ints.begin(),i+1);   // insert to the beginning - extremely slow
    cout << "size: " << setw(2) << ints.size() ;
    cout << " capacity: " << setw(2) << ints.capacity() << endl;
  }
  print(ints);
}

Η εκτύπωση του παραπάνω προγράμματος όσον αφορά το μέγεθος και τη χωρητικότητα του πίνακα είναι η εξής:

size:  0 capacity:  0                                                                                                                                                                     
size:  1 capacity:  1                                                                                                                                                                     
size:  2 capacity:  2                                                                                                                                                                     
size:  3 capacity:  4                                                                                                                                                                     
size:  4 capacity:  4                                                                                                                                                                     
size:  5 capacity:  8                                                                                                                                                                     
size:  6 capacity:  8                                                                                                                                                                     
size:  7 capacity:  8                                                                                                                                                                     
size:  8 capacity:  8                                                                                                                                                                     
size:  9 capacity: 16                                                                                                                                                                     
size: 10 capacity: 16                                                                                                                                                                     
size: 11 capacity: 16                                                                                                                                                                     
size: 12 capacity: 16                                                                                                                                                                     
size: 13 capacity: 16
size: 14 capacity: 16
size: 15 capacity: 16
size: 16 capacity: 16
size: 17 capacity: 32
size: 18 capacity: 32
size: 19 capacity: 32
size: 20 capacity: 32

Παρατηρήστε ότι κάθε φορά που χρειάζεται να γίνει μεγένθυση του πίνακα (re-allocation) η χωρητικότητα διπλασιάζεται. Το παραπάνω εξασφαλίζει οτι το επιμέρισμένο κόστος αντιγραφής για κάθε re-allocation είναι σταθερό Ο(1) (δες σχετικά την ανάλυση της επίδοσης του ανακατακερματισμού στο βιβλίο των Δομών Δεδομένων του κ. Μποζάνη).

vector_erase_01.cpp

#include <vector>
#include <list>
#include <iostream>
#include <iomanip>
 
using namespace std;
 
template<typename T>
void print(vector<T> v) {
  for(auto it = v.cbegin(); it!=v.cend(); it++) 
    cout << setw(3) << *it;
  cout << endl;
}
 
int main() {
  vector<int> ints;                  // initially zero size
  for(int i=0; i<10; i++) {
    ints.push_back(i+1);             // insert to the end - very fast
    ints.insert(ints.begin(),i+1);   // insert to the beginning - extremely slow
  }
  print(ints);
 
  while(ints.size() > 0) {
    auto pos = ints.begin() + ints.size()/2 - 1; 
    ints.erase(pos, pos+2);         // erase the two middle elements at every step.
    print(ints);
  }
}

vector_erase_02.cpp

#include <vector>
#include <list>
#include <iostream>
#include <iomanip>
 
using namespace std;
 
template<typename T>
void print(vector<T> v) {
  for(auto it = v.cbegin(); it!=v.cend(); it++) 
    cout << setw(3) << *it;
  cout << endl;
}
 
int main() {
  vector<int> ints;                  // initially zero size
  for(int i=0; i<10; i++) {
    ints.push_back(i+1);             // insert to the end - very fast
    ints.insert(ints.begin(),i+1);   // insert to the beginning - extremely slow
  }
  print(ints);
 
  while(ints.size() > 0) {
    ints.erase(ints.begin());    // erase the first element.
    ints.erase(ints.end()-1);    // erase the laste element.
    print(ints);
  }
}