Both sides previous revisionPrevious revisionNext revision | Previous revision |
cpp:stl:iterators [2021/06/06 18:44] – [STL Iterators] gthanos | cpp:stl:iterators [2023/05/30 18:48] (current) – gthanos |
---|
====== STL Iterators ====== | ====== STL Iterators ====== |
| |
Μία κλάση τύπου //iterator// έχει την δυνατότητα διάτρεξης μιας άλλης κλάσης που αντιπροσωπεύει μία δομή δεδομένων και ονομάζεται //container//. O //iterator// γνωρίζει την εσωτερική δομή της κλάσης και τον αλγόριθμο για να διαπεράσει το σύνολο των στοιχείων της. Κάθε //iterator// περιέχει κατ'ελάχιστο ένα δείκτη προς το τρέχον στοιχείο προς διάτρεξη του //container// στον οποίο αναφέρεται. Όλοι οι //iterators// ανεξάρτητα από τον τύπο τους υποστηρίζουν τις λειτουργίες: | Μία κλάση τύπου //iterator// έχει την δυνατότητα διάτρεξης μιας άλλης κλάσης που αντιπροσωπεύει μία δομή δεδομένων (τη γνωρίσαμε ως //container//). Η κλάση //iterator// γνωρίζει την εσωτερική δομή της κλάσης τύπου //container// και υλοποιεί τον αλγόριθμο για να διαπεράσει το σύνολο των στοιχείων της. Κάθε //iterator// περιέχει κατ'ελάχιστο ένα δείκτη προς το τρέχον στοιχείο προς διάτρεξη του //container// στον οποίο αναφέρεται. Όλοι οι //iterators// ανεξάρτητα από τον τύπο τους υποστηρίζουν τις λειτουργίες: |
* ''T::iterator it(other_it)'': copy-constructor | * ''T::iterator it(other_it)'': copy-constructor |
* ''it = other_it'': copy-assignment | * ''it = other_it'': copy-assignment |
* iterator destructor | * iterator destructor |
* ''++it'' ή ''it++'': μετακίνηση κατά μία θέση μέσα στον //container// και επιστροφή ενός //iterator// που δείχνει στην τρέχουσα θέση ή στην προηγούμενη θέση του //container// αντιστοίχως. | * ''++it'' ή ''it++'': μετακίνηση κατά μία θέση μέσα στον //container// και επιστροφή ενός //iterator// που δείχνει στην τρέχουσα θέση ή στην προηγούμενη θέση του //container// αντιστοίχως. |
| * Υπερφορτώνουν τους τελεστές ''=='' και ''!='' που υλοποιούν τη σύγκριση ως προς την ισότητα/ανισότητα δύο //iterators//. Δύο //iterators// είναι ίσοι εάν δείχνουν στην ίδια θέση του ιδίου //container// |
| |
Οι κατηγορίες (τύποι)των //iterator// είναι οι παρακάτω. Ένας //iterator// μπορεί να ανήκει σε περισσότερους από ένα τύπους. | Οι κατηγορίες (τύποι)των //iterator// είναι οι παρακάτω. Ένας //iterator// μπορεί να ανήκει σε περισσότερους από ένα τύπους. |
| |
* **Input Iterator:** Πρόκειται για έναν //iterator// από τον οποίο μπορούμε να διαβάσουμε το τρέχον στοιχείο της δομής στο οποίο δείχνει. Πρόκειται για έναν //iterator// ανάγνωσης του περιεχόμενου της δομής. Όλοι οι διαθέσιμοι //iterators// είναι //Input Iterators//. Παράδειγμα: | * **Input Iterator:** Πρόκειται για έναν //iterator// από τον οποίο μπορούμε μόνο να διαβάσουμε το τρέχον στοιχείο της δομής στο οποίο δείχνει. Πρόκειται για έναν //iterator// ανάγνωσης του περιεχόμενου της δομής. Όλοι οι διαθέσιμοι //iterators// είναι //Input Iterators//. Παράδειγμα: |
<code cpp> | |
| <code cpp input_iterator.cpp> |
| #include <vector> |
| #include <iostream> |
| #define SIZE 10 |
| using namespace std; |
| |
| int main() { |
| vector<int> ints; |
| for(int i=0; i<10; i++) |
| ints.push_back(SIZE-i); |
| |
for(vector<int>::const_iterator it=ints.cbegin(); it!=ints.cend(); it++) | for(vector<int>::const_iterator it=ints.cbegin(); it!=ints.cend(); it++) |
cout << *it << " "; | cout << *it << " "; |
cout << endl; | cout << endl; |
| } |
</code> | </code> |
* **Output Iterator:** Πρόκειται για έναν //iterator// μέσω του οποίου μπορούμε να γράψουμε στο τρέχον στοιχείο του //container//. Οι //iterators// που στον τύπο τους περιέχουν το συνθετικό //const_// (const_iterator, const_reverse_iterator) δεν ανήκουν στη συγκεκριμένη κατηγορία. Παραδείγματα: | * **Output Iterator:** Πρόκειται για έναν //iterator// μέσω του οποίου μπορούμε να διαβάσουμε και να γράψουμε στο τρέχον στοιχείο του //container//. Οι //iterators// που στον τύπο τους περιέχουν το συνθετικό //const_// (const_iterator, const_reverse_iterator) δεν ανήκουν στη συγκεκριμένη κατηγορία. Παραδείγματα: |
<code cpp> | <code cpp output_iterator.cpp> |
| #include <vector> |
| #include <iostream> |
| #define SIZE 10 |
| using namespace std; |
| |
| int main() { |
| vector<int> ints; |
| for(int i=0; i<10; i++) |
| ints.push_back(SIZE-i); |
| |
for(vector<int>::iterator it=ints.begin(); it!=ints.end(); it++) { | for(vector<int>::iterator it=ints.begin(); it!=ints.end(); it++) { |
*it += 10; // we modify container here | *it += 10; // we modify container here |
cout << *it << " "; | cout << *it << " "; |
} | } |
| cout << endl; |
| |
for(vector<int>::const_iterator it=ints.cbegin(); it!=ints.cend(); it++) { | for(vector<int>::const_iterator it=ints.cbegin(); it!=ints.cend(); it++) { |
cout << *it << " "; | cout << *it << " "; |
} | } |
| } |
</code> | </code> |
* **Bidirectional Iterator:** Πρόκειται για iterators που εκτός των πράξεων ''++it'', ''it++'' υποστηρίζουν και τις πράξεις ''%%--%%it'', ''it%%--%%''. //Bidirectional Iterators// είναι όλοι οι //iterators// με εξαίρεση εκείνούς που ανήκουν σε //Unordered Associative Containers// και οι //iterators// του //container forward_list// (απλά συνδεδεμένη λίστα). Παραδείγματα: | * **Bidirectional Iterator:** Πρόκειται για iterators που εκτός των πράξεων ''++it'', ''it++'' υποστηρίζουν και τις πράξεις ''%%--%%it'', ''it%%--%%''. //Bidirectional Iterators// είναι όλοι οι //iterators// με εξαίρεση εκείνούς που ανήκουν σε //Unordered Associative Containers// και οι //iterators// του //container forward_list// (απλά συνδεδεμένη λίστα). Παραδείγματα: |
<code cpp> | <code cpp bidirectional_iterator.cpp> |
for(vector<int>::iterator it=ints.cbegin(); it!=ints.cend(); it++) { | #include <iostream> |
cout << *it << " "; | #include <vector> |
} | #define SIZE 10 |
cout << endl; | |
| using namespace std; |
vector<int>::iterator it = ints.cend(); // starting from the end of the container | |
| int main() { |
| vector<int> ints(SIZE); |
| for(int i=0; i<SIZE; i++) |
| ints[i] = i+1; |
| |
| vector<int>::const_iterator it = ints.cend(); // starting from the end of the container |
while(true) { | while(true) { |
--it1; // move to the previous element | --it; // move to the previous element |
cout << *it1 << " "; | cout << *it << " "; |
if(it1 == ints.cbegin()) // stop when we reach the first element | if(it == ints.cbegin()) // stop when we reach the first element |
break; | break; |
} | } |
cout << endl; | cout << endl; |
| } |
</code> | </code> |
<WRAP tip center round> | |
Όταν μία κλάση υποστηρίζει //bidirectional iterators// τότε εκτός από τις μεθόδους //begin//, //end// (και τις συμμετρικές τους για //const iterators// //cbegin//, //cend//), διαθέτει και τις μεθόδους //rbegin//, //rend// (και τις συμμετρικές τους //crbegin//,//crend//). Οι iterators που επιστρέφονται από τις μεθόδους αυτές έχουν την ιδιότητα να διατρέχουν τη δομή του //container// από το τέλος προς την αρχή. Το παρακάτω παράδειγμα είναι αποκαλυπτικό της χρήσης αυτών των //iterator//. Σημειώστε ότι η διάτρεξη της λίστας από το τέλος προς την αρχή γίνεται με τη βοήθεια του τελεστή %++%, δηλαδή σε κάθε βήμα αυξάνει ο //reverse_iterator// κατά ένα. | Όταν μία κλάση υποστηρίζει //bidirectional iterators// τότε εκτός από τις μεθόδους //begin//, //end// (και τις συμμετρικές τους για //const iterators// //cbegin//, //cend//), διαθέτει και τις μεθόδους //rbegin//, //rend// (και τις συμμετρικές τους //crbegin//,//crend//). Οι iterators που επιστρέφονται από τις μεθόδους αυτές έχουν την ιδιότητα να διατρέχουν τη δομή του //container// από το τέλος προς την αρχή. Το παρακάτω παράδειγμα είναι αποκαλυπτικό της χρήσης αυτών των //iterator//. Σημειώστε ότι η διάτρεξη της λίστας από το τέλος προς την αρχή γίνεται με τη βοήθεια του τελεστή %% ++ %%, δηλαδή σε κάθε βήμα αυξάνει ο //reverse_iterator// κατά ένα. |
| |
<code cpp reverse_iterator.cpp> | <code cpp reverse_iterator.cpp> |
#include <iostream> | #include <iostream> |
#include <vector> | #include <vector> |
| #define SIZE 10 |
| |
int main () | int main () { |
{ | std::vector<int> myvector (SIZE); // SIZE default-constructed ints |
std::vector<int> myvector (5); // 5 default-constructed ints | |
int i=0; | int i=0; |
| |
std::vector<int>::reverse_iterator rit = myvector.rbegin(); | for (std::vector<int>::reverse_iterator rit = myvector.rbegin(); rit!= myvector.rend(); ++rit) |
for (; rit!= myvector.rend(); ++rit) | |
*rit = ++i; | *rit = ++i; |
| |
} | } |
</code> | </code> |
</WRAP> | |
* **Random Access Iterators:** Πρόκειται για //iterators// που υποστηρίζουν την πράξη της πρόσθεσης και τις αφαίρεσης μεταξύ του //iterator// και ενός ακεραίου αριθμού (η πράξη είναι ανάλογη της αριθμητικής δεικτών). Οι //iterators// αυτής της κατηγορίας υποστηρίζονται από τους //Sequence Containers// //array//, //vector// και //deque// αλλά όχι από τους //containers list// και //forward_list//. Παράδειγμα: | * **Random Access Iterators:** Πρόκειται για //iterators// που υποστηρίζουν την πράξη της πρόσθεσης και τις αφαίρεσης μεταξύ του //iterator// και ενός ακεραίου αριθμού (η πράξη είναι ανάλογη της αριθμητικής δεικτών). Οι //iterators// αυτής της κατηγορίας υποστηρίζονται από τους //Sequence Containers// //array//, //vector// και //deque// αλλά όχι από τους //containers list// και //forward_list//. Παράδειγμα: |
<code cpp> | <code cpp random_access_iterator.cpp> |
| #include <iostream> |
| #include <vector> |
| #define SIZE 10 |
| |
| using namespace std; |
| |
| int main() { |
| vector<int> ints(SIZE); |
| for(int i=0; i<SIZE; i++) |
| ints[i] = i+1; |
| |
vector<int>::iterator it = ints.cend(); // starting from the end of the container | vector<int>::const_iterator it = ints.cend(); // starting past the end of the container |
while(true) { | while(it > ints.cbegin()) { |
it -= 2; // move back by 2 elements | it -= 2; // move back by 2 elements |
cout << *it1 << " "; | cout << *it << " "; |
if(it1 <= ints.cbegin()) // stop when we reach or we have passed the first element | if(it <= ints.cbegin()) // stop when we reach or we have passed the first element |
break; | break; |
} | } |
cout << endl; | cout << endl; |
| } |
</code> | </code> |
| |
Τα παρακάτω παραδείγματα εφαρμόζονται σε //container// τύπου [[http://www.cplusplus.com/reference/vector/vector|vector]], όμως ο κώδικας της διάτρεξης είναι κοινός για όλους τους //containers//. | Τα παρακάτω παραδείγματα εφαρμόζονται σε //container// τύπου [[http://www.cplusplus.com/reference/vector/vector|vector]], όμως ο κώδικας της διάτρεξης είναι κοινός για όλους τους //containers//. |
| |
==== Διάτρεξη από την αρχή προς το τέλος ==== | ==== Διαπέραση από την αρχή προς το τέλος χωρίς μεταβολή του container ==== |
| |
| Η διαπέραση από την αρχή προς το τέλος υποστηρίζεται από το σύνολο των //iterators//. |
| |
<code cpp fw_iterate.cpp> | <code cpp fw_iterate.cpp> |
</WRAP> | </WRAP> |
| |
==== Διάτρεξη από το τέλος προς την αρχή ==== | ==== Διαπέραση από το τέλος προς την αρχή χωρίς μεταβολή του container ==== |
| |
| Η διαπέραση από τον τέλος προς την αρχή υποστηρίζεται μόνο από //bidirectional_iterators//. //Iterators// αυτού του τύπου διαθέτουν μόνον οι κλάσεις //array, list, vector, dequeue, set// και //map//. Δεν τους υποστηρίζουν οι κλάσεις //forward_list//, //unordered_set// και //unordered_map//. |
| |
<code cpp bw_iterate.cpp> | <code cpp bw_iterate.cpp> |
</code> | </code> |
| |
**Παρατήρηση:** Η συναρτήσεις [[http://www.cplusplus.com/reference/array/array/crbegin/|crbegin]] και [[http://www.cplusplus.com/reference/array/array/rbegin/|rbegin]] επιστρέφουν ένα //reverse_iterator// που δείχνει στο τελευταίο στοιχείο του //container//. Αντίστοιχα, οι συναρτήσεις [[http://www.cplusplus.com/reference/array/array/crend/|crend]] και [[http://www.cplusplus.com/reference/array/array/rend/|rend]] επιστρέφουν ένα //reverse_iterator// που δείχνει μετά το πρώτο στοιχείο του //container//. O //reverse_iterator// διατρέχει τα στοιχεία από το τέλος προς την αρχή του //container//. | **Παρατήρηση:** Η συναρτήσεις [[http://www.cplusplus.com/reference/array/array/crbegin/|crbegin]] και [[http://www.cplusplus.com/reference/array/array/rbegin/|rbegin]] επιστρέφουν ένα //reverse_iterator// που δείχνει στο τελευταίο στοιχείο του //container//. Αντίστοιχα, οι συναρτήσεις [[http://www.cplusplus.com/reference/array/array/crend/|crend]] και [[http://www.cplusplus.com/reference/array/array/rend/|rend]] επιστρέφουν ένα //reverse_iterator// που δείχνει αμέσως πριν από το πρώτο στοιχείο του //container//. Ο //reverse_iterator// διατρέχει τα στοιχεία από το τέλος προς την αρχή του //container//. |
| |
<WRAP tip 80% center round> | <WRAP tip 80% center round> |
</code> | </code> |
| |
<WRAP important center 80% round> | <WRAP tip center round> |
Κατά την δήλωση του //iterator// μπορείτε να χρησιμοποιήσετε τον πριοσδιοριστή ''auto'' αντί για τον πλήρη τύπο του //iterator//. O //compiler// έχει την "εξυπνάδα" να εξάγει τον τύπο δεδομένων της μεταβλητής που δηλώνεται μέσω του //keyward// ''auto'' από τον τύπο δεδομένων που βρίσκεται στα δεξιά του τελεστή %%=%%. Στα παραπάνω παραδείγματα, ο τύπος στα δεξιά του τελεστή %%=%% προσδιορίζεται από τον επιστρεφόμενο τύπο των συναρτήσεων //begin//, //rbegin// κλπ. | Κατά την δήλωση του //iterator// μπορείτε να χρησιμοποιήσετε τον πριοσδιοριστή ''auto'' αντί για τον πλήρη τύπο του //iterator//. O //compiler// έχει την "εξυπνάδα" να εξάγει τον τύπο δεδομένων της μεταβλητής που δηλώνεται μέσω του //keyward// ''auto'' από τον τύπο δεδομένων που βρίσκεται στα δεξιά του τελεστή %%=%%. Στα παραπάνω παραδείγματα, ο τύπος στα δεξιά του τελεστή %%=%% προσδιορίζεται από τον επιστρεφόμενο τύπο των συναρτήσεων //begin//, //rbegin// κλπ. |
| |
Εάν θέλουμε να υπολογίσουμε την απόσταση μεταξύ δύο //iterators// παρέχεται η συνάρτηση [[http://www.cplusplus.com/reference/iterator/distance/|distance]] η οποία υπολογίζει την απόσταση από το πρώτο όρισμα (//first//) έως το δεύτερο όρισμα (//last//) μετακινώντας τον δείκτη από //first// έως //last// με χρήση του τελεστή ''++''. Η συνάρτηση υποθέτει ότι το //first// βρίσκεται πριν από το //last//. | Εάν θέλουμε να υπολογίσουμε την απόσταση μεταξύ δύο //iterators// παρέχεται η συνάρτηση [[http://www.cplusplus.com/reference/iterator/distance/|distance]] η οποία υπολογίζει την απόσταση από το πρώτο όρισμα (//first//) έως το δεύτερο όρισμα (//last//) μετακινώντας τον δείκτη από //first// έως //last// με χρήση του τελεστή ''++''. Η συνάρτηση υποθέτει ότι το //first// βρίσκεται πριν από το //last//. |
| |
===== Κοινές συναρτήσεις για όλους τους containers για την επιστροφή των θέσεων αρχής και τέλους ===== | Δείτε το παρακάτω παράδειγμα χρήσης των συγκεκριμένων συναρτήσεων |
| |
| <code cpp advance_distance.cpp> |
| #include <iostream> // std::cout |
| #include <iterator> // std::advance |
| #include <list> // std::list |
| |
| int main () { |
| std::list<int> mylist; |
| for (int i=0; i<10; i++) mylist.push_back (i*10); |
| |
| for(std::list<int>::const_iterator it = mylist.cbegin(); it!=mylist.cend(); ++it) |
| std::cout << *it << " "; |
| std::cout << std::endl; |
| |
| std::list<int>::iterator it = mylist.begin(); |
| |
| std::advance (it,5); |
| |
| std::cout << "The sixth element in mylist is: " << *it << '\n'; |
| |
| std::list<int>::iterator it1 = mylist.begin(); |
| std::advance(it1,2); |
| |
| std::list<int>::iterator it2 = mylist.end(); |
| std::advance(it2,-2); |
| |
| std::cout << "Distance between it1 and it2 is: " << distance(it1, it2) << std::endl; |
| |
| return 0; |
| } |
| </code> |
| |
| ==== Κοινές συναρτήσεις για όλους τους containers για την επιστροφή των θέσεων αρχής και τέλους ==== |
| |
H //STL// παρέχει τις //templated// συναρτήσεις [[http://www.cplusplus.com/reference/iterator/begin/|begin]] και [[http://www.cplusplus.com/reference/iterator/end|end]] για την εύρεση της αρχικής και της τελικής θέσης οποιουδήποτε //container//. Οι συναρτήσεις αυτές είναι διαφορετικές από τις συναρτήσεις μέλη //begin// και //end// που περιέχει κάθε //container//. Παράδειγμα χρήσης των συναρτήσεων αυτών δίνεται παρακάτω: | H //STL// παρέχει τις //templated// συναρτήσεις [[http://www.cplusplus.com/reference/iterator/begin/|begin]] και [[http://www.cplusplus.com/reference/iterator/end|end]] για την εύρεση της αρχικής και της τελικής θέσης οποιουδήποτε //container//. Οι συναρτήσεις αυτές είναι διαφορετικές από τις συναρτήσεις μέλη //begin// και //end// που περιέχει κάθε //container//. Παράδειγμα χρήσης των συναρτήσεων αυτών δίνεται παρακάτω: |