Differences

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

--- cpp:stl:unordered_set [2020/05/31 18:07] – created gthanos
+++ cpp:stl:unordered_set [Unknown date] (current) – external edit (Unknown date) 127.0.0.1
@@ Line 3: / Line 3: @@
 Ένα [[http://www.cplusplus.com/reference/unordered_set/unordered_set/|std::unordered_set]] αποτελεί ένα σύνολο μοναδικών στοιχείων, τα οποία είναι αποθηκευμένα σε ένα πίνακα κατακερματισμού με αλύσίδες ([[wp>Hash_table#Separate_chaining]]).
-Η κατάταξη ενός νέου στοιχείου γίνεται πάντα μέσω της συνάρτησης κατακερματισμού (//hash function//), η οποία εξαρτάται από το είδος των στοιχείων που αποθηκεύονται στο //set//. Το ακόλουθο σχήμα περιγράφει την δομή της κλάσης //unordered_set//.
+Η κατάταξη ενός νέου στοιχείου γίνεται πάντα μέσω της συνάρτησης κατακερματισμού (//hash function//), η οποία εξαρτάται από το είδος των στοιχείων που αποθηκεύονται στο //set//. Το ακόλουθο σχήμα περιγράφει συνοπτικά τη δομή της κλάσης //unordered_set//.
 | {{ :cpp:stl:internal_structure_of_unordered_sets_and_multisets.png?600 |}} |
-| Σχήμα 1. Η δομή της κλάσης [[http://www.cplusplus.com/reference/unordered_set/unordered_set/|std::unordered_set]]|
+| Σχήμα 1. Η δομή της κλάσης [[http://www.cplusplus.com/reference/unordered_set/unordered_set/|std::unordered_set]] (Πηγή: [[https://conglang.github.io/2015/01/01/stl-unordered-container/|conglang.github.io]])|
 ===== Επίδοσης της δομής =====
-  * Οι πράξεις της αναζήτησης, της ένθεσης και της διαγραφής κοστίζουν σταθερό χρόνο.
+  * Οι πράξεις της αναζήτησης, της ένθεσης και της διαγραφής κοστίζουν ανάλογο του μεγέθους της λίστας του πίνακα κατακερματισμού. Επειδή η //default// τιμή για τον βαθμό πληρώσεως του πινακα είναι 1.0 μπορείτε να υποθέσετε ότι το μέσο κόστος της λίστας είναι μικρότερο από 2.0 και κατά συνέπεια η επίδοση της δομής είναι σταθερή (**O(1)**) και για τις τρεις πράξεις.
-  * Η διάτρεξη των στοιχείων γίνεται κατά τη σειρά διάτρεξης του πίνακα κατακερματισμού, η οποία δεν ακολουθεί τη σειρά εισαγωγής ούτε την πιθανή κατάταξη των στοιχείων.
+  * Η διάτρεξη των στοιχείων γίνεται κατά τη σειρά διάτρεξης του πίνακα κατακερματισμού, η οποία δεν ακολουθεί τη σειρά εισαγωγής, ούτε την πιθανή κατάταξη των στοιχείων.
-  * Σε σχέση με τις κλάσεις [[cpp:stl:set|std::set και std::multiset]] η συγκεκριμένη κλάση είναι πιο γρήγορη κατά αναζήτηση την ένθεση και διαγραφή, όμως σπαταλά συγκριτικά περισσότερο χώρο. Ο χρησιμοποιούμενος χώρος είναι περίπου ο διπλάσιος αν αγνοήσουμε το κόστος αποθήκευσης των δεικτών του δυαδικού δέντρου, και το κόστος αποθήκευσης των δεικτών της αλυσίδας του πίνακα κατακερματισμού.
+  * Σε σχέση με τις κλάσεις [[cpp:stl:set|std::set και std::multiset]] η συγκεκριμένη κλάση είναι πιο γρήγορη κατά αναζήτηση την ένθεση και διαγραφή, όμως σπαταλά συγκριτικά περισσότερο χώρο. Ο χώρος που σπαταλάται εξαρτάται από τον βαθμό πλήρωσης του πίνακα κατακερματισμού.
-===== Περισσότερα για τις κλάσεις std::uordered_set και std::unordered_multiset =====
+===== Περισσότερα για τις κλάσεις std::unordered_set και std::unordered_multiset =====
 H δήλωση της κλάσης //std::unordered_set// έχει ως εξής:
@@ Line 26: / Line 26: @@
 </code>
-Από την παραπάνω δήλωση της κλάσης παρατηρούμε ότι εκτός από το κλειδί ''Key'' κατά την δήλωση απαιτείται η  δήλωση δύο επιπλέον κλάσεων της κλάσης ''Hash=hash<Key>'' και της κλάσης ''Pred=equal_to<Key>''. Οι κλάσεις αυτές λειτουργούν ως συναρτήσεις (θα δώσουμε σχετικό παράδειγμα στη συνέχεια), η πρώτη υλοποιεί το //hash function// και η δεύτερη ελέγχει την ισότητα μεταξύ δύο αντικειμένων του ιδίου τύπου. Οι κλάσεις οι οποίες έχουν ως στόχο την αποκλειστική χρήση τους ως συναρτήσεις ειδικού σκοπού ονομάζονται στη βιβλιογραφία //[[https://www.quantstart.com/articles/Function-Objects-Functors-in-C-Part-1/|function objects]]//.
+Από την παραπάνω δήλωση της κλάσης παρατηρούμε ότι εκτός από το κλειδί ''Key'' κατά την δήλωση της κλάσης, απαιτείται η  δήλωση δύο επιπλέον κλάσεων //α)// της κλάσης ''Hash=hash<Key>'' και //β)// της κλάσης ''Pred=equal_to<Key>''. Οι κλάσεις αυτές λειτουργούν ως συναρτήσεις (θα δώσουμε σχετικό παράδειγμα στη συνέχεια). Η πρώτη υλοποιεί το //hash function// για την τοποθέτηση σε μία θέση του //hash table// (η θέση ονομάζεται και //bucket//) και η δεύτερη ελέγχει την ισότητα μεταξύ δύο αντικειμένων του ιδίου τύπου για την αναζήτηση μέσα στη λίστα του κάθε //bucket//. Οι κλάσεις οι οποίες έχουν ως στόχο την αποκλειστική χρήση τους ως συναρτήσεις ειδικού σκοπού μέσω της υπερφόρτωσης του τελεστή %%()%% ονομάζονται στη βιβλιογραφία [[cpp:functors|function objects ή functors]].
+Για τους βασικούς τύπους δεδομένων οι παραπάνω κλάσεις υλοποιούνται μέσω των //templated// κλάσεων [[http://www.cplusplus.com/reference/functional/hash/|std::hash]] και [[http://www.cplusplus.com/reference/functional/equal_to/|std::equal_to]]. Για δικούς σας τύπους δεδομένων καλείστε να υλοποιήσετε εσείς τις συγκεκριμένες συναρτήσεις.
+===== Παράδειγμα 1ο - Αποθήκευση std::string σε unordered_set ή unordered_multiset =====
+<code cpp string_unordered_set.cpp>
+#include <unordered_set>
+#include <string>
+#include <iostream>
+template<typename T, typename Hash, typename Pred>
+void print(std::unordered_set<T, Hash, Pred> s) {
+  for(auto it = s.cbegin(); it!=s.cend(); it++)
+    std::cout << *it << " ";
+  std::cout << std::endl;
+}
+int main(int argc, char *argv[]) {
+  std::unordered_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>
+<WRAP todo 80% center round>
+Αλλάξτε τον //STL container// από //std::unordered_set// σε //std::unordered_multiset// και παρατηρήστε την συμπεριφορά του προγράμματος σε αυτή την περίπτωση.
+</WRAP>
+Παρατηρήστε ότι και στις δύο περιπτώσεις η σειρά διάτρεξης είναι "τυχαία", αλλά ίδια όσες φορές και να επαναλάβετε την εκτέλεση του προγραάμματος. Η σειρά διάτρεξης δεν ακολουθεί τη σειρά εισόδου των στοιχείων όπως συμβαίνει στους //sequence containers//, ούτε διατρέχει τα στοιχεία με σειρά προτεραιτότητας.
+===== Παράδειγμα 2ο - Αποθήκευση Student σε unordered_set ή unordered_multiset =====
+<code cpp student_unordered_set.cpp>
+#include <unordered_set>
+#include <iostream>
+#include "Student.hpp"
+template<typename T, typename Hash, typename Eq>
+void print(std::unordered_set<T,Hash,Eq> s) {
+  for(auto it = s.cbegin(); it!=s.cend(); it++)
+    std::cout << *it << " ";
+  std::cout << std::endl;
+}
+struct HashByAEM {
+  size_t operator()(const Student& st) const {
+    std::hash<int> hash_int;
+    return hash_int(st.getAEM());
+  }
+};
+struct EqualToByAEM {
+  bool operator() (const Student& st1, const Student& st2) const {
+    return st1.getAEM() == st2.getAEM();
+  }
+};
+int main(int argc, char *argv[]) {
+  std::unordered_set<Student, HashByAEM, EqualToByAEM> 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::unordered_set// σε //std::unordered_multiset// και παρατηρήστε τη συμπεριφορά του προγράμματος και σε αυτή την περίπτωση.
+</WRAP>