Эффективность итераторов в unordered_map (C++)

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

К сожалению, вы не можете с уверенностью сказать, достаточно ли эффективно что-то, если не попробуете и не измерили результаты. Я могу сказать вам, что стандартная библиотека, классы TR1 и Boost уже давно наблюдали за ними. Вероятно, они настолько быстрые, насколько это возможно для наиболее распространенных случаев использования. Ходить по контейнеру, безусловно, является распространенным вариантом использования.

С учетом всего сказанного вам нужно задать себе несколько вопросов:

1. Как лучше всего выразить то, что я хочу? Возможно, написание класса-оболочки добавляет к вашему коду ненужную сложность. Сначала исправьте, затем сделайте быстро.

2. Могу ли я позволить себе дополнительную память и время для поддержки списка параллельно с unordered_map ?

3. Действительно ли unordered_map правильная структура данных? Если ваш наиболее частый вариант использования - обход от начала до конца, вам может быть лучше использовать вектор , потому что память гарантированно непрерывна.

Я не проверял TR1, но N3035 (черновик C ++ 0x) говорит следующее:

Все категории итераторов требуют только тех функций, которые возможность реализации для данной категории в постоянное время (с амортизацией). Следовательно, таблицы требований для итераторов не имеют столбца сложности.

Стандарт не дает гарантии эффективности, кроме как с точки зрения сложности, поэтому у вас нет гарантированного сравнения list и unordered_map , кроме того, что они оба амортизированное постоянное время (т. е. линейное время для полной итерации по контейнеру).

На практике я ожидаю, что итератор unordered_map будет по крайней мере рядом с list , , если только ваша хэш-карта не заполнена очень редко. В сложности полной итерации может быть термин O (количество сегментов).Но я никогда не рассматривал ни одной реализации специально unordered_map для C ++, поэтому я не знаю, каких украшений ожидать от упрощенной реализации хэш-таблицы «массив связанных списков». Если у вас есть "типичная" платформа, протестируйте это, если вы пытаетесь написать код, который определенно будет самым быстрым из всех реализаций C ++, тогда вам не повезет; -)