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 παρέχουν συναρτήσεις με τις οποίες κάποιος μπορεί να προσπελάσει τα στοιχεία της δομής, όπως συναρτήσεις για να προσθέσει κάποιος νέα στοιχεία στο τέλος της δομής ή οπουδήποτε μέσα, συναρτήσεις για διαγραφή στοιχείων ή συναρτήσει που επιστρέφουν τον αριθμό των στοιχείων.

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

Η προσπέλαση των στοιχείων μέσα στο 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; // ανεξέλεγκτη συμπεριφορά - ο δείκτης πλέον δείχνει ένα μη εκχωρημένο τμήμα μνήμης 
}

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

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