21 / 19 / 7
Регистрация: 14.03.2014
Сообщений: 249

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

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

Студворк — интернет-сервис помощи студентам
Решил разобраться с этим контейнером, но не вижу ни одной комплексной сатьи по этой теме.
Кто нибудь может ответить на простые вопросы:
1)Имеют ли данные контейнеры практический смысл в сравнение с вектором у которого свой аллокатор ?
2)Я так понимаю что контейнер малопригоден в готовом виде с параметрами по умолчанию ?
3)Если его использовать не в готовом, то хеши надо солить. а солить можно по разному и есть ли какая нибудь удачная реализация (так как чувствую что создам велосипед, если буду делать сам) ?
4)Чем отличается реализация boost unordered_map от std::unordered_map?
0
Лучшие ответы (1)
cpp_developer
Эксперт
20123 / 5690 / 1417
Регистрация: 09.04.2010
Сообщений: 22,546
Блог
25.11.2017, 15:26
Ответы с готовыми решениями:

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

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

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

62
21 / 19 / 7
Регистрация: 14.03.2014
Сообщений: 249
26.11.2017, 00:51  [ТС]
Студворк — интернет-сервис помощи студентам
TRam_, С диагностикой разобрался. это уже большое дело. С подмешиванием завтра. Хотя конечно подмешивание это в некоторой степени защита от дурака. Но так бывает что берёшь готовую загатовку кода и не хочешь её затачивать под конкретную задачу, хочешь чтоб сразу работала без допиливания и везде работала.

Добавлено через 1 час 17 минут
Как я и думал. Грамотно работать с этим зверем - целое исскусство.
Офигенная статья. То о чём я долго думал. https://habrahabr.ru/post/250383/
0
 Аватар для Kastaneda
5232 / 3206 / 362
Регистрация: 12.12.2009
Сообщений: 8,143
Записей в блоге: 2
26.11.2017, 12:44
Цитата Сообщение от Pechkin80 Посмотреть сообщение
Как я и думал. Грамотно работать с этим зверем - целое исскусство.
Офигенная статья. То о чём я долго думал. https://habrahabr.ru/post/250383/
Там же про lock-free, это уже совсем другая песня и к делу совершенно не относится. С таким же успехом можно нагуглить про lock-free list и потом говорить всем, что std::list необычайно сложный и работать с ним целое искусство.
1
21 / 19 / 7
Регистрация: 14.03.2014
Сообщений: 249
27.11.2017, 01:40  [ТС]
Результаты скромненькие:

Код тута:

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#ifndef HASH_WRAPPER_H
#define HASH_WRAPPER_H
#include "common.h"
#include "cstring.h"
 
namespace std
{
    struct THasher;
    typedef unordered_map<std::string,const char *,THasher> THContainer1;
    struct THasher
    {
      std::size_t operator () (const std::string &key) const
      {
            std::size_t result = 0;
            if (strlen(key.c_str()) == 1)
            {
                result = key[0];
                boost::hash_combine(result, boost::hash_value(key));
            }
            else
            {
                result = 0;
                boost::hash_combine(result, boost::hash_value(key));
            }
            return result;
      }
    };
}
 
typedef std::unordered_map<std::string,const char *> THContainer2;
 
extern void test_hash();
 
#endif // HASH_WRAPPER_H
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
#include "hash_wrapper.h"
 
const char * strarr[] = { "Hellow World !!!", "C++11 prog lang", "qtcreator" };
 
template <typename T1>
unsigned show_collision(T1 & _map)
{
      unsigned ncollisions = 0;
      for (unsigned i = 0; i< _map.bucket_count(); ++i)
      {
        if (_map.bucket_size(i) > 1)
        {
            ncollisions += _map.bucket_size(i) - 1;
            if (_map.bucket_size(i) > 4)
            {
                std::cout << "bucket #" << i << " has " << _map.bucket_size(i) << " elements.\n";
            }
        }
      }
      return ncollisions;
}
 
void test_hash()
{
    const auto c_maxindex = 13500;
    std::string str_item;
 
    // немного кастомная буст-хеш-функция
    std::THContainer1 mapa1;    
    mapa1.max_load_factor(0.98);
    // Заполнение хеш-таблицы
    std::cout << "collisions with buckets > 4: ";
    for (int i1 = 0; i1 < c_maxindex; i1++)
    {
        str_item = std::to_string(i1);
        mapa1.insert(std::pair<std::string,const char *>(str_item,strarr[i1%3]));
    }
    std::cout << std::endl;
    // Вывод списка вёдер (buckets)
    std::cout << "number of collisions is " << show_collision(mapa1) << std::endl;
    std::cout << "bucket count " << mapa1.bucket_count() << std::endl;
    std::cout << "load factor " << mapa1.load_factor() << std::endl;
 
    // stl-хеш-функция,
    THContainer2 mapa2;
    std::cout << "collisions with buckets > 4: ";
    mapa2.max_load_factor(0.98);
    for (int i1 = 0; i1 < c_maxindex; i1++)
    {
        str_item = std::to_string(i1);
        mapa2.insert(std::pair<std::string,const char *>(str_item,strarr[i1%3]));
    }
    std::cout << std::endl;
    std::cout << "number of collisions is " << show_collision(mapa2) << std::endl;
    std::cout << "bucket count " << mapa2.bucket_count() << std::endl;
    std::cout << "load factor " << mapa2.load_factor() << std::endl;
}

Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
boost collisions with buckets > 4:
bucket #2894 has 5 elements.
bucket #9501 has 5 elements.
bucket #9504 has 5 elements.
bucket #9630 has 5 elements.
bucket #9684 has 5 elements.
bucket #9687 has 5 elements.
bucket #9688 has 5 elements.
bucket #9689 has 5 elements.
bucket #9751 has 5 elements.
bucket #9752 has 5 elements.
bucket #10326 has 5 elements.
bucket #10329 has 5 elements.
bucket #10330 has 5 elements.
bucket #10460 has 5 elements.
bucket #12726 has 5 elements.
bucket #13359 has 5 elements.
bucket #13360 has 5 elements.
bucket #13361 has 5 elements.
number of collisions is 4358
bucket count 15173
load factor 0.889738
stl collisions with buckets > 4:
bucket #16 has 6 elements.
bucket #197 has 5 elements.
bucket #1036 has 5 elements.
bucket #1963 has 5 elements.
bucket #2030 has 5 elements.
bucket #2182 has 6 elements.
bucket #2454 has 5 elements.
bucket #3670 has 5 elements.
bucket #4310 has 5 elements.
bucket #6232 has 5 elements.
bucket #7075 has 6 elements.
bucket #8347 has 5 elements.
bucket #8914 has 5 elements.
bucket #9242 has 6 elements.
bucket #9296 has 5 elements.
bucket #9449 has 5 elements.
bucket #9864 has 5 elements.
bucket #9893 has 6 elements.
bucket #10448 has 5 elements.
bucket #10736 has 5 elements.
bucket #11031 has 5 elements.
bucket #11073 has 5 elements.
bucket #11123 has 5 elements.
bucket #11428 has 5 elements.
bucket #11578 has 5 elements.
bucket #11699 has 6 elements.
bucket #12000 has 6 elements.
bucket #12113 has 6 elements.
bucket #13201 has 5 elements.
bucket #13943 has 5 elements.
bucket #13970 has 5 elements.
bucket #14262 has 5 elements.
number of collisions is 4560
bucket count 15173
load factor 0.889738
Общий итог - std::hash полуфабрикат, который нормально работает не на всех типах.
Если кто расскажит методы оптимизации хеш-функции - будет здорово.
Если ктото чего не понял, то не надо тут меня спрашивать. совсем не претендую чтоб было всем понятно.
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
raxper
Эксперт
30234 / 6612 / 1498
Регистрация: 28.12.2010
Сообщений: 21,154
Блог
27.11.2017, 01:40

Контейнер unordered_map<string, unordered_map<string,int>>
Ну можно и не unordered_map&lt;string, unordered_map&lt;string,int&gt;&gt;. Мне нужен контейнер который будет по 2 ключам типа string выдавать int. ...

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

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

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

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


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

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

Новые блоги и статьи
Саморегулирующийся социальный контракт для сервера cross-section.
Hrethgir 14.08.2026
С кодом конечно таких глубоких размышлений пока не было, впрочем я уже привык к алгоритмизации. Суть предмета записи: снова в диалоге с нейросетью (я взял пока себе ник для учётки админа - Rector). . . .
Часы электронные
Uhbif79 12.08.2026
Выкладываю программу часов. Программа позволяет: 1. Использовать системное время и дату, 2. Есть возможность вводить время и дату вручную. 3. Реализованы 2 будильника: начало и конец рабочего дня. . . .
Часы с будильником на основе класса QLCDNumber
Uhbif79 12.08.2026
Всем добрый день, выкладываю программу часов с будильником на основе класса QLCDNumber. Здесь я пробовал самостоятельно создавал классы, впервые столкнулся с видимостью переменной одного класса из. . .
Установка MinGW GCC 16.2 и CMake
8Observer8 10.08.2026
VK Видео: https:/ / vkvideo. ru/ video-240781534_456239017 YouTube: eY5-5PyI9NM Текстовая версия
Неделя из жизни имитационной модели склада: мои кривые руки растут, откуда надо
anaschu 10.08.2026
Неделя из жизни имитационной модели склада: как я почти написал неправильную логику и что с этим делать Работаю сейчас над учебно-рабочим проектом: строю в AnyLogic имитационную модель процессов. . .
Калькулятор для расчета родства
russiannick 07.08.2026
1. Задача: Создать калькулятор для расчета родства. Родственных связей существует 8 ступеней, такие как: p - отец P - мать q - муж Q - жена b - брат B - сестра s - сын S - дочь
Мир по моей воле
kumehtar 07.08.2026
Когда-то кажется, что всё просто. Ты весь такой светлый. Причиняешь добро. Борешься за справедливость в этом тёмном мире. Потом начинаешь замечать одну неприятную вещь. Почти каждый хороший. . .
Кредитный калькулятор
Maks 05.08.2026
Решение задачи по прикладной информатике средствами 1С. Задача: Напишите приложение-калькулятор, которое помогает рассчитывать параметры кредита для аннуитетного и дифференцированного видов. . .
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2026, CyberForum.ru