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

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

Восстановить пароль Регистрация
 
 
Рейтинг: Рейтинг темы: голосов - 31, средняя оценка - 4.68
ninja2
 Аватар для ninja2
230 / 186 / 7
Регистрация: 26.09.2012
Сообщений: 2,018
Завершенные тесты: 1
17.06.2013, 02:12     Контейнер hash_map #1
Здорова!
Нужно создать контейнер 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++
Контейнер set C++
Контейнер на пободия hash_map. C++
C++ контейнер
C++ Контейнер map ?
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
ninja2
 Аватар для ninja2
230 / 186 / 7
Регистрация: 26.09.2012
Сообщений: 2,018
Завершенные тесты: 1
20.06.2013, 14:05  [ТС]     Контейнер hash_map #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
 Аватар для Olivеr
411 / 407 / 13
Регистрация: 06.10.2011
Сообщений: 830
20.06.2013, 14:13     Контейнер hash_map #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
Ворчун
Эксперт С++
 Аватар для MrGluck
4920 / 2663 / 243
Регистрация: 29.11.2010
Сообщений: 7,409
20.06.2013, 14:19     Контейнер hash_map #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
 Аватар для ninja2
230 / 186 / 7
Регистрация: 26.09.2012
Сообщений: 2,018
Завершенные тесты: 1
20.06.2013, 14:34  [ТС]     Контейнер hash_map #44
Цитата Сообщение от Olivеr Посмотреть сообщение
А каким боком это относится к хеш таблицам?
Относится это я просто кусок выдрал из кода, что бы понятнее было где ошибка, не кидать же весь большой код?
ForEveR
Модератор
Эксперт C++
 Аватар для ForEveR
7927 / 4709 / 318
Регистрация: 24.06.2010
Сообщений: 10,524
Завершенные тесты: 3
20.06.2013, 14:37     Контейнер hash_map #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;
}
Tulosba
:)
Эксперт С++
4378 / 3221 / 297
Регистрация: 19.02.2013
Сообщений: 9,044
20.06.2013, 14:55     Контейнер hash_map #46
Цитата Сообщение от ForEveR Посмотреть сообщение
C++
1
2
std::vector<Entry*> b; 
std::fill(b.begin(), b.end(), (void*)0);
Заполнение пустого вектора?
P.S. И тип всё же должен быть Entry*
ninja2
 Аватар для ninja2
230 / 186 / 7
Регистрация: 26.09.2012
Сообщений: 2,018
Завершенные тесты: 1
20.06.2013, 15:06  [ТС]     Контейнер hash_map #47
Я уже тут с книги тот код что есть как бы запустил и чуток протестил кое что.
Вот файл 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
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
//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;
    
    //конструктор по умолчанию
    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;
    //...
 
    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();//хэш
 
        for(Entry* p=b[i];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;
    }
 
#endif
Файл 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
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:
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
#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["gacpada"]=44;
    cout <<"h.size()= "<<h.size()<<endl;//2
    
    h.resize(108);
 
    cout <<"h['hellow']= "<<h["hellow"]<<endl;
    cout <<"h['gacpada']= "<<h["gacpada"]<<endl;
 
    return 0;
}
Тут не все функции работают например erase нельзя протестить, потому что она принимает тип iterator, а у меня пока нету fined() которая могла б вернуть iterator, ну это уже мелочи тут пока главное с оформлением шаблона разобраться.
От как вы думаете правильно ли я все сделал, там файлы слепил? Структура шаблона правильная или нет?
Мб как то лучше можно сделать само оформление? В логику программы не вникаем это мелочь.

Добавлено через 1 минуту
А еще отето от что за фигня в книге она есть, я просто ее закоментировал, что бы не мешалась?
C++
1
2
//  template<class In>hash_map(In first, In last, const T& dv=T(), size_type n=101,
//      const H& hf=H(), const EQ&=EQ()){}
Добавлено через 2 минуты
Это похоже какой то конструктор преобразования наверно? Наверно два итератора принимает начало и конец, в общем хз.

Добавлено через 51 секунду
Да точно конструктор преобразования.
Olivеr
 Аватар для Olivеr
411 / 407 / 13
Регистрация: 06.10.2011
Сообщений: 830
20.06.2013, 15:07     Контейнер hash_map #48
Цитата Сообщение от ninja2 Посмотреть сообщение
А еще отето от что за фигня в книге она есть, я просто ее закоментировал, что бы не мешалась?
C++
1
2
// *template<class In>hash_map(In first, In last, const T& dv=T(), size_type n=101,
// * * *const H& hf=H(), const EQ&=EQ()){}
какой-то конструктор из range последовательности
ninja2
 Аватар для ninja2
230 / 186 / 7
Регистрация: 26.09.2012
Сообщений: 2,018
Завершенные тесты: 1
20.06.2013, 15:15  [ТС]     Контейнер hash_map #49
Сама хеш таблица как создается не понятно от если у нас в b всего 101 ячейка, а в v ничего нету (это при пустом hash_map), то что ж тогда хешь функция должна генерировать хэш в пределах 0-101?????? , а если она случайно сгенерирует 102 и мы попытаемся в b[102] записать какое то значение это что будет UB ??

Добавлено через 2 минуты
Даже не 102, а 101.
ForEveR
Модератор
Эксперт C++
 Аватар для ForEveR
7927 / 4709 / 318
Регистрация: 24.06.2010
Сообщений: 10,524
Завершенные тесты: 3
20.06.2013, 15:40     Контейнер hash_map #50
Tulosba, Да, с пустым я конечно протормозил.) Спасибо.
Tulosba
20.06.2013, 15:44
  #51

Не по теме:

ForEveR, хорошо быть модератором. Взял подправил записи камер видеонаблюдения сообщение .

ninja2
 Аватар для ninja2
230 / 186 / 7
Регистрация: 26.09.2012
Сообщений: 2,018
Завершенные тесты: 1
27.06.2013, 19:57  [ТС]     Контейнер hash_map #52
А как же сделать hash_multimap ????? Как в нем будет хэш использоваться? В multimap вроде как нету операции operator[]() ???
ninja2
 Аватар для ninja2
230 / 186 / 7
Регистрация: 26.09.2012
Сообщений: 2,018
Завершенные тесты: 1
28.06.2013, 20:44  [ТС]     Контейнер hash_map #53
Что никто не знает как хэш использовать в контейнерах hash_multimap, hash_set и hash_multiset????????
Там просто нету operator[]() поэтому фиг его знает как поиск осуществлять, не ну понятно как делать поиск перебрать все элементы, ну а как хэш привязать? Или просто сделать копии multimap, set и multiset и не парится с хэшем ????? Хотябы примитивные копии с итераторами и все, я думаю пол задачи сделаю, на троечку ???
ForEveR
Модератор
Эксперт C++
 Аватар для ForEveR
7927 / 4709 / 318
Регистрация: 24.06.2010
Сообщений: 10,524
Завершенные тесты: 3
28.06.2013, 21:04     Контейнер hash_map #54
@ninja2, Читаем - просвещаемся. http://en.cppreference.com/w/cpp/con...dered_multimap
Kastaneda
Модератор
Эксперт С++
 Аватар для Kastaneda
4236 / 2769 / 218
Регистрация: 12.12.2009
Сообщений: 7,104
Записей в блоге: 1
Завершенные тесты: 1
28.06.2013, 21:19     Контейнер hash_map #55
Вообще перед всем этим делом не мешало бы просветиться в этой области. Гуглим "хеш таблицы с цепочками коллизий" и "хеш таблицы с открытой адресацией". Плюс еще методы хеширования (мультипликативный, т.н. квадратичный и т.д.). Далее формулы выбора размера таблицы в зависимости от типа ключа и метода хеширования, ну и т.д. и т.п.
Тупо опираясь на справку по STL такие вещи не напишешь.
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
28.06.2013, 23:24     Контейнер hash_map
Еще ссылки по теме:

C++ Stdext::hash_map и std::map
C++ Контейнер map
Hash_map unordered_map C++

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

Или воспользуйтесь поиском по форуму:
ninja2
 Аватар для ninja2
230 / 186 / 7
Регистрация: 26.09.2012
Сообщений: 2,018
Завершенные тесты: 1
28.06.2013, 23:24  [ТС]     Контейнер hash_map #56
Та там долго вникать, я так подумал, наверно я просто сделаю multimep, set и multiset как аналоги из стл, быстрее будет, а то с хэшем долго затянится, когда нибудь в другой раз вникну, хоть на половину задачку сделаю на троечку.

Добавлено через 1 минуту
@Kastaneda, Да да это похоже головняк.
Yandex
Объявления
28.06.2013, 23:24     Контейнер hash_map
Ответ Создать тему
Опции темы

Текущее время: 05:15. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru