21 / 19 / 7
Регистрация: 14.03.2014
Сообщений: 249
|
|
1 | |
Unordered_map правильное применение25.11.2017, 15:26. Показов 9635. Ответов 62
Метки нет Все метки)
(
Решил разобраться с этим контейнером, но не вижу ни одной комплексной сатьи по этой теме.
Кто нибудь может ответить на простые вопросы: 1)Имеют ли данные контейнеры практический смысл в сравнение с вектором у которого свой аллокатор ? 2)Я так понимаю что контейнер малопригоден в готовом виде с параметрами по умолчанию ? 3)Если его использовать не в готовом, то хеши надо солить. а солить можно по разному и есть ли какая нибудь удачная реализация (так как чувствую что создам велосипед, если буду делать сам) ? 4)Чем отличается реализация boost unordered_map от std::unordered_map?
__________________
Помощь в написании контрольных, курсовых и дипломных работ, диссертаций здесь
0
|
|
25.11.2017, 15:26 | |
Ответы с готовыми решениями:
62
Правильное применение функций
Контейнер unordered_map<string, unordered_map<string,int>> |
7275 / 6220 / 2833
Регистрация: 14.04.2014
Сообщений: 26,871
|
|
25.11.2017, 15:37 | 2 |
При чём тут вектор? Он не заменяет map.
В boost должно быть тоже самое. Оттуда он и пришёл.
0
|
21 / 19 / 7
Регистрация: 14.03.2014
Сообщений: 249
|
|
25.11.2017, 15:41 [ТС] | 3 |
nmcf, Вектор тут при том что он имеет соизмеримую оценку производительности по операциям поиска, а если с аллокатором то и по операциям вставки т.е. константу.
0
|
1550 / 875 / 179
Регистрация: 05.12.2015
Сообщений: 2,555
|
|
25.11.2017, 16:48 | 4 |
0
|
21 / 19 / 7
Регистрация: 14.03.2014
Сообщений: 249
|
|
25.11.2017, 16:51 [ТС] | 5 |
avgoor, Я в курсе, но вектор это динамический массив.
Добавлено через 1 минуту точнее обертка над динамическим массивом + сам массив
0
|
1550 / 875 / 179
Регистрация: 05.12.2015
Сообщений: 2,555
|
|
25.11.2017, 16:52 | 6 |
Pechkin80, Ну, вставтье в середину вектора элемент без сдвига остальных...
0
|
зомбяк
1564 / 1213 / 345
Регистрация: 14.05.2017
Сообщений: 3,936
|
|
25.11.2017, 16:53 | 7 |
0
|
21 / 19 / 7
Регистрация: 14.03.2014
Сообщений: 249
|
|
25.11.2017, 16:57 [ТС] | 8 |
avgoor, ну так unordered_map вам вообще не гарантирует в какое место он вставит.
Добавлено через 1 минуту TRam_, Необязательно, в данном контексте я имею ввиду если известен индекс, так как при использовании unordered_map мы подразумеваем что ключ известен.
0
|
1550 / 875 / 179
Регистрация: 05.12.2015
Сообщений: 2,555
|
|
25.11.2017, 17:01 | 9 |
Но он гарантирует (с оговорками) константный доступ по ключу. Отсортированный вектор корректно сравнивать с map, а не unordered_map (у обоих логарифмическое время). Плюс вставка даже в конец вектора иногда требует реаллокации. Константная вставка у дека.
0
|
21 / 19 / 7
Регистрация: 14.03.2014
Сообщений: 249
|
|
25.11.2017, 17:09 [ТС] | 10 |
avgoor, У вектора тоже константный доступ к ключу, если известен индекс (как аналог ключа). А сортированный вектор или нет это в данном контексте без разницы.
Добавлено через 5 минут По поводу вставки я специально оговорился в первом посте, то я рассматриваю случай с кастомным аллокатором. Тем более оба контейнера резервируют память по элементы.
0
|
зомбяк
1564 / 1213 / 345
Регистрация: 14.05.2017
Сообщений: 3,936
|
|
25.11.2017, 17:09 | 11 |
Если у нас есть функция преобразования ключа в индекс, то это хэш-таблица. Если у нас поиск идёт по индексу, то время для вектора константно, а вот для map'ов останется логарифмическим.
0
|
1550 / 875 / 179
Регистрация: 05.12.2015
Сообщений: 2,555
|
|
25.11.2017, 17:11 | 12 |
Откуда же он известен?
map и unordered_map ставят в соответствие значению ключа почти любого типа другое значение. Когда говорят о соответствии вектора мапу - обычно имеют ввиду вектор пар ключ-значение, отсортированный по ключу. И чтобы определить индекс в векторе нужен поиск.
0
|
21 / 19 / 7
Регистрация: 14.03.2014
Сообщений: 249
|
|
25.11.2017, 17:15 [ТС] | 13 |
TRam_, Я про map тут ничего не говорил. Я только unordered_map который к map не имеет никакого отношения (кроме того что оба ассоциативные контейнеры)
Добавлено через 3 минуты avgoor, Поиск в данном случае это только получение адреса по ключу и не более. Поиск в обычном смысли в unordered_map сравним с вектором т.е. оба O(n)
0
|
1550 / 875 / 179
Регистрация: 05.12.2015
Сообщений: 2,555
|
|
25.11.2017, 17:20 | 14 |
Pechkin80, Вот вам задача: хранятся данные об уголовных элементах
![]()
0
|
21 / 19 / 7
Регистрация: 14.03.2014
Сообщений: 249
|
|
25.11.2017, 17:27 [ТС] | 15 |
avgoor, Я понял ответ на первый вопрос. т.е. преимущество хеш-таблиц когда индекс неизвестен и надо искать очень быстро. С вопросами 2-4 пока непонятно.
0
|
1550 / 875 / 179
Регистрация: 05.12.2015
Сообщений: 2,555
|
|
25.11.2017, 17:36 | 16 |
Я б сказал не преимущество, а прямое предназначение (организовать соответствие одних данных другим)
2) Вполне пригоден. Только, если тип ключа свой - надо указать hasher. 3) Ничего солить не надо. Скорее наоборот - ситуации в которых стандартные алгоритмы хэшей не подходят достаточно редкие. 4) Посмотрите. заодно поймете как работают хэш таблицы В яве, например, используется именно HashMap по умолчанию.
0
|
21 / 19 / 7
Регистрация: 14.03.2014
Сообщений: 249
|
|
25.11.2017, 17:44 [ТС] | 17 |
![]()
0
|
25.11.2017, 17:45 | 18 |
Выше уже намекнули, попробую дополнить.
Нужно рассматривать вопрос гораздо шире - где нужна хеш таблица и в чем она лучше массива (читай вектора). Как выше писали сравнивать вектор и мап это теплое с мягким. Пригоден, именно так он и используется в 99% случаев, 1% - это специфичный случай (особая архитектура системы или особые требования к продукту) Соль тут не при чем, ты думаешь в другую сторону. Соль нужна когда ты пароли пользователей в БД пишешь, а тут просто хеш-таблица (контейнер с быстрым доступом по ключу любого типа) Вопрос не корректен. Никто не знает как это делается в std::, потому что в стандарте есть только требования по скорости операций (выраженные через big O). Плюс явный намек на то, что хеш таблица (unordered_map) использует баккеты (buckets). Сама же реализация может сильно отличаться например в stdlib от майкрософт и от gnu сообщества могут иметь совершенно разные реализации. Советую почитать про реализацию хеш-таблиц (точнее про разрешение коллизий) - метод открытой адресации и метод цепочек. Потом придти на форум с правильным вопросом "когда использовать std::map а когда std::unordered_map" ![]()
1
|
зомбяк
1564 / 1213 / 345
Регистрация: 14.05.2017
Сообщений: 3,936
|
|
25.11.2017, 17:51 | 19 |
Случай, когда мы задаём для точно такого же ключа новое значение коллизией не называется.
По поводу универсальности - чем больше элементов в таблице, тем больше должен быть её размер (т.е. диапазон разбивки индексов должен расти быстрее, чем длина ключа )
0
|
21 / 19 / 7
Регистрация: 14.03.2014
Сообщений: 249
|
|
25.11.2017, 17:55 [ТС] | 20 |
Я может толком не объяснил, но я про случай когда ключ это захешированные данные часто т.е. в паре {Key, Data} Key = F(Data). Наверно корректнее былобы рассматривать unordered_set, но не так важно. Суть в то что пространство ключей меньше пространства данных.
0
|
25.11.2017, 17:55 | |
Помогаю со студенческими работами здесь
20
Правильное применение с basic_stream Правильное применение ! Правильное применение токового зеркала VAO, VBO и их правильное применение Искать еще темы с ответами Или воспользуйтесь поиском по форуму: |