Какой самый быстрый контейнер STL для поиска?

Question

Хорошо, как предисловие Мне необходимо кэшировать относительно небольшое подмножество редко изменяемых данных, чтобы избежать частых запросов к базе данных по соображениям производительности. Эти данные интенсивно используются только для чтения, так как на них часто ссылается гораздо больший набор данных в других таблицах.

Я написал класс, который будет иметь возможность хранить в основном все две таблицы, о которых идет речь, в памяти, одновременно прослушивая изменения фиксации в сочетании с поточно-безопасным механизмом обратного вызова для обновления кэшированных объектов.

Моя текущая реализация имеет два std::vectors по одному для элементов каждой таблицы. Этот класс предоставляет как доступ ко всему каждому вектору, так и удобные методы для поиска определенного элемента данных таблицы с помощью std::find, std::find_if и т. Д.

Кто-нибудь знает, будет ли предпочтительным использование std::list, std::set или std::map вместо std::vector для поиска? В большинстве случаев именно эти контейнеры будут запрашиваться после однократного заполнения базы данных при установлении нового соединения.

Я также открыт для использования функций C ++ 0x, поддерживаемых VS2010 или Boost.

Answer 1

Для поиска определенного значения с std::set и std::map требуется время O (log N), а с двумя другими - O (N); Итак, std::set или std::map, вероятно, лучше. Поскольку у вас есть доступ к C ++ 0x, вы также можете использовать std::unordered_set или std::unordered_map, которые в среднем занимают постоянное время.

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

Однако, если вы будете часто вызывать find_if с определенным предикатом, вы можете оптимизировать себя: используйте std::map или std::set с пользовательским компаратором или специальными клавишами и используйте find вместо.

Answer 2

Сортированный вектор с использованием std::lower_bound может быть таким же быстрым, как std::set, если вы не обновляете его очень часто; они оба O (войдите n). Стоит попробовать оба, чтобы увидеть, что лучше для вашей собственной ситуации.

Answer 3

Поскольку из ваших (расширенных) требований вам нужно выполнять поиск по нескольким полям, я бы указал на Boost.MultiIndex.

Эта библиотека Boost позволяет вам создать один контейнер (только содин пример каждого элемента, который он содержит) и индексировать его над произвольным числом индексов.Это также позволяет точно определить, какие индексы использовать.

Чтобы определить тип используемого индекса, вам потребуются обширные тесты.500 - это относительно небольшое количество записей, поэтому постоянные факторы не будут играть хорошо.Кроме того, может быть заметная разница между однопоточным и многопоточным использованием (большинство реализаций хеш-таблиц могут рухнуть при использовании MT, потому что они не используют линейную перефразировку, и, таким образом, один поток в итоге перефразирует таблицу, блокируя вседругие).

Я бы порекомендовал отсортированный индекс (например, список пропусков, если возможно) для размещения запросов диапазона (все имена начинаются с Abc?), если разница в производительности либо незаметна, либо просто не имеет значения.

Answer 4

Если вы хотите искать только отдельные значения в одном конкретном столбце таблицы, тогда std::hash самый быстрый.

Если вы хотите иметь возможность поиска с использованием нескольких разных предикатов, вам понадобится какая-то структура индекса. Это может быть реализовано путем расширения вашего текущего векторного подхода на основе нескольких хеш-таблиц или карт, по одной на каждое поле для поиска, где значение является либо индексом в векторе, либо прямым указателем на элемент в векторе.

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

Answer 5

Проверьте это. Это очень просто, контейнеры в STL практически взаимозаменяемы.

Answer 6

Не stl, но коммерческий контейнер c ++ является abax-контейнером, в котором O (1) находится в поиске, удалении, изменении, O (logn) во вставке.

Answer 7

Не является ответом как таковым, но обязательно используйте typedef для ссылки на тип контейнера, который вы используете, что-то вроде typedef std::vector< itemtype > data_table_cache; Затем используйте ваш тип typedef везде.