Αντικειμενοστραφής Προγραμματισμός

User Tools

Site Tools

Trace:
cpp:stl:vector

Differences

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

Link to this comparison view

Both sides previous revisionPrevious revision
Next revision		Previous revision
cpp:stl:vector [2020/05/27 18:05] – [Επίδοσης της δομής] gthanoscpp:stl:vector [2023/05/29 19:12] (current) – [Πρόσβαση στα στοιχεία του πίνακα] gthanos
Line 1: Line 1:
 ====== std::vector ====== ====== std::vector ======
  
-Πρόκειται για μία δομή πίνακα του οποίου η χωρητικότητα μεταβάλλεται δυναμικά με βάση τις ανάγκες αποθήκευσης του προγράμματος. Η παρακάτω εικόνα είναι ενδεικτική της υφιστάμενης δομής δεδομένω που περιγράφει ένα //vector//. Παρατηρήστε ότι η χωρητικότητα ενός vector μπορεί να είναι μεγαλύτερη από τον αριθμό των αποθηκευμένων στοιχείων του. +Πρόκειται για μία δομή πίνακα του οποίου η χωρητικότητα μεταβάλλεται δυναμικά με βάση τις ανάγκες αποθήκευσης του προγράμματος. Η παρακάτω εικόνα είναι ενδεικτική της υφιστάμενης δομής δεδομένων που περιγράφει ένα //vector//. Παρατηρήστε ότι η χωρητικότητα ενός [[http://www.cplusplus.com/reference/vector/vector/|std::vector]] μπορεί να είναι μεγαλύτερη από τον αριθμό των αποθηκευμένων στοιχείων του. H δομή //std::vector// υποστηρίζει random access iterators.
- +
-{{ :cpp:stl:vector01.png?400 |}} +
- +
-**Σημείωση:** H δομή //vector// υποστηρίζει random access iterators.+
  
 +{{ :cpp:stl:vector03.png?600 |}}
 ===== Επίδοσης της δομής ===== ===== Επίδοσης της δομής =====
  
Line 12: Line 9:
   * Η πράξη της ένθεσης ή της διαγραφής από το μέσο ή την αρχή του πίνακα συνεπάγεται την μετακίνηση όλων των στοιχείων που βρίσκονται δεξιότερα κατά μία θέση και η επίδοση της εξαρτάται από την θέση της ένθεσης ή της διαγραφής σε σχέση με το τέλος του πίνακα. Ο επιμερισμένος χρόνος της συγκεκριμένης πράξης είναι γραμμικός στο μέγεθος των αποθηκευμένων στοιχείων του πίνακα **(Ο(Ν))**.   * Η πράξη της ένθεσης ή της διαγραφής από το μέσο ή την αρχή του πίνακα συνεπάγεται την μετακίνηση όλων των στοιχείων που βρίσκονται δεξιότερα κατά μία θέση και η επίδοση της εξαρτάται από την θέση της ένθεσης ή της διαγραφής σε σχέση με το τέλος του πίνακα. Ο επιμερισμένος χρόνος της συγκεκριμένης πράξης είναι γραμμικός στο μέγεθος των αποθηκευμένων στοιχείων του πίνακα **(Ο(Ν))**.
   * Η πράξη της αναζήτησης είναι γραμμική στο μέγεθος των στοιχείων του πίνακα **(Ο(Ν))**.   * Η πράξη της αναζήτησης είναι γραμμική στο μέγεθος των στοιχείων του πίνακα **(Ο(Ν))**.
 +  * Η πρόσβαση στο i-στο στοιχείο του πίνακα έχει κόστος 1.
  
 ===== Πρόσβαση στα στοιχεία του πίνακα ===== ===== Πρόσβαση στα στοιχεία του πίνακα =====
  
-Για τη συνάρτηση //vector// ισχύει η πρόσβαση μέσω των συναρτήσεων [[http://www.cplusplus.com/reference/vector/vector/operator[]/|operator[] ]] και [[http://www.cplusplus.com/reference/vector/vector/at|at]] στα υφιστάμενη στοιχεία του //container//. +Για τη συνάρτηση //vector// ισχύει η πρόσβαση μέσω των συναρτήσεων [[http://www.cplusplus.com/reference/vector/vector/operator[]/|operator[] ]] και [[http://www.cplusplus.com/reference/vector/vector/at|at]] στα υφιστάμενη στοιχεία του //container//. Η διαφορά ανάμεσα στη συνάρτηση [[http://www.cplusplus.com/reference/vector/vector/at|at]] και στην υπερφόρτωση του τελεστή [[http://www.cplusplus.com/reference/vector/vector/operator[]/|operator[] ]] είναι ότι η πρώτη παράγει ένα [[https://cplusplus.com/reference/stdexcept/out_of_range/| std::out_of_range]] exception, εάν προσπελάσουμε μία θέση του πίνακα που βρίσκεται εκτός ορίων, ενώ η δεύτερη δεν σας προστατεύει με αποτέλεσμα να εισαχθούν λάθη στο πρόγραμμα ή αν είστε πιο τυχεροι να λάβετε //segmenation fault//.
  
 <code cpp vector_access.cpp> <code cpp vector_access.cpp>
Line 24: Line 22:
 int main () { int main () {
   vector<int> v(4);   vector<int> v(4);
-  cout << "size: " << v.size() << endl; +  cout << "size    : " << v.size() << endl; 
-  cout << "capa: " << v.capacity() << endl;+  cout << "capacity: " << v.capacity() << endl;
  
   try {   try {
Line 98: Line 96:
 </code> </code>
  
-Παρατηρήστε ότι κάθε φορά που χρειάζεται να γίνει μεγένθυση του πίνακα (re-allocation) η χωρητικότητα διπλασιάζεται. Το παραπάνω εξασφαλίζει οτι το επιμέρισμένο κόστος αντιγραφής για κάθε re-allocation είναι σταθερό Ο(1) (δες σχετικά την ανάλυση της επίδοσης του ανακατακερματισμού στο βιβλίο των Δομών Δεδομένων του κ. Μποζάνη).+Παρατηρήστε ότι κάθε φορά που γεμίζει ο πίνακας (δηλαδή size()==capacity()) και επιχειρούμε να προσθέσουμε ένα νέο στοιχείο, η χωρητικότητα του πίνακα διπλασιάζεται. Ο διπλασιασμός συνεπάγεται ότι τα στοιχεία του πίνακα αντιγράφονται σε νέο πίνακα διπλασίου μεγέθους. Αν και το κόστος της αντιγραφής είναι σημαντικό, το επιμερισμένο κόστος της πράξης αυτής είναι σταθερό Ο(1), μην αλλάζοντας την επίδοση της δομής.
  
 ===== Διαγραφή των περιεχομένων του πίνακα ===== ===== Διαγραφή των περιεχομένων του πίνακα =====
Line 135: Line 133:
      
   while(ints.size() > 0) {   while(ints.size() > 0) {
-    auto pos = ints.begin() + ints.size()/2 - 1;  +    auto middle = ints.begin() + ints.size()/2 - 1;  
-    ints.erase(pos, pos+2);         // erase the two middle elements at every step.+    ints.erase(middle, middle+2);    // erase position middle, middle+1
     print(ints);     print(ints);
   }   }
Line 143: Line 141:
  
 <WRAP tip center round 80%> <WRAP tip center round 80%>
-Παρατηρήστε ότι η εγγραφή ''auto pos = ints.begin() + ints.size()/2 - 1;'' προσθέτει τον ακέραιο ''ints.size()/2+1'' στον iterator ''ints.begin()''. +Παρατηρήστε ότι η εγγραφή ''auto middle = ints.begin() + ints.size()/2 - 1;'' προσθέτει τον ακέραιο ''ints.size()/2+1'' στον iterator ''ints.begin()''. 
 Ο λόγος που μεταγλωττίζεται και λειτουργεί επιτυχώς η παραπάνω δήλωση είναι ότι η κλάση //vector// επιτρέπει τη χρήση //Random Access Iterators//. Ο λόγος που μεταγλωττίζεται και λειτουργεί επιτυχώς η παραπάνω δήλωση είναι ότι η κλάση //vector// επιτρέπει τη χρήση //Random Access Iterators//.
 </WRAP> </WRAP>
Line 201: Line 199:
   print(ints);   print(ints);
      
-  while(ints.size() > 0) { +  ints.erase(ints.begin(), ints.end());    // erase everything! 
-    ints.erase(ints.begin(), ints.end());    // erase everything! +  print(ints);                             // vector is empty
-    print(ints); +
-  }+
 } }
 </code> </code>
  
-===== Ανάθεση των περιεχομένων του vector από οποιοδήποτε άλλο container =====+<WRAP important 80% center round> 
 +**Σημείωση:** H κλάση //vector// υποστηρίζει τις συναρτήσεις [[http://www.cplusplus.com/reference/vector/vector/push_back/|push_back]] για ένθεση στο τέλος του πίνακα και [[http://www.cplusplus.com/reference/vector/vector/pop_back/|pop_back]] για διαγραφή του τελευταίου στοιχείου του πίνακα. 
  
-Η ανάθεση των περιεχομένων ενός //vector// μέσω της συνάρτησης //assign//.  +Αποτελεί γενικότερο κανόνα της STL ότι παρέχει εξειδικευμένες συναρτήσεις για ένθεση και διαγραφή στην αρχή ή/και στο τέλος της δομής μόνο εάν η δομή υποστηρίζει τη γρήγορη ένθεση/διαγραφή στην αρχή ή/και στο τέλος αυτής. 
- +</WRAP>
-<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>+
  
  
  
cpp/stl/vector.1590602700.txt.gz · Last modified: 2020/05/27 17:05 (external edit)