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

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

Σχήμα 1. Η δομή της κλάσης std::unordered_set

• Οι πράξεις της αναζήτησης, της ένθεσης και της διαγραφής κοστίζουν σταθερό χρόνο.
• Η διάτρεξη των στοιχείων γίνεται κατά τη σειρά διάτρεξης του πίνακα κατακερματισμού, η οποία δεν ακολουθεί τη σειρά εισαγωγής ούτε την πιθανή κατάταξη των στοιχείων.
• Σε σχέση με τις κλάσεις 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 και η δεύτερη ελέγχει την ισότητα μεταξύ δύο αντικειμένων του ιδίου τύπου. Οι κλάσεις οι οποίες έχουν ως στόχο την αποκλειστική χρήση τους ως συναρτήσεις ειδικού σκοπού ονομάζονται στη βιβλιογραφία function objects ή functors.

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

#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_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 {
    return std::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;
}