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

User Tools

Site Tools

Trace: • unordered_map
cpp:stl:unordered_map

Differences

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

Link to this comparison view

Both sides previous revision Previous revision
Previous revision
cpp:stl:unordered_map [2020/06/01 06:29]
 cpp:stl:unordered_map [2020/06/01 07:29]
gthanos [Περισσότερα για τις κλάσεις std::unordered_map και std::unordered_multimap]
Line 1: Line 1:
 +====== std::unordered_map και std::unordered_multimap ======
 +
 +Ένα [[http://www.cplusplus.com/reference/unordered_map/unordered_map/|std::unordered_map]] αποτελεί ένα σύνολο μοναδικών στοιχείων, όπου κάθε τέτοιο στοιχείο αποτελεί κλειδί για την εύρεση ή αντιστοίχιση του με ένα άλλο αντικείμενο που ονομάζουμε "τιμή" (//value//). Κάθε κλειδί προσδιορίζει μοναδικά μία "τιμή", η οποία δεν είναι απαραίτητο να είναι μοναδική (οι τιμές μπορεί να επαναλαμβάνονται).
 +
 +Τα κλειδιά του [[http://www.cplusplus.com/reference/unordered_map/unordered_map/|std::unordered_map]] είναι αποθηκευμένα σε ένα πίνακα κατακερματισμού με αλύσίδες ([[wp>Hash_table#Separate_chaining]]).
 +
 +Η κατάταξη ενός νέου ζεύγους κλειδιού-τιμής γίνεται πάντα μέσω της συνάρτησης κατακερματισμού (//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]]. Για δικούς σας τύπους δεδομένων καλείστε να υλοποιήσετε εσείς τις συγκεκριμένες συναρτήσεις.
 +
 +
 +===== Παράδειγμα 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>
 +
  
cpp/stl/unordered_map.txt · Last modified: 2020/06/01 06:29 (external edit)

Page Tools

Except where otherwise noted, content on this wiki is licensed under the following license: CC Attribution 4.0 International
CC Attribution 4.0 International Donate Powered by PHP Valid HTML5 Valid CSS Driven by DokuWiki