Stl: нужен контейнер для быстрого поиска по имени? map?

map обеспечивает поиск логаритмической сложности. В принципе да - ассоциативный контейнер (либо отсортированный обычный контейнер - даст возможность применить бинарный поиск).

Добавлено через 2 минуты и 52 секунды
В принципе можно немного ускорить саму операцию сравнения - хранить вместо имени - числовой хеш. Сравнение чисел быстрее чем сравнение строк. Все зависит от задачи.

если не нужно получать элементы в определенном порядке, а нужно только быстро искать их по имени, то лучше использовать hash_map  

У меня в файле храняться данные о пользователях:

надо организовать быстрый поиск по имени пользователя.

Alca

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

если нестандартные решения подходят

если нет - хешируйте имя пользователя сами.

http://ru.wikipedia.org/wiki/%D0%A5%D0%B5%...%BD%D0%B8%D0%B5


Это сообщение отредактировал(а) azesmcar - 7.5.2009, 10:41

если известны данные, что имя может начинаться с буквы из определенного множества, то можно сделать массив map-ов, нечто вроде vector<map<string>> , где индексом в vector будет первая буква имени. Т.о. мы существенно уменьшим количество данных в отдельной карте и увеличим скорость, в ущерб, конечно, памяти.
Аналогично можно делать vector<vector<.....<map>>...> .... - главное фантазия.

Мне кажется, что при большом количестве имен при таком подходе получится кака, т.к. не получится равномерно распределить все имена. Они имеют подлую особенность начинаться с одинаковых букв. Может и не получиться "существенно уменьшить количество данных в одной карте". Или я неправ?

Кол-во строк в файле порядка 1000 -1500.

двоичный поиск даст максимум 10-11 сравнений. это довольно быстро. думаю отсортированный массив вполне подойдет

поиск в map - столько-же, в hash_map - в зависимости от количества коллизий

Получилось префиксное дерево (trie). Дальше фантазия может работать в сторону Patricia и ternary search tree.
Впрочем, не думаю, что топикстартеру при такой постановке задачи нужно что-то кроме хэш-таблицы.

хм. может заюзать простенькую БД. Что - то пихать такое количество инфы в контейнер, имхо, не айс.

Типа эксесса? 

для 1000-1500 записей? там мап и хэш таблица особой разницы не дадут. Там порядке 10 сравнений, для подсчета хэша потеряем больше чем получим прироста при поиске на мой взгляд..хотя надо проверить, но по любому отходить от стандарта ради пары десятка милисекунд думаю  не стоит.

Добавлено @ 13:04

почему? ну пусть каждая структура в среднем ..ну пусть будет 100 байт. Пусть будет 2000 записей, 2000*100=20000, делим на 1024 получаем где-то 20 килобайт..учитывая некоторые затраты памяти требуемые ассоциативными контейнерами, пусть будет 25 килобайт, не больше..это что, так страшно? на мой взгляд не очень 

Это сообщение отредактировал(а) azesmcar - 7.5.2009, 13:06

задача мелкая, изобретений не стоит.
Alca, тестирование уже показало, что требуется оптимизация?
если нет - возьми простейшую реализацию.

Lazin, 

не совсем.
во-первых это не идеально сбаласированные деревья, во вторых там больше накладные расходы на одну проверку. да и памяти больше требует.

Это сообщение отредактировал(а) baldina - 7.5.2009, 13:23