Differences

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

--- cpp:stl:vector [2020/05/27 16:30] – [Ένθεση στον πίνακα] gthanos
+++ cpp:stl:vector [2020/05/27 16:54] – [Ένθεση στον πίνακα] gthanos
@@ Line 19: / Line 19: @@
 #include <list>
 #include <iostream>
+#include <iomanip>
 using namespace std;
@@ Line 25: / Line 26: @@
 void print(vector<T> v) {
   for(auto it = v.cbegin(); it!=v.cend(); it++)
-    cout << setw(4) << *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) (δες σχετικά την ανάλυση της επίδοσης του ανακατακερματισμού στο βιβλίο των Δομών Δεδομένων του κ. Μποζάνη).
+==== Διαγραφή των περιεχομένων του πίνακα ====
+<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;
 }
@@ Line 32: / Line 125: @@
 void print_r(vector<T> v) {
   for(auto it = v.crbegin(); it!=v.crend(); it++)
-    cout << setw(4) << *it;
+    cout << setw(3) << *it;
   cout << endl;
 }
@@ Line 43: / Line 136: @@
   }
   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>