Я новичок в С++. Мне нужно сохранить список адресов, которые дают очень хорошую производительность с точки зрения поиска и добавления новых записей.
Сначала я хочу увидеть, присутствует ли этот адрес в списке, если да, то не пишите, иначе добавьте новую запись в этот список.
И в момент той или иной операции смотреть, присутствует адрес в списке или нет.
Есть ли в C++ быстрый доступ и динамично растущая структура данных с точки зрения памяти и места.
Я бы предложил использовать std::map (обычно реализованный как некоторый красно-черное дерево), которое имеет логарифмическую сложность, поэтому на практике должно быть достаточно.
Если у вас есть реализация, соответствующая стандарту C++11, вы можете рассмотреть std::unordered_map (обычно реализован в виде некоторой хеш-таблицы).
Если вам не нужны никакие данные, связанные с ключами, а только для обработки их наборов, используйте std::set или std::unordered_set
И многие библиотеки (Boost, Qt,...) также реализуют ассоциативные контейнеры.
boost::unordered_map в C++03.
- person Cat Plus Plus; 18.03.2012
std::unordered_map в значительной степени взят из Boost, а реализация Boost, вероятно, довольно автономна и может быть скопирована в проект, если кто-то не зависит от полного пакета Boost.
- person Cat Plus Plus; 18.03.2012
