существует ли структура данных в c ++, которая имеет сложность времени поиска O (1)?Как проверить, присутствует ли элемент в нем или нет, и, если присутствует, какова его позиция или связанный индекс / ключ / значение
В библиотеке Google Abseil есть также высококачественные контейнеры с открытым исходным кодом "Swiss table" .На CppCon 2017, , был забавный доклад , в котором описывается реализация и цели этих контейнеров.
Короче говоря, они похожи на хеш-контейнеры в стандарте, но обычно обеспечивают лучшую производительностьпотому что они более дружественны к кешу (за счет несоблюдения стабильности ссылок, как отмечено в комментариях).
То, что вам нужно, это C ++ 11 std::unordered_map, со средним временем доступа O (1) и наихудшим случаем O (n).
std::unordered_map