Кто-то вчера сказал мне, что базовая структура упорядоченной карты - это двоичное дерево поиска. Это не имеет смысла для меня, так как вы не можете получить O (1), если это так. Может ли кто-нибудь объяснить?Какова основная структура std :: map?
Кроме того, если кто-то должен был реализовать хеш-таблицу на C++ без использования stdlib, что было бы лучшим способом сделать это?
Основная структура данных определяется реализацией. Он чаще всего реализуется как дерево Red-Black, которое является самобалансирующимся двоичным деревом поиска. Сложность времени для получения элемента равна O (logn) (см. this)
В качестве отправной точки я просто прочитал бы реализацию std::unordered_map. Я предполагаю, что это учебная деятельность, поэтому чтение и понимание работы STL-реализации было бы хорошим упражнением. Если это не упражнение, используйте std::unordered_map
std :: map использует дерево Red-Black, поскольку оно получает разумный компромисс между сложностью вставки/удаления узлов и поиска.
Это относится к текущим реализациям, но стандарт не требуется. (Никто в настоящее время не знает другую структуру данных, которая может отвечать требованиям, но завтра ее можно было бы открыть). –
std :: время поиска карты не O (1) его O (log (n)).
std :: unordered_map имеет время поиска O (1), амортизированное.
std :: unordered_map и std :: unordered_set - hashtables.
где вы узнали, что поиск O (1)? Сначала прочитайте [docs] (http://en.cppreference.com/w/cpp/container/map), во-вторых, они обычно реализуются как [красно-черные деревья] (https://en.wikipedia.org/wiki/Red% E2% 80% 93black_tree), в-третьих, ваш другой вопрос слишком широк. – EdChum
Также постарайтесь ограничить себя вопросом на вопрос. – nwp