Преимущества использования map над unordered_map при тривиальных ключах?

Не забывайте, что map сохраняет порядок своих элементов. Если вы не можете отказаться от этой особенности, то, очевидно, unordered_map вам не подойдёт.

Кроме того, стоит помнить, что unordered_map обычно использует больше памяти. У map есть всего несколько служебных указателей и память под каждый объект. Напротив, unordered_map имеет большой массив (в некоторых реализациях он может быть довольно большим), плюс дополнительная память под каждый объект. Если вы хотите следить за потреблением памяти, map будет более эффективным, поскольку в нём нет этого большого массива.

Итак, если вам нужна чистая операция поиска, я бы сказал, что unordered_map – это правильный выбор. Однако всегда есть компромиссы, и если вы не можете их себе позволить, то вам стоит отказаться от использования unordered_map.

Из личного опыта могу сказать, что я заметил огромный прирост производительности (измеренный, конечно), когда использовал unordered_map вместо map в главной таблице поиска сущностей.

С другой стороны, я заметил, что вставка и удаление элементов в unordered_map происходит значительно медленнее. Это отличный вариант для относительно статического набора элементов, но если вы выполняете множество вставок и удалений, то процесс хеширования и распределения может оказаться затратным. (Замечу, что это наблюдение было сделано за многими итерациями.)

Я бы повторил примерно ту же мысль, которую высказал GMan: в зависимости от конкретного использования std::map может быть (и часто оказывается) быстрее, чем std::tr1::unordered_map (используя реализацию, включённую в VS 2008 SP1).

Есть несколько усложняющих факторов, которые стоит учитывать. Например, в std::map вы сравниваете ключи, что означает, что вы просматриваете только ту часть ключа, которая необходима для различия между правым и левым поддеревом. На моем опыте, почти единственный случай, когда вы смотрите на весь ключ, это если вы используете что-то простое, вроде int, что можно сравнить за одну инструкцию. С более типичными типами ключей, такими как std::string, вы часто сравниваете только несколько символов.

С другой стороны, хороший хеш-функция всегда рассматривает весь ключ. Иными словами, даже если поиск в таблице имеет постоянную сложность, сам процесс хеширования имеет примерно линейную сложность (хотя по длине ключа, а не по количеству элементов). При использовании длинных строк в качестве ключей std::map может закончить поиск быстрее, чем unordered_map даже начнёт свой.

Во-вторых, хотя существует множество методов изменения размера хеш-таблиц, большинство из них довольно медленные — до такой степени, что если поиск происходит значительно чаще, чем вставка и удаление, std::map часто будет быстрее, чем std::unordered_map.

Конечно, как я упоминал в комментарии к вашему предыдущему вопросу, вы также можете использовать таблицы с деревьями. Это имеет свои плюсы и минусы. С одной стороны, это ограничивает худший случай до дерева. Также это позволяет быстро вставлять и удалять элементы, потому что (по крайней мере в моем опыте) я использовал фиксированный размер таблицы. Исключение всех изменений размера таблицы позволяет сделать вашу хеш-таблицу намного проще и, как правило, быстрее.

Ещё один момент: требования к хешированию и к картам на основе деревьев различны. Хеширование, очевидно, требует хеш-функцию и проверку на равенство, в то время как упорядоченные карты требуют сравнения по принципу "меньше чем". Конечно, гибрид, о котором я упоминал, требует обоих подходов. Конечно, в общем случае использования строк в качестве ключа это не является проблемой, но некоторые типы ключей лучше подходят для упорядочивания, чем для хеширования (или наоборот).

Значительные различия, которые здесь не были должным образом упомянуты:

• map сохраняет итераторы ко всем элементам стабильными; начиная с C++17, вы даже можете перемещать элементы из одного map в другой, не нарушая итераторы для них (и, если это правильно реализовано, без потенциальных аллокаций).
• Временные характеристики map для одиночных операций, как правило, более предсказуемы, так как он никогда не требует больших аллокаций.
• unordered_map, использующий std::hash, как реализовано в libstdc++, уязвим для атаки типа DoS при обработке недоверенного ввода (он использует MurmurHash2 с постоянным значением начального семени — это не сильно поможет, см. https://emboss.github.io/blog/2012/12/14/breaking-murmur-hash-flooding-dos-reloaded/).
• Наличие порядка позволяет эффективно выполнять диапазонные запросы, например, итерировать по всем элементам с ключом ≥ 42.

В других ответах уже приведены причины, поэтому я добавлю свои.

Операции с std::map (сбалансированное бинарное дерево) имеют амортизированную сложность O(log n) и худший случай O(log n). В то время как операции с std::unordered_map (хеш-таблица) имеют амортизированную сложность O(1) и худший случай O(n).

На практике это означает, что хеш-таблица иногда "пауза", выполняя операцию со сложностью O(n), что вашему приложению может не подойти. Если ваше приложение не может терпеть такие задержки, вам стоит предпочесть std::map вместо std::unordered_map.

Хеш-таблицы имеют более высокие постоянные множители в сложности времени по сравнению с обычными реализациями отображений, и это становится значительным для небольших контейнеров. Максимальный размер составляет 10, 100 или даже 1000 и более? Постоянные множители остаются прежними, но O(log n) близок к O(1). (Помните, что логарифмическая сложность все еще очень хороша.)

Что делает хорошую хеш-функцию, зависит от характеристик ваших данных. Если я не планирую использовать пользовательскую хеш-функцию (но, безусловно, могу изменить свое мнение позже, так как яtypedef почти все), и хотя значения по умолчанию выбраны так, чтобы хорошо работать с множеством источников данных, я считаю, что упорядоченная структура map вначале достаточно полезна, чтобы я всё равно использовал map вместо хеш-таблицы в таком случае.

Кроме того, таким образом, вам не придется беспокоиться о написании хеш-функции для других (обычно пользовательских типов данных), и достаточно просто реализовать оператор < (что, в любом случае, вам нужно).