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

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

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

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

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

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

Ответ 1

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

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

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

Ответ 2

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

Ответ 3

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

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

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

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

Ответ 4

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

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

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

Ответ 5

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

Ответ 6

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

Ответ 7

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