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

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

Восстановить пароль Регистрация
Другие темы раздела
C++ Работа с файлами (подсчитать количество слов в файле, содержащих нечетное количеством букв) http://www.cyberforum.ru/cpp-beginners/thread903962.html
Первый раз работаю с файлами и тут у меня проблемы. После компиляции выводит неправильный ответ и выбивает: 'Lab 8.exe': Loaded 'D:\Projects\C++\Training\Lab 8\debug\Lab 8.exe', Binary was not built with debug information. 'Lab 8.exe': Loaded 'C:\WINDOWS\system32\ntdll.dll', No symbols loaded. 'Lab 8.exe': Loaded 'C:\WINDOWS\system32\kernel32.dll', No symbols loaded. The program ' Lab 8.exe:...
C++ ДИНАМИЧЕСКИЕ МАССИВЫ.Найти номер строки, в которой сумма отрицательных нечетных элементов самая большая не знаю почему не правильно считает ведь все правильно сделал?(( подскажите кто нибуть Пожалуста #include <iostream> #include <cmath> #include <cstdio> #include <cstdlib> #include <iomanip> using namespace std; int main() { int n, m, k; http://www.cyberforum.ru/cpp-beginners/thread903938.html
Как спростить код ? рекурсия (ввести последовательность чисел (окончание ввода - 0) и вывести их вобратной последовательности) C++
#include <iostream> using std::cout; using std::endl; using std::cin; const int n=100; int arr = {}; int i = 0; int count = 0;
C++ Дан массив. Выберите из него все элементы, которые встречаются в массиве наибольшее число раз
СРОЧНО!!! ПОМОГИТЕ ПОЖАЛУЙСТА,ОЧЕНЬ НУЖНО!!! ЗАРАНИЕ БЛАГОДАРЮ!) Дан*массив.*Выберите*из*него*все*элементы,*которые*встречаются*в*массиве*наибольшее*число*раз.
C++ В текстовом файле структура – информация о компьютерах. Структура с полями: название, стоимость. http://www.cyberforum.ru/cpp-beginners/thread903890.html
Ребят, помогите пожалуйста, 29 июня экзамен по "Основы программирования",кто сколько сможет сделать задач, тем всей группой поставим "+" пожалуйста:cry:, Заранее, СПАСИБО.... a)Требования: 1. Подготовить текстовый файл с входными данными в редакторе. 2. Составить алгоритм программы. 3. Выделить функции ввода, обработки и вывода. 4. Входные данные прочитать из файла. 5. Выполнить...
C++ Ввести с клавиатуры знак Зодиака. Найти в файле запись с таким знаком и вывести его Ребят, помогите пожалуйста, 29 июня экзамен по "Основы программирования",кто сколько сможет сделать задач, тем всей группой поставим "+" пожалуйста:cry:, Заранее, СПАСИБО.... a)Требования: 1. Подготовить текстовый файл с входными данными в редакторе. 2. Составить алгоритм программы. 3. Выделить функции ввода, обработки и вывода. 4. Входные данные прочитать из файла. 5. Выполнить... подробнее

Показать сообщение отдельно
ninja2
 Аватар для ninja2
230 / 186 / 7
Регистрация: 26.09.2012
Сообщений: 2,018
Завершенные тесты: 1
20.06.2013, 15:06  [ТС]     Контейнер hash_map
Я уже тут с книги тот код что есть как бы запустил и чуток протестил кое что.
Вот файл 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 секунду
Да точно конструктор преобразования.
 
Текущее время: 10:44. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru