Зачем (в с++) существует контейнер map, если есть hash_map, который быстрее? Например, std::map чем лучше std::unordered_map'a?
3 ответа
Нет понятия «лучше» или «хуже», есть различные свойства контейнера.
std::map
держит данные в отсортированном по ключу виде, в отличие от std::unordered_map
. Если вам нужно это свойство, вам нужен std::map
. Если нет, достаточно и std::unordered_map
.
(Как следствие отсортированности, например, в std::map
есть функция lower_bound
, которой нет в std::unordered_map
.)
-
1можно вопрос немного не по теме: поделитесь ссылкой как внутри устроены стандартные контейнеры? Commented 15 дек. 2015 в 4:52
-
@aleks.andr видео про stl контейнеры youtube.com/playlist?list=PL5jc9xFGsL8G3y3ywuFSvOuNm3GjBwdkb– bkknCommented 15 дек. 2015 в 8:08
-
2@aleks.andr: Это не гарантировано стандартом, и каждый автор стандартной библиотеки может делать как ему вздумается, он лишь обязан соблюдать гарантии O-нотации (типа «добавление за O(1)»). Например,
std::map
в gcc сначала было AVL-деревом, а потом его перевели на красно-чёрное дерево. Так что никакого предписанного устройства контейнеров нету.– VladDCommented 15 дек. 2015 в 10:04 -
Как видно из самого названия контейнера std::unordered_map
элементы этого контейнера не упорядочены. В то время как элементы контейнера std::map
упорядочены в соответствии с ключом.