| Both sides previous revisionPrevious revisionNext revision | Previous revision |
| cpp:stl:intro [2020/05/28 14:56] – [Αντιγραφή των στοιχείων προς ένθεση μέσα στον Container] gthanos | cpp:stl:intro [2023/05/30 18:30] (current) – [Η κλάση Student] gthanos |
|---|
| Βασικό χαρακτηριστικό της //STL// είναι ότι οι κλάσεις (//containers// και //iterators//) και οι συναρτήσεις των αλγορίθμων είναι γενικευμένες, ώστε να μπορούν να εφαρμοστούν με ασφάλεια σε οποιονδήποτε τύπο δεδομένων. Για να το επιτύχουν αυτό, χρησιμοποιούν [[cpp:templates|templates]]. | Βασικό χαρακτηριστικό της //STL// είναι ότι οι κλάσεις (//containers// και //iterators//) και οι συναρτήσεις των αλγορίθμων είναι γενικευμένες, ώστε να μπορούν να εφαρμοστούν με ασφάλεια σε οποιονδήποτε τύπο δεδομένων. Για να το επιτύχουν αυτό, χρησιμοποιούν [[cpp:templates|templates]]. |
| |
| ===== STL Containers ===== | ===== Η κλάση Student ===== |
| |
| Στο παρακάτω διάγραμμα περιέχονται το σύνολο των //containers// που παρέχει η βιβλιοθήκη //STL//. | Στα παραδείγματα που ακολουθούν στις επόμενες ενότητες συχνά χρησιμοποιείται η παρακάτω κλάση //Student//. |
| |
| {{ :cpp:stl:stl.png?800 |}} | <code cpp Student.hpp> |
| | #ifndef _STUDENT_HPP_ |
| | #define _STUDENT_HPP_ |
| | #include <cstring> |
| | #include <iostream> |
| |
| Οι //containers// της STL διακρίνονται στις εξής κατηγορίες: | class Student { |
| | private: |
| * **Sequence containers:** Αποθηκεύουν τα δεδομένα σειριακά, οδηγώντας σε χρόνους αναζήτησης γραμμικούς στο μέγεθος του πλήθους των στοιχείων που είναι αποθηκευμένα. Παραδείγματα τέτοιων //containers// είναι | char *name; |
| * **array:** Πίνακας σταθερού μεγέθους το οποίο προσδιορίζεται κατά τη δήλωση του πίνακα. | int aem; |
| * **vector:** Πίνακας μεταβλητού μεγέθους. Παρέχει δυνατότητα εισαγωγής στοιχείων σε οποιαδήποτε θέση του πίνακα. Η εισαγωγή/διαγραφή στο/από το τέλος του πίνακα είναι πράξη σταθερού κόστους, ενώ η εισαγωγή σε ή η διαγραφή από ενδιάμεση θέση συνεπάγεται την αντιγραφή των αποθηκευμένων στοιχείων που βρίσκονται μετά από τη συγκεκριμένη εγγραφή κατά μία θέση και είναι ανάλογη του μήκους αυτού. | public: |
| * **dequeue:** Πρόκειται για την γνωστή διπλοουρά που επιτρέπει την γρήγορη ένθεση και διαγραφή από την αρχή και το τέλος της ουράς. Για την εισαγωτή ή διαγραφή από ενδιάμεση θέση απαιτείται η αντιγραφή των στοιχείων που βρίσκονται πριν ή μετά τη συγκεκριμένη θέση κατά μία θέση και όπως και στην κλάση //vector// είναι ανάλογη του μήκους αυτού. | Student(); |
| * **list:** Πρόκειται για την διπλά συνδεδεμένη λίστα. Η λίστα δίνει την δυνατότητα διάτρεξης της δομής και προς τις δύο κατευθύνσεις, την εισαγωγή σε συγκεκριμένη θέση ή την διαγραφή στοιχείου από συγκεκριμένη θέση (δες σε αντιδιαστολή τη forward_list). Το κόστος αναζήτησης είναι ανάλογο των στοιχείων που είναι αποθηκευμένα στη λίστα, ενώ το κόστος εισαγωγής στοιχείου και διαγραφής στοιχείου είναι σταθερό. Η επιπλέον ευελιξία που παρέχεται σε σχέση με την forward list, έχει ως κόστος την διαχείριση ενός επιπλέον δείκτη σε κάθε κόμβο της λίστας σε σχέση με την απλά συνδεδεμένη λίστα. | Student(const char *name, int aem); |
| * **forward_list:** Πρόκειται για την απλά συνδεδεμένη λίστα. Η λίστα δίνει την δυνατότητα διάτρεξης της δομής προς τη μία κατεύθυνση (από την αρχή προς το τέλος). Για την εισαγωγή και διαγραφή θα πρέπει οπωσδήποτε να γνωρίζουμε τον προηγούμενο κόμβο (θέση). Το κόστος αναζήτησης είναι ανάλογο των στοιχείων που είναι αποθηκευμένα στη λίστα, ενώ το κόστος εισαγωγής στοιχείου και διαγραφής στοιχείου είναι σταθερό. | Student(const Student& ); |
| * **Container Adapters:** Χρησιμοποιούν εσωτερικά ένα //sequence container// για να υλοποιήσουν την λειτουργικότητα τους. Οι βασικές κλάσεις είναι οι εξής: | ~Student(); |
| * **stack:** Υλοποιεί μία δομή Last-In-First-Out (LIFO) με την βοήθεια ενός //vector// ή //deque//. | |
| * **queue:** Υλοποιεί μία δομή First-In-First-Out (FIFO) με την βοήθεια ενός //deque//. | |
| * **priority_queue:** Υλοποιεί μία ουρά προτεραιότητας. Προκειμένου να επιτευχθεί η προτεραιότητα κατά την εισαγωγή και διαγραφή στοιχείου εφαρμόζεται ο αλγόριθμος make_heap για την επίτευξη σωρού με λογαριθμικό κόστος στο μέγεθος των αποθηκευμένων στοιχείων της δομής. | |
| * **Associative Containers:** Πρόκειται για δομές που τα στοιχεία εισάγονται ταξινομημένα σε αύξουσα σειρά. Η αποθήκευση γίνεται σε ένα ισοζυγισμένο δέντρο αναζητήσεως (π.χ.[[wp>Red–black_tree]]) και ο χρόνος αναζήτησης, εισαγωγής και διαγραφής είναι λογαριθμικός στο μέγεθος των αποθηκευμένων στοιχείων. Διακρίνονται σε [[cpp:stl:set|sets]] που είναι σύνολα από __μοναδικά__ στοιχεία-κλειδιά και [[cpp:stl:map|maps]] που είναι συνολά από απεικονίσεις __μοναδικών__ στοιχείων-κλειδιών σε τιμές. Παραλλαγές των παραπάνω κλάσεων είναι τα **multiset** και **multimap** όπου δίνεται η επιπλέον δυνατότητα αποθήκευσης περισσότερων του ενός ίδιων κλειδιών στην υφιστάμενη δομή. | |
| * **Unordered Associative Containers:** Δομές ανάλογες με τους //Associative Containers// με την διαφορά ότι η αποθήκευση δεν γίνεται σε ισοζυγισμένο δέντρο αναζητήσεως, αλλά σε πίνακα κατακερματισμού ([[wp>Hash_table]]). Για τον λόγο αυτό, τα στοιχεία δεν αποθηκεύονται ταξινομημένα, αλλά με "τυχαία" σειρά. Η σειρά διάτρεξης τους αντιστοιχεί στη σειρά που τα κλειδιά είναι αποθηκευμένα στον πίνακα κατακερματισμού. Ο μέσος χρόνος αναζήτησης, εισαγωγής και διαγραφής είναι σταθερός στο μέγεθος των αποθηκευμένων στοιχείων, ενώ ο απαιτούμενος χώρος είναι περισσότερος (κατ' ελάχιστο διπλάσιος από τον αριθμό των αποθηκευμένων στοιχείων στην δομή). Οι κλάσεις **unordered_set** και **unordered_map** επιτρέπουν την αποθήκευση μοναδικών κλειδιών, ενώ οι δομές **unordered_multiset** και **unordered_multimap** επιτρέπουν την αποθήκευση περισσότερων του ενός ιδίων στοιχείων-κλειδιών στη δομή. | |
| | |
| | |
| ===== Κοινά χαρακτηριστικά για όλους τους containers ===== | |
| | |
| ==== Αντιγραφή των στοιχείων προς ένθεση μέσα σε ένα Container ==== | |
| | |
| Κατά την ένθεση ενός στοιχείου σε ένα //container//, δημιουργείται πάντοτε ένα αντίγραφο του στοιχείου σε αυτόν. Για παράδειγμα, για την ένθεση στοιχείων της κλάσης [[student|Student]] μέσα σε ένα //container list// τα στοιχεία θα αντιγραφούν εντός του //list// ως εξής: | |
| | |
| <code cpp student_list.cpp> | |
| #include <iostream> // std::cout | |
| #include <algorithm> // std::copy | |
| #include <list> // std::list | |
| #include <array> // std::array | |
| #include "Student.hpp" | |
| | |
| int main () { | |
| Student students[] = { Student("Peter_Pan", 1234), Student("Tinker_Bell", 1235) }; | |
| | |
| std::cerr << "----- Init list -----" << std::endl; | |
| std::list<Student> mylist; | |
| for(int i=0; i<2; i++) { | |
| mylist.push_back(students[i]); | |
| //mylist.insert(mylist.end(),students[i]); // equivalent with push_back | |
| //mylist.emplace_back(students[i].name, students[i].aem); | |
| //mylist.emplace(mylist.end(), students[i].name, students[i].aem); // equivalent with emplace_back | |
| } | |
| | |
| std::cerr << "-------------------------\n"; | char* getName() const; |
| std::cerr << "mylist contains:"; | int getAEM() const; |
| for (std::list<Student>::iterator it = mylist.begin(); it!=mylist.end(); ++it) | void setName(char*); |
| std::cerr << ' ' << *it; | void setAEM(int); |
| std::cerr << std::endl; | |
| std::cerr << "-------------------------\n"; | |
| | |
| return 0; | friend std::ostream& operator<<(std::ostream& out, const Student & st); |
| } | bool operator>(const Student& st) const; |
| </code> | bool operator<(const Student& st) const; |
| | Student& operator=(const Student& st); |
| | }; |
| |
| <WRAP todo 80% center round> | Student::Student(const char *name, int aem) { |
| Κατεβάστε, μεταγλωττίστε και εκτελέστε το παραπάνω πρόγραμμα. Ποιος κατασκευαστής καλείται κατά την κατασκευή των αντικείμενων μέσω της συνάρτησης //push_back//. Δοκιμάστε να αντικαταστήσετε τη //push_back// με την //emplace_back// και δοκιμάστε να μεταγλωττίσετε-εκτελέσετε ξανά. Παρατηρήστε τις διαφορές στις εκτυπώσεις στις δύο περιπτώσεις. | this->name = new char [strlen(name) + 1]; |
| </WRAP> | strcpy(this->name, name); |
| | this->aem = aem; |
| | std::cerr << "Argu Construct : " << *this << std::endl; |
| | } |
| |
| Κατά την εισαγωγή ενός στοιχείου μέσω των συναρτήσεων //insert//, //insert_back//, //emplace//, //emplace_back// δημιουργείται ένα νέο αντικείμενο μέσω στον //container//. Η δημιουργία του αντικείμένου γίνεται είτε μέσω του copy-constructor (μέθοδοι //insert//, //insert_back//) ή μέσω του κατασκευαστή που λαμβάνει ως παραμέτρους τους τύπους των ορισμάτων που περνιούνται στις μεθόδους //emplace// ή //emplace_back//. | Student::Student(const Student& st) { |
| | name = new char [strlen(st.name) + 1]; |
| | strcpy(name, st.name); |
| | aem = st.aem; |
| | std::cerr << "Copy Construct : " << *this << std::endl; |
| | } |
| |
| Αντιστοίχως, στο παρακάτω πρόγραμμα ανατίθεται σε ένα //container// τύπου //array// περιεχόμενα μέσω του τελεστή %%[]%%. Μεταγλωττίζοντας και εκτελώντας το πρόγραμμα θα παρατηρήσετε ότι καλείται ο τελεστής %%=%% (//operator=//) της κλάσης //Student//. | Student::Student() { |
| | this->name = nullptr; |
| | this->aem = 0; |
| | } |
| |
| <code cpp student_array.cpp> | Student::~Student() { |
| #include <iostream> // std::cout | if(name != nullptr) { |
| #include <algorithm> // std::copy | std::cerr << "Destruct: " << *this << std::endl; |
| #include <array> // std::array | delete []name; |
| #include <array> // std::array | |
| #include "Student.hpp" | |
| | |
| int main () { | |
| Student students[] = { Student("Peter_Pan", 1234), Student("Tinker_Bell", 1235) }; | |
| | |
| std::cerr << "----- Init array -----" << std::endl; | |
| std::array<Student,2> myarray; | |
| for(int i=0; i<2; i++) { | |
| myarray[i] = students[i]; | |
| } | } |
| | } |
| std::cerr << "-------------------------\n"; | |
| std::cerr << "myarray contains:"; | |
| for (std::array<Student,2>::iterator it = myarray.begin(); it!=myarray.end(); ++it) | |
| std::cerr << ' ' << *it; | |
| std::cerr << std::endl; | |
| std::cerr << "-------------------------\n"; | |
| | |
| return 0; | |
| } | |
| <code> | |
| |
| ==== Προσδιορισμός εύρους στοιχείων ==== | char* Student::getName() const { |
| | return name; |
| | } |
| |
| Όταν στην STL προσδιορίζεται ένα εύρος στοιχείων εντός ενός //container// μεταξύ των υποτιθέμενων θέσεων //**start**// και //**stop**// (προσδιορίζονται πάντοτε από //iterators//) το διάστημα το οποιό υπολογίζεται είναι από //**start**// (συμπεριλαμβανομένου) έως και //**stop**// (μη συμπεριλαμβανομένου). Δείτε το παρακάτω παράδειγμα, όπου αντιγράφονται τα περιεχόμενα του πίνακα //array// αρχικά στον πίνακα //myarray// και στη συνέχεια ένα μέρος από αυτά στη λιστα //mylist//. | int Student::getAEM() const { |
| | return aem; |
| | } |
| |
| <code cpp int_copy.cpp> | void Student::setName(char* name) { |
| #include <iostream> // std::cout | this->name != nullptr; |
| #include <algorithm> // std::copy | delete this->name; |
| #include <list> // std::list | this->name = new char [strlen(name) + 1]; |
| #include <array> // std::array | strcpy(this->name, name); |
| #include "Student.hpp" | } |
| #define SIZE 10 | |
| |
| int main () { | void Student::setAEM(int aem) { |
| int array[] = { 1,2,3,4,5,6,7,8,9,10 }; | this->aem = aem; |
| | |
| std::array<int,SIZE> myarray; | |
| for(int i=0; i<SIZE; i++) | |
| myarray[i] = array[i]; | |
| | |
| std::cerr << "myarray contains:"; | |
| for (std::array<int,SIZE>::iterator it = myarray.begin(); it!=myarray.end(); ++it) | |
| std::cerr << ' ' << *it; | |
| std::cerr << std::endl; | |
| | |
| std::list<int> mylist; | |
| mylist.assign(myarray.cbegin(), myarray.cbegin() + 3); | |
| std::cerr << "mylist contains:"; | |
| for (std::list<int>::iterator it = mylist.begin(); it!=mylist.end(); ++it) | |
| std::cerr << ' ' << *it; | |
| std::cerr << std::endl; | |
| | |
| return 0; | |
| } | } |
| </code> | |
| |
| <WRAP tip 80% center round> | Student& Student::operator=(const Student& st) { |
| Η μέθοδος [[http://www.cplusplus.com/reference/list/list/assign/|assign]] δημιουργεί ένα αντίγραφο των περιεχομένων ξεκινώντας από το πρώτο όρισμα (συμπεριλαμβανομένου) έως και το δεύτερο όρισμα (μη συμπεριλαμβανομένου). Στο παραπάνω παράδειγμα ξεκινά από τη θέση 0 του πίνακα (myarray.cbegin()) έως και τη θέση 2 (myarray.cbegin()+2). Η θέση myarray.cbegin()+3 που είναι το 2ο όρισμα δεν περιλαμβάνεται στο διάστημα. | if(name != nullptr) |
| </WRAP> | delete name; |
| | name = new char [strlen(st.name) + 1]; |
| | strcpy(name, st.name); |
| | aem = st.aem; |
| | std::cerr << "Copy : " << *this << std::endl; |
| | return *this; |
| | } |
| |
| Όπως θα δούμε και στη συνέχεια, οι //iterators// της //STL// διατρέχουν οποιαδήποτε δομή από τη θέση //begin()// (δείκτης στην πρώτη θέση περιεχομένων του //container//) έως //end()// (δείκτης αμέσως μετά την τελευταία θέση περιεχομένων του //container//). | std::ostream& operator<<(std::ostream& out, const Student& st) { |
| ===== Κοινές συναρτήσεις για όλους τους containers ===== | if(st.name != nullptr) |
| | out << st.name << " " << st.aem; |
| | return out; |
| | } |
| |
| ==== Εισαγωγή στοιχείου σε container ==== | bool Student::operator>(const Student& st) const { |
| | if(aem > st.aem) |
| | return true; |
| | return false; |
| | } |
| |
| Με εξαίρεση την κλάση [[array|std::array]] που το μέγεθος των πινάκων που δημιουργεί είναι σταθερό οι υπόλοιποι //containers// μπορούν να μεταβάλλουν το αριθμό των στοιχείων που αποθηκεύουν. Για την εισαγωγή ενός στοιχείου σε έναν //container// υπάρχει η συνάρτηση μέλους //insert//. Για //sequence containers// η //insert// λαμβάνει ως πρώτο όρισμα έναν //iterator// που δηλώνει τη θέση εισαγωγής | bool Student::operator<(const Student& st) const { |
| | if(aem < st.aem) |
| | return true; |
| | return false; |
| | } |
| | #endif |
| | </code> |
| |
