Легенда:
новое сообщение
закрытая нитка
новое сообщение
в закрытой нитке
старое сообщение
|
- Напоминаю, что масса вопросов по функционированию форума снимается после прочтения его описания.
- Новичкам также крайне полезно ознакомиться с данным документом.
Сортировка вектора всегда гарантирована в данной задаче. 23.05.07 05:17 Число просмотров: 4961
Автор: void <Grebnev Valery> Статус: Elderman
|
> Если бы набор данных был большим, то я бы их хранил в векторе, а к нему > прицепил бы std::map или std::hash_map из boost::shared_ptr-ов (или > boost::intrusive_ptr-ов) на элементы этого вектора.
Сортировка вектора всегда гарантирована в данной задаче.
Кстати вопрос - а гарантируется ли построение сбалансированного дерева std::map или 3party::map?
> А это смотря сколько запросов будет на один вектор. Если одна сортировка - > один запрос, то сортировать каждый раз - очень дорого.
То же относится и к map.
Только std::map хуже. В перед включением ключа std::string (по условию задачи) в map, его надо будет "привести" к верхнему/нижнему регистру.
Это потому, что сравнение должно быть лексикографическое (без учета регистра).
А перед поиском в map, соответственно привести к тому же регистру ключ.
Это очень затратная операция для std::string.
В практических задачах с вектором этого можно не делать, выполняя сортировку "как есть"; а бинарном поиске использовать _stricmp(str1.c_str(), str2.c_str()).
> Если нужна еще бОльшая скорость, то на таких объемах данных очень неплохо > должна проявить себя хэш-таблица.
Для хэш-таблицы перед вычислением хеша потребуется преобразование строки std::string к верхнему/нижнему регистру как при постоении таблицы, так и при определении индекса ("поиске").
|
|
|