Differences

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

--- cpp:stl:unordered_map [2020/06/01 06:48] – gthanos
+++ cpp:stl:unordered_map [2020/06/01 07:29] – [Περισσότερα για τις κλάσεις std::unordered_map και std::unordered_multimap] gthanos
@@ Line 11: / Line 11: @@
+===== Επίδοσης της δομής =====
+Η επίδοση της δομής είναι ανάλογη των δομών [[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]]. Για δικούς σας τύπους δεδομένων καλείστε να υλοποιήσετε εσείς τις συγκεκριμένες συναρτήσεις.
+===== Παράδειγμα 1ο - Αποθήκευση std::string ως κλειδί σε unordered_map ή unordered_multimap =====
+<code cpp color_unordered_map.cpp>
+#include <map>
+#include <utility>
+#include <string>
+#include <iostream>
+template<typename K, typename V, typename Hash, typename Pred>
+void print(std::map<K,V,Hash,Pred> s) {
+  for(auto it = s.cbegin(); it!=s.cend(); it++)
+    std::cout << it->first << " -> " << std::hex << std::uppercase << "0x" << it->second << std::endl;
+}
+int main(int argc, char *argv[]) {
+  std::map<std::string, int> colormap;
+  colormap.insert(std::pair<std::string, int>(std::string("orange"), 0xFF8C00 ));
+  colormap.insert(std::pair<std::string, int>(std::string("green"), 0x008C00 ));
+  colormap.insert(std::pair<std::string, int>(std::string("blue"), 0x0000FF ));
+  colormap.insert(std::make_pair(std::string("red"), 0x8C0000 ));
+  colormap.insert(std::make_pair(std::string("cyan"), 0x00FFFF));
+  colormap.insert(std::make_pair(std::string("orange"), 0xFF6347 ));
+  colormap.emplace(std::string("blue"), 0x0000AA );
+  colormap.emplace(std::string("purple"), 0x9400D3 );
+  colormap.emplace(std::string("magenta"), 0xFF00FF );
+  print(colormap);
+  return 0;
+}
+</code>
+<WRAP todo 80% center round>
+Αλλάξτε τον //STL container// από //std::unordered_map// σε //std::unordered_multimap// και παρατηρήστε την συμπεριφορά του προγράμματος σε αυτή την περίπτωση.
+</WRAP>
+===== Παράδειγμα 2ο - Αποθήκευση Student ως κλειδί σε unordered_map ή unordered_multimap =====
+<code cpp student_unordered_map.cpp>
+#include <unordered_map>
+#include <iostream>
+#include "Student.hpp"
+template<typename K, typename V, typename Hash, typename Pred>
+void print(std::unordered_map<K,V,Hash,Pred> s) {
+  for(auto it = s.cbegin(); it!=s.cend(); it++)
+    std::cout << it->first << " -> " << it->second << 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[]) {
+  // map students to their address
+  std::unordered_map<Student, std::string, HashByAEM, EqualToByAEM> students;
+  std::pair<Student,std::string> peter_pan_pair(Student("Peter Pan", 1234), std::string("Wendy House, Neverland"));
+  std::pair<Student,std::string> mickey_mouse_pair = make_pair(Student("Mickey Mouse", 1235), std::string("Walt Disney World Communications, P.O Box 10040, Lake Buena Vista, Florida 32830-0040 "));
+  students.insert( peter_pan_pair );
+  students.insert( mickey_mouse_pair );
+  students.emplace( Student("Minie Mouse", 1240), std::string("Walt Disney World Communications, P.O Box 10040, Lake Buena Vista, Florida 32830-0040 "));
+  print(students);
+  return 0;
+}
+</code>
+<WRAP todo 80% center round>
+Αλλάξτε τον //STL container// από //std::unordered_set// σε //std::unordered_multiset// και παρατηρήστε τη συμπεριφορά του προγράμματος και σε αυτή την περίπτωση.
+</WRAP>