Какую структуру STL использовать?

Мне нужно решение, в котором будут храниться не уникальные пары ключей - значений. Я не хочу повторять клавиши (эффективность пространства), и я хочу сосредоточиться на скорости поиска (эффективность вставки новых данных менее важна). Здесь я буду использовать std :: multimap. Но мне придется искать ключи, которые соответствуют некоторым критериям диапазона.Какую структуру STL использовать?

Самый сложный пример: Ключ - это строка, значения не важны. Я хотел бы узнать все значения, ключи которых начинаются с «Lol». Или я хотел бы узнать все значения, ключи которых находятся между «" баром "и" foo ".

Могу ли я сделать это с помощью мультимапа? Моя вторая мысль - использовать отсортированный вектор, который будет указывать на векторы значений. Что-то вроде этого:

std::vector<std::string, std::vector<T>> sorted_vec;

Тогда я с легкостью отвечаю критериям поиска. Но я действительно забочусь о результатах поиска. Это правильный подход?

источник

2013-04-07 Dejwi

Похоже, что упорядоченная карта векторов больше по линии, которую вы описываете, но я не уверен, что она достаточно универсальна для вас. – WhozCraig

Если вставка не важна, я думаю, что '' vector'' будет предпочтительнее, чем '' map'' ', потому что последний основан на rb-tree. '' struct foo {}; вектор ; '' может быть в порядке. – gongzhitaao

Да, вы можете использовать std :: multimap. И для завершения запроса базы значений диапазона вы можете использовать два алгоритма std :: lower_bound и std :: upper_bound в алгоритме файла заголовка.

источник

2013-04-07 03:28:50

Я думаю, что допустил ошибку в lower_bound и upper_bound. Эти два алгоритма не эффективны для многоадресного итератора. Вместо этого используйте multimap :: lower_bound и multimap :: upper_bound. –

Во-первых, поскольку Dejwi нуждается в «ключах между баром и foo» - тогда [equal_range] (http://en.cppreference.com/w/cpp/container/multimap/equal_range) будет лучше, чем lower_bound + upper_bound. Во-вторых, поскольку он «действительно заботится о производительности поисков» - мультимайл - плохой выбор - отсортированный вектор будет быстрее из-за лучшей локальности. –

Или я хотел бы узнать все значения, ключи которых находятся между «" баром "и" foo ".

Если у вас есть подталкивание, я бы рекомендовал использовать boost::flat_map (это только заголовок только для библиотеки) - он поддерживает sorted vector inside. Как правило, он имеет лучший поиск, чем std :: map из-за лучшей компактности/локальности.

В противном случае используйте

vector<pair<string,value>> 
or 
vector<pair<string,vector<value>>> //(for re-use of keys) 
// instead of pair, you may use just struct if you concerned with lexicographical compare

плюс std::sort

плюс зЬй :: equal_range/lower_bound

источник

2013-04-07 02:46:45

Вы должны использовать Patricia trie.

Есть one in libstdc++, хотя это нестандартно.

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

источник

2013-04-07 02:51:50 tmyklebu