Vector (C++)

Το vector (C++) (μεταφράζεται από τα αγγλικά ως διάνυσμα) είναι μια στάνταρντ βιβλιοθήκη προτύπων (STL: Standard Template Library) της γλώσσας προγραμματισμού C++ η οποία δημιουργεί μια δομή δεδομένων με τις ιδιότητες ενός δυναμικού πίνακα. Η υλοποίηση έχει γίνει με την χρήστη προτύπων (Templates) της γλώσσας C++, έτσι η βιβλιοθήκη αυτή μπορεί να δεχτεί διαφορετικούς τύπους. Έτσι μπορούμε να δημιουργήσουμε ένα δυναμικό πίνακα ακέραιους (int) ή αλφαριθμητικών (string) ή γενικότερα ένα δυναμικό πίνακα από μια κλάση την οποία έχουμε ορίσει.

Σχεδιασμός

Το πρότυπο vector ορίζεται στο header αρχείο <vector>. Όπως και τα υπόλοιπα πρότυπα της στάνταρντ βιβλιοθήκης προτύπων (STL: Standard Template Library) βρίσκεται μέσα στο namespace std.

Το περιβάλλον του προτύπου εξομοιώνει την συμπεριφορά της δομής πίνακα της γλώσσας προγραμματισμού C. Για παράδειγμα μπορεί να έχει τυχαία πρόσβαση σε στοιχεία αλλά έχει και την δυνατότητα να αυξάνει δυναμικά το μέγεθος της δομής κάθε φορά που εισέρχεται ή αφαιρείται κάποιο αντικείμενο.

Το πρότυπο vector μπορεί να αρχικοποιηθεί με οποιαδήποτε δομή-κλάση (class) ή οποία είναι σχεδιασμένη με τις ιδιότητες: CopyConstructible και Assignable

εκφράσεις	τύπος επιστροφής	προϋπόθεση
t = u	T&	t ισοδυναμεί με το u
T(t)	μη διαθέσιμο	t ισοδυναμεί με το T(t)
T(u)	μη διαθέσιμο	u ισοδυναμεί με το T(u)
&u	(const) T*	δίνει την διεύθυνση του u
t.~T()	μη διαθέσιμο	μη διαθέσιμο

Όταν T είναι ο τύπος ο οποίος αρχικοποιεί το vector, t είναι η τιμή του T και u είναι η τιμή του (πιθανού constructor const) T.

Για ένα δεδομένο vector όλα τα στοιχεία πρέπει να είναι του ίδιου τύπου-κλάσης. Για παράδειγμα, ένα vector δεν μπορεί να περιέχει ταυτόχρονα στοιχεία χαρακτήρων (char) μαζί με στοιχεία ακεραίων (int). Τα vector παρέχουν συναρτήσεις με τις οποίες κάποιος μπορεί να προσπελάσει τα στοιχεία της δομής, όπως συναρτήσεις για να προσθέσει κάποιος νέα στοιχεία στο τέλος της δομής ή οπουδήποτε μέσα, συναρτήσεις για διαγραφή στοιχείων ή συναρτήσει που επιστρέφουν τον αριθμό των στοιχείων.

Χρήση

Ένα πρόγραμμα C++ το οποίο χρησιμοποιεί τον container vector πρέπει να συμπεριλάβει στο header το <vector>: #include <vector>. Ένα vector ορίζεται χρησιμοποιώντας:

std::vector<T> instance;

όπου "T" είναι η κλάση-δομή την οποία το vector θα περιέχει και "instance" είναι το όνομα μεταβλητή που θα χρησιμοποιηθεί στο πρόγραμμα. T μπορεί να είναι οποιαδήποτε δομή-κλάση της C++ η οποία είναι τύπου Assignable, όπως και δομές που έχουν οριστεί από τον προγραμματιστή.

Εναλλακτικός τρόπος για αποθήκευση μέσα στο vector δομών-κλάσεων της μορφής T είναι αποθήκευση με την μορφή τύπου T*. Αυτό είναι χρήσιμο όταν η δομή-κλάση T δεν είναι Assignable, ή έχει κόστος η αντιγραφή.

Προσπέλαση στοιχείων

Η προσπέλαση των στοιχείων μέσα στο vector μπορεί να γίνει με τους τελεστές που φαίνονται στο πίνακα παρακάτω. Χρησιμοποιώντας τις στάνταρντ συμβάσεις της γλώσσας C/C++ το πρώτο στοιχείο βρίσκεται στην σειρά (index) 0, ενώ το τελευταίο στοιχείο βρίσκεται στη σειρά size() - 1.

έκφραση	τύπος επιστροφής	έλεγχος ορίων;
v.at(i)	T& ή const T& το στοιχείο στην σειρά i	ναι, επιστρέφει την out_of_range εξαίρεση
v[i]	T& ή const T& το στοιχείο με σειρά i	απρόβλεπτη συμπεριφορά εάν i >= v.size()
v.front()	T& ή const T& το πρώτο στοιχείο της δομής	απρόβλεπτη συμπεριφορά εάν η σημαία v.empty() είναι true αληθής - δηλαδή έχουμε κενή δομή
v.back()	T& ή const T& το τελευταίο στοιχείο της δομής	απρόβλεπτη συμπεριφορά εάν η σημαία v.empty() είναι true αληθής - δηλαδή έχουμε κενή δομή

Όπου v είναι το αντικείμενο τύπου (πιθανόν const) vector<T> και το i αντιπροσωπεύει την σειρά (index).

Παρουσίαση των συναρτήσεων

Η vector κλάση μοντελοποιεί την ιδέα του C++ Container, το οποίο συνεπάγεται ότι περιέχει τις μεθόδους begin(), end(), size(), max_size(), empty(), και swap().

• πληροφοριακά
  • vector::front - Παραπέμπει στο πρώτο στοιχείο του vector.
  • vector::back - Παραπέμπει στο τελευταίο στοιχείο του vector.
  • vector::size - Επιστρέφει τον αριθμό των στοιχείων που υπάρχουν στο vector.
  • vector::empty - Η σημαία αυτή είναι αληθής όταν το vector δεν έχει κανένα στοιχείο.
  • vector::capacity - Επιστρέφει την τωρινή κατάσταση χωρητικότητας του vector (πόση μνήμη έχει εκχωρηθεί για χρήση).
• στάνταρντ λειτουργίες
  • vector::insert - Εισάγει στοιχεία μέσα στο vector (είτε ένα μεμονωμένο είτε μια σειρά στοιχείων), μετακινεί τα υπόλοιπα στοιχεία προς επάνω.
  • vector::push_back - Εισάγει ένα στοιχείο στο τέλος της δομής και εκχωρεί αυτόματα μνήμη αν αυτό είναι αναγκαίο.
  • vector::erase - Σβήνει ένα ή μια σειρά στοιχείων από το vector. Τα εναπομείναντα στοιχεία μετακινούνται προς τα κάτω.
  • vector::pop_back - Αφαιρεί-διαγράφει το τελευταίο στοιχείο του vector. Συνήθως δεν αφαιρεί την εκχωρημένη μνήμη που υπάρχει για το στοιχείο αυτό.
  • vector::clear - Διαγράφονται-αφαιρούνται όλα τα στοιχεία του vector. (Η μέθοδος αυτή δεν μειώνει την χωρητικότητα του vector - εκχωρημένη μνήμη)
• εκχώρηση μνήμης/αλλαγή μεγέθους
  • vector::reserve - Αλλάζει την χωρητικότητα του vector (εκχωρεί περισσότερη μνήμη εάν χρειάζεται). Σε πολλές υλοποιήσεις της στάνταρντ βιβλιοθήκης STL η χωρητικότητα μπορεί μόνο να μεγαλώσει (εκχώρηση νέας μνήμης), και ποτέ να μειωθεί.
  • vector::resize - Αλλάζει το μέγεθος του vector.
• προσπέλαση
  • vector::begin - Επιστρέφει ένα iterator (προσπελαστή) που δείχνει το πρώτο στοιχείο του vector.
  • vector::end - Επιστρέφει ένα iterator (προσπελαστή) ο οποίος δείχνει το τέλος μετά το τελευταίο στοιχείο του vector.

Παράδειγμα χρήσης μερικών από των παραπάνω συναρτήσεων:

vector<int> vec;    // ο πίνακας vec περιέχει ακέραιους αριθμούς

// Αρχικοποίησε τον πίνακα ώστε να περιέχει τους ακέραιους αριθμούς [100, 200, 300, 400]
for (int i=0; i<4; i++)
        vec.push_back((i + 1) * 100);

cout << "Πρώτο στοιχείο: " << vec.front() << endl;
cout << "Τελευταίο στοιχείο: " << vec.back() << endl;
cout << "Αριθμός στοιχείων στον πίνακα: " << vec.size() << endl;

// Διέγραψε το τελευταίο στοιχείο του πίνακα. Η αρίθμηση των στοιχείων στο vector
// ξεκινά από το 0, έτσι το vec.end() ουσιαστικά δείχνει ένα στοιχείο μετά το τελευταίο.
vec.erase(vec.end() - 1);

cout << endl << "Μετά την διαγραφή του τελευταίου στοιχείου, το νέο στοιχείο στο τέλος είναι το: " 
             << vec.back() << endl;

// Διέγραψε το πρώτο στοιχείο του πίνακα.
vec.erase(vec.begin());

cout << "Μετά την διαγραφή του πρώτου στοιχείου, το νέο πρώτο στοιχείο είναι το: "
     << vec.front() << endl;

cout << "Αριθμός στοιχείων στο πίνακα: " << vec.size() << endl;

// Εισαγωγή του στοιχείου (ακέραιος αριθμός -11) στην αρχή του πίνακα.
vec.insert(vec.begin(),-11);

Για να προσπελαστούν τα στοιχεία του vector μπορεί να χρησιμοποιηθεί ένας for βρόχος μαζί με την χρήση ενός προσπελαστή (iterator) όπως φαίνεται στο παρακάτω παράδειγμα:

// #include<iostream>
// #include<vector>
// using namespace std;

vector<int> vec;

vec.push_back(11);
vec.push_back(15);
vec.push_back(20);

// το vec περιέχει τα στοιχεία (ακέραιοι): {11, 15, 20}

vector<int>::iterator iter;

// το *iter δείχνει το κάθε στοιχείο του vec 
for (iter=vec.begin(); iter!=vec.end(); ++iter) {
    cout << *iter << ' ';
}

// Η έξοδος στην οθόνη μέσω της cout είναι: 11 15 20

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

Μια τυπική υλοποίηση ενός 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> // printf
int 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 στοιχεία τα οποία αρχικοποιούνται με την προκαθορισμένη τιμή αρχικοποίησης.

Παραπομπές

• William Ford, William Topp. Data Structures with C++ and STL, Second Edition. Prentice Hall, 2002. ISBN 0-13-085850-1. Chapter 4: The Vector Class, pp.195–203.