This is an old revision of the document!
Table of Contents
std::vector
Πρόκειται για μία δομή πίνακα του οποίου η χωρητικότητα μεταβάλλεται δυναμικά με βάση τις ανάγκες αποθήκευσης του προγράμματος. Η παρακάτω εικόνα είναι ενδεικτική της υφιστάμενης δομής δεδομένων που περιγράφει ένα vector. Παρατηρήστε ότι η χωρητικότητα ενός vector μπορεί να είναι μεγαλύτερη από τον αριθμό των αποθηκευμένων στοιχείων του.
Σημείωση: H δομή vector υποστηρίζει random access iterators.
Επίδοσης της δομής
- Η πράξη της ένθεσης ή της διαγραφής από τον τέλος του πίνακα έχει σταθερό κόστος (O(1)).
- Η πράξη της ένθεσης ή της διαγραφής από το μέσο ή την αρχή του πίνακα συνεπάγεται την μετακίνηση όλων των στοιχείων που βρίσκονται δεξιότερα κατά μία θέση και η επίδοση της εξαρτάται από την θέση της ένθεσης ή της διαγραφής σε σχέση με το τέλος του πίνακα. Ο επιμερισμένος χρόνος της συγκεκριμένης πράξης είναι γραμμικός στο μέγεθος των αποθηκευμένων στοιχείων του πίνακα (Ο(Ν)).
- Η πράξη της αναζήτησης είναι γραμμική στο μέγεθος των στοιχείων του πίνακα (Ο(Ν)).
- Η πρόσβαση στο i-στο στοιχείο της λίστας έχει κόστος 1.
Πρόσβαση στα στοιχεία του πίνακα
Για τη συνάρτηση vector ισχύει η πρόσβαση μέσω των συναρτήσεων operator[] και at στα υφιστάμενη στοιχεία του container.
- vector_access.cpp
#include <iostream> #include <vector> using namespace std; int main () { vector<int> v(4); cout << "size: " << v.size() << endl; cout << "capa: " << v.capacity() << endl; try { v.at(3) = 600; cout << "v[3]:" << v.at(3) << endl; v.at(4) = 1; cout << "v[4]:" << v.at(4) << endl; } catch(std::out_of_range& ex) { cout << ex.what() << endl; } }
Ένθεση στον πίνακα
Όπως προαναφέρθηκε, η κλάση vector παρέχει την δυνατότητα ένθεσης και διαγραφής στοιχείων, ώστε το μέγεθος των αποθηκευμένων στοιχείων του vector να μεταβάλλεται. Πιο συγκεκριμένα, η ένθεση μπορεί να γίνει μέσω των συναρτήσεων insert (ένθεση σε οποιαδήποτε θέση του πίνακα μέσω ενός iterator) και push_back ένθεση στο τέλος του πίνακα push_back.
- vector_insert.cpp
#include <vector> #include <list> #include <iostream> #include <iomanip> using namespace std; template<typename T> void print(vector<T> v) { for(auto it = v.cbegin(); it!=v.cend(); it++) cout << setw(3) << *it; cout << endl; } int main() { vector<int> ints; // initially zero size cout << "size: " << setw(2) << ints.size() ; cout << " capacity: " << setw(2) << ints.capacity() << endl; for(int i=0; i<10; i++) { ints.push_back(i+1); // insert to the end - very fast cout << "size: " << setw(2) << ints.size() ; cout << " capacity: " << setw(2) << ints.capacity() << endl; ints.insert(ints.begin(),i+1); // insert to the beginning - extremely slow cout << "size: " << setw(2) << ints.size() ; cout << " capacity: " << setw(2) << ints.capacity() << endl; } print(ints); }
Η εκτύπωση του παραπάνω προγράμματος όσον αφορά το μέγεθος και τη χωρητικότητα του πίνακα είναι η εξής:
size: 0 capacity: 0 size: 1 capacity: 1 size: 2 capacity: 2 size: 3 capacity: 4 size: 4 capacity: 4 size: 5 capacity: 8 size: 6 capacity: 8 size: 7 capacity: 8 size: 8 capacity: 8 size: 9 capacity: 16 size: 10 capacity: 16 size: 11 capacity: 16 size: 12 capacity: 16 size: 13 capacity: 16 size: 14 capacity: 16 size: 15 capacity: 16 size: 16 capacity: 16 size: 17 capacity: 32 size: 18 capacity: 32 size: 19 capacity: 32 size: 20 capacity: 32
Παρατηρήστε ότι κάθε φορά που γεμίζει ο πίνακας (δηλαδή size()==capacity()), η χωρητικότητα toy πίνακα διπλασιάζεται. Ο διπλασιασμός εξασφαλίζει οτι το επιμέρισμένο κόστος αντιγραφής για κάθε μεγένθυση είναι σταθερό Ο(1), μην αλλάζοντας την επίδοση της δομής (δες σχετικά την ανάλυση της επίδοσης του ανακατακερματισμού στο βιβλίο των Δομών Δεδομένων του κ. Μποζάνη).
Διαγραφή των περιεχομένων του πίνακα
Η διαγραφή των περιεχομένων ενός της κλάσης vector μπορεί να γίνει μέσω της μεθόδου erase, η οποία έχει τις εξής δύο παραλλαγές:
iterator erase (iterator position)
: Διαγραφή της θέσης στην οποία δείχνει ο iterator position.iterator erase (iterator first, iterator last)
: Διαγραφή των περιεχομένων του vector από first (συμπεριλαμβανομένου) έως και last (μη συμπεριλαμβανομένου) [first,last).
Όταν μία συνάρτηση της STL λαμβάνει ως παραμέτρους δύο iterators first,last που προσδιορίζουν τμήμα ενός container και υποθέτοντας ότι το first προηγείται του last, το διάστημα το οποίο υπολογίζεται είναι πάντα από first (συμπεριλαμβανομένου) έως last (μη συμπεριλαμβανομένου).
- vector_erase_01.cpp
#include <vector> #include <list> #include <iostream> #include <iomanip> using namespace std; template<typename T> void print(vector<T> v) { for(auto it = v.cbegin(); it!=v.cend(); it++) cout << setw(3) << *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); while(ints.size() > 0) { auto middle = ints.begin() + ints.size()/2 - 1; ints.erase(middle, middle+2); // erase position middle, middle+1 print(ints); } }
Παρατηρήστε ότι η εγγραφή auto middle = ints.begin() + ints.size()/2 - 1;
προσθέτει τον ακέραιο ints.size()/2+1
στον iterator ints.begin()
.
Ο λόγος που μεταγλωττίζεται και λειτουργεί επιτυχώς η παραπάνω δήλωση είναι ότι η κλάση vector επιτρέπει τη χρήση Random Access Iterators.
- vector_erase_02.cpp
#include <vector> #include <list> #include <iostream> #include <iomanip> using namespace std; template<typename T> void print(vector<T> v) { for(auto it = v.cbegin(); it!=v.cend(); it++) cout << setw(3) << *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); while(ints.size() > 0) { ints.erase(ints.begin()); // erase the first element. ints.erase(ints.end()-1); // erase the laste element. print(ints); } }
- vector_erase_03.cpp
#include <vector> #include <list> #include <iostream> #include <iomanip> using namespace std; template<typename T> void print(vector<T> v) { for(auto it = v.cbegin(); it!=v.cend(); it++) cout << setw(3) << *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); ints.erase(ints.begin(), ints.end()); // erase everything! print(ints); // vector is empty }
Σημείωση: H κλάση vector υποστηρίζει τις συναρτήσεις push_back για ένθεση στο τέλος του πίνακα και pop_back για διαγραφή του τελευταίου στοιχείου του πίνακα.
Αποτελεί γενικότερο κανόνα της STL ότι παρέχει εξειδικευμένες συναρτήσεις για ένθεση και διαγραφή στην αρχή ή/και στο τέλος της δομής μόνο εάν η δομή υποστηρίζει τη γρήγορη ένθεση/διαγραφή στην αρχή ή/και στο τέλος αυτής.