Форум программистов, компьютерный форум 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 ?
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Croessmah
19.06.2013, 14:20     Контейнер hash_map
  #21

Не по теме:

Ну да, мелочь... одна мелочь, вторая... так самолеты то и падают

После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Kastaneda
Модератор
Эксперт С++
 Аватар для Kastaneda
4236 / 2769 / 218
Регистрация: 12.12.2009
Сообщений: 7,104
Записей в блоге: 1
Завершенные тесты: 1
19.06.2013, 22:35     Контейнер hash_map #22
Цитата Сообщение от ninja2 Посмотреть сообщение
контейнер hash_map это тот же контейнер как и map, только он в разы иногда раз в 10-20 быстрее осуществляет поиск элементов по ключу чем стандартный контейнер map
Буквально вчера разбирался с организацией хеш-таблиц, наконец то узнал чем они отличаюся Просто интересно - Страуструп в книге не объясняет за счет чего достигается такой прирост в скорости? В std::map доступ вроде как тоже через функцию хеширования.

Добавлено через 8 минут
Цитата Сообщение от Kastaneda Посмотреть сообщение
В std::map доступ вроде как тоже через функцию хеширования.
Не, гоню я, переучился) Там все завязано на key_comp(); Похоже что-то типа BST, более подробно разбираться сейчас лень.
ninja2
 Аватар для ninja2
230 / 186 / 7
Регистрация: 26.09.2012
Сообщений: 2,018
Завершенные тесты: 1
19.06.2013, 23:02  [ТС]     Контейнер hash_map #23
Kastaneda, Да а я думаю отличие в том что map это дерево, а vector это указатель и возможно поиск в дереве более затратный чем в списке. Хз. Я сам не сильно понял за счет чего производительность возрастает. Мне б щас хотябы запустить рабочую версию.

Да и вообще там написано что этот hash_map это просто в учебных целях нужно создать, а так на практике советует использовать коммерческий версии, либо версии в свободном доступе.

Добавлено через 4 минуты
Я хочу в учебных целях и для остальных деревьев посоздавать hash_multimap, hash_set и hash_multiset, вточь точ такие как их стд товарищи. Там дальше задачки будут, но без этого hash_map я остальные не смогу понять как делать, придется разбираться никуда не дется.
Croessmah
Модератор
Эксперт С++
 Аватар для Croessmah
11825 / 6804 / 769
Регистрация: 27.09.2012
Сообщений: 16,873
Записей в блоге: 2
Завершенные тесты: 1
19.06.2013, 23:03     Контейнер hash_map #24
Цитата Сообщение от Kastaneda Посмотреть сообщение
Не, гоню я, переучился)
Проверяется эквивалентность элементов
ninja2
 Аватар для ninja2
230 / 186 / 7
Регистрация: 26.09.2012
Сообщений: 2,018
Завершенные тесты: 1
19.06.2013, 23:07  [ТС]     Контейнер hash_map #25
Kastaneda, Так ты тоже Страуструпа читаешь щас и на том месте где я?

Добавлено через 2 минуты
Цитата Сообщение от Kastaneda Посмотреть сообщение
Там все завязано на key_comp();
Эта функция просто сравнивает ключи, она хэш не создает. А хэш у страуструпа это походу индекс массива, от мне интересно функцию эту запустить и вывести посмотреть каки хэши будут создаваться. Диапазон интересно посмотреть какой будит.
Kastaneda
Модератор
Эксперт С++
 Аватар для Kastaneda
4236 / 2769 / 218
Регистрация: 12.12.2009
Сообщений: 7,104
Записей в блоге: 1
Завершенные тесты: 1
19.06.2013, 23:15     Контейнер hash_map #26
Цитата Сообщение от ninja2 Посмотреть сообщение
а vector это указатель и возможно поиск в дереве более затратный чем в списке.
я даже незнаю как это понимать) В BST поиск O(log n), в списке и векторе (если вектор не упорядочен и не испльзуется бинарный поиск) О(n).
Цитата Сообщение от ninja2 Посмотреть сообщение
Так ты тоже Страуструпа читаешь щас и на том месте где я?
Нет, не читаю, поэтому и спросил.
Цитата Сообщение от ninja2 Посмотреть сообщение
Эта функция просто сравнивает ключи, она хэш не создает.
Я в курсе, посмотрел уже, написал же выше. Там похоже хеш вообще никаким боком не используется.
Цитата Сообщение от Croessmah Посмотреть сообщение
Проверяется эквивалентность элементов
Не совсем, она возвращает key_compare (метод для сравнения), который в свою очередь возвращает bool, и используется для сравнения элементов.
пример кода
Пример с msdn
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
   map <int, int, less<int> > m1;
   map <int, int, less<int> >::key_compare kc1 = m1.key_comp( ) ;
   bool result1 = kc1( 2, 3 ) ;
   if( result1 == true )
   {
      cout << "kc1( 2,3 ) returns value of true, "
           << "where kc1 is the function object of m1."
           << endl;
   }
   else   
   {
      cout << "kc1( 2,3 ) returns value of false "
           << "where kc1 is the function object of m1."
           << endl;
   }
 
   map <int, int, greater<int> > m2;
   map <int, int, greater<int> >::key_compare kc2 = m2.key_comp( );
   bool result2 = kc2( 2, 3 ) ;
   if( result2 == true )
   {
      cout << "kc2( 2,3 ) returns value of true, "
           << "where kc2 is the function object of m2."
           << endl;
   }
   else   
   {
      cout << "kc2( 2,3 ) returns value of false, "
           << "where kc2 is the function object of m2."
           << endl;
   }
}
вывод
Код
kc1( 2,3 ) returns value of true, where kc1 is the function object of m1.
kc2( 2,3 ) returns value of false, where kc2 is the function object of m2.

Интуитивно могу предположить, что она испльзуется для определения "куда засунуть элемент в дереве". За подробностями можно обратиться в исходники map'а, но мне уже неохото)
Croessmah
Модератор
Эксперт С++
 Аватар для Croessmah
11825 / 6804 / 769
Регистрация: 27.09.2012
Сообщений: 16,873
Записей в блоге: 2
Завершенные тесты: 1
19.06.2013, 23:24     Контейнер hash_map #27
Kastaneda, я к тому, что определяется не равенство, а эквивалентность
если проверять равенство ключей, то рано или поздно порушим дерево
ninja2
 Аватар для ninja2
230 / 186 / 7
Регистрация: 26.09.2012
Сообщений: 2,018
Завершенные тесты: 1
20.06.2013, 00:09  [ТС]     Контейнер hash_map #28
Ладно хватит флудить я тут с unery_function разобрался продолжим дальше разбираться с примерам, будем исправлять ошибки.
Файл 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
//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;
 
 
//делаем определение шаблона функции хеширования
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,
    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;
    }
и main.cpp, для тех кто будет сразу с последней страници просматривать :
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
#include <iostream>
using std::cout;
using std::endl;
#include <cstdlib>
using std::exit;
 
#include "hash_map.h"
 
int main()
{
    cout <<"Test hash_map"<<endl;
 
    return 0;
}
И от ошибка вылазит:
1>------ Построение начато: проект: test, Конфигурация: Debug Win32 ------
1> main.cpp
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 ==========


Отетa от часть кода делает ошибку:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
//несколько специализаций функции 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<>, она просто без ничего ???

Добавлено через 22 минуты
Как мне правильно без ошибок сделать специализацию шаблона??????
ForEveR
Модератор
Эксперт C++
 Аватар для ForEveR
7927 / 4709 / 318
Регистрация: 24.06.2010
Сообщений: 10,524
Завершенные тесты: 3
20.06.2013, 00:12     Контейнер hash_map #29
ninja2, В .cpp файл унести специализацию.
ninja2
 Аватар для ninja2
230 / 186 / 7
Регистрация: 26.09.2012
Сообщений: 2,018
Завершенные тесты: 1
20.06.2013, 00:16  [ТС]     Контейнер hash_map #30
ForEveR, Как оно неожиданно заработало.
Olivеr
 Аватар для Olivеr
411 / 407 / 13
Регистрация: 06.10.2011
Сообщений: 830
20.06.2013, 00:25     Контейнер hash_map #31
Цитата Сообщение от Kastaneda Посмотреть сообщение
Похоже что-то типа BST, более подробно разбираться сейчас лень.
std::map построен на основе красно-черного дерева

Цитата Сообщение от Kastaneda Посмотреть сообщение
Там похоже хеш вообще никаким боком не используется.
ее там даже нету:
C++
1
2
3
4
5
template < class Key,                                     // map::key_type
           class T,                                       // map::mapped_type
           class Compare = less<Key>,                     // map::key_compare
           class Alloc = allocator<pair<const Key,T> >    // map::allocator_type
           > class map;
То, что пишет ninja2 в STL называется unordered_map
C++
1
2
3
4
5
6
template < class Key,                                    // unordered_map::key_type
           class T,                                      // unordered_map::mapped_type
           class Hash = hash<Key>,                       // unordered_map::hasher
           class Pred = equal_to<Key>,                   // unordered_map::key_equal
           class Alloc = allocator< pair<const Key,T> >  // unordered_map::allocator_type
           > class unordered_map;
ninja2
 Аватар для ninja2
230 / 186 / 7
Регистрация: 26.09.2012
Сообщений: 2,018
Завершенные тесты: 1
20.06.2013, 11:59  [ТС]     Контейнер hash_map #32
Здорова!
Снова вылезла непонятная ошибка
От файл 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
//opredelenie hash_map
 
#include "hash_map.h"
 
#include <iostream>
using std::cout;
using std::endl;
#include <cstdlib>
using std::exit;
 
//несколько специализаций функции Hash
template<class T>size_t Hash<T>::operator()(const T& key)const
{
    size_t res=1;
    cout <<"mu v Hash"<<endl;exit(1);
    return res;
}
 
typedef char Pchar; //char как тип Pchar
template<> size_t Hash<Pchar>::operator()(const Pchar& key)const
{
    size_t res=2;
    cout <<"mu v Hash<Pchar>"<<endl;exit(1);
    return res;
}
 
template<> size_t Hash<string>::operator()(const string& key)const
{
    size_t res=3;
    cout <<"mu v Hash<string>"<<endl;exit(1);
    return res;
}
//конец специализации функции хеширования
 
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
//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;
 
 
//делаем определение шаблона функции хеширования
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>
{
    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
{
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;
    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(hf),eq(e)
    {
        set_load();//все что по умолчанию
        v.reserve(max_load*b.size());//резервирует память для роста
        cout <<v.size()<<' '<<b.size()<<endl;
    }
 
    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),next(n){}
    };
 
    vector<Entry> v;//истиные входы
    vector<Entry*> b;//хешь таблица указатели внутрь v
    //...
 
};
 
//определения функци
 
 
#endif
и main.cpp:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#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<string, int> h;
    h["hellow"]=4;
 
    return 0;
}
при вызове operator[]() происходит ошибка:Создание кода...
1>main.obj : error LNK2019: ссылка на неразрешенный внешний символ "public: int & __thiscall hash_map<class std::basic_string<char,struct std::char_traits<char>,class std::allocator<char> >,int,struct Hash<class std::basic_string<char,struct std::char_traits<char>,class std::allocator<char> > >,struct equal_to<class std::basic_string<char,struct std::char_traits<char>,class std::allocator<char> > >,class std::allocator<struct std:air<class std::basic_string<char,struct std::char_traits<char>,class std::allocator<char> > const ,int> > >::operator[](class std::basic_string<char,struct std::char_traits<char>,class std::allocator<char> > const &)" (??A?$hash_map@V?$basic_string@DU?$char_traits@D@std@@V?$allocator@D@2@@std@@HU?$Hash@V?$basic_string@DU?$char_traits@D@std@@V?$allocator@D@2@@std@@@@U?$equal_to@V?$basic_string@DU?$char_traits@D@std@@V?$allocator@D@2@@std@@@@V?$allocator@U?$pair@$$CBV?$basic_string@DU?$char_traits@D@std@@V?$allocator@D@2@@std@@H@std@@@2@@@QAEAAHABV?$basic_string@DU?$char_traits@D@std@@V?$allocator@D@2@@std@@@Z) в функции _main
1>C:\test\test\Debug\test.exe : fatal error LNK1120: 1 неразрешенных внешних элементов
========== Построение: успешно: 0, с ошибками: 1, без изменений: 0, пропущено: 0 ==========


Если я закомментирую определение функции operator[] в файле hash_map.cpp и определю ее в классе hash_map то этой ошибки нету. Наверно как то шаблон функции operator[]() ее определение как то не правильно определено?????
Croessmah
Модератор
Эксперт С++
 Аватар для Croessmah
11825 / 6804 / 769
Регистрация: 27.09.2012
Сообщений: 16,873
Записей в блоге: 2
Завершенные тесты: 1
20.06.2013, 12:08     Контейнер hash_map #33
опять реализация отдельно от объявления?
ninja2
 Аватар для ninja2
230 / 186 / 7
Регистрация: 26.09.2012
Сообщений: 2,018
Завершенные тесты: 1
20.06.2013, 12:12  [ТС]     Контейнер hash_map #34
Цитата Сообщение от Croessmah Посмотреть сообщение
опять реализация отдельно от объявления?
А когда я добавляю определение hash_map::operator[]() в файл hash_map.h то тогда вроде норм компилируется, что ж тогда придется мне их в одном файле делать?
Croessmah
Модератор
Эксперт С++
 Аватар для Croessmah
11825 / 6804 / 769
Регистрация: 27.09.2012
Сообщений: 16,873
Записей в блоге: 2
Завершенные тесты: 1
20.06.2013, 12:17     Контейнер hash_map #35
Цитата Сообщение от ninja2 Посмотреть сообщение
что ж тогда придется мне их в одном файле делать?
Почитайте про то что такое шаблоны Ответ придет неожиданно
Kastaneda
Модератор
Эксперт С++
 Аватар для Kastaneda
4236 / 2769 / 218
Регистрация: 12.12.2009
Сообщений: 7,104
Записей в блоге: 1
Завершенные тесты: 1
20.06.2013, 12:45     Контейнер hash_map #36

Не по теме:

Цитата Сообщение от Olivеr Посмотреть сообщение
std::map построен на основе красно-черного дерева
Сенкс, а откуда информация? Лень в стандарт лезть, но там вроде это не оговорено. Скорее всего там сказано, что нибудь типа "скорость доступа по ключу не более О(log n)"



Добавлено через 12 минут

Не по теме:

Цитата Сообщение от Kastaneda Посмотреть сообщение
Лень в стандарт лезть
Залез таки) Про внутреннию структуру там ничего не сказано, только написано про скорость доступа, как я и предполагал. Например вот:
T& operator[](const key_type& x);
1 Effects: If there is no key equivalent to x in the map, inserts value_type(x, T()) into the map.
2 Requires: key_type shall be CopyConstructible and mapped_type shall be DefaultConstructible.
3 Returns: A reference to the mapped_type corresponding to x in *this.
4 Complexity: logarithmic.

ForEveR
20.06.2013, 12:47
  #37

Не по теме:

Kastaneda, Всецело верно.

Associative containers provide fast retrieval of data based on keys. The library provides four basic kinds of
associative containers: set, multiset, map and multimap.
A map is an associative container that supports unique keys (contains at most one of each key value) and
provides for fast retrieval of values of another type T based on the keys. The map class supports bidirectional
iterators.
Правильнее будет сказать примерно так: все современные реализации строят std::map на основе красно-черного дерева.

Olivеr
20.06.2013, 12:48
  #38

Не по теме:

Цитата Сообщение от Kastaneda Посмотреть сообщение
Сенкс, а откуда информация? Лень в стандарт лезть, но там вроде это не оговорено. Скорее всего там сказано, что нибудь типа "скорость доступа по ключу не более О(log n)"
http://gcc.gnu.org/onlinedocs/libstd...8h-source.html
C++
1
 enum _Rb_tree_color { _S_red = false, _S_black = true };
Видимо у разработчиков был выбор или красно-черное дерево или АВЛ.
Выбрали красно-черное потому, что оно является чем-то средним между BST и AVL.

ForEveR
20.06.2013, 12:50
  #39

Не по теме:

Olivеr, libstdc++ не является стандартом, просто реализация, не более того.

MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
20.06.2013, 12:51     Контейнер hash_map
Еще ссылки по теме:

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

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

Или воспользуйтесь поиском по форуму:
Olivеr
20.06.2013, 12:51     Контейнер hash_map
  #40

Не по теме:

Цитата Сообщение от ForEveR Посмотреть сообщение
Olivеr, libstdc++ не является стандартом, просто реализация, не более того.
Понятное дело.

Yandex
Объявления
20.06.2013, 12:51     Контейнер hash_map
Ответ Создать тему
Опции темы

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