979 / 196 / 33
Регистрация: 26.09.2012
Сообщений: 2,041
|
|
1 | |
Контейнер hash_map17.06.2013, 02:12. Показов 11923. Ответов 55
Метки нет (Все метки)
Здорова!
Нужно создать контейнер hash_map это тот же контейнер как и map, только он в разы иногда раз в 10-20 быстрее осуществляет поиск элементов по ключу чем стандартный контейнер map, поэтому если нужен быстрый поиск, то советуют использовать свой hash_map. В общем ребятки какой будет алгоритм создания? Я видел внутреннее представление этого контейнера, так там внутри просто два вектора, один с объектами, а второй с указателями. Интересно как же он работает или по какому алгоритму его строить? Это задачка из книги Страуструпа. Нужно потом будет еще создать hash_set, hash_multiset или я точно не помню еще какието.
0
|
17.06.2013, 02:12 | |
Ответы с готовыми решениями:
55
Контейнер на пободия hash_map. Hash_map unordered_map <hash_map> is deprecated and will be REMOVED Hash_Map Error (C2338) |
Croessmah
|
19.06.2013, 14:20
Контейнер hash_map
#21
|
Не по теме: Ну да, мелочь... одна мелочь, вторая... так самолеты то и падают :)
0
|
19.06.2013, 22:35 | 22 |
Буквально вчера разбирался с организацией хеш-таблиц, наконец то узнал чем они отличаюся Просто интересно - Страуструп в книге не объясняет за счет чего достигается такой прирост в скорости? В std::map доступ вроде как тоже через функцию хеширования.
Добавлено через 8 минут Не, гоню я, переучился) Там все завязано на key_comp(); Похоже что-то типа BST, более подробно разбираться сейчас лень.
0
|
979 / 196 / 33
Регистрация: 26.09.2012
Сообщений: 2,041
|
|
19.06.2013, 23:02 [ТС] | 23 |
Kastaneda, Да а я думаю отличие в том что map это дерево, а vector это указатель и возможно поиск в дереве более затратный чем в списке. Хз. Я сам не сильно понял за счет чего производительность возрастает. Мне б щас хотябы запустить рабочую версию.
Да и вообще там написано что этот hash_map это просто в учебных целях нужно создать, а так на практике советует использовать коммерческий версии, либо версии в свободном доступе. Добавлено через 4 минуты Я хочу в учебных целях и для остальных деревьев посоздавать hash_multimap, hash_set и hash_multiset, вточь точ такие как их стд товарищи. Там дальше задачки будут, но без этого hash_map я остальные не смогу понять как делать, придется разбираться никуда не дется.
0
|
979 / 196 / 33
Регистрация: 26.09.2012
Сообщений: 2,041
|
|
19.06.2013, 23:07 [ТС] | 25 |
Kastaneda, Так ты тоже Страуструпа читаешь щас и на том месте где я?
Добавлено через 2 минуты Эта функция просто сравнивает ключи, она хэш не создает. А хэш у страуструпа это походу индекс массива, от мне интересно функцию эту запустить и вывести посмотреть каки хэши будут создаваться. Диапазон интересно посмотреть какой будит.
0
|
19.06.2013, 23:15 | 26 | |||||
я даже незнаю как это понимать) В BST поиск O(log n), в списке и векторе (если вектор не упорядочен и не испльзуется бинарный поиск) О(n).
Нет, не читаю, поэтому и спросил. Я в курсе, посмотрел уже, написал же выше. Там похоже хеш вообще никаким боком не используется. Не совсем, она возвращает key_compare (метод для сравнения), который в свою очередь возвращает bool, и используется для сравнения элементов. пример кода
Пример с msdn
Код
kc1( 2,3 ) returns value of true, where kc1 is the function object of m1. kc2( 2,3 ) returns value of false, where kc2 is the function object of m2. Интуитивно могу предположить, что она испльзуется для определения "куда засунуть элемент в дереве". За подробностями можно обратиться в исходники map'а, но мне уже неохото)
0
|
979 / 196 / 33
Регистрация: 26.09.2012
Сообщений: 2,041
|
|||||||||||||||||||||
20.06.2013, 00:09 [ТС] | 28 | ||||||||||||||||||||
Ладно хватит флудить я тут с unery_function разобрался продолжим дальше разбираться с примерам, будем исправлять ошибки.
Файл hash_map.h:
1>------ Построение начато: проект: test, Конфигурация: Debug Win32 ------ 1> main.cpp 1>main.obj : error LNK2005: "public: unsigned int __thiscall Hash<char>::operator()(char const &)const " (??R?$Hash@D@@QBEIABD@Z) уже определен в hash_map.obj 1>main.obj : error LNK2005: "public: unsigned int __thiscall Hash<class std::basic_string<char,struct std::char_traits<char>,class std::allocator<char> > >::operator()(class std::basic_string<char,struct std::char_traits<char>,class std::allocator<char> > const &)const " (??R?$Hash@V?$basic_string@DU?$char_traits@D@std@@V?$allocator@D@2@@std@@@@QBEIA BV?$basic_string@DU?$char_traits@D@std@@V?$allocator@D@2@@std@@@Z) уже определен в hash_map.obj 1>C:\test\test\Debug\test.exe : fatal error LNK1169: обнаружен многократно определенный символ - один или более ========== Построение: успешно: 0, с ошибками: 1, без изменений: 0, пропущено: 0 ========== Отетa от часть кода делает ошибку:
Добавлено через 22 минуты Как мне правильно без ошибок сделать специализацию шаблона??????
0
|
В астрале
8049 / 4806 / 655
Регистрация: 24.06.2010
Сообщений: 10,562
|
|
20.06.2013, 00:12 | 29 |
ninja2, В .cpp файл унести специализацию.
1
|
979 / 196 / 33
Регистрация: 26.09.2012
Сообщений: 2,041
|
|
20.06.2013, 00:16 [ТС] | 30 |
ForEveR, Как оно неожиданно заработало.
0
|
415 / 411 / 95
Регистрация: 06.10.2011
Сообщений: 832
|
|||||||||||
20.06.2013, 00:25 | 31 | ||||||||||
std::map построен на основе красно-черного дерева
ее там даже нету:
2
|
979 / 196 / 33
Регистрация: 26.09.2012
Сообщений: 2,041
|
||||||||||||||||
20.06.2013, 11:59 [ТС] | 32 | |||||||||||||||
Здорова!
Снова вылезла непонятная ошибка От файл hash_map.cpp:
1>main.obj : error LNK2019: ссылка на неразрешенный внешний символ "public: int & __thiscall hash_map<class std::basic_string<char,struct std::char_traits<char>,class std::allocator<char> >,int,struct Hash<class std::basic_string<char,struct std::char_traits<char>,class std::allocator<char> > >,struct equal_to<class std::basic_string<char,struct std::char_traits<char>,class std::allocator<char> > >,class std::allocator<struct std:air<class std::basic_string<char,struct std::char_traits<char>,class std::allocator<char> > const ,int> > >::operator[](class std::basic_string<char,struct std::char_traits<char>,class std::allocator<char> > const &)" (??A?$hash_map@V?$basic_string@DU?$char_traits@D@std@@V?$allocator@D@2@@std@@HU? $Hash@V?$basic_string@DU?$char_traits@D@std@@V?$allocator@D@2@@std@@@@U?$equal_t o@V?$basic_string@DU?$char_traits@D@std@@V?$allocator@D@2@@std@@@@V?$allocator@U ?$pair@$$CBV?$basic_string@DU?$char_traits@D@std@@V?$allocator@D@2@@std@@H@std@@ @2@@@QAEAAHABV?$basic_string@DU?$char_traits@D@std@@V?$allocator@D@2@@std@@@Z) в функции _main 1>C:\test\test\Debug\test.exe : fatal error LNK1120: 1 неразрешенных внешних элементов ========== Построение: успешно: 0, с ошибками: 1, без изменений: 0, пропущено: 0 ========== Если я закомментирую определение функции operator[] в файле hash_map.cpp и определю ее в классе hash_map то этой ошибки нету. Наверно как то шаблон функции operator[]() ее определение как то не правильно определено?????
0
|
979 / 196 / 33
Регистрация: 26.09.2012
Сообщений: 2,041
|
|
20.06.2013, 12:12 [ТС] | 34 |
А когда я добавляю определение hash_map::operator[]() в файл hash_map.h то тогда вроде норм компилируется, что ж тогда придется мне их в одном файле делать?
0
|
20.06.2013, 12:45 | 36 |
Не по теме: Сенкс, а откуда информация? Лень в стандарт лезть, но там вроде это не оговорено. Скорее всего там сказано, что нибудь типа "скорость доступа по ключу не более О(log n)" Добавлено через 12 минут
0
|
ForEveR
|
20.06.2013, 12:47
#37
|
Не по теме: Kastaneda, Всецело верно.
0
|
Olivеr
|
|||||
20.06.2013, 12:48
#38
|
|||||
Не по теме: http://gcc.gnu.org/onlinedocs/... ource.html
Выбрали красно-черное потому, что оно является чем-то средним между BST и AVL.
0
|
ForEveR
|
20.06.2013, 12:50
#39
|
Не по теме: Olivеr, libstdc++ не является стандартом, просто реализация, не более того.
0
|
Olivеr
|
20.06.2013, 12:51
Контейнер hash_map
#40
|
0
|
20.06.2013, 12:51 | |
Stdext::hash_map и std::map Ошибка <hash_map> при выполнении программы Чем отличается map и hash_map в плюсах? контейнер Искать еще темы с ответами Или воспользуйтесь поиском по форуму: |