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

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

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

vector_insert.cpp

#include <vector>
#include <list>
#include <iostream>
 
using namespace std;
 
template<typename T>
void print(vector<T> v) {
  for(auto it = v.cbegin(); it!=v.cend(); it++) 
    cout << setw(4) << *it;
  cout << endl;
}
 
template<typename T>
void print_r(vector<T> v) {
  for(auto it = v.crbegin(); it!=v.crend(); it++) 
    cout << setw(4) << *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);
}