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

Question

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

Answer 1

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

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

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

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

Answer 2

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

Answer 3

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

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

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

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

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

Answer 4

Отвечает на тесты здесь https://stackoverflow.com/a/25027750/1085128 unordered_map является частью между вектором и картой для итерацииЭто значительно быстрее, чем карта.