M>Тогда, получается, что не обязательно использовать unordered_map, можно и простой map, если мне нужно упорядочивание по ключу (про разницу в сложности поиска этих map я в курсе)? По идее, в обычной map там же ноды в куче выделяются, а при изменении дерева только перенастраиваются указатели в нодах?
Если нужно обращение по индексам, то не важно — простой map или unordered, все равно или вектор городить рядом, или гетерогенный поиск со сложным ключом, или boost::multi_index.
Если тебе (внезапно) просто нужна сортировка по именам, простой map, конечно же.

M>Тогда, получается, что не обязательно использовать unordered_map, можно и простой map, если мне нужно упорядочивание по ключу (про разницу в сложности поиска этих map я в курсе)? По идее, в обычной map там же ноды в куче выделяются, а при изменении дерева только перенастраиваются указатели в нодах?
Если нужно обращение по индексам, то не важно — простой map или unordered, все равно или вектор городить рядом, или boost::multi_index.
Если тебе (внезапно) просто нужна сортировка по именам, простой map, конечно же.