Differences

This shows you the differences between two versions of the page.

--- cpp:stl:vector [2020/05/27 16:07] – created gthanos
+++ cpp:stl:vector [2020/05/27 17:48] – [std::vector] gthanos
@@ Line 1: / Line 1: @@
 ====== std::vector ======
-Πρόκειται για μία δομή πίνακα του οποίου η χωρητικότητα μεταβάλλεται δυναμικά με βάση τις ανάγκες αποθήκευσης του προγράμματος. Η χωρητικότητα ενός vector μπορεί να είναι μεγαλύτερη από τον αριθμό των αποθηκευμένων στοιχείων που υπάρχουν σε αυτό. Η παρακάτω εικόνα είναι ενδεικτική της υφιστάμενης δομής δεδομένω που περιγράφει ένα //vector//.
+Πρόκειται για μία δομή πίνακα του οποίου η χωρητικότητα μεταβάλλεται δυναμικά με βάση τις ανάγκες αποθήκευσης του προγράμματος. Η παρακάτω εικόνα είναι ενδεικτική της υφιστάμενης δομής δεδομένω που περιγράφει ένα //vector//. Παρατηρήστε ότι η χωρητικότητα ενός vector μπορεί να είναι μεγαλύτερη από τον αριθμό των αποθηκευμένων στοιχείων του.
 {{ :cpp:stl:vector01.png?400 |}}
+**Σημείωση:** H δομή //vector// υποστηρίζει random access iterators.
+===== Επίδοσης της δομής =====
+  * Η πράξη της ένθεσης ή της διαγραφής από τον τέλος του πίνακα έχει σταθερό κόστος **(O(1))**.
+  * Η πράξη της ένθεσης ή της διαγραφής από το μέσο ή την αρχή του πίνακα συνεπάγεται την μετακίνηση όλων των στοιχείων που βρίσκονται δεξιότερα κατά μία θέση και η επίδοσης της εξαρτάται από την θέση της ένθεσης ή της διαγραφής σε σχέση με το τέλος του πίνακα. Ο επιμερισμένος χρόνος της συγκεκριμένης πράξης είναι γραμμικός στο μέγεθος των αποθηκευμένων στοιχείων του πίνακα **(Ο(Ν))**.
+  * Η πράξη της αναζήτησης είναι γραμμική στο μέγεθος των στοιχείων του πίνακα **(Ο(Ν))**.
+===== Πρόσβαση στα στοιχεία του πίνακα =====
+Για τη συνάρτηση //vector// ισχύει η πρόσβαση μέσω των συναρτήσεων [[http://www.cplusplus.com/reference/vector/vector/operator[]/|operator[] ]] και [[http://www.cplusplus.com/reference/vector/vector/at|at]] στα υφιστάμενη στοιχεία του //container//.
+<code cpp 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;
+  }
+}
+</code>
+===== Ένθεση στον πίνακα =====
+Όπως προαναφέρθηκε, η κλάση [[http://www.cplusplus.com/reference/vector/|vector]] παρέχει την δυνατότητα ένθεσης και διαγραφής στοιχείων, ώστε το μέγεθος των αποθηκευμένων στοιχείων του //vector// να μεταβάλλεται. Πιο συγκεκριμένα, η ένθεση μπορεί να γίνει μέσω των συναρτήσεων [[http://www.cplusplus.com/reference/vector/vector/insert/|insert]] (ένθεση σε οποιαδήποτε θέση του πίνακα μέσω ενός iterator) και [[http://www.cplusplus.com/reference/vector/vector/push_back|push_back]] ένθεση στο τέλος του πίνακα [[http://www.cplusplus.com/reference/vector/vector/push_back|push_back]].
+<code cpp 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);
+}
+</code>
+Η εκτύπωση του παραπάνω προγράμματος όσον αφορά το μέγεθος και τη χωρητικότητα του πίνακα είναι η εξής:
+<code>
+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
+</code>
+Παρατηρήστε ότι κάθε φορά που χρειάζεται να γίνει μεγένθυση του πίνακα (re-allocation) η χωρητικότητα διπλασιάζεται. Το παραπάνω εξασφαλίζει οτι το επιμέρισμένο κόστος αντιγραφής για κάθε re-allocation είναι σταθερό Ο(1) (δες σχετικά την ανάλυση της επίδοσης του ανακατακερματισμού στο βιβλίο των Δομών Δεδομένων του κ. Μποζάνη).
+===== Διαγραφή των περιεχομένων του πίνακα =====
+Η διαγραφή των περιεχομένων ενός της κλάσης //vector// μπορεί να γίνει μέσω της μεθόδου [[http://www.cplusplus.com/reference/vector/vector/erase/|erase]], η οποία έχει τις εξής δύο παραλλαγές:
+  * ''iterator erase (iterator position)'': Διαγραφή της θέσης στην οποία δείχνει ο //iterator// position.
+  * ''iterator erase (iterator first, iterator last)'': Διαγραφή των περιεχομένων του //vector// από //first// (συμπεριλαμβανομένου) έως και //last// (μη συμπεριλαμβανομένου) **[first,last)**.
+<WRAP important 80% center round>
+Όταν μία συνάρτηση της STL λαμβάνει ως παραμέτρους δύο //iterators// **first,last** που προσδιορίζουν τμήμα ενός //container// και υποθέτοντας ότι το **first** προηγείται του **last**, το διάστημα το οποίο υπολογίζεται είναι πάντα από **first** (συμπεριλαμβανομένου) έως **last** (μη συμπεριλαμβανομένου).
+</WRAP>
+<code cpp 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);
+  }
+}
+</code>
+<code cpp 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);
+  }
+}
+</code>
+<code cpp 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);
+  while(ints.size() > 0) {
+    ints.erase(ints.begin(), ints.end());    // erase everything!
+    print(ints);
+  }
+}
+</code>
+===== Ανάθεση των περιεχομένων του vector από οποιοδήποτε άλλο container =====
+Η ανάθεση των περιεχομένων ενός //vector// μέσω της συνάρτησης //assign//.
+<code cpp vector_assign.cpp>
+#include <iostream>
+#include <vector>
+#include <array>
+#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> v;
+  array<int,6> a = {10, 20, 30, 40, 50, 60};
+  v.assign(a.begin(), a.end());
+  print(v);
+}
+</code>