Что такое структура данных карты в C++

std::unordered_map использует хеширование для хранения своих объектов.

Стандарт не требует какой-либо конкретной реализации std::map. Это только дает необходимые операции и их сложность. Эти факторы приводят к фактическому выбору реализации, который обычно представляет собой красно-черное дерево.

Глава, в которой перечислены требования для std::map, — это 23.2.4 Associative Containers в C++11.

Он обычно реализуется с помощью самобалансирующегося BST. Реализация на самом деле зависит от компилятора.

std::map<char, int> dict;

char — это ключ, а int — соответствующее значение.

Он использует красно-черное дерево для организации ключей по порядку.

Вот почему вы можете перебирать его в порядке возрастания, а ключевой объект должен иметь перегруженный оператор‹.