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

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

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

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

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

Здорова!
Нужно создать контейнер hash_map это тот же контейнер как и map, только он в разы иногда раз в 10-20 быстрее осуществляет поиск элементов по ключу чем стандартный контейнер map, поэтому если нужен быстрый поиск, то советуют использовать свой hash_map. В общем ребятки какой будет алгоритм создания? Я видел внутреннее представление этого контейнера, так там внутри просто два вектора, один с объектами, а второй с указателями. Интересно как же он работает или по какому алгоритму его строить? Это задачка из книги Страуструпа. Нужно потом будет еще создать hash_set, hash_multiset или я точно не помню еще какието.
0
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;; ...

Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
__guest__
Заблокирован
17.06.2013, 02:45 #2
Цитата Сообщение от ninja2 Посмотреть сообщение
Это задачка из книги Страуструпа
как решишь, так тебя работодатель и оценит.

Добавлено через 11 секунд
В будущем
0
ninja2
231 / 187 / 7
Регистрация: 26.09.2012
Сообщений: 2,018
Завершенные тесты: 1
19.06.2013, 12:14  [ТС] #3
От в общем кусочек шаблона который есть в книге, пытаюсь создать рабочий каркас, но он не работает, да и по шаблону много непоняток.
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
//klacc hash_map
#ifndef HASH_MAP
#define 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
{
    //как map за исключением
    typedef H Hasher;
    typedef EQ key_equal;
    //typedef int size_type;
    
    hash_map(const T& dv=T(),size_type n=101, const H& hf=H(), const EQ&=EQ() ){}
 
    template<class In>hash_map(In first, In last, const T& dv=T(), size_type n=101,
        const H& hf=H(), const EQ&=EQ()){}
 
};
 
#endif
size_type нету, что это такое? Я думаю наверно его нужно самому определить как int
typedef int size_type????
Когда так сделал ошибка на size_type пропала

Потом тут ошибка const H& hf=H(), const EQ&=EQ() в конструкторах. В чом ошибка? Что не создано шаблонов функций? или что? Походу видно, что конструктора вызываются так это получается классы тогда, а как же с этой фигней в начале шаблона быть с шапкой class H=Hash<Key> или class EQ=equal_to<Key>?

А от еще утета запись меня смущает class A=allocator<pair<const Key,T> >, что это такое? Здесь как стандартный шаблон используется или как? Пока я не дошол что бы тут ошибка вылезла в этой строке, но думаю вылезит, так как явно шаблон allocator и шаблон pair не подключены.

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

Добавлено через 35 минут
От щас я полностью вес код что есть в книге набрал, правда он не компилируется, куча ошибок вылазит. Я его оформил в два файла от файл 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
//klacc hash_map
#ifndef HASH_MAP
#define HASH_MAP
 
//делаем определение шаблона функции хеширования
template<class T> struct Hash : unary_function<T,size_t>
{
    size_t operator()(const T& key) const;
};
//определение функции хеширования она как то вызывается через operator()() хз. почему?
template<class T>size_t Hash<T>::operator()(const T& key)const
{
    size_t res=0;
    cout <<"mu v Hash"<<endl;exit(1);
    return res;
}
//несколько специализаций функции Hash
typedef char Pchar;
 
template<> size_t Hash<Pchar>::operator()(const Pchar& key)const
{
    size_t res=0;
    cout <<"mu v Hash<Pchar>"<<endl;exit(1);
    return res;
}
 
template<> size_t Hash<string>::operator()(const string& key)const
{
    size_t res=0;
    cout <<"mu v Hash<string>"<<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
{
    //как map за исключением
    typedef H Hasher;
    typedef EQ key_equal;
    typedef size_t size_type;//из функции Hash видно что size_t нужно, а не int
    
    hash_map(const T& dv=T(), size_type n=101, const H& hf=H(), const EQ&=EQ())
        :default_value(dv),b(n),no_of_erased(0),hash(h),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()){}
 
    //Поиск
    mapped_type& operator[](const key_type& k);
 
    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;
        moped_type val;
        bool erased;
 
        Entry* next; //следущий элемент или хз что
 
        Entry(key_type k, moped_type v, Entry* n)
            :key(k),val(v),next(n){}
    };
 
    vector<Entry> v;//истиные входы
    vector<Entry*> b;//хешь таблица указатели внутрь v
    //...
 
};
 
#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
//opredelenie hash_map
#include <iostream>
using std::cout;
using std::endl;
#include <cstdlib>
using std::exit;
 
template<class Key, class T, class H=Hash<Key>,
    class EQ=equal_to<Key>,class A=allocator<pair<const Key, T> > >
        typename hash_map<Key,T,H,EQ,A>::moped_type&
        hash_map<Key,T,H,EQ,A>::operator[](const key_type& k)
    {
        cout <<"mu v operator[]"<<end;exit(1);
 
        return b[0]->val;
    }
 
template<class Key,class T,class H=Hash<Key>,
    class EQ=equal_ty<Key>,class A=allocator<pair<const Key,T> > >
        void hash_map<Key,T,H,EQ,A>::resize(size_type s)
    {
        cout <<"resize"<<endl;exit(1);
    }
 
template<class Key,class T,class H=Hash<Key>,
    class EQ=equal_to<Key>,class A=allocator<pair<const Key,T> > >
        void hash_map<Key,T,H,EQ,A>::erase(iterator p)
    {
        if(p->erased==false) no_of_erased++;
        p->erased=true;
    }
и файл main.cpp:
C++
1
2
3
4
5
6
7
8
9
10
11
12
#include <iostream>
using std::cout;
using std::endl;
 
#include "hash_map.h"
 
int main()
{
    cout <<"Test hash_map"<<endl;
 
    return 0;
}
Ту еще похоже нету структуры для сравнения EQ наверно она так же делается как и функция H хэш, так же структура создается и переопределяется operator()()?

Еще утета от строчка не ясна
template<class T> struct Hash : unary_function<T,size_t>
что такое unary_function<T, size_t>, что это за класс? Почему от нее наследуется struct Hash?

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

Добавлено через 5 минут
От при компиляции сразу первая ошибка вылезла в этой строке: template<class T> struct Hash : unary_function<T,size_t>
понятно что не понятно что такое за фигня unary_function<T,size_t> ????????????? Да в примере есть, а что это такое, его определения нету, я от предполагаю мб это функция из СТЛ, Там то написано что struct Hash - это класс функциональных объекто или он создан в виде функционального объекта, от и думаю мб unary_function это какое то средство стандартное для создания функциональных объектов???????

Добавлено через 2 минуты
Кто делал хелп, это ж одна из популярных задач по С++, Хорошо б еслиб кто нить скинул код уже готового отлаженого примера

Добавлено через 15 минут
Еще в этой строке ошибка mopped_type& operator[](const key_type& k);
Отут когда я типы mopped_type и key_type меняю на int, то ошибки нету, видно что типы не определены, как мне их определить? typedef Key key_type; это вроде как бы ясно, а от mopped_type Что это будет? это наверно T ??? хз. Запутанная такая фигня.

Добавлено через 3 минуты
От теперь ошибка в этой строчке iterator find(const key_type&);
Как мне iterator определить? Что это будет указатель на Т* или указатель на ключ? хз.

Добавлено через 1 минуту
Отето вам и пример из книги, просто куски набрасали, которые в куче ничего не работают ппц. Все самому доделыввай, догадывайся.

Добавлено через 3 минуты
Класс должен получится такой же как std::map, по функционалу и красиво оформлен
Давайте активней! Активней! Шнеля! Шнеля!

Добавлено через 1 минуту
Меня эти typedefы не сильно волнуют, больше волнует новое понятие "функциональные объекты", что это?
0
Jupiter
Каратель
Эксперт С++
6554 / 3975 / 226
Регистрация: 26.03.2010
Сообщений: 9,273
Записей в блоге: 1
Завершенные тесты: 2
19.06.2013, 12:25 #4
Цитата Сообщение от ninja2 Посмотреть сообщение
От щас я полностью вес код что есть в книге набрал, правда он не компилируется, куча ошибок вылазит. Я его оформил в два файла от файл hash_map.h:
раздельная компиляция не работает для шаблонов
1
ninja2
231 / 187 / 7
Регистрация: 26.09.2012
Сообщений: 2,018
Завершенные тесты: 1
19.06.2013, 12:34  [ТС] #5
Jupiter, Ок щас все в одном попробую, у меня как раз 3 ошибки осталось и все в файле hash_map.cpp, возможно потому что нельзя скомпилировать.

Jupiter, А чо не работает? Я вроде помню делал шаблон класса в два файла и вроде компилировалось?
0
Jupiter
Каратель
Эксперт С++
6554 / 3975 / 226
Регистрация: 26.03.2010
Сообщений: 9,273
Записей в блоге: 1
Завершенные тесты: 2
19.06.2013, 12:38 #6
Цитата Сообщение от ninja2 Посмотреть сообщение
А чо не работает?
у Страуструпа все написано
1
ninja2
231 / 187 / 7
Регистрация: 26.09.2012
Сообщений: 2,018
Завершенные тесты: 1
19.06.2013, 12:42  [ТС] #7
в этом файле hash_map.cpp отут вылезло три ошибки одинаковые для кадой из трех функций, по одной ошибке
C++
1
2
3
4
5
6
7
8
9
template<class Key, class T, class H=Hash<Key>,
    class EQ=equal_to<Key>,class A=allocator<pair<const Key, T> > >
        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[]"<<end;exit(1);
 
        return b[0]->val;
    }
Ошибка : 1>c:\test\test\test\hash_map.cpp(19): error C4519: аргументы шаблона по умолчанию можно использовать только в шаблоне класса
и так для каждой из трех функци. хз что за ошибка, наверно шаблон как то не правильно определел????

Добавлено через 59 секунд
Цитата Сообщение от Jupiter Посмотреть сообщение
у Страуструпа все написано
Да там так написано, кусками код накидан, нет бы все в одном месте написали, что бы просто перепечатал и заработало, а не с кусков собирать класс.

Добавлено через 2 минуты
Jupiter, Ну а как нужно просто определения функций добавить в файл hash_map.h ниже определения класса?
Я добавлял и та же ошибка. Или как последний вариант добавить определение функций в сам класс? А в книге они ж написаны так как будто они в отдельном файле. ?????
0
Jupiter
Каратель
Эксперт С++
6554 / 3975 / 226
Регистрация: 26.03.2010
Сообщений: 9,273
Записей в блоге: 1
Завершенные тесты: 2
19.06.2013, 12:43 #8
Цитата Сообщение от ninja2 Посмотреть сообщение
Ну а как нужно просто определения функций добавить в файл hash_map.h ниже определения класса?
можно
1
ninja2
231 / 187 / 7
Регистрация: 26.09.2012
Сообщений: 2,018
Завершенные тесты: 1
19.06.2013, 12:49  [ТС] #9
Jupiter, Щас еще посмотрю как стандартные контейнеры оформлены, так и сам попробую сделать.
1
Jupiter
19.06.2013, 12:51
  #10

Не по теме:

Цитата Сообщение от ninja2 Посмотреть сообщение
Щас еще посмотрю как стандартные контейнеры оформлены, так и сам попробую сделать.
первая рациональная идея, браво

2
ninja2
231 / 187 / 7
Регистрация: 26.09.2012
Сообщений: 2,018
Завершенные тесты: 1
19.06.2013, 13:24  [ТС] #11
Цитата Сообщение от Jupiter Посмотреть сообщение
первая рациональная идея, браво
Так оно мне ничего не дало, я сразу смотрел как токо начал делать еще позавчера, ну думаю еще гляну мб поможе, да толку ноль. (куча кода там и все.)
Буду пытаться исправить всем известным методом - методом тыка , как нас учил один препод лучше метода еще не придумали.

Добавлено через 3 минуты
Как надоест тыкать снова посмотрю на код стандартных контейнеров.

Добавлено через 24 минуты
Скину пока готовый код тот что уже получился, тут уже не множко ошибок осталось но они ни черта не понятные
Файл 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
//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;
 
 
//делаем определение шаблона функции хеширования
template<class T> struct Hash// : unary_function<T,size_t>
{
    size_t operator()(const T& key) const;
};
//определение функции хеширования она как то вызывается через operator()() хз. почему?
template<class T>size_t Hash<T>::operator()(const T& key)const
{
    size_t res=0;
    cout <<"mu v Hash"<<endl;exit(1);
    return res;
}
//несколько специализаций функции Hash
typedef char Pchar;
 
template<> size_t Hash<Pchar>::operator()(const Pchar& key)const
{
    size_t res=0;
    cout <<"mu v Hash<Pchar>"<<endl;exit(1);
    return res;
}
 
template<> size_t Hash<string>::operator()(const string& key)const
{
    size_t res=0;
    cout <<"mu v Hash<string>"<<endl;exit(1);
    return res;
}
//конец определения шаблона функции хеширования
//делаем шаблон функции сравнения
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
{
    //как 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(h),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);
 
    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
Файл 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
//opredelenie hash_map
 
#include "hash_map.h"
 
#include <iostream>
using std::cout;
using std::endl;
#include <cstdlib>
using std::exit;
 
template<class Key, class T, class H=Hash<Key>,
    class EQ=equal_to<Key>,class A=allocator<pair<const Key, T> > >
        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[]"<<end;exit(1);
 
        return b[0]->val;
    }
 
template<class Key,class T,class H=Hash<Key>,
    class EQ=equal_ty<Key>,class A=allocator<pair<const Key,T> > >
        void hash_map<Key,T,H,EQ,A>::resize(size_type s)
    {
        cout <<"resize"<<endl;exit(1);
    }
 
template<class Key,class T,class H=Hash<Key>,
    class EQ=equal_to<Key>,class A=allocator<pair<const Key,T> > >
        void hash_map<Key,T,H,EQ,A>::erase(iterator p)
    {
        if(p->erased==false) no_of_erased++;
        p->erased=true;
    }
файл main.cpp:
C++
1
2
3
4
5
6
7
8
9
10
11
12
#include <iostream>
using std::cout;
using std::endl;
 
#include "hash_map.h"
 
int main()
{
    cout <<"Test hash_map"<<endl;
 
    return 0;
}
А от ошибки которые вылазят :
1>------ Построение начато: проект: test, Конфигурация: Debug Win32 ------
1> hash_map.cpp
1>c:\test\test\test\hash_map.cpp(19): error C4519: аргументы шаблона по умолчанию можно использовать только в шаблоне класса
1>c:\test\test\test\hash_map.cpp(26): error C4519: аргументы шаблона по умолчанию можно использовать только в шаблоне класса
1>c:\test\test\test\hash_map.cpp(34): error C4519: аргументы шаблона по умолчанию можно использовать только в шаблоне класса
========== Построение: успешно: 0, с ошибками: 1, без изменений: 0, пропущено: 0 ==========


Мб кто поймет в чом ошибка?

Я еще закомментировал файл hash_map.cpp и запускал, так уже другие ошибки были по поводу struct Hash, но это уже потом не будем забегать на перед, разберемся пока с этой ошибкой что щас вылазит в порядке очереди.
0
0x10
2464 / 1636 / 238
Регистрация: 24.11.2012
Сообщений: 4,031
19.06.2013, 13:27 #12
Сказали же выше, что не работают шаблоны с раздельной компиляцией, что за hash_map.cpp?
0
ninja2
231 / 187 / 7
Регистрация: 26.09.2012
Сообщений: 2,018
Завершенные тесты: 1
19.06.2013, 13:43  [ТС] #13
Цитата Сообщение от 0x10 Посмотреть сообщение
Сказали же выше, что не работают шаблоны с раздельной компиляцией, что за 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
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
//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;
 
 
//делаем определение шаблона функции хеширования
template<class T> struct Hash// : unary_function<T,size_t>
{
    size_t operator()(const T& key) const;
};
//определение функции хеширования она как то вызывается через operator()() хз. почему?
template<class T>size_t Hash<T>::operator()(const T& key)const
{
    size_t res=0;
    cout <<"mu v Hash"<<endl;exit(1);
    return res;
}
//несколько специализаций функции Hash
typedef char Pchar;
 
template<> size_t Hash<Pchar>::operator()(const Pchar& key)const
{
    size_t res=0;
    cout <<"mu v Hash<Pchar>"<<endl;exit(1);
    return res;
}
 
template<> size_t Hash<string>::operator()(const string& key)const
{
    size_t res=0;
    cout <<"mu v Hash<string>"<<endl;exit(1);
    return res;
}
//конец определения шаблона функции хеширования
//делаем шаблон функции сравнения
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
{
    //как 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(h),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);
 
    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
    //...
 
};
 
//определения функци
template<class Key, class T, class H=Hash<Key>,
    class EQ=equal_to<Key>,class A=allocator<pair<const Key, T> > >
        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[]"<<end;exit(1);
 
        return b[0]->val;
    }
 
template<class Key,class T,class H=Hash<Key>,
    class EQ=equal_ty<Key>,class A=allocator<pair<const Key,T> > >
        void hash_map<Key,T,H,EQ,A>::resize(size_type s)
    {
        cout <<"resize"<<endl;exit(1);
    }
 
template<class Key,class T,class H=Hash<Key>,
    class EQ=equal_to<Key>,class A=allocator<pair<const Key,T> > >
        void hash_map<Key,T,H,EQ,A>::erase(iterator p)
    {
        if(p->erased==false) no_of_erased++;
        p->erased=true;
    }
 
#endif
Ошибки: 1>------ Построение начато: проект: test, Конфигурация: Debug Win32 ------
1> main.cpp
1>c:\test\test\test\hash_map.h(141): error C4519: аргументы шаблона по умолчанию можно использовать только в шаблоне класса
1>c:\test\test\test\hash_map.h(148): error C4519: аргументы шаблона по умолчанию можно использовать только в шаблоне класса
1>c:\test\test\test\hash_map.h(156): error C4519: аргументы шаблона по умолчанию можно использовать только в шаблоне класса
========== Построение: успешно: 0, с ошибками: 1, без изменений: 0, пропущено: 0 ==========


Те же ошибки.

Добавлено через 9 минут
От в этой строчке ошибка typename hash_map<Key,T,H,EQ,A>::mopped_type& мы тут обратились к аргументам шаблона наверно по умолчанию.
0
0x10
2464 / 1636 / 238
Регистрация: 24.11.2012
Сообщений: 4,031
19.06.2013, 13:45 #14
Цитата Сообщение от ninja2 Посмотреть сообщение
аргументы шаблона по умолчанию можно использовать только в шаблоне класса
Русским по белому: убрать арументы по умолчанию из шаблонов функций.
1
ninja2
231 / 187 / 7
Регистрация: 26.09.2012
Сообщений: 2,018
Завершенные тесты: 1
19.06.2013, 13:54  [ТС] #15
Цитата Сообщение от 0x10 Посмотреть сообщение
Русским по белому: убрать арументы по умолчанию из шаблонов функций.
А если я уберу аргументы по умолчанию, а поставлю туда допустим реальные аргументы там int, float, string, то это уже будет отдельная специализация шаблона, а не шаблон?

Добавлено через 1 минуту
Отут typename hash_map<Key,T,H,EQ,A>::mopped_type& когда я запишу отак typename hash_map<>::mopped_type& , то ошибка мало аргументов шаблона, если я добавлю что нить какие нить реальные аргументы то это ж уже не шаблон, а вызов шаблона? Или мне нужно просто буквы поменять?

Добавлено через 3 минуты
Отак от таже ошибка
C++
1
2
3
4
5
6
7
8
9
template<class Key1, class T1, class H1=Hash<Key>,
    class EQ1=equal_to<Key>,class A1=allocator<pair<const Key1, T1> > >
        typename hash_map<Key1,T1,H1,EQ1,A1>::mopped_type&
        hash_map<Key1,T1,H1,EQ1,A1>::operator[](const key_type& k)
    {
        cout <<"mu v operator[]"<<end;exit(1);
 
        return b[0]->val;
    }
0
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
19.06.2013, 13:54
Привет! Вот еще темы с ответами:

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

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

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

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


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

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

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