Ένα std::unordered_set αποτελεί ένα σύνολο μοναδικών στοιχείων, τα οποία είναι αποθηκευμένα σε ένα πίνακα κατακερματισμού με αλύσίδες (Hash_table#Separate_chaining).

Η κατάταξη ενός νέου στοιχείου γίνεται πάντα μέσω της συνάρτησης κατακερματισμού (hash function), η οποία εξαρτάται από το είδος των στοιχείων που αποθηκεύονται στο set. Το ακόλουθο σχήμα περιγράφει συνοπτικά τη δομή της κλάσης unordered_set.

Σχήμα 1. Η δομή της κλάσης std::unordered_set (Πηγή: conglang.github.io)

• Οι πράξεις της αναζήτησης, της ένθεσης και της διαγραφής κοστίζουν ανάλογο του μεγέθους της λίστας του πίνακα κατακερματισμού. Επειδή η default τιμή για τον βαθμό πληρώσεως του πινακα είναι 1.0 μπορείτε να υποθέσετε ότι το μέσο κόστος της λίστας είναι μικρότερο από 2.0 και κατά συνέπεια η επίδοση της δομής είναι σταθερή (O(1)) και για τις τρεις πράξεις.
• Η διάτρεξη των στοιχείων γίνεται κατά τη σειρά διάτρεξης του πίνακα κατακερματισμού, η οποία δεν ακολουθεί τη σειρά εισαγωγής, ούτε την πιθανή κατάταξη των στοιχείων.
• Σε σχέση με τις κλάσεις std::set και std::multiset η συγκεκριμένη κλάση είναι πιο γρήγορη κατά αναζήτηση την ένθεση και διαγραφή, όμως σπαταλά συγκριτικά περισσότερο χώρο. Ο χώρος που σπαταλάται εξαρτάται από τον βαθμό πλήρωσης του πίνακα κατακερματισμού.

H δήλωση της κλάσης std::unordered_set έχει ως εξής:

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;

Από την παραπάνω δήλωση της κλάσης παρατηρούμε ότι εκτός από το κλειδί Key κατά την δήλωση της κλάσης, απαιτείται η δήλωση δύο επιπλέον κλάσεων α) της κλάσης Hash=hash<Key> και β) της κλάσης Pred=equal_to<Key>. Οι κλάσεις αυτές λειτουργούν ως συναρτήσεις (θα δώσουμε σχετικό παράδειγμα στη συνέχεια). Η πρώτη υλοποιεί το hash function για την τοποθέτηση σε μία θέση του hash table (η θέση ονομάζεται και bucket) και η δεύτερη ελέγχει την ισότητα μεταξύ δύο αντικειμένων του ιδίου τύπου για την αναζήτηση μέσα στη λίστα του κάθε bucket. Οι κλάσεις οι οποίες έχουν ως στόχο την αποκλειστική χρήση τους ως συναρτήσεις ειδικού σκοπού μέσω της υπερφόρτωσης του τελεστή () ονομάζονται στη βιβλιογραφία function objects ή functors.

Για τους βασικούς τύπους δεδομένων οι παραπάνω κλάσεις υλοποιούνται μέσω των templated κλάσεων std::hash και std::equal_to. Για δικούς σας τύπους δεδομένων καλείστε να υλοποιήσετε εσείς τις συγκεκριμένες συναρτήσεις.

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;
}

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

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;
}