> Сортировка вектора всегда гарантирована в данной задаче.
> Кстати вопрос - а гарантируется ли построение
> сбалансированного дерева std::map или 3party::map?
Да. Логарифмическое (для худшего случая) время поиска/вставки/удаления элемента в std::map - это требование стандарта. На данный момент я знаю только одну структуру данных, которая отвечает данным требованиям: RB-деревья. Соответственно std::map-ы практически всегда реализуются на них.
> > А это смотря сколько запросов будет на один вектор.
> Если одна сортировка -
> > один запрос, то сортировать каждый раз - очень дорого.
>
> То же относится и к map.
Ну, вставка КАЖДОГО элемента в map - операция с логарифмической сложностью. А сортировка массива - однократная операция. Хотя согласен, они похожи в том смысле, что если дерево/вектор создается только один раз, а потом из него только выбираются элементы, то поиск и в том и в другом - логарифмический.
> Только std::map хуже. В перед включением ключа std::string
> (по условию задачи) в map, его надо будет "привести" к
> верхнему/нижнему регистру.
> Это потому, что сравнение должно быть лексикографическое
> (без учета регистра).
> А перед поиском в map, соответственно привести к тому же
> регистру ключ.
template <
class Key,
class Type,
class Traits = less<Key>,
class Allocator=allocator<pair <const Key, Type> >
>
class map
---
Есть целая пачка способов указать операцию сравнения для map-ы. Если не считать извращений с наследованием от std::string, то самыми логичными видятся два:
1. Специализация std::less<std::string>
2. Создание std::map<<Key, Type, case_insensitive_compare>
> Это очень затратная операция для std::string.
> В практических задачах с вектором этого можно не делать,
> выполняя сортировку "как есть"; а бинарном поиске
> использовать _stricmp(str1.c_str(), str2.c_str()).
"Как есть" в данном случае это посимвольное преобразование регистра и первой и второй строки непосредственно в момент сравнения. Для худшего случая такой вариант будет в 2 раза медленнее, чем вариант с однократным преобразованием первой строки.
Да и в случае std::map этого тоже можно не делать, если есть увернность в том, что худшего случая не будет.
> Для хэш-таблицы перед вычислением хеша потребуется
> преобразование строки std::string к верхнему/нижнему
> регистру как при постоении таблицы, так и при определении
> индекса ("поиске").
Хэш функция не обязана использовать ВСЮ строку (данные в общем случае), которую ей передают. В частности алфавитный указатель в словарях - пример хэш таблицы. В этом случае хэшем является первая буква.
|
подробно о проекте
Анализ криптографических сетевых...
новое сообщение
закрытая нитка
новое сообщение
в закрытой нитке
старое сообщение
