Differences

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

--- cpp:stl:vector [2020/05/27 16:14] – gthanos
+++ cpp:stl:vector [2020/05/27 17:29] – gthanos
@@ Line 7: / Line 7: @@
 ===== Επίδοσης της δομής =====
-  * Η πράξη της ένθεσης ή της διαγραφής από τον τέλος του πίνακα είναι σταθερού χρόνου (O(1)).
+  * Η πράξη της ένθεσης ή της διαγραφής από τον τέλος του πίνακα έχει σταθερό κόστος **(O(1))**.
-  * Η πράξη της ένθεσης ή της διαγραφής από το μέσο ή την αρχή του πίνακα συνεπάγεται την μετακίνηση όλων των στοιχείων που βρίσκονται δεξιότερα κατά μία θέση και εξαρτάται από την θέση της ένθεσης ή της διαγραφής σε σχέση με το τέλος του πίνακα. Ο επιμερισμένος χρόνος της συγκεκριμένης πράξης είναι γραμμικός στο μέγεθος των αποθηκευμένων στοιχείων του πίνακα (Ο(Ν)).
+  * Η πράξη της ένθεσης ή της διαγραφής από το μέσο ή την αρχή του πίνακα συνεπάγεται την μετακίνηση όλων των στοιχείων που βρίσκονται δεξιότερα κατά μία θέση και η επίδοσης της εξαρτάται από την θέση της ένθεσης ή της διαγραφής σε σχέση με το τέλος του πίνακα. Ο επιμερισμένος χρόνος της συγκεκριμένης πράξης είναι γραμμικός στο μέγεθος των αποθηκευμένων στοιχείων του πίνακα **(Ο(Ν))**.
-  * Η πράξη της αναζήτησης είναι γραμμική στο μέγεθος των στοιχείων του πίνακα (Ο(Ν)).
+  * Η πράξη της αναζήτησης είναι γραμμική στο μέγεθος των στοιχείων του πίνακα **(Ο(Ν))**.
+==== Ένθεση στον πίνακα ====
+Όπως προαναφέρθηκε, η κλάση [[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>