| Both sides previous revisionPrevious revisionNext revision | Previous revision |
| cpp:stl:unordered_set [2020/06/01 05:00] – [std::unordered_set και std::unordered_multiset] gthanos | cpp:stl:unordered_set [Unknown date] (current) – external edit (Unknown date) 127.0.0.1 |
|---|
| ===== Επίδοσης της δομής ===== | ===== Επίδοσης της δομής ===== |
| |
| * Οι πράξεις της αναζήτησης, της ένθεσης και της διαγραφής κοστίζουν σταθερό χρόνο. | * Οι πράξεις της αναζήτησης, της ένθεσης και της διαγραφής κοστίζουν ανάλογο του μεγέθους της λίστας του πίνακα κατακερματισμού. Επειδή η //default// τιμή για τον βαθμό πληρώσεως του πινακα είναι 1.0 μπορείτε να υποθέσετε ότι το μέσο κόστος της λίστας είναι μικρότερο από 2.0 και κατά συνέπεια η επίδοση της δομής είναι σταθερή (**O(1)**) και για τις τρεις πράξεις. |
| * Η διάτρεξη των στοιχείων γίνεται κατά τη σειρά διάτρεξης του πίνακα κατακερματισμού, η οποία δεν ακολουθεί τη σειρά εισαγωγής ούτε την πιθανή κατάταξη των στοιχείων. | * Η διάτρεξη των στοιχείων γίνεται κατά τη σειρά διάτρεξης του πίνακα κατακερματισμού, η οποία δεν ακολουθεί τη σειρά εισαγωγής, ούτε την πιθανή κατάταξη των στοιχείων. |
| * Σε σχέση με τις κλάσεις [[cpp:stl:set|std::set και std::multiset]] η συγκεκριμένη κλάση είναι πιο γρήγορη κατά αναζήτηση την ένθεση και διαγραφή, όμως σπαταλά συγκριτικά περισσότερο χώρο. Ο χρησιμοποιούμενος χώρος είναι περίπου ο διπλάσιος αν αγνοήσουμε το κόστος αποθήκευσης των δεικτών του δυαδικού δέντρου, και το κόστος αποθήκευσης των δεικτών της αλυσίδας του πίνακα κατακερματισμού. | * Σε σχέση με τις κλάσεις [[cpp:stl:set|std::set και std::multiset]] η συγκεκριμένη κλάση είναι πιο γρήγορη κατά αναζήτηση την ένθεση και διαγραφή, όμως σπαταλά συγκριτικά περισσότερο χώρο. Ο χώρος που σπαταλάται εξαρτάται από τον βαθμό πλήρωσης του πίνακα κατακερματισμού. |
| |
| ===== Περισσότερα για τις κλάσεις std::unordered_set και std::unordered_multiset ===== | ===== Περισσότερα για τις κλάσεις std::unordered_set και std::unordered_multiset ===== |
| </code> | </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 ή functors]]//. | Από την παραπάνω δήλωση της κλάσης παρατηρούμε ότι εκτός από το κλειδί ''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]]. Για δικούς σας τύπους δεδομένων καλείστε να υλοποιήσετε εσείς τις συγκεκριμένες συναρτήσεις. |
| |
| Για τους βασικούς τύπους δεδομένων οι συναρτήσεις αυτές υλοποιούνται μέσω των //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 ===== | ===== Παράδειγμα 1ο - Αποθήκευση std::string σε unordered_set ή unordered_multiset ===== |
| |
| <code cpp > | <code cpp string_unordered_set.cpp> |
| #include <unordered_set> | #include <unordered_set> |
| #include <string> | #include <string> |
| ===== Παράδειγμα 2ο - Αποθήκευση Student σε unordered_set ή unordered_multiset ===== | ===== Παράδειγμα 2ο - Αποθήκευση Student σε unordered_set ή unordered_multiset ===== |
| |
| <code cpp student_set.cpp> | <code cpp student_unordered_set.cpp> |
| #include <unordered_set> | #include <unordered_set> |
| #include <iostream> | #include <iostream> |
| struct HashByAEM { | struct HashByAEM { |
| size_t operator()(const Student& st) const { | size_t operator()(const Student& st) const { |
| return std::hash<int>()(st.getAEM()); | std::hash<int> hash_int; |
| | return hash_int(st.getAEM()); |
| } | } |
| }; | }; |
