====== 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]] (Πηγή: [[https://conglang.github.io/2015/01/01/stl-unordered-container/|conglang.github.io]])|

===== Επίδοσης της δομής =====

  * Οι πράξεις της αναζήτησης, της ένθεσης και της διαγραφής κοστίζουν ανάλογο του μεγέθους της λίστας του πίνακα κατακερματισμού. Επειδή η //default// τιμή για τον βαθμό πληρώσεως του πινακα είναι 1.0 μπορείτε να υποθέσετε ότι το μέσο κόστος της λίστας είναι μικρότερο από 2.0 και κατά συνέπεια η επίδοση της δομής είναι σταθερή (**O(1)**) και για τις τρεις πράξεις.
  * Η διάτρεξη των στοιχείων γίνεται κατά τη σειρά διάτρεξης του πίνακα κατακερματισμού, η οποία δεν ακολουθεί τη σειρά εισαγωγής, ούτε την πιθανή κατάταξη των στοιχείων.
  * Σε σχέση με τις κλάσεις [[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// για την τοποθέτηση σε μία θέση του //hash table// (η θέση ονομάζεται και //bucket//) και η δεύτερη ελέγχει την ισότητα μεταξύ δύο αντικειμένων του ιδίου τύπου για την αναζήτηση μέσα στη λίστα του κάθε //bucket//. Οι κλάσεις οι οποίες έχουν ως στόχο την αποκλειστική χρήση τους ως συναρτήσεις ειδικού σκοπού μέσω της υπερφόρτωσης του τελεστή %%()%% ονομάζονται στη βιβλιογραφία [[cpp:functors|function objects ή functors]].

Για τους βασικούς τύπους δεδομένων οι παραπάνω κλάσεις υλοποιούνται μέσω των //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_set ή unordered_multiset =====

<code cpp string_unordered_set.cpp>
#include <unordered_set>
#include <string>
#include <iostream>

template<typename T, typename Hash, typename Pred>
void print(std::unordered_set<T, Hash, Pred> s) {
  for(auto it = s.cbegin(); it!=s.cend(); it++) 
    std::cout << *it << " ";
  std::cout << std::endl;
}

int main(int argc, char *argv[]) {
  std::unordered_set<std::string> strset;
  
  strset.emplace("orange");
  strset.emplace("apple");
  strset.emplace("mango");
  strset.emplace("cherry");
  strset.emplace("melon");
  strset.emplace("apricot");
  strset.emplace("pineapple");
  strset.emplace("mango");
  strset.emplace("apricot");
  strset.emplace("apple");
  strset.emplace("apple");
  
  print(strset);
  
  return 0;
}
</code>

<WRAP todo 80% center round>
Αλλάξτε τον //STL container// από //std::unordered_set// σε //std::unordered_multiset// και παρατηρήστε την συμπεριφορά του προγράμματος σε αυτή την περίπτωση.
</WRAP>

Παρατηρήστε ότι και στις δύο περιπτώσεις η σειρά διάτρεξης είναι "τυχαία", αλλά ίδια όσες φορές και να επαναλάβετε την εκτέλεση του προγραάμματος. Η σειρά διάτρεξης δεν ακολουθεί τη σειρά εισόδου των στοιχείων όπως συμβαίνει στους //sequence containers//, ούτε διατρέχει τα στοιχεία με σειρά προτεραιτότητας.

===== Παράδειγμα 2ο - Αποθήκευση Student σε unordered_set ή unordered_multiset =====

<code cpp student_unordered_set.cpp>
#include <unordered_set>
#include <iostream>
#include "Student.hpp"

template<typename T, typename Hash, typename Eq>
void print(std::unordered_set<T,Hash,Eq> s) {
  for(auto it = s.cbegin(); it!=s.cend(); it++) 
    std::cout << *it << " ";
  std::cout << 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[]) {
  std::unordered_set<Student, HashByAEM, EqualToByAEM> students;
  
  students.emplace("Mickie Mouse", 1239);
  students.emplace("Mary Poppins", 1240);
  students.emplace("Minnie Mouse", 1234);
  students.emplace("Peter Pan",    1235);
  students.emplace("Tinker Bell",  1233);
  students.emplace("Donald Duck",  1230);
  students.emplace("Minnie Mouse", 1234);
  students.emplace("Tinker Bell",  1233);
  
  print(students);
  
  return 0;
}
</code>

<WRAP todo 80% center round>
Αλλάξτε τον //STL container// από //std::unordered_set// σε //std::unordered_multiset// και παρατηρήστε τη συμπεριφορά του προγράμματος και σε αυτή την περίπτωση.
</WRAP>