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)	n/a	t ισοδυναμεί με το T(t)
T(u)	n/a	u ισοδυναμεί με το T(u)
&u	(const) T*	δίνει την διεύθυνση του u
t.~T()	μη διαθέσιμο	μη διαθέσιμο

Όταν T είναι ο τύπος ο οποίος αρχικοποιεί το vector, t είναι η τιμή του T και u είναι η τιμή του (πιθανού constractor 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 περιέχει, εσωτερικά, ένα δείκτη σε μια δυναμική δομή πίνακα , και πιθανώς τα στοιχεία αυτά περιέχουν τη συνολική χωρητικότητα και το μέγεθος της δομής. Το μέγεθος (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; // ανεξέλεγκτη συμπεριφορά - ο δείκτης πλέον δείχνει ένα μη εκχωρημένο τμήμα μνήμης 
}

Η συνάρτηση 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)
}

Το 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
}

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

Παρακάτω βλέπουμε την λειτουργία της συνάρτησης 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.