Vector (C++)

Χρήση

Ένα πρόγραμμα C++ το οποίο χρησιμοποιεί τον container vector πρέπει να συμπεριλάβει στο header το <vector>: #include <vector>. Ένα vector ορίζεται χρησιμοποιώντας:
std::vector<T> instance;
όπου "T" είναι η κλάση-δομή την οποία το vector θα περιέχει και "instance" είναι το όνομα μεταβλητή που θα χρησιμοποιηθεί στο πρόγραμμα. T μπορεί να είναι οποιαδήποτε δομή-κλάση της C++ η οποία είναι τύπου Assignable, όπως και δομές που έχουν οριστεί από τον προγραμματιστή. 
Εναλλακτικός τρόπος για αποθήκευση μέσα στο vector δομών-κλάσεων της μορφής T είναι αποθήκευση με την μορφή τύπου T*. Αυτό είναι χρήσιμο όταν η δομή-κλάση T δεν είναι Assignable, ή έχει κόστος η αντιγραφή.

Χωρητικότητα και εκχώρηση μνήμης

Μια τυπική υλοποίηση ενός vector περιέχει, εσωτερικά, ένα δείκτη σε μια δυναμική δομή πίνακα , και πιθανώς τα στοιχεία αυτά περιέχουν τη συνολική χωρητικότητα και το μέγεθος της δομής. Το μέγεθος (size) του vector αναφέρεται στο αριθμό των στοιχείων τα οποία περιέχει η δομή, ενώ η χωρητικότητα (capacity) αναφέρεται στο μέγεθος της εσωτερικής δομής (μνήμη που συνολικά έχει εκχωρηθεί).
Όταν νέα στοιχεία εισάγονται, εάν το μέγεθος του vector γίνεται μεγαλύτερο από το μέγεθος της χωρητικότητας, νέα εκχώρηση μνήμης λαμβάνει τόπο.  Αυτό σημαίνει ότι το vector εκχωρεί νέα μεγαλύτερη περιοχή μνήμης και μετακινεί τα στοιχεία στη νέα περιοχή,  απελευθερώνοντας την παλαιότερη εκχωρημένη περιοχή μνήμης.

Επειδή οι διευθύνσεις μνήμης των στοιχείων αλλάζουν κατά την διαδικασία αυτή, όλοι οι δείκτες ή προσπελαστές (interators) σε στοιχεία αλλάζουν δείχνουν λάθος (δείχνουν οι διευθύνσεις στην παλαιότερη εκχωρημένη μνήμη).  Χρησιμοποιώντας τέτοιου είδους δείκτες μπορεί να οδηγήσει το πρόγραμμα σε ανεξέλεγκτη συμπεριφορά. Για παράδειγμα:
#include <vector>int main() {
  std::vector<int> v(1); // δημιουργεί ένα vector το οποίο περιέχει ένα ακέραιο με τιμή 0

  int& first = *v.begin(); // αρχικοποίηση δείκτη στο πρώτο στοιχείο του vector 

  v.insert(v.end(), v.capacity(), 0); // προσθήκη περισσότερων στοιχείων στο vector, εκτελείται νέα εκχώρηση μνήμης

  int i = first; // ανεξέλεγκτη συμπεριφορά - ο δείκτης πλέον δείχνει ένα μη εκχωρημένο τμήμα μνήμης 
  
  return 0;}
Η συνάρτηση reserve() μπορεί να χρησιμοποιηθεί για να αποφευχθεί η εκχώρηση παραπάνω μνήμης. Μετά την κλήση της reserve(n), το μέγεθος του vector εγγυάται ότι θα μπορεί να είναι τουλάχιστον n.  Για παράδειγμα:
#include <vector>int main() {
  std::vector<int> v(1);   // δημιουργία ενός vector με μια τιμή ακεραίου με την τυπική τιμή 0

  v.reserve(10);           // δέσμευσε χώρο μνήμης να αποφευχθεί η περαιτέρω νέα εκχώρηση

  int& first = *v.begin(); // δημιούργησε ένα δείκτη μνήμης που αναφέρεται στο πρώτο στοιχείο του vector

  v.insert(v.end(), 5, 0); // πρόσθεσε περισσότερα στοιχεία στο τέλος του vector

  int i = first;           // OK, δεν έχει γίνει νέα εκχώρηση μνήμης μετά την χρήση του v.reserve(10)

  return 0;}
Το vector διατηρεί μια συγκεκριμένη σειρά στα στοιχεία που περιέχει, έτσι κάθε φορά που ένα νέο στοιχείο εισέρχεται στην αρχή ή στο μέσο του vector, τα υπόλοιπα στοιχεία μετακινούνται προς τα πίσω σύμφωνα με την μέθοδο ανάθεσης-εκχώρησης (assignment operator) και την μέθοδο αρχικοποίησης με αντιγραφή (copy constructor). Έτσι όλες οι αναφορές σε στοιχεία (με διεύθυνση μνήμης) μέσω δεικτών όπως και οι αναφορές μνήμης μέσω προσπελαστών (iterators) αλλάζουν.  Για παράδειγμα:
#include <vector>int main() {
  std::vector<int> v(2); // αρχικοποιεί ένα vector με 2 ακέραιους int

  // δημιουργία δεικτών οι οποίοι δείχνουν τις θέσεις μνημών των δύο ακεραίων
  int& first = v.front();     
  int& last = v.back();       
 
  v.insert(v.begin() + 1, 1, 1); // εισαγωγή ενός νέου ακέραιου στην μέση του vector 

  int i = first; // ανεξέλεγκτη συμπεριφορά εάν η προηγούμενη εισαγωγή έκανε εκχώρηση νέας μνήμης
  int j = last;  // ανεξέλεγκτη συμπεριφορά σύμφωνα με το πρότυπο της C++, §23.2.4.3/1

  return 0;}

vector<bool> τυποποίηση

Η στάνταρντ βιβλιοθήκη ορίζει το ορισμό του vector για τον τύπο bool. Σύμφωνα με την περιγραφή της στάνταρντ βιβλιοθήκης, η υλοποίηση του vector<bool> θα πρέπει να είναι με τέτοιο τρόπο ώστε κάθε στοιχείο τύπου bool να χρησιμοποιεί ένα bit μνήμης. Αυτό γενικά θεωρείται λάθος. Η υλοποίηση vector<bool> δεν καλύπτει τις προϋποθέσεις που έχει επιβάλει η στάνταρντ βιβλιοθήκη. Για παράδειγμα το container<T>::reference πρέπει να είναι lvalue τύπου bool. Αυτό δεν ισχύει με το vector<bool>::reference, το οποίο είναι μια proxy κλάση ή οποία μετατρέπεται σε bool.  Παρομοίως ο κώδικας vector<bool>::iterator δεν δίνει το bool& όταν χρησιμοποιείται dereferencing (τελεστής μετατροπής του δείκτη στην τιμή). Υπάρχει μια συναίνεση ανάμεσα την επιτροπή προτυποποίησης της C++ με την ομάδα εργασίας της βιβλιοθήκης (Library Working Group) στο ότι ο vector<bool> θα πρέπει να αφαιρεθεί από την στάνταρντ βιβλιοθήκη, και η λειτουργικότητα να επανέλθει στη γλώσσα με διαφορετικό όνομα. Αυτή η αλλαγή ίσως γίνει στην C++0x.

Χρήση του vector ως πίνακα

Στην C++, οι πίνακες είναι συνεχόμενα τμήματα μνήμης. Είναι τμήματα τα οποία είναι παρατεταγμένα στη σειρά και κάθε τμήμα αντιπροσωπεύεται από ένα αριθμό και αν κάποιος θέλει να προσπελάσει κάποιο τμήμα θα πρέπει να γνωρίζει το αριθμό του. Επίσης όλα τα στοιχεία ενός πίνακα θα πρέπει να είναι ίδιου τύπου.
Το vector είναι παρόμοιο με ένα δυναμικά εκχωρημένο πίνακα αλλά έχει την δυνατότητα να αλλάζει μέγεθος αυτόματα, χωρίς να χρειάζεται χειροκίνητη εκχώρηση μνήμης.

Επειδή τα στοιχεία σε ένα vector αποθηκεύονται σε συνεχόμενα τμήματα μνήμης, η διεύθυνση του πρώτου στοιχείου στο vector μπορεί να περαστεί ως παράμετρος σε συναρτήσεις οι οποίες δέχονται ως όρισμα πίνακα (τέτοιες συναρτήσεις δέχονται δείκτη σε πρώτο στοιχείο του πίνακα). Το παρακάτω παράδειγμα κώδικα δείχνει πως ένα  vector μπορεί να χρησιμοποιηθεί με την συνάρτηση memcpy και printf της στάνταρντ βιβλιοθήκης της γλώσσας C:
#include <cstring> // memcpy#include <vector> #include <cstdio> // printfint main() {
  using namespace std;
  const char arr[] = "1234567890";
  // δημιύργησε ένα vector με  11 χαρακτήρες (τύπος char) με τιμή αρχικοποίησης το μηδέν
  vector<char> vec(sizeof arr);  
  // αντέγραψε 11 chars από το arr μέσα στο vector
  memcpy(&vec[0], arr, sizeof arr); 
  // εμφάνισε "1234567890"
  printf("%s", &vec[0]); 

  return 0;}
Σημειώνουμε ότι τέτοια χρήση της συνάρτησης memcpy και της printf γενικά αποθαρρύνεται για λόγους ασφάλειας τύπων και των εναλλακτικών επιλογών που προσφέρει η στάνταρντ βιβλιοθήκη της C++.

Σχηματική οπτικοποίηση

Παρακάτω βλέπουμε την λειτουργία της συνάρτησης push_back( data ) του πρότυπου vector η οποία προσθέτει ένα νέο στοιχείο στο τέλος.  Παρατηρούμε ότι το vector αυξάνεται δυναμικά από 6 στοιχεία σε 7 μετά την πρόσθεση του νέου στοιχείου.

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

Παρακάτω βλέπουμε την λειτουργία της συνάρτησης resize( int ) του πρότυπου vector ή οποία αλλάζει το μέγεθος της δομής.  Παρατηρούμε ότι το μέγεθος της δομής αλλάζει δυναμικά σε 9 στοιχεία τα οποία αρχικοποιούνται με την προκαθορισμένη τιμή αρχικοποίησης.