Differences

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

--- cpp:stl:set [2020/05/29 13:06] – gthanos
+++ cpp:stl:set [2023/05/30 11:04] (current) – [Παράδειγμα ένθεσης και διάτρεξης ενός set] gthanos
@@ Line 3: / Line 3: @@
 Ένα [[http://www.cplusplus.com/reference/set/set/|std::set]] αποτελεί ένα σύνολο μοναδικών στοιχείων. Τα στοιχεία αποθηκεύονται εσωτερικά σε ένα ισοζυγισμένο δέντρο αναζητήσεως (π.χ.[[wp>Red–black_tree]], [[wp>AVL_tree]]).
-Η κατάταξη ενός νέου στοιχείου γίνεται πάντα μέσω σύγκρισης με τα υπόλοιπα στοιχεία που είναι αποθηκευμένα στην δομή. Για τον λόγο αυτό, απαραίτητη προϋπόθεση για τη λειτουργία του //set// είναι για τους τύπους δεδομένων που αποθηκεύονται να παρέχονται οι τελεστές σύγκρισης %%<%% και %%>%%. Δύο στοιχεία θεωρούνται είναι σε ένα //set// εάν η παρακάτω λογική έκφραση είναι αληθής.
+Η κατάταξη ενός νέου στοιχείου γίνεται πάντα μέσω σύγκρισης με τα υπόλοιπα στοιχεία που είναι αποθηκευμένα στην δομή. Για τον λόγο αυτό, απαραίτητη προϋπόθεση για τη λειτουργία του //set// είναι για τους τύπους δεδομένων που αποθηκεύονται να παρέχονται ο τελεστής σύγκρισης %%<%%. Δύο στοιχεία ιδίου τύπου θεωρούνται ίσα σε ένα //set// εάν η παρακάτω λογική έκφραση είναι αληθής.
 <code cpp>
 if(!(a < b) && !(b < a))
-<code>
+</code>
-Ένα [[http://www.cplusplus.com/reference/set/multiset/|std::multiset]] αποτελεί ένα σύνολο όχι απαραίτητα μοναδικών στοιχείων, τα οποία είναι αποθηκευμένα σε ένα ισοζυγισμένο δέντρο αναζητήσεως. Ο τρόπος σύγκρισης και η κατάταξη των στοιχείων είναι παρόμοια με την επίπλέον σημείωση ότι το δέντρο επιτρέπει την εμφάνιση ενός κλειδιού περισσότερες από μία φορές.
+Ένα [[http://www.cplusplus.com/reference/set/multiset/|std::multiset]] αποτελεί ένα σύνολο όχι απαραίτητα μοναδικών στοιχείων (μπορεί να είναι, μπορεί και να μην είναι μοναδικά), τα οποία είναι αποθηκευμένα σε ένα ισοζυγισμένο δέντρο αναζητήσεως (όπως το //set//). Ο τρόπος σύγκρισης και η κατάταξη των στοιχείων είναι όμοια με την επίπλέον σημείωση ότι το δέντρο επιτρέπει την εμφάνιση ενός κλειδιού περισσότερες από μία φορές.
-Στα παρακάτω σχήματα διακρίνεται η δομή ενός [[http://www.cplusplus.com/reference/set/set/|std::set]] και ενός [[http://www.cplusplus.com/reference/set/multiset/|std::multiset]].
+Στα παρακάτω σχήματα διακρίνεται η δομή ενός [[http://www.cplusplus.com/reference/set/set/|std::set]] και ενός [[http://www.cplusplus.com/reference/set/multiset/|std::multiset]], όπου τα στοιχεία είναι ακέραιοι.
 | {{ :cpp:stl:set01.png? |}}| {{ :cpp:stl:multiset01.png? |}} |
 |  **Σχήμα 1. std::set**  |  **Σχήμα 2. std::multiset**  |
+Το προγραμματιστικό //interface// των //set// και //multiset// είναι κοινό και έχει καλυφθεί στις προηγούμενες ενότητες.
@@ Line 23: / Line 25: @@
   * Η πρόσβαση στο i-στο στοιχείο της δομής δεν υφίσταται.
   * Η διάτρεξη των στοιχείων γίνεται ξεκινώντας από το μικρότερο στοιχείο και καταλήγοντας στο μεγαλύτερο στοιχείο της δομής.
+===== Παράδειγμα ένθεσης και διάτρεξης ενός set =====
+=== Παράδειγμα 1ο - std::string ===
+<code cpp string_set.cpp>
+#include <set>
+#include <string>
+#include <iostream>
+template<typename T>
+void print(std::set<T> s) {
+  for(auto it = s.cbegin(); it!=s.cend(); it++)
+    std::cout << *it << " ";
+  std::cout << std::endl;
+}
+int main(int argc, char *argv[]) {
+  std::set<std::string> strset;
+  strset.emplace("orange");
+  strset.emplace("apple");
+  strset.emplace("mango");
+  strset.emplace("cherry");
+  strset.emplace("melon");
+  strset.emplace("apricot");
+  strset.emplace("pineapple");
+  strset.emplace("mango");
+  strset.emplace("apricot");
+  strset.emplace("apple");
+  strset.emplace("apple");
+  print(strset);
+  return 0;
+}
+</code>
+=== Παράδειγμα 2ο - Student ===
+Κατεβάστε την κλάση //Student// από [[https://courses.e-ce.uth.gr/ECE326/doku.php?do=export_code&id=cpp:stl:intro&codeblock=0|εδώ]].
+<code cpp student_set.cpp>
+#include <set>
+#include <iostream>
+#include "Student.hpp"
+template<typename T>
+void print(std::set<T> s) {
+  for(auto it = s.cbegin(); it!=s.cend(); it++)
+    std::cout << *it << " ";
+  std::cout << std::endl;
+}
+int main(int argc, char *argv[]) {
+  std::set<Student> students;
+  students.emplace("Mickie Mouse", 1239);
+  students.emplace("Mary Poppins", 1240);
+  students.emplace("Minnie Mouse", 1234);
+  students.emplace("Peter Pan",    1235);
+  students.emplace("Tinker Bell",  1233);
+  students.emplace("Donald Duck",  1230);
+  students.emplace("Minnie Mouse", 1234);
+  students.emplace("Tinker Bell",  1233);
+  print(students);
+  return 0;
+}
+</code>
+<WRAP todo 80% center round>
+Αλλάξτε τον //STL container// από //std::set// σε //std::multiset// και παρατηρήστε την συμπεριφορά του προγράμματος σε αυτή την περίπτωση.
+</WRAP>
+<WRAP tip 80% center round>
+Παρατηρήστε ότι η σειρά εκτύπωσης των στοιχείων κατά την διάτρεξη του //std::set// ή του //std::multiset// είναι από το μικρότερο αποθηκευμένο στοιχείο προς το μεγαλύτερο. Τα αντικείμενα της κλάσης //Student// κατατάσσονται με βάση το ΑΕΜ.
+</WRAP>
+===== Οι συναρτήσεις lower_bound, upper_bound και equal_range =====
+Οι κλάσεις //std::set// και //std::multiset// διαθέτουν τις συναρτήσεις [[http://www.cplusplus.com/reference/set/set/lower_bound/|lower_bound]], [[http://www.cplusplus.com/reference/set/set/upper_bound/|upper_bound]] και [[http://www.cplusplus.com/reference/set/set/equal_range/|equal_range]] οι οποίες λειτουργούν ως εξής:
+  * **iterator lower_bound (const value_type& val) const:** Επιστρέφει έναν //iterator// που δείχνει στη θέση ενός στοιχείου που είναι ίσο ή μεγαλύτερο από την τιμή //**val**//.
+  * **iterator upper_bound (const value_type& val) const:** Επιστρέφει έναν //iterator// που δείχνει στην θέση ενός στοιχείου που είναι ίσο ή μικρότερο από την τιμή //**val**//.
+  * **pair<iterator,iterator> equal_range (const value_type& val):** Επιστρέφει έναν ζεύγος //iterator// (δες περισσότερα σχετικά με την κλάση //pair// στην ενότητα [[cpp:stl:map|std::map και std::multimap]]) που δείχνει στην αρχή και στο τέλος ενός εύρους στοιχείων στον //container//, όπου τα κλειδιά είναι ίδια με την τιμή //**val**//. Για ένα //set// το εύρος αυτό έχει μέγιστο μέγεθος ένα στοιχείο, ενώ για ένα //multiset// μπορεί να περιέχει περισσότερα στοιχεία. Εάν δεν βρεθεί κανένα στοιχείο με τιμή //**val**// οι //iterators// του ζεύγους δείχνουν και οι δύο σε κοινή θέση.
+=== Παράδειγμα upper_bound, lower_bound, equal_range ===
+<code cpp string_multiset.cpp>
+#include <set>
+#include <string>
+#include <iostream>
+template<typename T>
+void print(std::multiset<T> s) {
+  for(auto it = s.cbegin(); it!=s.cend(); it++)
+    std::cout << *it << " ";
+  std::cout << std::endl;
+}
+int main(int argc, char *argv[]) {
+  std::multiset<std::string> strset;
+  strset.emplace("orange");
+  strset.emplace("apple");
+  strset.emplace("mango");
+  strset.emplace("cherry");
+  strset.emplace("melon");
+  strset.emplace("apricot");
+  strset.emplace("pineapple");
+  strset.emplace("mango");
+  strset.emplace("apricot");
+  strset.emplace("apple");
+  strset.emplace("apple");
+  print(strset);
+  auto lower_it = strset.lower_bound("apricot");
+  auto upper_it = strset.upper_bound("kiwi");
+  strset.erase(lower_it, upper_it);
+  print(strset);
+  auto range = strset.equal_range("mango");
+  strset.erase(range.first,range.second);
+  print(strset);
+  //Searching for mango again...
+  range = strset.equal_range("mango");
+  if(range.first == range.second)
+    std::cout << "range.first == range.second\n";
+  return 0;
+}
+</code>