Differences

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

--- cpp:stl:unordered_map [2020/06/01 06:31] – created gthanos
+++ cpp:stl:unordered_map [2020/06/01 07:04] – [Επίδοσης της δομής] gthanos
@@ Line 5: / Line 5: @@
 Τα κλειδιά του [[http://www.cplusplus.com/reference/unordered_map/unordered_map/|std::unordered_map]] είναι αποθηκευμένα σε ένα πίνακα κατακερματισμού με αλύσίδες ([[wp>Hash_table#Separate_chaining]]).
-Η κατάταξη ενός νέου ζεύγους κλειδιού-τιμής γίνεται πάντα μέσω της συνάρτησης κατακερματισμού (//hash function//), η οποία εξαρτάται από το είδος των κλειδιών που αποθηκεύονται στο //map//. Το ακόλουθο σχήμα περιγράφει συνοπτικά τη δομή της κλάσης //unordered_set//.
+Η κατάταξη ενός νέου ζεύγους κλειδιού-τιμής γίνεται πάντα μέσω της συνάρτησης κατακερματισμού (//hash function//), η οποία εξαρτάται από το είδος των κλειδιών που αποθηκεύονται στο //map//. Το ακόλουθο σχήμα περιγράφει συνοπτικά τη δομή της κλάσης //unordered_map//.
 | {{ :cpp:stl:internal_structure_of_unordered_maps_and_multimaps.png?600 |}} |
 | Σχήμα 1. Η δομή της κλάσης [[http://www.cplusplus.com/reference/unordered_map/unordered_map/|std::unordered_map]] (Πηγή: [[https://conglang.github.io/2015/01/01/stl-unordered-container/|conglang.github.io]])|
+===== Επίδοσης της δομής =====
+Η επίδοση της δομής είναι ανάλογη των δομών [[cpp:stl:unordered_set|std::unordered_set και std::unordered_multiset]] λαμβάνοντας υπόψη τα στοιχεία-κλειδιά των //std::unordered_map// και //std::unordered_multimap//.
+===== Περισσότερα για τις κλάσεις std::unordered_map και std::unordered_multimap =====
+H δήλωση της κλάσης //std::unordered_map// έχει ως εξής:
+<code cpp>
+template < class Key,                                    // unordered_map::key_type
+           class T,                                      // unordered_map::mapped_type
+           class Hash = hash<Key>,                       // unordered_map::hasher
+           class Pred = equal_to<Key>,                   // unordered_map::key_equal
+           class Alloc = allocator< pair<const Key,T> >  // unordered_map::allocator_type
+           > class unordered_map;
+</code>
+Από την παραπάνω δήλωση της κλάσης παρατηρούμε ότι εκτός από το κλειδί ''Key'' και τον τύπο ''T'' που αντιστοιχεί στην τιμή κάθε ζεύγους κλειδιού-τιμής, κατά την δήλωση της κλάσης απαιτείται η  δήλωση δύο επιπλέον κλάσεων //α)// της κλάσης ''Hash=hash<Key>'' και //β)// της κλάσης ''Pred=equal_to<Key>''. Οι κλάσεις αυτές λειτουργούν ως συναρτήσεις (δες σχετικό παράδειγμα στη συνέχεια). Η πρώτη υλοποιεί το //hash function// για την τοποθέτηση σε μία θέση του //hash table// (μία θέση ονομάζεται και //bucket//) και η δεύτερη ελέγχει την ισότητα μεταξύ δύο αντικειμένων του ιδίου τύπου για την αναζήτηση μέσα στη λίστα του κάθε //bucket//.
+Για τους βασικούς τύπους δεδομένων οι παραπάνω κλάσεις υλοποιούνται μέσω των //templated// κλάσεων [[http://www.cplusplus.com/reference/functional/hash/|std::hash]] και [[http://www.cplusplus.com/reference/functional/equal_to/|std::equal_to]]. Για δικούς σας τύπους δεδομένων καλείστε να υλοποιήσετε εσείς τις συγκεκριμένες συναρτήσεις.