Форум программистов, компьютерный форум CyberForum.ru

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
 
Рейтинг: Рейтинг темы: голосов - 31, средняя оценка - 4.68
ninja2
231 / 187 / 7
Регистрация: 26.09.2012
Сообщений: 2,018
Завершенные тесты: 1
#1

Контейнер hash_map - C++

17.06.2013, 02:12. Просмотров 4318. Ответов 55
Метки нет (Все метки)

Здорова!
Нужно создать контейнер hash_map это тот же контейнер как и map, только он в разы иногда раз в 10-20 быстрее осуществляет поиск элементов по ключу чем стандартный контейнер map, поэтому если нужен быстрый поиск, то советуют использовать свой hash_map. В общем ребятки какой будет алгоритм создания? Я видел внутреннее представление этого контейнера, так там внутри просто два вектора, один с объектами, а второй с указателями. Интересно как же он работает или по какому алгоритму его строить? Это задачка из книги Страуструпа. Нужно потом будет еще создать hash_set, hash_multiset или я точно не помню еще какието.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
17.06.2013, 02:12
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Контейнер hash_map (C++):

Контейнер на пободия hash_map. - C++
Всем привет. Столкнулся с такой задачей, нужно написать собственный контейнер на подобие hash_map. Почитал Страуструпа, некоторые моменты...

Hash_map unordered_map - C++
class P{ public: int x, y; friend bool operator< (const P u, const P v) { if(u.x < v.x) { return true; } else...

Hash_Map Error (C2338) - C++
1) Ребята, начинал учить C++ и как всегда и как у всех, не без проблем. Пробовал писать в DevC++, все хорошо, но потом понял, что рано или...

Stdext::hash_map и std::map - C++
Здравствуйте форумчане! Может ли кто нибудь объяснить мне отличие stdext::hash_map от std::map? В интернете не так много информации о нем,...

Чем отличается map и hash_map в плюсах? - C++
Чем отличается map и hash_map в плюсах? с hash_map еще не работал, хочу разобраться есть ли семантические отличия и в чем заключаются.

Ошибка <hash_map> при выполнении программы - C++
При выполнении простого консольного проекта C++ #include &quot;std_lib_facilities.h&quot; int main() { cout &lt;&lt; &quot;I hate u, VS!\n&quot;; ...

Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Olivеr
412 / 408 / 13
Регистрация: 06.10.2011
Сообщений: 831
20.06.2013, 00:25 #31
Цитата Сообщение от Kastaneda Посмотреть сообщение
Похоже что-то типа BST, более подробно разбираться сейчас лень.
std::map построен на основе красно-черного дерева

Цитата Сообщение от Kastaneda Посмотреть сообщение
Там похоже хеш вообще никаким боком не используется.
ее там даже нету:
C++
1
2
3
4
5
template < class Key,                                     // map::key_type
           class T,                                       // map::mapped_type
           class Compare = less<Key>,                     // map::key_compare
           class Alloc = allocator<pair<const Key,T> >    // map::allocator_type
           > class map;
То, что пишет ninja2 в STL называется unordered_map
C++
1
2
3
4
5
6
template < class Key,                                    // unordered_map::key_type
           class T,                                      // unordered_map::mapped_type
           class Hash = hash<Key>,                       // unordered_map::hasher
           class Pred = equal_to<Key>,                   // unordered_map::key_equal
           class Alloc = allocator< pair<const Key,T> >  // unordered_map::allocator_type
           > class unordered_map;
ninja2
231 / 187 / 7
Регистрация: 26.09.2012
Сообщений: 2,018
Завершенные тесты: 1
20.06.2013, 11:59  [ТС] #32
Здорова!
Снова вылезла непонятная ошибка
От файл hash_map.cpp:
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
58
//opredelenie hash_map
 
#include "hash_map.h"
 
#include <iostream>
using std::cout;
using std::endl;
#include <cstdlib>
using std::exit;
 
//несколько специализаций функции Hash
template<class T>size_t Hash<T>::operator()(const T& key)const
{
    size_t res=1;
    cout <<"mu v Hash"<<endl;exit(1);
    return res;
}
 
typedef char Pchar; //char как тип Pchar
template<> size_t Hash<Pchar>::operator()(const Pchar& key)const
{
    size_t res=2;
    cout <<"mu v Hash<Pchar>"<<endl;exit(1);
    return res;
}
 
template<> size_t Hash<string>::operator()(const string& key)const
{
    size_t res=3;
    cout <<"mu v Hash<string>"<<endl;exit(1);
    return res;
}
//конец специализации функции хеширования
 
template<class Key,class T,class H,
    class EQ,class A>
        typename hash_map<Key,T,H,EQ,A>::mopped_type&
        hash_map<Key,T,H,EQ,A>::operator[](const key_type& k)
    {
        cout <<"mu v operator[]"<<endl;exit(1);
 
        return b[0]->val;
    }
 
template<class Key, class T, class H,
    class EQ,class A >
        void hash_map<Key,T,H,EQ,A>::resize(size_type s)
    {
        cout <<"resize"<<endl;exit(1);
    }
 
template<class Key, class T, class H,
    class EQ,class A >
        void hash_map<Key,T,H,EQ,A>::erase(iterator p)
    {
        if(p->erased==false) no_of_erased++;
        p->erased=true;
    }
Файл hash_map.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
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
//klacc hash_map
#ifndef HASH_MAP
#define HASH_MAP
 
#include <string>
using std::string;
#include <vector>
using std::vector;
#include <iostream>
using std::cout;
using std::endl;
#include <cstdlib>
using std::exit;
#include <functional>
using std::unary_function;
#include <allocators>
using std::allocator;
#include <utility>
using std::pair;
 
 
//делаем определение шаблона функции хеширования
template<class T> struct Hash : unary_function<T,size_t>
{
    size_t operator()(const T& key) const;
    
};
 
//делаем шаблон функции сравнения
template<class T> struct equal_to : unary_function<T,size_t>
{
    size_t operator()(const T& key) const;
};
//определение функции хеширования она как то вызывается через operator()() хз. почему?
template<class T>size_t equal_to<T>::operator()(const T& key)const
{
    size_t res=0;
    cout <<"mu v Hash"<<endl;exit(1);
    return res;
}
//конец функции сравнения
 
 
//Начало класса hash_map
template<class Key,class T,class H=Hash<Key>,
    class EQ=equal_to<Key>,class A=allocator<pair<const Key,T> > >
class hash_map
{
public:
    //как map за исключением
    typedef H Hasher;
    typedef EQ key_equal;
    typedef size_t size_type;//из функции Hash видно что size_t нужно, а не int
    typedef Key key_type;
    typedef T mopped_type;
    typedef T* iterator;
    typedef const T* const_iterator;
    
    
    hash_map(const T& dv=T(), size_type n=101, const H& hf=H(), const EQ& e=EQ())
        :default_value(dv),b(n),no_of_erased(0),hash(hf),eq(e)
    {
        set_load();//все что по умолчанию
        v.reserve(max_load*b.size());//резервирует память для роста
        cout <<v.size()<<' '<<b.size()<<endl;
    }
 
    void set_load(float m=0.7,float g=1.6){max_load=m;grow=g;}
 
//  template<class In>hash_map(In first, In last, const T& dv=T(), size_type n=101,
//      const H& hf=H(), const EQ&=EQ()){}
 
    //Поиск
    mopped_type& operator[](const key_type& k);//{cout <<"mu tyt"<<endl; return b[0]->val;}
 
    iterator find(const key_type&);
    const_iterator find(const key_type&) const;
    //...
 
    void resize(size_type n);//размер хэш таблицы в n
    
    void erase(iterator position);//удаление указуемого элемента
 
    size_type size() const {return v.size()-no_of_erased;}//число элементов
 
    size_type bucket_count() const {return b.size();}//размер хэш таблицы
 
    Hasher hash_fun() const {return hash;}//применяемая хэш функция
    key_equal key_eq() const {return eq;}//равенство
 
private://внутреннее представление
    float max_load;//сохраняем v.size()<=b.size()*max_load
    float grow;//при необходимости меняем размер, resize(bucket_count()* grow)
    size_type no_of_erased;//количество входов в v занятых стертыми элементами
    Hasher hash; //хэш функция
    key_equal eq;//равенство
 
    const T default_value;//умолчательное значение используется операцией []
 
    struct Entry
    {
        key_type key;
        mopped_type val;
        bool erased;
 
        Entry* next; //следущий элемент или хз что
 
        Entry(key_type k, mopped_type v, Entry* n)
            :key(k),val(v),next(n){}
    };
 
    vector<Entry> v;//истиные входы
    vector<Entry*> b;//хешь таблица указатели внутрь v
    //...
 
};
 
//определения функци
 
 
#endif
и main.cpp:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include <iostream>
using std::cout;
using std::endl;
#include <cstdlib>
using std::exit;
#include <string>
using std::string;
 
#include "hash_map.h"
 
int main()
{
    cout <<"Test hash_map"<<endl;
 
    hash_map<string, int> h;
    h["hellow"]=4;
 
    return 0;
}
при вызове operator[]() происходит ошибка:Создание кода...
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_to@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[]() ее определение как то не правильно определено?????
Croessmah
Модератор
Эксперт CЭксперт С++
13133 / 7396 / 828
Регистрация: 27.09.2012
Сообщений: 18,227
Записей в блоге: 3
Завершенные тесты: 1
20.06.2013, 12:08 #33
опять реализация отдельно от объявления?
ninja2
231 / 187 / 7
Регистрация: 26.09.2012
Сообщений: 2,018
Завершенные тесты: 1
20.06.2013, 12:12  [ТС] #34
Цитата Сообщение от Croessmah Посмотреть сообщение
опять реализация отдельно от объявления?
А когда я добавляю определение hash_map::operator[]() в файл hash_map.h то тогда вроде норм компилируется, что ж тогда придется мне их в одном файле делать?
Croessmah
Модератор
Эксперт CЭксперт С++
13133 / 7396 / 828
Регистрация: 27.09.2012
Сообщений: 18,227
Записей в блоге: 3
Завершенные тесты: 1
20.06.2013, 12:17 #35
Цитата Сообщение от ninja2 Посмотреть сообщение
что ж тогда придется мне их в одном файле делать?
Почитайте про то что такое шаблоны Ответ придет неожиданно
Kastaneda
Форумчанин
Эксперт С++
4652 / 2860 / 228
Регистрация: 12.12.2009
Сообщений: 7,268
Записей в блоге: 2
Завершенные тесты: 1
20.06.2013, 12:45 #36

Не по теме:

Цитата Сообщение от Olivеr Посмотреть сообщение
std::map построен на основе красно-черного дерева
Сенкс, а откуда информация? Лень в стандарт лезть, но там вроде это не оговорено. Скорее всего там сказано, что нибудь типа "скорость доступа по ключу не более О(log n)"



Добавлено через 12 минут

Не по теме:

Цитата Сообщение от Kastaneda Посмотреть сообщение
Лень в стандарт лезть
Залез таки) Про внутреннию структуру там ничего не сказано, только написано про скорость доступа, как я и предполагал. Например вот:
T& operator[](const key_type& x);
1 Effects: If there is no key equivalent to x in the map, inserts value_type(x, T()) into the map.
2 Requires: key_type shall be CopyConstructible and mapped_type shall be DefaultConstructible.
3 Returns: A reference to the mapped_type corresponding to x in *this.
4 Complexity: logarithmic.

ForEveR
20.06.2013, 12:47
  #37

Не по теме:

Kastaneda, Всецело верно.

Associative containers provide fast retrieval of data based on keys. The library provides four basic kinds of
associative containers: set, multiset, map and multimap.
A map is an associative container that supports unique keys (contains at most one of each key value) and
provides for fast retrieval of values of another type T based on the keys. The map class supports bidirectional
iterators.
Правильнее будет сказать примерно так: все современные реализации строят std::map на основе красно-черного дерева.

Olivеr
20.06.2013, 12:48
  #38

Не по теме:

Цитата Сообщение от Kastaneda Посмотреть сообщение
Сенкс, а откуда информация? Лень в стандарт лезть, но там вроде это не оговорено. Скорее всего там сказано, что нибудь типа "скорость доступа по ключу не более О(log n)"
http://gcc.gnu.org/onlinedocs/libstd...8h-source.html
C++
1
 enum _Rb_tree_color { _S_red = false, _S_black = true };
Видимо у разработчиков был выбор или красно-черное дерево или АВЛ.
Выбрали красно-черное потому, что оно является чем-то средним между BST и AVL.

ForEveR
20.06.2013, 12:50
  #39

Не по теме:

Olivеr, libstdc++ не является стандартом, просто реализация, не более того.

Olivеr
20.06.2013, 12:51
  #40

Не по теме:

Цитата Сообщение от ForEveR Посмотреть сообщение
Olivеr, libstdc++ не является стандартом, просто реализация, не более того.
Понятное дело.

ninja2
231 / 187 / 7
Регистрация: 26.09.2012
Сообщений: 2,018
Завершенные тесты: 1
20.06.2013, 14:05  [ТС] #41
Тут снова ошибка вылазить
Вот код:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <iostream>     // std::cout
#include <algorithm>    // std::fill
#include <vector>       // std::vector
 
struct Entry
{
 
};
 
int main () {
  std::vector<Entry*> b;
    std::fill<std::vector<Entry*>::iterator,int>(b.begin(),b.end(),0);
 
  //Отак когда то нету ошибки
    /*std::vector<Entry*>::iterator it;
        for(it=b.begin();it!=b.end();++it)
            *it=0;*/
 
  return 0;
}
в книге в примере отак написано std::fill(b.begin(),b.end(),0); Но ошибка вылазить типо не может преобразовать в Entry* тип const int

ошбика:
1>------ Построение начато: проект: test, Конфигурация: Debug Win32 ------
1> main.cpp
1>c:\program files\microsoft visual studio 10.0\vc\include\xutility(2692): error C2440: =: невозможно преобразовать "const int" в "Entry *"
1> Для преобразования из целого типа в указатель требуется reinterpret_cast, приведение в стиле С или приведение в стиле функции
1> c:\program files\microsoft visual studio 10.0\vc\include\xutility(2715): см. ссылку на создание экземпляров функции шаблон при компиляции "void std::_Fill<Entry**,_Ty>(_FwdIt,_FwdIt,const _Ty &)"
1> with
1> [
1> _Ty=int,
1> _FwdIt=Entry **
1> ]
1> c:\test\test\test\main.cpp(34): см. ссылку на создание экземпляров функции шаблон при компиляции "void std::fill<std::_Vector_iterator<_Myvec>,int>(_FwdIt,_FwdIt,const _Ty &)"
1> with
1> [
1> _Myvec=std::_Vector_val<Entry *,std::allocator<Entry *>>,
1> _FwdIt=std::_Vector_iterator<std::_Vector_val<Entry *,std::allocator<Entry *>>>,
1> _Ty=int
1> ]
========== Построение: успешно: 0, с ошибками: 1, без изменений: 0, пропущено: 0 ==========


Если я просто через итератор обнуляю то все нормально, что в книге тогда ошиблись?
От шаблон класса fill:
C++
1
2
3
4
5
6
7
template<class _FwdIt,
    class _Ty> inline
    void _Fill(_FwdIt _First, _FwdIt _Last, const _Ty& _Val)
    {   // copy _Val through [_First, _Last)
    for (; _First != _Last; ++_First)
        *_First = _Val;
    }
Olivеr
412 / 408 / 13
Регистрация: 06.10.2011
Сообщений: 831
20.06.2013, 14:13 #42
А каким боком это относится к хеш таблицам?

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
#include <iostream>     // std::cout
#include <algorithm>    // std::fill
#include <vector>       // std::vector
 
struct Entry {};
 
int main ()
{
    std::vector<Entry*> b;
    std::fill(b.begin(), b.end(), nullptr);
 
    return 0;
}
MrGluck
Модератор
Эксперт CЭксперт С++
7210 / 4376 / 638
Регистрация: 29.11.2010
Сообщений: 11,887
20.06.2013, 14:19 #43
Цитата Сообщение от ninja2 Посмотреть сообщение
в книге в примере отак написано std::fill(b.begin(),b.end(),0); Но ошибка вылазить типо не может преобразовать в Entry* тип const int
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <iostream>     // std::cout
#include <algorithm>    // std::fill
#include <vector>       // std::vector
 
struct Entry
{
    //explicit Entry(const int x) : a(x) {}
    //operator int() const {return a; }
    int a;
};
 
int main () {
  std::vector<Entry*> b(10);
    std::fill<std::vector<Entry*>::iterator,Entry*>(b.begin(),b.end(),0);
 
  //Отак когда то нету ошибки
    std::vector<Entry*>::iterator it;
        for(it=b.begin();it!=b.end();++it)
            std::cout << *it;
 
  return 0;
}
Добавлено через 1 минуту
хоть это и криво
ninja2
231 / 187 / 7
Регистрация: 26.09.2012
Сообщений: 2,018
Завершенные тесты: 1
20.06.2013, 14:34  [ТС] #44
Цитата Сообщение от Olivеr Посмотреть сообщение
А каким боком это относится к хеш таблицам?
Относится это я просто кусок выдрал из кода, что бы понятнее было где ошибка, не кидать же весь большой код?
ForEveR
В астрале
Эксперт С++
7970 / 4732 / 321
Регистрация: 24.06.2010
Сообщений: 10,541
Завершенные тесты: 3
20.06.2013, 14:37 #45
Если С++11 нет
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
#include <iostream>     // std::cout
#include <algorithm>    // std::fill
#include <vector>       // std::vector
 
struct Entry {};
 
int main ()
{
    std::vector<Entry*> b(10);
    std::fill(b.begin(), b.end(), (Entry*)0);
 
    return 0;
}
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
20.06.2013, 14:37
Привет! Вот еще темы с ответами:

контейнер - C++
Создать контейнер, в который можно добавлять и удалять методы. Размер контейнера должен увеличиваться автоматически. Вот такое задание ,...

Контейнер map - C++
Стоит задача реализовать контейнер map. Вопрос возникает при реализации итератора для этого контейнера. В итераторе должны быть реализованы...

контейнер set - C++
Создать контейнер set, ввести в него 3 числа. Создать метод по вычислении наибольшего из этих чисел помогите, пожалуйста, с заданием или...

контейнер vector - C++
Как я понимаю, vector представляет собой что-то вроде динамического массива. Но массивы бывают одномерные,двумерные и так далее. Есть ли...


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

Или воспользуйтесь поиском по форуму:
Yandex
Объявления
20.06.2013, 14:37
Ответ Создать тему
Опции темы

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