Какой самый быстрый контейнер 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 везде.
