Ένα std::unordered_map αποτελεί ένα σύνολο μοναδικών στοιχείων, όπου κάθε τέτοιο στοιχείο αποτελεί κλειδί για την εύρεση ή αντιστοίχιση του με ένα άλλο αντικείμενο που ονομάζουμε “τιμή” (value). Κάθε κλειδί προσδιορίζει μοναδικά μία “τιμή”, η οποία δεν είναι απαραίτητο να είναι μοναδική (οι τιμές μπορεί να επαναλαμβάνονται).

Τα κλειδιά του std::unordered_map είναι αποθηκευμένα σε ένα πίνακα κατακερματισμού με αλύσίδες (Hash_table#Separate_chaining).

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

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

Η επίδοση της δομής είναι ανάλογη των δομών std::unordered_set και std::unordered_multiset λαμβάνοντας υπόψη τα στοιχεία-κλειδιά των std::unordered_map και std::unordered_multimap.

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

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;

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

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