IZ
Alex Sandrov
Дольше по сравнению с vector
Да нет, ты ошибаешься.
https://www.boost.org/doc/libs/1_74_0/doc/html/boost/container/flat_map.html
есть такое, но там нет по индексу обращения
Size: a a a
2020 August 17
SE
IZ
Alex Sandrov
Дольше по сравнению с vector
Итератор что по мап, что по вектору одинаковой сложности.
AS
но зачем?
К примеру, у меня вирутальная грида, я скроллюсь на 100000-й элемент в гриде, и мне надо быстро получить 100000-й элемент в контейнере
AS
Итератор что по мап, что по вектору одинаковой сложности.
Ну что-то мне не верится, в векторе элементы лежат в памяти один за другим, там итерации быстрее, нет разве?
IZ
Alex Sandrov
Ну что-то мне не верится, в векторе элементы лежат в памяти один за другим, там итерации быстрее, нет разве?
Нет разве
IZ
Alex Sandrov
Ну что-то мне не верится, в векторе элементы лежат в памяти один за другим, там итерации быстрее, нет разве?
Тебе не надо верить, тебе надо пройти в cpprefereence найти нужные тебе операции и прочитать про их вычислительную сложность, про гарантии, которые должны давать реализации
AT
Alex Sandrov
Нет, хочется доступа И по ключу (например, текстовый ключ) И по индексу.
Я это и имел в виду в своём вопросе.
(Спасибо Илье за более чёткий вопрос.)
(Спасибо Илье за более чёткий вопрос.)
m
Тебе не надо верить, тебе надо пройти в cpprefereence найти нужные тебе операции и прочитать про их вычислительную сложность, про гарантии, которые должны давать реализации
Эти оценки не учитывают локальность доступа.
IZ
Эти оценки не учитывают локальность доступа.
Чего не учитывают?
m
Чего не учитывают?
Что быстрее итерироваться по листу или вектору?
IZ
Что быстрее итерироваться по листу или вектору?
Одинаково
SE
Одинаково
AK
(с точностью до константы)
IZ
(с точностью до константы)
Согласен
AS
Одинаково
И это хорошая новость. Раньше было не так.
IZ
Alex Sandrov
И это хорошая новость. Раньше было не так.
Всегда было так
m
(с точностью до константы)
Ну вот собственно проблема в том, что итерация по нодам разбросанным в памяти на современных процессорах на порядки медленее чем последовательный доступ. Модели считающие асимптотику по количеству операций это не показывают.
AS
Всегда было так
Пару лет назад, не помню на каком компиляторе, тестировал vector, map и unordered_map, результаты сильно отличались