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

Я не могу найти никакой информации об этом, поэтому я перехожу к stackoverflow. Насколько эффективны итераторы std:: tr1:: unordered_map в С++? Особенно по сравнению с, скажем, списком итераторов. Было бы целесообразно создать класс-оболочку, который также содержит все ключи в списке, чтобы обеспечить эффективную итерацию (мой код действительно использует много итераций по клавишам в unordered_map). Для тех, кто будет рекомендовать повышение, я не могу использовать его (по каким-либо причинам).

Ответ 1

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

Ответ 2

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

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

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

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

Ответ 3

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

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

Какой самый лучший способ сказать то, что я хочу? Возможно, запись класса оболочки добавляет ненужную сложность вашему коду. Сначала сделайте это правильно, затем сделайте это быстро.
Могу ли я предоставить дополнительную память и время для поддержки list параллельно с unordered_map?
Действительно ли unordered_map правильная структура данных? Если ваш наиболее распространенный вариант использования - обход от начала до конца, вам может быть лучше с vector, потому что память гарантированно будет непрерывной.

Ответ 4

Ответы на тесты здесь fooobar.com/info/80763/... unordered_map является частью пути между вектором и картой для итерации. Это значительно быстрее, чем карта.