Differences

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

--- cpp:stl:set [2020/05/29 12:54] – created gthanos
+++ cpp:stl:set [2023/05/30 11:04] (current) – [Παράδειγμα ένθεσης και διάτρεξης ενός set] gthanos
@@ Line 1: / Line 1: @@
-====== std::set ======
+====== std::set και std::multiset ======
 Ένα [[http://www.cplusplus.com/reference/set/set/|std::set]] αποτελεί ένα σύνολο μοναδικών στοιχείων. Τα στοιχεία αποθηκεύονται εσωτερικά σε ένα ισοζυγισμένο δέντρο αναζητήσεως (π.χ.[[wp>Red–black_tree]], [[wp>AVL_tree]]).
-Η κατάταξη ενός νέου στοιχείου γίνεται πάντα μέσω σύγκρισης με τα υπόλοιπα στοιχεία που είναι αποθηκευμένα στην δομή. Για τον λόγο αυτό είναι απαραίτητο για τα στοιχεία που αποθηκεύονται να παρέχονται οι τελεστές σύγκρισης %%<%% και %%>%%.
+Η κατάταξη ενός νέου στοιχείου γίνεται πάντα μέσω σύγκρισης με τα υπόλοιπα στοιχεία που είναι αποθηκευμένα στην δομή. Για τον λόγο αυτό, απαραίτητη προϋπόθεση για τη λειτουργία του //set// είναι για τους τύπους δεδομένων που αποθηκεύονται να παρέχονται ο τελεστής σύγκρισης %%<%%. Δύο στοιχεία ιδίου τύπου θεωρούνται ίσα σε ένα //set// εάν η παρακάτω λογική έκφραση είναι αληθής.
+<code cpp>
+if(!(a < b) && !(b < a))
+</code>
+Ένα [[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]], όπου τα στοιχεία είναι ακέραιοι.
+| {{ :cpp:stl:set01.png? |}}| {{ :cpp:stl:multiset01.png? |}} |
+|  **Σχήμα 1. std::set**  |  **Σχήμα 2. std::multiset**  |
+Το προγραμματιστικό //interface// των //set// και //multiset// είναι κοινό και έχει καλυφθεί στις προηγούμενες ενότητες.
+===== Επίδοσης της δομής =====
+  * Η πράξη της ένθεσης ή της διαγραφής κοστίζει λογαριθμικό χρόνο **O(logN)**.
+  * Η πράξη της αναζήτησης κοστίζει επίσης λογαριθμικό χρόνο **O(logN)**.
+  * Η πρόσβαση στο 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>