Структура данных для одного списка столбцов для хранения адресов, лучший поиск O (1) в C ++

Question

Я новичок в C ++.Мне нужно сохранить список адресов, которые дают очень хорошую производительность с точки зрения поиска и добавления новых записей.

Сначала я хочу посмотреть, присутствует ли адрес в списке, если да, то ненапишите, иначе добавьте новую запись в этот список.

И во время определенной операции посмотрите, присутствует ли адрес в списке или нет.

Есть ли быстрый доступ и динамический ростструктура данных в терминах памяти и пространства в C ++.

Answer 1

Я бы предложил использовать std::map (обычно реализуемое как некое красно-черное дерево ), которое имеет логарифмическую сложность, поэтому на практике должно быть достаточно.

Если бы у вас была реализация, соответствующая стандарту C ++ 11, вы могли бы рассмотреть std::unordered_map (обычно реализуемую как некоторую хеш-таблицу ).

Если вы нене требуется никаких связанных данных с ключами, но только для обработки их наборов, например std::set или std::unordered_set

И многие библиотеки (Boost, Qt, ...) также реализуют ассоциативные контейнеры.

Answer 2

Вы ищете boost :: unordered_map .