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

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

25.11.2017, 15:26. Показов 14522. Ответов 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
Ответ Создать тему
Новые блоги и статьи
Сезонность и суточность закисления почв
anaschu 04.07.2026
200 часов это все равно моловато. Есть ситуации, но нестандартные, когда смена происходит за 5 лет. Но обычно это 50 лет и более. Наверное, закисление почвы происходит сезонно в средней. . .
В чем ценность человеческого опыта в глобальном смысле?
kumehtar 03.07.2026
Возможно, ценность человека не в том, что он однажды достигает мудрости, а в том, что он становится носителем карты пути. Он знает не только истину, но и последовательность внутренних изменений,. . .
интеграция AnyLogic с самописным REST API и переход на Odoo
anaschu 03.07.2026
Успешная интеграция AnyLogic с самописным REST API и переход на промышленную Odoo WMS Сегодня проделал огромный путь от простой симуляции физических процессов до построения полноценной. . .
Поиск всех путей на ориентированном графе. Linux
dcc0 02.07.2026
Переработка старого кода из моей статьи. Через несколько переработок от PHP кода к C89 (надеюсь, 89). Но довольно запутанно получилось. Код для Linux. Но если убрать time и то, что с ним. . .
Сам себя обучал rest api
anaschu 02.07.2026
Педагогический лайфхак: Почему чистый REST API для ученика намного круче, чем готовые библиотеки Когда мы отказались от капризного JAR-файла AnyLogic и переписали код на стандартный HttpClient,. . .
rest api anylogic - выполнение модели на своём русском сайте
anaschu 02.07.2026
Как подружиться с AnyLogic Cloud API, победить провайдеров и развернуться Java-бэкенд в Docker на бесплатном хостинге: Двухдневный лог борьбы Всем привет! Хочу поделиться свежим (и довольно. . .
Где деньги лежат
kumehtar 02.07.2026
Это - японская подводная лодка I-52 (тип C2, кодовое имя Momi) вышла из Японии в марте 1944 года с миссией в оккупированную немцами Францию (Лорьян). Это была одна из «Янаги»-миссий по обмену. . .
Krabik для WoW 3.3.5a, многоязычный
AmbA 02.07.2026
Допилил бота, думаю что окончательно. Изменения: - добавлена многоязычность - добавлено снятие скриншотов - добавлено поддержание бафов хождения по воде (для жреца, дк и шамана) - и так, по. . .
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2026, CyberForum.ru