This is an old revision of the document!
Table of Contents
std::vector
Πρόκειται για μία δομή πίνακα του οποίου η χωρητικότητα μεταβάλλεται δυναμικά με βάση τις ανάγκες αποθήκευσης του προγράμματος. Η παρακάτω εικόνα είναι ενδεικτική της υφιστάμενης δομής δεδομένω που περιγράφει ένα vector. Παρατηρήστε ότι η χωρητικότητα ενός vector μπορεί να είναι μεγαλύτερη από τον αριθμό των αποθηκευμένων στοιχείων του.
Επίδοσης της δομής
- Η πράξη της ένθεσης ή της διαγραφής από τον τέλος του πίνακα έχει σταθερό κόστος (O(1)).
- Η πράξη της ένθεσης ή της διαγραφής από το μέσο ή την αρχή του πίνακα συνεπάγεται την μετακίνηση όλων των στοιχείων που βρίσκονται δεξιότερα κατά μία θέση και η επίδοσης της εξαρτάται από την θέση της ένθεσης ή της διαγραφής σε σχέση με το τέλος του πίνακα. Ο επιμερισμένος χρόνος της συγκεκριμένης πράξης είναι γραμμικός στο μέγεθος των αποθηκευμένων στοιχείων του πίνακα (Ο(Ν)).
- Η πράξη της αναζήτησης είναι γραμμική στο μέγεθος των στοιχείων του πίνακα (Ο(Ν)).
Ένθεση στον πίνακα
Όπως προαναφέρθηκε, η κλάση 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
Παρατηρήστε ότι κάθε φορά που χρειάζεται να γίνει μεγένθυση του πίνακα (re-allocation) η χωρητικότητα διπλασιάζεται. Το παραπάνω εξασφαλίζει οτι το επιμέρισμένο κόστος αντιγραφής για κάθε re-allocation είναι σταθερό Ο(1) (δες σχετικά την ανάλυση της επίδοσης του ανακατακερματισμού στο βιβλίο των Δομών Δεδομένων του κ. Μποζάνη).
Διαγραφή των περιεχομένων του πίνακα
- 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 pos = ints.begin() + ints.size()/2 - 1; ints.erase(pos, pos+2); // erase the two middle elements at every step. print(ints); } }
- 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; } template<typename T> void print_r(vector<T> v) { for(auto it = v.crbegin(); it!=v.crend(); 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(), ints.end()); // erase everything! print(ints); } }