Есть ли структура данных в C++ с O(1) lookup?O (1) поиск в C++
A std::map имеет O(log(n)) время поиска (справа?).
Я ищу что-то в std предпочтительно (так что не Boost PLS). Также, если есть, как это работает?
EDIT: Хорошо, я не был достаточно ясным, я думаю. Я хочу связать ценности, вроде как в map. Поэтому я хочу что-то вроде std::map<int,string>, и find и insert следует взять O(1).
Массивы имеют O (1) поиск. Hashtable (std :: unordered_map) для C++ 11 имеет O (1) поиск. (Амортизировано, но более или менее постоянное.)
Я также хотел бы упомянуть, что древовидные структуры данных, такие как карты, имеют большие преимущества и являются только log (n), которые чаще всего являются недостаточными.
Ответ на редактирование -> Вы можете буквально связать индекс массива с одним из значений. Также хеш-таблицы являются ассоциативными, но идеальный хеш (каждый ключ отображает точно 1 значение) действительно сложно получить.
Еще одна вещь, о которой стоит упомянуть: массивы обладают большой пропускной способностью (из-за локальности, ака-элементы находятся рядом друг с другом, чтобы их можно было предварительно кэшировать с помощью механизма предварительной обработки). Деревья, не так много. При разумном количестве элементов хеш-производительность может быть более критичной, чем асимптотическая производительность.
Также стоит упомянуть, что в TR1 имеется неупорядоченная карта. Некоторые компиляторы, такие как VS2008 и ранее GCC, реализуют TR1, но не C++ 11. – Puppy
@scarletamaranth Основная причина, по которой массивы настолько эффективны, потому что они находятся рядом друг с другом -> система просто перескакивает в памяти (индекс индекса index + sizeof (type) *), как вы сказали, что это не совсем ясно, как вы говорите кэш. –
@Shingetsu Вот что я сказал ... – ScarletAmaranth
Структуры данных с O (1) поиска (без учета размера ключа) включают в себя:
Для сложных типов, сбалансированные деревья будут штраф в O (log n), или иногда вы можете уйти с patricia trie по номеру O (k).
Для справки: complexity of search structures
Массивы не являются ассоциативными. Какая хеш-таблица есть в 'std'? – AMCoder
@AMCoder: существует 'std :: unordered_map'. – Puppy
хэш-таблицы не O (1) - все еще должны быть проверки на столкновение и повторение ведер, если есть столкновение. Наилучшим случаем является O (1), но не всегда. –
Все зависит от данных, особенно от типа и * возможных * значений ключа: так какие данные вы хотите сохранить? – Nawaz
Возможно, что-то похожее на связанный массив? Он имеет около O (1). Связанный массив - это связанный список массивов. –
'std :: unordered_map <>'. И причина, по которой это происходит в пространстве имен 'std', заключается в том, что она была в пространстве имен' boost' в первую очередь. – ildjarn