Форум программистов, компьютерный форум 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 ?
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
__guest__
Заблокирован
17.06.2013, 02:45     Контейнер hash_map #2
Цитата Сообщение от ninja2 Посмотреть сообщение
Это задачка из книги Страуструпа
как решишь, так тебя работодатель и оценит.

Добавлено через 11 секунд
В будущем
ninja2
 Аватар для ninja2
230 / 186 / 7
Регистрация: 26.09.2012
Сообщений: 2,018
Завершенные тесты: 1
19.06.2013, 12:14  [ТС]     Контейнер hash_map #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ы не сильно волнуют, больше волнует новое понятие "функциональные объекты", что это?
Jupiter
Каратель
Эксперт C++
6543 / 3963 / 226
Регистрация: 26.03.2010
Сообщений: 9,273
Записей в блоге: 1
Завершенные тесты: 2
19.06.2013, 12:25     Контейнер hash_map #4
Цитата Сообщение от ninja2 Посмотреть сообщение
От щас я полностью вес код что есть в книге набрал, правда он не компилируется, куча ошибок вылазит. Я его оформил в два файла от файл hash_map.h:
раздельная компиляция не работает для шаблонов
ninja2
 Аватар для ninja2
230 / 186 / 7
Регистрация: 26.09.2012
Сообщений: 2,018
Завершенные тесты: 1
19.06.2013, 12:34  [ТС]     Контейнер hash_map #5
Jupiter, Ок щас все в одном попробую, у меня как раз 3 ошибки осталось и все в файле hash_map.cpp, возможно потому что нельзя скомпилировать.

Jupiter, А чо не работает? Я вроде помню делал шаблон класса в два файла и вроде компилировалось?
Jupiter
Каратель
Эксперт C++
6543 / 3963 / 226
Регистрация: 26.03.2010
Сообщений: 9,273
Записей в блоге: 1
Завершенные тесты: 2
19.06.2013, 12:38     Контейнер hash_map #6
Цитата Сообщение от ninja2 Посмотреть сообщение
А чо не работает?
у Страуструпа все написано
ninja2
 Аватар для ninja2
230 / 186 / 7
Регистрация: 26.09.2012
Сообщений: 2,018
Завершенные тесты: 1
19.06.2013, 12:42  [ТС]     Контейнер hash_map #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 ниже определения класса?
Я добавлял и та же ошибка. Или как последний вариант добавить определение функций в сам класс? А в книге они ж написаны так как будто они в отдельном файле. ?????
Jupiter
Каратель
Эксперт C++
6543 / 3963 / 226
Регистрация: 26.03.2010
Сообщений: 9,273
Записей в блоге: 1
Завершенные тесты: 2
19.06.2013, 12:43     Контейнер hash_map #8
Цитата Сообщение от ninja2 Посмотреть сообщение
Ну а как нужно просто определения функций добавить в файл hash_map.h ниже определения класса?
можно
ninja2
 Аватар для ninja2
230 / 186 / 7
Регистрация: 26.09.2012
Сообщений: 2,018
Завершенные тесты: 1
19.06.2013, 12:49  [ТС]     Контейнер hash_map #9
Jupiter, Щас еще посмотрю как стандартные контейнеры оформлены, так и сам попробую сделать.
Jupiter
19.06.2013, 12:51
  #10

Не по теме:

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

ninja2
 Аватар для ninja2
230 / 186 / 7
Регистрация: 26.09.2012
Сообщений: 2,018
Завершенные тесты: 1
19.06.2013, 13:24  [ТС]     Контейнер hash_map #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, но это уже потом не будем забегать на перед, разберемся пока с этой ошибкой что щас вылазит в порядке очереди.
0x10
2425 / 1597 / 232
Регистрация: 24.11.2012
Сообщений: 3,919
19.06.2013, 13:27     Контейнер hash_map #12
Сказали же выше, что не работают шаблоны с раздельной компиляцией, что за hash_map.cpp?
ninja2
 Аватар для ninja2
230 / 186 / 7
Регистрация: 26.09.2012
Сообщений: 2,018
Завершенные тесты: 1
19.06.2013, 13:43  [ТС]     Контейнер hash_map #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& мы тут обратились к аргументам шаблона наверно по умолчанию.
0x10
2425 / 1597 / 232
Регистрация: 24.11.2012
Сообщений: 3,919
19.06.2013, 13:45     Контейнер hash_map #14
Цитата Сообщение от ninja2 Посмотреть сообщение
аргументы шаблона по умолчанию можно использовать только в шаблоне класса
Русским по белому: убрать арументы по умолчанию из шаблонов функций.
ninja2
 Аватар для ninja2
230 / 186 / 7
Регистрация: 26.09.2012
Сообщений: 2,018
Завершенные тесты: 1
19.06.2013, 13:54  [ТС]     Контейнер hash_map #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;
    }
Jupiter
19.06.2013, 13:55
  #16

Не по теме:

Цитата Сообщение от ninja2 Посмотреть сообщение
cout <<"mu v operator[]"<<end;exit(1);
return b[0]->val;


Цитата Сообщение от ninja2 Посмотреть сообщение
Отак от таже ошибка
пока вы так пишите, у вас всегда будет ошибка

ninja2
 Аватар для ninja2
230 / 186 / 7
Регистрация: 26.09.2012
Сообщений: 2,018
Завершенные тесты: 1
19.06.2013, 13:56  [ТС]     Контейнер hash_map #17
0x10, Ладно я понял где убрать в самом шаблоне, догадался щас попробую.
0x10
2425 / 1597 / 232
Регистрация: 24.11.2012
Сообщений: 3,919
19.06.2013, 13:58     Контейнер hash_map #18
C++
1
2
3
4
5
6
7
8
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;
* * }
Чтобы получилось
C++
1
2
3
4
5
6
template<
  class Key1,
  class T1,
  class H1,
* class EQ1,
  class A1>
Потому что умолчания уже есть в
Цитата Сообщение от ninja2 Посмотреть сообщение
C++
1
2
3
4
//Начало класса 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
Добавлено через 45 секунд

Не по теме:

Тяжело читать что кашу в коде, что поток сознания в комментах.

ninja2
 Аватар для ninja2
230 / 186 / 7
Регистрация: 26.09.2012
Сообщений: 2,018
Завершенные тесты: 1
19.06.2013, 14:14  [ТС]     Контейнер hash_map #19
Цитата Сообщение от Jupiter Посмотреть сообщение
пока вы так пишите, у вас всегда будет ошЫбка
Нет ну описки не сложно исправить, в данном случае ошибки идут на оформление. Это мелочь

В общем исправил файл 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,
    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)
    {
        cout <<"mu v operator[]"<<endl;exit(1);
 
        return b[0]->val;
    }
 
template<class Key, class T, class H,
    class EQ,class A >
        void hash_map<Key,T,H,EQ,A>::resize(size_type s)
    {
        cout <<"resize"<<endl;exit(1);
    }
 
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;
    }
все правильно компилируется

файл 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
//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
    //...
 
};
 
//определения функци
 
 
#endif
файл main.cpp таже

тут уже новая ошибка вылезла :
1>------ Построение начато: проект: test, Конфигурация: Debug Win32 ------
1>main.obj : error LNK2005: "public: unsigned int __thiscall Hash<char>::operator()(char const &)const " (??R?$Hash@D@@QBEIABD@Z) уже определен в hash_map.obj
1>main.obj : error LNK2005: "public: unsigned int __thiscall Hash<class std::basic_string<char,struct std::char_traits<char>,class std::allocator<char> > >::operator()(class std::basic_string<char,struct std::char_traits<char>,class std::allocator<char> > const &)const " (??R?$Hash@V?$basic_string@DU?$char_traits@D@std@@V?$allocator@D@2@@std@@@@QBEIABV?$basic_string@DU?$char_traits@D@std@@V?$allocator@D@2@@std@@@Z) уже определен в hash_map.obj
1>C:\test\test\Debug\test.exe : fatal error LNK1169: обнаружен многократно определенный символ - один или более
========== Построение: успешно: 0, с ошибками: 1, без изменений: 0, пропущено: 0 ==========


Добавлено через 4 минуты
Когда я комментирую отети строчки кода:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
/*//несколько специализаций функции 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 Hash// : unary_function<T,size_t>
Я пока что unary_function<T,size_t> закомментировал, хотя должен быть видимо базовый класс???? В книге то есть.

Добавлено через 5 минут
Ну как в книге есть, в книге нету просто из кода видно что должен быть как бы базовый класс unary_function<T,size_t>? Господа знатоки СТЛ, я от подозреваю мб это стандартный класс? Или его нужно самому создать, и от него сделать наследование и для класса struct equal_to в книге struct equal_to вообще нету это я уже его сам придумал, типо он такой как и Hash, ну пусть пока такой как Hash побудет, мне главное разобраться с самим Hash, что это за фигня почему его сделали в виде класса, а не в виде функции? Мб удобней было б сделать его в виде функции? И зачем в этом классе функцию Hash вызывается в виде прегрузки operator()(). Мб я и читал, да щас все призабыл .
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
19.06.2013, 14:17     Контейнер hash_map
Еще ссылки по теме:

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

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

Или воспользуйтесь поиском по форуму:
0x10
2425 / 1597 / 232
Регистрация: 24.11.2012
Сообщений: 3,919
19.06.2013, 14:17     Контейнер hash_map #20
http://www.cplusplus.com/reference/f...nary_function/
Yandex
Объявления
19.06.2013, 14:17     Контейнер hash_map
Ответ Создать тему
Опции темы

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