Kselax.ru

Hacker Kselax — the best hacker in the world

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

struct St.

Posted on 24 июня, 201325 июня, 2013 by admin

Дана структура данных, описывающая строкоподобную сущность:

1
2
3
4
5
6
7
struct St
{
int size;
char type_indicator;
char* buf; //указывает на size символов
St(const char* p); //выделяет память под буфер и заполняет его
}

Создайте 1000 объектов типа St и используйте их в качестве ключей для hash_map. Измерьте производительность такого hash_map. Напишите хэш-функцию (Hash; параграф 17.6.2.3) специально для ключа St.

В общем отакая от фиговина получилась пришлось конечно и свою Hash писать специально для ключа, в общем еле ее запустил, придется весь код скидывать и самого класса, потому что я промучился с ней много, и много чего не получалось, еле еле ее доделал. Ладно закончим с прелюдией, перейдем к файлам.

Файл 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
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
//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;
#include <cstring>
using std::strcmp;
 
struct St
{
int size;
char type_indicator;
char* buf; //указывает на size символов
St(const char* p) //выделяет память под буфер и заполняет его
{
size=strlen(p);
type_indicator='c';
buf=new char[size+1];
strcpy(buf,p);
cout <<buf<<endl;
//exit(1);
}
bool operator==(const St& a)const
{
if(strcmp(a.buf,buf)==0)
return true;
 
return false;
}
};
 
//делаем определение шаблона функции хеширования
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
66
67
68
69
70
71
72
73
74
75
76
77
78
79
//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;
}
 
template<> size_t Hash<St>::operator()(const St& key)const
{
size_t res=0;
char* p=key.buf;
while(*p) 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;
}
 
template<>bool equal_to<St>::operator()(const St& key1,const St& 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
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
#include <iostream>
using std::cout;
using std::endl;
#include <cstring>
using std::strlen;
using std::strcpy;
#include <cstdlib>
using std::exit;
#include <string>
using std::string;
 
#include "hash_map.h"
 
/*struct St
{
int size;
char type_indicator;
char* buf; //указывает на size символов
St(const char* p) //выделяет память под буфер и заполняет его
{
size=strlen(p);
type_indicator='c';
buf=new char[size+1];
strcpy(buf,p);
cout <<buf<<endl;
//exit(1);
}
bool operator==(const St& a)
{
if(strcmp(a.buf,buf)==0)
return true;
 
return false;
}
};*/
 
int main()
{
St S("hello");
cout <<S.size<<' '<<S.type_indicator<<endl;
cout <<S.buf<<endl;
 
hash_map<St,int> h;
for(int i=0;i<1000;i++)
{
string st="";
int n=i;
while(n>0)
{
st+=n/10+'0';
n/=10;
}
 
cout <<st<<endl;
St a(st.c_str());
h[a]=i;
}
 
return 0;
}

Снова получился гомнокодец, но увы ничего не поделаешь, какой получился такой получился.

[youtube]http://www.youtube.com/watch?v=VCy18HGmYZc[/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