Kselax.ru

Hacker Kselax — the best hacker in the world

Menu
  • Блог
  • Контакты
  • wp plugin генератор
  • Русский
    • Русский
    • English
Menu

Шаблон hash_map.

Posted on 16 июня, 201321 июня, 2013 by admin

Завершите шаблон hash_map (параграф 17.6.1), то есть реализуйте функции find() и equal_range(), а также продумайте схему его тестирования. Выявите хотя бы один тип ключа, для которого хэш функция у типа hash_map плохо подходит (так что требуется иная хэш-функция)

Тяжелая задачка оказалась, долго я ее делал, не стал сильно разбирать ее. Там в книге конечно в примере куча ошибок, замучился я ошибки исправлять, да и с шаблонами проблемы были с оформлением. Как шаблон сделать? Да хз. Как специализацию шаблона правильно оформить? Почему в шаблоне функция Hash оформлена в виде класса в котором перегружен operator()() это тоже для меня не сильно ясно и щас я даже после того как сделал эту задачку не сильно понимаю. Еще там класс Hash наследуется от unary_function — это есть специальный класс в стл от которого нужно наследовать одиночные функции, они просто возвращают принимаемые аргументы. Нужно конечно для полноты создать пример и пост с этой функцией, но как то щас не сильно охота, замучился просто с самим классом. Нет я все таки создам. Ладно я щас вам приведу примерчики кода

Файл hash_map.h:

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
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
//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;
#include <algorithm>
using std::fill;
 
//делаем определение шаблона функции хеширования
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>
{
bool operator()(const T& key1,const T& key2) const;
};
 
 
//Начало класса 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;
//делаем объявление
struct Entry;
typedef Entry* iterator;
typedef const Entry* const_iterator;
typedef pair<iterator,iterator> equal_r;
//конструктор по умолчанию
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());//резервирует память для роста
}
 
//установка умолчания
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;
equal_r equal_range(const key_type& k);
//...
 
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),erased(false),next(n){}
};
vector<Entry> v;//истиные входы
vector<Entry*> b;//хешь таблица указатели внутрь v
//...
 
};
 
//определения функци
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)
{
size_type i=hash(k)%b.size();//хэш
//cout <<"i= "<<i<<endl;
for(Entry* p=b[i];p;p=p->next)//поиск среди входов хэшированых в i
if(eq(k,p->key))//найдено
{
if(p->erased)//повторная вставка
{
p->erased=false;
no_of_erased--;
return p->val=default_value;
}
return p->val;
}
//не найдено
if(b.size()*max_load<=v.size())//слишком плотное заполнение
{
cout <<"mu v b.size()*max_load"<<endl;exit(1);
resize(b.size()*grow);//расширяем
return operator[](k);//рехэшируем
}
v.push_back(Entry(k,default_value,b[i]));//добавляем Entry
b[i]=&v.back();//указываем на новый элемент
 
return b[i]->val;
}//вроде как проверено
 
template<class Key, class T, class H,
class EQ,class A >
void hash_map<Key,T,H,EQ,A>::resize(size_type s)
{
size_type i=v.size();
if(s<=b.size()) return;
 
while(no_of_erased)//реально устраняет удаленные элементы
{
if(v[--i].erased)
{
v.erase(v.begin()+i);//передаем указатель
--no_of_erased;
}
}
 
b.resize(s);
fill<vector<Entry*>::iterator,Entry*>(b.begin(),b.end(),0);//обнуляем входы (параграф 18.6.6)
 
v.reserve(s*max_load);//если v нуждается в памяти, делаем это сейчас
 
for(size_type i=0;i<v.size();i++)//рехэширование
{
size_type ii=hash(v[i].key)%b.size();//хэширование
v[i].next=b[ii];//связь
b[ii]=&v[i];
}
}
 
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;
}
 
template<class Key,class T,class H,
class EQ,class A>
typename hash_map<Key,T,H,EQ,A>::iterator
hash_map<Key,T,H,EQ,A>::find(const key_type& k)
{
size_type i=hash(k)%b.size();//хэш
//поиск среди входов хэшированых
for(Entry* p=b[i];p;p=p->next)//поиск среди входов хэшированых в i
if(eq(k,p->key))//найдено
{
if(p->erased)//проверка что не стерта
{
return 0;
}
return p;
}
return 0;
}
 
template<class Key,class T,class H,
class EQ,class A>
typename hash_map<Key,T,H,EQ,A>::const_iterator
hash_map<Key,T,H,EQ,A>::find(const key_type& k) const
{
size_type i=hash(k)%b.size();//хэш
//поиск среди входов хэшированых
for(Entry* p=b[i];p;p=p->next)//поиск среди входов хэшированых в i
if(eq(k,p->key))//найдено
{
if(p->erased)//проверка что не стерта
{
return 0;
}
return p;
}
return 0;
}
 
template<class Key,class T,class H,
class EQ,class A>
typename hash_map<Key,T,H,EQ,A>::equal_r
hash_map<Key,T,H,EQ,A>::equal_range(const key_type& k)
{
size_type i=hash(k)%b.size();//хэш
pair<iterator,iterator> res;
//поиск среди входов хэшированых
int count(0);
for(Entry* p=b[i];p;p=p->next)//поиск среди входов хэшированых в i
{
if(eq(k,p->key))//найдено
{
if(p->erased)//проверка что стерта
{
continue;
}
res.first=p;
count++;
}
// cout <<"mu tyt"<<endl;
}
if(count==0)
{
//cout <<"mu tyt 0"<<endl;
res.first=0;
res.second=0;
}
else if(count==1)
{
//cout <<"mu tyt 1"<<endl;
//cout <<"res.first->val= "<<res.first->val<<endl;
res.second=++res.first;
--res.first;
//cout <<"end"<<endl;exit(1);
//res.first--;
}
 
return res;
}
 
#endif

Файл hash_map.cpp:

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
//opredelenie hash_map
 
#include "hash_map.h"
 
#include <iostream>
using std::cout;
using std::endl;
#include <cstdlib>
using std::exit;
#include <cstring>
using std::strcmp;
 
//несколько специализаций функции Hash
template<class T>size_t Hash<T>::operator()(const T& key)const
{
size_t res=0;
sizt_t len=sizeof(T);
const char* p=reinterpret_cast<const char*>(&key);
 
while(len--) res=(res<<1)^*p++;
return res;
}
 
typedef char* Pchar; //char как тип Pchar
template<> size_t Hash<Pchar>::operator()(const Pchar& key)const
{
size_t res=0;
Pchar p=key;
while(*p) res=(res<<1)^*p++;
return res;
}
 
template<> size_t Hash<string>::operator()(const string& key)const
{
size_t res=0;
typedef string::const_iterator CI;
 
CI p=key.begin();
CI end=key.end();
 
while(p!=end)res=(res<<1)^*p++;
return res;
}
 
//специализация для equal_to
 
template<class T>bool equal_to<T>::operator()(const T& key1,const T& key2)const
{
return key1==key2;
}
 
template<>bool equal_to<Pchar>::operator()(const Pchar& key1,const Pchar& key2) const
{
if(strcmp(key1,key2)==0)
return true;
return false;
}
 
template<>bool equal_to<string>::operator()(const string& key1,const string& key2)const
{
return key1==key2;
}

И файл main.cpp:

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
#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<char*, int> h;
 
cout <<"h.size()= "<<h.size()<<endl;
h["hellow"]=35;
h.erase(h.find("hellow"));
h["gacpada"]=44;
cout <<"h.size()= "<<h.size()<<endl;//2
h.resize(108);
pair<hash_map<char*,int>::iterator,hash_map<char*,int>::iterator> ret;
ret=h.equal_range("hello");
hash_map<char*,int>::iterator it;
for(it=ret.first;it!=ret.second;++it)
cout <<"ret.first->val= "<<ret.first->val<<endl;
 
cout <<"h['hellow']= "<<h["hellow"]<<endl;
cout <<"h['gacpada']= "<<h["gacpada"]<<endl;
 
return 0;
}

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

Ну от как мы видим определение функций класса hash_map находятся в одном и том же файле, почему то они не компилировались и мне на форуме говорили, что не поддерживает раздельную компиляцию шаблонов, ну фиг сним, сделал как сказали. Но тут еще одно но как же не поддерживает когда мы видим, что класс Hash объявлен в одном файле а его специализация находится в другом файле? Отут от не сильная понятка, ладно пропустим останемся в не понятке.

Теперь еще рассмотрим специализацию шаблона, специализация шаблона это такая фигня когда один шаблон можно переопределить для определенного типа данных, по другому его обрабатывать, конечно она полезная фигня эта только для создателей библиотек, обозначается та template<> это значит что специализация пошла. Ладно пока что хватит, конечно я не последовательно излагая, но то что запомнилось, я хочу как бы законспектировать, что бы если что прочитать и вспомнить мб некоторые важные моменты.

Можно еще добавить мно чего, но от как добавлять так и нечо в голову не лезет, ну ладно на этом хватит. 🙂

Да вспомнил можно чуток и за логику поговорить, но я ее не сильно понял, там есть два вектора, один содержит указатели на хэш, а второй содержит объекты реальные, индекс для вектора с указателями является хэш — это хэш таблица, ну я не знаю из этого получается, что функция хэширования должна обязательно делать уникальный хэшь, иначе можно потерять данные.

Ладно опустим эту логику дурацкую, хотя честно скажу после создания этого шаблона я чуток лучше стал понимать как устроена библиотека, хотябы эти typedef что это такое, да и итератор разобрал, раньше я его создавал вложенным классом. Конечно плюсы есть, что разобрал, да и думаю не зря разобрал, мб потом другие библиотеки поддадутся легче.

[youtube]http://www.youtube.com/watch?v=9XewOH8co2o[/youtube]

Добавить комментарий Отменить ответ

Ваш адрес email не будет опубликован. Обязательные поля помечены *

Рубрики

  • C++ (293)
  • JavaScript (1)
  • linux (1)
  • MFC (39)
  • node.js (2)
  • React (3)
  • vBulletin (5)
  • Visual Studio (9)
  • wordpress (18)
  • Разное (29)

Метки

Ajax bootstrap CentOS CLI expressjs FormData GDlib google Invisible reCAPTCHA JWT media MFC php react-router-dom redux repository wordpress RTTI STL vBulletin vector Visual Studio WINAPI wordpress wp-plugins XMLHttpRequest Двоичное дерево Задачи С++ Игры С++ Исключения С++ О-большое Операторы_С++ Перегрузка операторов С++ Поиск С++ Потоки Проектирование_С++ С++ Типы_С++ Типы С++ Шаблоны С++ библиотеки локализация макросы С++ сортировка С++

Свежие комментарии

  • RA3PKJ к записи visual C++, создание диалоговых окон.
  • admin к записи Как удалить изображение из google
  • Shakanris к записи Программка для заполнения форума на vBulletin 3.8.7
  • костя к записи visual C++, создание диалоговых окон.
  • Татьяна к записи Как удалить изображение из google
©2021 Kselax.ru Theme by ThemeGiant