Ускорение позиционного доступа к std :: map

Question

Я нахожусь в ситуации, когда мне нужно получить доступ к std :: map по позиции.Поскольку std::advance(iter, position) медленный, я хочу добавить вторую структуру данных для ускорения этой операции.

Моя идея: поддерживать вектор для каждой пары ключ-значение на карте.Затем получите доступ к вектору по позиции, vector[position]->second.

. При стирании / вставке нового элемента мне, очевидно, придется удалить итератор из вектора.Но, кроме того, свойства std :: map, сохраняющие итератор, кажутся достаточными.

Вопрос: Это хорошая идея?

Альтернатива: Поддерживать вектор map::keys.Затем получите доступ к вектору по положению и используйте ключ для поиска значения на карте map[vector[position]].Это умнее?

Answer 1

std::map операции поиска, удаления и вставки имеют логарифмическую сложность.Та же сложность может быть достигнута отсортированным std::vector

Не используйте карту, но вектор.Держите это отсортировано по ключу.Бинарный поиск по ключу логарифмический.Доступ по позиции - самый быстрый.

Единственным недостатком является то, что для вставки и удаления требуется перераспределение памяти.Вы можете проверить его производительность и подумать, стоит ли оно.

Answer 2

Если итерация по map является вашей основной проблемой производительности, тогда вы должны использовать flat_map (пока не является частью стандарта, но Boost имеет достойную).Если у вас нет одного из них, просто используйте vector<pair>, который вы продолжаете сортировать, используя ту же функцию сравнения, которую вы использовали бы в своем map.

. Вы можете использовать std::lower_bound в качестве эквивалентафункция для возможности найти значение по его ключу.Вы также можете использовать итератор, возвращаемый из std::lower_bound, в качестве позиции для вставки нового элемента в один элемент.Все остальное работает так же, как и все остальные vector;просто держите это в порядке, и все будет в порядке.