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

Решил разобраться с этим контейнером, но не вижу ни одной комплексной сатьи по этой теме.
Кто нибудь может ответить на простые вопросы:
1)Имеют ли данные контейнеры практический смысл в сравнение с вектором у которого свой аллокатор ?
2)Я так понимаю что контейнер малопригоден в готовом виде с параметрами по умолчанию ?
3)Если его использовать не в готовом, то хеши надо солить. а солить можно по разному и есть ли какая нибудь удачная реализация (так как чувствую что создам велосипед, если буду делать сам) ?
4)Чем отличается реализация boost unordered_map от std::unordered_map?

0

При чём тут вектор? Он не заменяет map.
В boost должно быть тоже самое. Оттуда он и пришёл.

0

nmcf, Вектор тут при том что он имеет соизмеримую оценку производительности по операциям поиска, а если с аллокатором то и по операциям вставки т.е. константу.

0

Сообщение от Pechkin80 а если с аллокатором то и по операциям вставки т.е. константу.

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

0

avgoor, Я в курсе, но вектор это динамический массив.

Добавлено через 1 минуту
точнее обертка над динамическим массивом + сам массив

0

Pechkin80, Ну, вставтье в середину вектора элемент без сдвига остальных...

0

Сообщение от Pechkin80 он имеет соизмеримую оценку производительности по операциям поиска

только если он был заранее отсортирован.

0

avgoor, ну так unordered_map вам вообще не гарантирует в какое место он вставит.

Добавлено через 1 минуту
TRam_, Необязательно, в данном контексте я имею ввиду если известен индекс, так как при использовании unordered_map мы подразумеваем что ключ известен.

0

Сообщение от Pechkin80 ну так unordered_map вам вообще не гарантирует в какое место он вставит.

Но он гарантирует (с оговорками) константный доступ по ключу. Отсортированный вектор корректно сравнивать с map, а не unordered_map (у обоих логарифмическое время). Плюс вставка даже в конец вектора иногда требует реаллокации. Константная вставка у дека.

0

avgoor, У вектора тоже константный доступ к ключу, если известен индекс (как аналог ключа). А сортированный вектор или нет это в данном контексте без разницы.

Добавлено через 5 минут
По поводу вставки я специально оговорился в первом посте, то я рассматриваю случай с кастомным аллокатором. Тем более оба контейнера резервируют память по элементы.

0

Сообщение от Pechkin80 известен индекс (как аналог ключа)

Если у нас есть функция преобразования ключа в индекс, то это хэш-таблица. Если у нас поиск идёт по индексу, то время для вектора константно, а вот для map'ов останется логарифмическим.

0

Сообщение от Pechkin80 если известен индекс (как аналог ключа)

Откуда же он известен?
map и unordered_map ставят в соответствие значению ключа почти любого типа другое значение. Когда говорят о соответствии вектора мапу - обычно имеют ввиду вектор пар ключ-значение, отсортированный по ключу. И чтобы определить индекс в векторе нужен поиск.

0

TRam_, Я про map тут ничего не говорил. Я только unordered_map который к map не имеет никакого отношения (кроме того что оба ассоциативные контейнеры)

Добавлено через 3 минуты
avgoor, Поиск в данном случае это только получение адреса по ключу и не более. Поиск в обычном смысли в unordered_map сравним с вектором т.е. оба O(n)

0

Pechkin80, Вот вам задача: хранятся данные об уголовных элементах Т.е. Каждому ФИО соответствует "погоняло". Задача, соответственно, по погонялу определить ФИО (ну, или наоборот, как вам нравится). Решить через вектор.

0

avgoor, Я понял ответ на первый вопрос. т.е. преимущество хеш-таблиц когда индекс неизвестен и надо искать очень быстро. С вопросами 2-4 пока непонятно.

0

Сообщение от Pechkin80 преимущество хеш-таблиц когда индекс неизвестен и надо искать очень быстро. С вопросами 2-4 пока непонятно.

Я б сказал не преимущество, а прямое предназначение (организовать соответствие одних данных другим)

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

В яве, например, используется именно HashMap по умолчанию.

0

Сообщение от avgoor 3) Ничего солить не надо. Скорее наоборот - ситуации в которых стандартные алгоритмы хэшей не подходят достаточно редкие.

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

0

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

Сообщение от 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

Сообщение от Pechkin80 данных которые могут вызывать коллизии

Случай, когда мы задаём для точно такого же ключа новое значение коллизией не называется.

По поводу универсальности - чем больше элементов в таблице, тем больше должен быть её размер (т.е. диапазон разбивки индексов должен расти быстрее, чем длина ключа )

0

Я может толком не объяснил, но я про случай когда ключ это захешированные данные часто т.е. в паре {Key, Data} Key = F(Data). Наверно корректнее былобы рассматривать unordered_set, но не так важно. Суть в то что пространство ключей меньше пространства данных.

0