====== 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>