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

This page is read only. You can view the source, but not change it. Ask your administrator if you think this is wrong.
====== std::vector ======

Πρόκειται για μία δομή πίνακα του οποίου η χωρητικότητα μεταβάλλεται δυναμικά με βάση τις ανάγκες αποθήκευσης του προγράμματος. Η παρακάτω εικόνα είναι ενδεικτική της υφιστάμενης δομής δεδομένων που περιγράφει ένα //vector//. Παρατηρήστε ότι η χωρητικότητα ενός [[http://www.cplusplus.com/reference/vector/vector/|std::vector]] μπορεί να είναι μεγαλύτερη από τον αριθμό των αποθηκευμένων στοιχείων του. H δομή //std::vector// υποστηρίζει random access iterators.

{{ :cpp:stl:vector03.png?600 |}}
===== Επίδοσης της δομής =====

  * Η πράξη της ένθεσης ή της διαγραφής από τον τέλος του πίνακα έχει σταθερό κόστος **(O(1))**. 
  * Η πράξη της ένθεσης ή της διαγραφής από το μέσο ή την αρχή του πίνακα συνεπάγεται την μετακίνηση όλων των στοιχείων που βρίσκονται δεξιότερα κατά μία θέση και η επίδοση της εξαρτάται από την θέση της ένθεσης ή της διαγραφής σε σχέση με το τέλος του πίνακα. Ο επιμερισμένος χρόνος της συγκεκριμένης πράξης είναι γραμμικός στο μέγεθος των αποθηκευμένων στοιχείων του πίνακα **(Ο(Ν))**.
  * Η πράξη της αναζήτησης είναι γραμμική στο μέγεθος των στοιχείων του πίνακα **(Ο(Ν))**.
  * Η πρόσβαση στο i-στο στοιχείο του πίνακα έχει κόστος 1.

===== Πρόσβαση στα στοιχεία του πίνακα =====

Για τη συνάρτηση //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>
#include <iostream>
#include <vector>
using namespace std;

int main () {
  vector<int> v(4);
  cout << "size    : " << v.size() << endl;
  cout << "capacity: " << 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>

Παρατηρήστε ότι κάθε φορά που γεμίζει ο πίνακας (δηλαδή size()==capacity()) και επιχειρούμε να προσθέσουμε ένα νέο στοιχείο, η χωρητικότητα του πίνακα διπλασιάζεται. Ο διπλασιασμός συνεπάγεται ότι τα στοιχεία του πίνακα αντιγράφονται σε νέο πίνακα διπλασίου μεγέθους. Αν και το κόστος της αντιγραφής είναι σημαντικό, το επιμερισμένο κόστος της πράξης αυτής είναι σταθερό Ο(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 middle = ints.begin() + ints.size()/2 - 1; 
    ints.erase(middle, middle+2);    // erase position middle, middle+1
    print(ints);
  }
}
</code>

<WRAP tip center round 80%>
Παρατηρήστε ότι η εγγραφή ''auto middle = ints.begin() + ints.size()/2 - 1;'' προσθέτει τον ακέραιο ''ints.size()/2+1'' στον iterator ''ints.begin()''. 
Ο λόγος που μεταγλωττίζεται και λειτουργεί επιτυχώς η παραπάνω δήλωση είναι ότι η κλάση //vector// επιτρέπει τη χρήση //Random Access Iterators//.
</WRAP>

<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);
  
  ints.erase(ints.begin(), ints.end());    // erase everything!
  print(ints);                             // vector is empty
}
</code>

<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]] για διαγραφή του τελευταίου στοιχείου του πίνακα. 

Αποτελεί γενικότερο κανόνα της STL ότι παρέχει εξειδικευμένες συναρτήσεις για ένθεση και διαγραφή στην αρχή ή/και στο τέλος της δομής μόνο εάν η δομή υποστηρίζει τη γρήγορη ένθεση/διαγραφή στην αρχή ή/και στο τέλος αυτής.
</WRAP>