Differences

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

--- cpp:stl:unordered_set [2020/05/31 18:11]
gthanos [Περισσότερα για τις κλάσεις std::uordered_set και std::unordered_multiset]
+++ cpp:stl:unordered_set [2020/06/01 06:05]
@@ Line 1: / Line 1: @@
-====== std::unordered_set και std::unordered_multiset ======
-Ένα [[http://www.cplusplus.com/reference/unordered_set/unordered_set/|std::unordered_set]] αποτελεί ένα σύνολο μοναδικών στοιχείων, τα οποία είναι αποθηκευμένα σε ένα πίνακα κατακερματισμού με αλύσίδες ([[wp>Hash_table#Separate_chaining]]).
-Η κατάταξη ενός νέου στοιχείου γίνεται πάντα μέσω της συνάρτησης κατακερματισμού (//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]]|
-===== Επίδοσης της δομής =====
-  * Οι πράξεις της αναζήτησης, της ένθεσης και της διαγραφής κοστίζουν σταθερό χρόνο.
-  * Η διάτρεξη των στοιχείων γίνεται κατά τη σειρά διάτρεξης του πίνακα κατακερματισμού, η οποία δεν ακολουθεί τη σειρά εισαγωγής ούτε την πιθανή κατάταξη των στοιχείων.
-  * Σε σχέση με τις κλάσεις [[cpp:stl:set|std::set και std::multiset]] η συγκεκριμένη κλάση είναι πιο γρήγορη κατά αναζήτηση την ένθεση και διαγραφή, όμως σπαταλά συγκριτικά περισσότερο χώρο. Ο χρησιμοποιούμενος χώρος είναι περίπου ο διπλάσιος αν αγνοήσουμε το κόστος αποθήκευσης των δεικτών του δυαδικού δέντρου, και το κόστος αποθήκευσης των δεικτών της αλυσίδας του πίνακα κατακερματισμού.
-===== Περισσότερα για τις κλάσεις std::unordered_set και std::unordered_multiset =====
-H δήλωση της κλάσης //std::unordered_set// έχει ως εξής:
-<code cpp>
-template < class Key,                        // unordered_set::key_type/value_type
-           class Hash = hash<Key>,           // unordered_set::hasher
-           class Pred = equal_to<Key>,       // unordered_set::key_equal
-           class Alloc = allocator<Key>      // unordered_set::allocator_type
-           > class unordered_set;
-</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]]//.

Αντικειμενοστραφής Προγραμματισμός

User Tools

Site Tools

Differences

Page Tools