Форум программистов, компьютерный форум, киберфорум
С++ для начинающих
Войти
Регистрация
Восстановить пароль
 
 
Рейтинг 4.78/40: Рейтинг темы: голосов - 40, средняя оценка - 4.78
21 / 19 / 7
Регистрация: 14.03.2014
Сообщений: 249
1

Unordered_map правильное применение

25.11.2017, 15:26. Показов 8153. Ответов 62
Метки нет (Все метки)

Решил разобраться с этим контейнером, но не вижу ни одной комплексной сатьи по этой теме.
Кто нибудь может ответить на простые вопросы:
1)Имеют ли данные контейнеры практический смысл в сравнение с вектором у которого свой аллокатор ?
2)Я так понимаю что контейнер малопригоден в готовом виде с параметрами по умолчанию ?
3)Если его использовать не в готовом, то хеши надо солить. а солить можно по разному и есть ли какая нибудь удачная реализация (так как чувствую что создам велосипед, если буду делать сам) ?
4)Чем отличается реализация boost unordered_map от std::unordered_map?
__________________
Помощь в написании контрольных, курсовых и дипломных работ здесь
0
Лучшие ответы (1)
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
25.11.2017, 15:26
Ответы с готовыми решениями:

Каким образом unordered_map выдает правильное значение для ключа, если его хеш функция допускает коллизии?
Читаю книгу джосаттис стандартная библиотека c++, там в разделе про unordered_map есть описание...

Правильное применение функций
Есть задачка одна, студенческая, простая вроде, проблема лишь в том что к ней надо подключить...

Правильное применение перечисления enum
Дело в том, что не пойму как работать с перечислением. Мне нужно, чтобы программа принимала данные...

Контейнер unordered_map<string, unordered_map<string,int>>
Ну можно и не unordered_map&lt;string, unordered_map&lt;string,int&gt;&gt;. Мне нужен контейнер который будет...

62
7031 / 6054 / 2751
Регистрация: 14.04.2014
Сообщений: 25,922
25.11.2017, 15:37 2
При чём тут вектор? Он не заменяет map.
В boost должно быть тоже самое. Оттуда он и пришёл.
0
21 / 19 / 7
Регистрация: 14.03.2014
Сообщений: 249
25.11.2017, 15:41  [ТС] 3
nmcf, Вектор тут при том что он имеет соизмеримую оценку производительности по операциям поиска, а если с аллокатором то и по операциям вставки т.е. константу.
0
1501 / 803 / 175
Регистрация: 05.12.2015
Сообщений: 2,391
25.11.2017, 16:48 4
Цитата Сообщение от Pechkin80 Посмотреть сообщение
а если с аллокатором то и по операциям вставки т.е. константу.
Вы заблуждаетесь. Вектор это всегда непрерывный кусок памяти.
0
21 / 19 / 7
Регистрация: 14.03.2014
Сообщений: 249
25.11.2017, 16:51  [ТС] 5
avgoor, Я в курсе, но вектор это динамический массив.

Добавлено через 1 минуту
точнее обертка над динамическим массивом + сам массив
0
1501 / 803 / 175
Регистрация: 05.12.2015
Сообщений: 2,391
25.11.2017, 16:52 6
Pechkin80, Ну, вставтье в середину вектора элемент без сдвига остальных...
0
зомбяк
1543 / 1185 / 336
Регистрация: 14.05.2017
Сообщений: 3,846
25.11.2017, 16:53 7
Цитата Сообщение от Pechkin80 Посмотреть сообщение
он имеет соизмеримую оценку производительности по операциям поиска
только если он был заранее отсортирован.
0
21 / 19 / 7
Регистрация: 14.03.2014
Сообщений: 249
25.11.2017, 16:57  [ТС] 8
avgoor, ну так unordered_map вам вообще не гарантирует в какое место он вставит.

Добавлено через 1 минуту
TRam_, Необязательно, в данном контексте я имею ввиду если известен индекс, так как при использовании unordered_map мы подразумеваем что ключ известен.
0
1501 / 803 / 175
Регистрация: 05.12.2015
Сообщений: 2,391
25.11.2017, 17:01 9
Цитата Сообщение от Pechkin80 Посмотреть сообщение
ну так unordered_map вам вообще не гарантирует в какое место он вставит.
Но он гарантирует (с оговорками) константный доступ по ключу. Отсортированный вектор корректно сравнивать с map, а не unordered_map (у обоих логарифмическое время). Плюс вставка даже в конец вектора иногда требует реаллокации. Константная вставка у дека.
0
21 / 19 / 7
Регистрация: 14.03.2014
Сообщений: 249
25.11.2017, 17:09  [ТС] 10
avgoor, У вектора тоже константный доступ к ключу, если известен индекс (как аналог ключа). А сортированный вектор или нет это в данном контексте без разницы.

Добавлено через 5 минут
По поводу вставки я специально оговорился в первом посте, то я рассматриваю случай с кастомным аллокатором. Тем более оба контейнера резервируют память по элементы.
0
зомбяк
1543 / 1185 / 336
Регистрация: 14.05.2017
Сообщений: 3,846
25.11.2017, 17:09 11
Цитата Сообщение от Pechkin80 Посмотреть сообщение
известен индекс (как аналог ключа)
Если у нас есть функция преобразования ключа в индекс, то это хэш-таблица. Если у нас поиск идёт по индексу, то время для вектора константно, а вот для map'ов останется логарифмическим.
0
1501 / 803 / 175
Регистрация: 05.12.2015
Сообщений: 2,391
25.11.2017, 17:11 12
Цитата Сообщение от Pechkin80 Посмотреть сообщение
если известен индекс (как аналог ключа)
Откуда же он известен?
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
1501 / 803 / 175
Регистрация: 05.12.2015
Сообщений: 2,391
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
1501 / 803 / 175
Регистрация: 05.12.2015
Сообщений: 2,391
25.11.2017, 17:36 16
Цитата Сообщение от Pechkin80 Посмотреть сообщение
преимущество хеш-таблиц когда индекс неизвестен и надо искать очень быстро. С вопросами 2-4 пока непонятно.
Я б сказал не преимущество, а прямое предназначение (организовать соответствие одних данных другим)

2) Вполне пригоден. Только, если тип ключа свой - надо указать hasher.
3) Ничего солить не надо. Скорее наоборот - ситуации в которых стандартные алгоритмы хэшей не подходят достаточно редкие.
4) Посмотрите. заодно поймете как работают хэш таблицы

В яве, например, используется именно HashMap по умолчанию.
0
21 / 19 / 7
Регистрация: 14.03.2014
Сообщений: 249
25.11.2017, 17:44  [ТС] 17
Цитата Сообщение от avgoor
3) Ничего солить не надо. Скорее наоборот - ситуации в которых стандартные алгоритмы хэшей не подходят достаточно редкие.
Ну во первых, я тоже думаю что стандартные алгоритмы вполне хороши, вопрос не в алгоритмах а в данных. Солят не из-за плохих алгоритмов, а из-за данных которые могут вызывать коллизии и вот про эти "редкие" случае я и виду речь. Но мой вопрос шире ем когда солить, а когда не солить. Просто интересно чтото универсальное. Так как хеш таблица это штука ненужная для малых n(при малых n простой перебор может быть быстрее), то и дополнительные затраты на универсальность не страшны.
0
Jesus loves me
Эксперт С++
5196 / 3167 / 357
Регистрация: 12.12.2009
Сообщений: 8,001
Записей в блоге: 2
25.11.2017, 17:45 18
Выше уже намекнули, попробую дополнить.
Нужно рассматривать вопрос гораздо шире - где нужна хеш таблица и в чем она лучше массива (читай вектора).
Цитата Сообщение от Pechkin80 Посмотреть сообщение
1)Имеют ли данные контейнеры практический смысл в сравнение с вектором у которого свой аллокатор ?
Как выше писали сравнивать вектор и мап это теплое с мягким.
Цитата Сообщение от Pechkin80 Посмотреть сообщение
2)Я так понимаю что контейнер малопригоден в готовом виде с параметрами по умолчанию ?
Пригоден, именно так он и используется в 99% случаев, 1% - это специфичный случай (особая архитектура системы или особые требования к продукту)
Цитата Сообщение от Pechkin80 Посмотреть сообщение
3)Если его использовать не в готовом, то хеши надо солить. а солить можно по разному и есть ли какая нибудь удачная реализация (так как чувствую что создам велосипед, если буду делать сам) ?
Соль тут не при чем, ты думаешь в другую сторону. Соль нужна когда ты пароли пользователей в БД пишешь, а тут просто хеш-таблица (контейнер с быстрым доступом по ключу любого типа)
Цитата Сообщение от Pechkin80 Посмотреть сообщение
4)Чем отличается реализация boost unordered_map от std::unordered_map?
Вопрос не корректен. Никто не знает как это делается в std::, потому что в стандарте есть только требования по скорости операций (выраженные через big O). Плюс явный намек на то, что хеш таблица (unordered_map) использует баккеты (buckets). Сама же реализация может сильно отличаться например в stdlib от майкрософт и от gnu сообщества могут иметь совершенно разные реализации.

Советую почитать про реализацию хеш-таблиц (точнее про разрешение коллизий) - метод открытой адресации и метод цепочек. Потом придти на форум с правильным вопросом "когда использовать std::map а когда std::unordered_map"
1
зомбяк
1543 / 1185 / 336
Регистрация: 14.05.2017
Сообщений: 3,846
25.11.2017, 17:51 19
Цитата Сообщение от Pechkin80 Посмотреть сообщение
данных которые могут вызывать коллизии
Случай, когда мы задаём для точно такого же ключа новое значение коллизией не называется.

По поводу универсальности - чем больше элементов в таблице, тем больше должен быть её размер (т.е. диапазон разбивки индексов должен расти быстрее, чем длина ключа )
0
21 / 19 / 7
Регистрация: 14.03.2014
Сообщений: 249
25.11.2017, 17:55  [ТС] 20
Я может толком не объяснил, но я про случай когда ключ это захешированные данные часто т.е. в паре {Key, Data} Key = F(Data). Наверно корректнее былобы рассматривать unordered_set, но не так важно. Суть в то что пространство ключей меньше пространства данных.
0
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
25.11.2017, 17:55

Правильное применение с basic_stream
Доброго времени суток! Класс ios_base&lt;&gt; дает нам стандартные потоки из/в файл, строку и...

Правильное применение !
Решил открыть сайт о играх и фильмах, есть уже около 1000 готовых копирайт статей ... тематика...

Правильное применение токового зеркала
Всем привет. Хочу собрать усилитель на транзисторе с низкими собственными шумами. Нагрузка...

VAO, VBO и их правильное применение
Всех с наступившем, в общем меня интересует вопрос как правильно использовать VBO и VAO чтобы...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
20
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2021, vBulletin Solutions, Inc.