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

Τα στοιχεία-κλειδιά αποθηκεύονται εσωτερικά σε ένα ισοζυγισμένο δέντρο αναζητήσεως (π.χ.Red–black_tree, AVL_tree), όπως ακριβώς και στο std::set.

Η κατάταξη ενός νέου στοιχείου-κλειδιού γίνεται πάντα μέσω σύγκρισης με τα υπόλοιπα στοιχεία που είναι αποθηκευμένα στην δομή. Για τον λόγο αυτό, απαραίτητη προϋπόθεση για τη λειτουργία του map (όπως και στο std::set) είναι για τον τύπο του κλειδιού να παρέχονται οι τελεστές σύγκρισης < και >. Δύο κλειδιά ιδίου τύπου θεωρούνται ίσα σε ένα map εάν η παρακάτω λογική έκφραση είναι αληθής.

if(!(a < b) && !(b < a))

Ένα std::multimap αποτελεί ένα σύνολο από όχι απαραίτητα μοναδικά κλειδιά, τα οποία είναι αποθηκευμένα σε ένα ισοζυγισμένο δέντρο αναζητήσεως (όπως το map). Ο τρόπος σύγκρισης και η κατάταξη των στοιχείων είναι όμοια με την επίπλέον σημείωση ότι το δέντρο επιτρέπει την εμφάνιση ενός κλειδιού περισσότερες από μία φορές.

Στα παρακάτω σχήματα διακρίνεται η δομή ενός std::map και ενός std::multimap, όπου τα κλειδιά είναι ακέραιοι και οι τιμές είναι αντικείμενα τύπου std::string.

Σχήμα 1. std::map	Σχήμα 2. std::multimap