Differences

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

--- cpp:stl:intro [2020/05/28 08:44] – [Κοινές συναρτήσεις για όλους τους containers για την επιστροφή των θέσεων αρχής και τέλους] gthanos
+++ cpp:stl:intro [2023/05/30 18:30] (current) – [Η κλάση Student] gthanos
@@ Line 5: / Line 5: @@
 Βασικό χαρακτηριστικό της //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** επιτρέπουν την αποθήκευση περισσότερων του ενός ιδίων στοιχείων-κλειδιών στη δομή.
-===== STL Iterators =====
-Μία κλάση τύπου //iterator// έχει την δυνατότητα διάτρεξης μιας άλλης κλάσης που αντιπροσωπεύει μία δομή δεδομένων (//container//). O //iterator// συνήθως γνωρίζει την εσωτερική δομή της κλάσης και πως να μετακινηθεί ανάμεσα στα στοιχεία της. Ο //iterator// περιέχει κατ'ελάχιστο ένα δείκτη προς το τρέχον στοιχείο προς διάτρεξη του //container//. Όλοι οι //iterators// ανεξάρτητα από τον τύπο τους υποστηρίζουν τις λειτουργίες:
-  * ''T::iterator it(other_it)'': copy-constructor
-  * ''it = other_it'': copy-assignment
-  * iterator destructor
-  * ''++it'' ή ''it++'': μετακίνηση κατά μία θέση μέσα στον //container// και επιστροφή ενός //iterator// που δείχνει στην τρέχουσα θέση ή στην προηγούμενη θέση του //container// αντιστοίχως.
-Οι κατηγορίες των //iterator// είναι οι εξής:
-  * **Input Iterator:** Πρόκειται για έναν //iterator// από τον οποίο μπορούμε να διαβάσουμε το στοιχείο της δομής στο οποίο δείχνει, δηλαδή για έναν //iterator// ανάγνωσης του περιεχόμενου της δομής. Όλοι οι διαθέσιμοι //iterators// είναι και //Input Iterators//. Παράδειγμα:
-<code cpp>
-  for(vector<int>::const_iterator it=ints.cbegin(); it!=ints.cend(); it++)
-    cout << *it << " ";
-  cout << endl;
-</code>
-  * **Output Iterator:** Πρόκειται για έναν //iterator// μέσω του οποίου μπορούμε να γράψουμε στο τρέχον στοιχείο του //container//. Οι //iterators// που στον τύπο τους περιέχουν το συνθετικό //const_// (const_iterator, const_reverse_iterator) δεν ανήκουν στη συγκεκριμένη κατηγορία. Παραδείγματα:
-<code cpp>
-  for(vector<int>::iterator it=ints.begin(); it!=ints.end(); it++) {
-    *it += 10;                         // we modify container here
-    cout << *it << " ";
-  }
-  for(vector<int>::const_iterator it=ints.cbegin(); it!=ints.cend(); it++) {
+  char* getName() const;
-    // *it += 10;       // this is not allowed for a const_iterator (only input iterator)
+  int getAEM() const;
-    cout << *it << " ";
+  void setName(char*);
-  }
+  void setAEM(int);
-</code>
-  * **Bidirectional Iterator:** Πρόκειται για iterators που εκτός των πράξεων ''++it'', ''it++'' υποστηρίζουν και τις πράξεις ''%%--%%it'', ''it%%--%%''. //Bidirectional Iterators// είναι όλοι οι //iterators// με εξαίρεση εκείνούς που ανήκουν σε //Unordered Associative Containers// και οι //iterators// του //container forward_list// (απλά συνδεδεμένη λίστα). Παραδείγματα:
-<code cpp>
-  for(vector<int>::iterator it=ints.cbegin(); it!=ints.cend(); it++) {
-    cout << *it << " ";
-  }
-  cout << endl;
-  vector<int>::iterator it = ints.cend(); // starting from the end of the container
+  friend std::ostream& operator<<(std::ostream& out, const Student & st);
-  while(true) {
+  bool operator>(const Student& st) const;
-    --it1;                                // move to the previous element
+  bool operator<(const Student& st) const;
-    cout << *it1 << " ";
+  Student& operator=(const Student& st);
-    if(it1 == ints.cbegin())              // stop when we reach the first element
+};
-      break;
-  }
-  cout << endl;
-</code>
-  * **Random Access Iterators:** Πρόκειται για //iterators// που υποστηρίζουν την πράξη της πρόσθεσης και τις αφαίρεσης μεταξύ του //iterator// και ενός ακεραίου αριθμού (η πράξη είναι ανάλογη της αριθμητικής δεικτών). Οι //iterators// αυτής της κατηγορίας υποστηρίζονται από τους //Sequence Containers// //array//, //vector// και //deque// αλλά όχι από τους //containers list// και //forward_list//. Παράδειγμα:
-<code cpp>
-  vector<int>::iterator it = ints.cend(); // starting from the end of the container
-  while(true) {
-    it -= 2;                              // move back by 2 elements
-    cout << *it1 << " ";
-    if(it1 <= ints.cbegin())              // stop when we reach or we have passed the first element
-      break;
-  }
-  cout << endl;
-</code>
-===== Κοινές συναρτήσεις για όλους τους iterators =====
+Student::Student(const char *name, int aem) {
+  this->name = new char [strlen(name) + 1];
-Για όλους τους //iterators// είναι διαθέσιμη η συνάρτηση [[http://www.cplusplus.com/reference/iterator/advance/|advance]] η οποία μετακινεί τον //iterator// κατά όσες θέσεις προσδιορίζει το δεύτερο όρισμα (μπορεί να πάρει και αρνητικές τιμές για //Bidirectional// και //Random Access// //iterators//). Η συνάρτηση λειτουργεί με χρήση του τελεστή ''++'', μετακινώντας τον //iterator// κατά μία θέση κάθε φορά, όσες φορές απαιτείται.
+  strcpy(this->name, name);
+  this->aem = aem;
-Εάν θέλουμε να υπολογίσουμε την απόσταση μεταξύ δύο //iterators// παρέχεται η συνάρτηση [[http://www.cplusplus.com/reference/iterator/distance/|distance]] η οποία υπολογίζει την απόσταση από το πρώτο όρισμα (//first//) έως το δεύτερο όρισμα (//last//) μετακινώντας τον δείκτη από //first// έως //last// με χρήση του τελεστή ''++''. Η συνάρτηση υποθέτει ότι το //first// βρίσκεται πριν από το //last//.
+  std::cerr << "Argu Construct : " << *this << std::endl;
-===== Κοινές συναρτήσεις για όλους τους containers για την επιστροφή των θέσεων αρχής και τέλους =====
-H //STL// παρέχει τις //templated// συναρτήσεις [[http://www.cplusplus.com/reference/iterator/begin/|begin]] και [[http://www.cplusplus.com/reference/iterator/end|end]] για την εύρεση της αρχικής και της τελικής θέσης οποιουδήποτε //container//. Οι συναρτήσεις αυτές είναι διαφορετικές από τις συναρτήσεις μέλη //begin// και //end// που περιέχει κάθε //container//. Παράδειγμα χρήσης των συναρτήσεων αυτών δίνεται παρακάτω:
-<code cpp iterator_begin_end.cpp>
-#include <iostream>     // std::cout
-#include <vector>       // std::vector, std::begin, std::end
-int main () {
-  int foo[] = {10,20,30,40,50};
-  std::vector<int> bar;
-  // iterate foo: inserting into bar
-  for (auto it = std::begin(foo); it!=std::end(foo); ++it)
-    bar.push_back(*it);
-  // iterate bar: print contents:
-  std::cout << "bar contains:";
-  for (auto it = std::begin(bar); it!=std::end(bar); ++it)
-    std::cout << ' ' << *it;
-  std::cout << '\n';
-  return 0;
 }
-</code>
-==== Διάτρεξη οποιαδήποτε δομής με χρήση iterator ====
-Τα παρακάτω παραδείγματα εφαρμόζονται σε //container// τύπου [[http://www.cplusplus.com/reference/vector/vector|vector]], όμως ο κώδικας της διάτρεξης είναι κοινός για όλους τους //containers//.
-=== Διάτρεξη από την αρχή προς το τέλος ===
-<code cpp fw_iterate.cpp>
-#include <vector>
-#include <iostream>
-#define SIZE 10
-using namespace std;
-int main() {
+Student::Student(const Student& st) {
-  vector<int> ints;
+  name = new char [strlen(st.name) + 1];
-  for(int i=0; i<10; i++)
+  strcpy(name, st.name);
-    ints.push_back(SIZE-i);
+  aem = st.aem;
+  std::cerr << "Copy Construct : " << *this << std::endl;
-  for(vector<int>::const_iterator it=ints.cbegin(); it!=ints.cend(); it++)
-    cout << *it << " ";
-  cout << endl;
 }
-</code>
-**Παρατήρηση:** Η συναρτήσεις [[http://www.cplusplus.com/reference/array/array/cbegin/|cbegin]] και [[http://www.cplusplus.com/reference/array/array/begin/|begin]] επιστρέφουν ένα //iterator// που δείχνει στο πρώτο στοιχείο του //container//. Αντίστοιχα, οι συναρτήσεις [[http://www.cplusplus.com/reference/array/array/cend/|cend]] και [[http://www.cplusplus.com/reference/array/array/end/|end]] επιστρέφουν ένα //iterator// που δείχνει μετά το τελευταίο στοιχείο του //container//. O //iterator// διατρέχει τα στοιχεία από την αρχή προς το τέλος του //container//.
+Student::Student() {
+  this->name = nullptr;
-<WRAP tip 80% center round>
+  this->aem = 0;
-Χρησιμοποιούμε τις συναρτήσεις [[http://www.cplusplus.com/reference/vector/vector/cbegin/|cbegin]] και [[http://www.cplusplus.com/reference/vector/vector/cend/|cend]], διότι οι συγκεκριμένες επιστρέφουν αντικείμενο τύπου ''const_iterator'' και όχι ''iterator''. Στην περίπτωση που δεν θέλουμε να μεταβάλλουμε τα περιεχόμενα του υφιστάμενου //container// η χρήση //const_iterator// είναι ασφαλέστερη διότι ο //compiler// θα εμφανίσει λάθος σε οποιαδήποτε προσπάθεια μεταβολής.
-</WRAP>
-=== Διάτρεξη από το τέλος προς την αρχή ===
-<code cpp bw_iterate.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_reverse_iterator it=ints.crbegin(); it!=ints.crend(); it++)
-    cout << *it << " ";
-  cout << endl;
 }
-</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//.
-<WRAP tip 80% center round>
-Ομοίως, χρησιμοποιούμε τις συναρτήσεις [[http://www.cplusplus.com/reference/vector/vector/crbegin/|crbegin]] και [[http://www.cplusplus.com/reference/vector/vector/crend/|crend]], διότι οι συγκεκριμένες επιστρέφουν ''const_reverse_iterator'' και όχι ''reverse_iterator''. Στην περίπτωση που δεν θέλουμε να μεταβάλλουμε τα περιεχόμενα του υφιστάμενου //container// η χρήση //const_reverse_iterator// είναι ασφαλέστερη για τους λόγους που τεκμηριώθηκαν παραπάνω.
-</WRAP>
-=== Διάτρεξη από την αρχή προς το τέλος και μεταβολή του container ===
-<code cpp fw_iterate_modify.cpp>
-#include <vector>
-#include <iostream>
-#define SIZE 10
-using namespace std;
-int main() {
+Student::~Student() {
-  vector<int> ints;
+  if(name != nullptr) {
-  for(int i=0; i<10; i++)
+    std::cerr << "Destruct: " << *this << std::endl;
-    ints.push_back(SIZE-i);
+    delete []name;
-  for(vector<int>::iterator it=ints.begin(); it!=ints.end(); it++) {
-    *it += 10;                         // we modify container here
-    cout << *it << " ";
   }
-  cout << endl;
 }
-</code>
-=== Διάτρεξη από το τέλος προς την αρχή και μεταβολή του container ===
+char* Student::getName() const {
+  return name;
+}
-<code cpp bw_iterate_modify.cpp>
+int Student::getAEM() const {
-#include <vector>
+  return aem;
-#include <iostream>
+}
-#define SIZE 10
-using namespace std;
-int main() {
+void Student::setName(char* name) {
-  vector<int> ints;
+  this->name != nullptr;
-  for(int i=0; i<10; i++)
+  delete this->name;
-    ints.push_back(SIZE-i);
+  this->name = new char [strlen(name) + 1];
+  strcpy(this->name, name);
-  for(vector<int>::reverse_iterator it=ints.rbegin(); it!=ints.rend(); it++) {
-    *it += 10;                         // we modify container here
-    cout << *it << " ";
-  }
-  cout << endl;
 }
-</code>
+void Student::setAEM(int aem) {
+  this->aem = aem;
+}
-<WRAP important center 80% round>
+Student& Student::operator=(const Student& st) {
-Κατά την δήλωση του //iterator// μπορείτε να χρησιμοποιήσετε τον πριοσδιοριστή ''auto'' αντί για τον πλήρη τύπο του //iterator//. O //compiler// έχει την "εξυπνάδα" να εξάγει τον τύπο δεδομένων της μεταβλητής που δηλώνεται μέσω του //keyward// ''auto'' από τον τύπο δεδομένων που βρίσκεται στα δεξιά του τελεστή %%=%%. Στα παραπάνω παραδείγματα, ο τύπος στα δεξιά του τελεστή %%=%% προσδιορίζεται από τον επιστρεφόμενο τύπο των συναρτήσεων //begin//, //rbegin// κλπ.
+  if(name != nullptr)
+    delete name;
+  name = new char [strlen(st.name) + 1];
+  strcpy(name, st.name);
+  aem = st.aem;
+  std::cerr << "Copy : " << *this << std::endl;
+  return *this;
+}
-Στο προηγούμενο παράδειγμα, η διάτρεξη από το τέλος προς την αρχή με μεταβολή του //container// θα μπορούσε να γραφεί εναλλακτικά (και συντομότερα) ως εξής:
+std::ostream& operator<<(std::ostream& out, const Student& st) {
+  if(st.name != nullptr)
+    out << st.name << " " << st.aem;
+  return out;
+}
-<code cpp bw_iterate_modify.cpp>
+bool Student::operator>(const Student& st) const {
-#include <vector>
+  if(aem > st.aem)
-#include <iostream>
+    return true;
-#define SIZE 10
+  return false;
-using namespace std;
+}
-int main() {
+bool Student::operator<(const Student& st) const {
-  vector<int> ints;
+  if(aem < st.aem)
-  for(int i=0; i<10; i++)
+    return true;
-    ints.push_back(SIZE-i);
+  return false;
-  for(auto it=ints.rbegin(); it!=ints.rend(); it++) {
-    *it += 10;                         // we modify container here
-    cout << *it << " ";
-  }
-  cout << endl;
 }
+#endif
 </code>
-</WRAP>
-===== STL Algorithms =====
-//TODO