Имеется некоторая реализация hash_map, Реализуйте hash_multimap, hash_set и hash_multiset.
Здесь будем реализовывать hash_multimap, это будет такой же шаблон как и hash_map, только нужно сделать как то ему поддержку не уникальных элементов, это нужно сделать так что бы нескольким одинаковым ключам можно было присвоить разные значения. В этом шаблоне должны быть не уникальные элементы.
В общем немного разобравшись в теме, я решил сделать просто шаблон для multimap, set и multiset без всяких там хэшей, потому что это тема сильно большая и за один час не вникнешь в нее, поэтому я уже сделал шаблон как бы своего multimap, производительность ничего я не проверял, мне оно шас нафиг не нужно.
Файл Multimap.h:
|
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 |
//klacc hash_map #ifndef MULTIMAP_H #define MULTIMAP_H #include <iostream> using std::cout; using std::endl; #include <cstdlib> using std::exit; #include <vector> using std::vector; #include <utility> using std::pair; #include <algorithm> using std::sort; //Начало класса hash_map template<class Key,class T> class Multimap { public: //как map за исключением typedef size_t size_type;//из функции Hash видно что size_t нужно, а не int typedef Key key_type; typedef T mopped_type; //делаем объявление struct Entry; typedef pair<key_type,mopped_type>* iterator; typedef const pair<key_type,mopped_type>* const_iterator; typedef pair<iterator,iterator> equal_r; //конструктор по умолчанию Multimap(const T& dv=T(), size_type n=0) :default_value(),v(n){} //добавление элемента void insert(pair<key_type,mopped_type> a); //этой фигни нету пока iterator find(const key_type&); const_iterator find(const key_type&) const; equal_r equal_range(const key_type& k); //... void erase(iterator position);//удаление указуемого элемента size_type size() const {return v.size();}//число элементов private://внутреннее представление const T default_value;//умолчательное значение используется операцией [] vector<pair<key_type,mopped_type> > v;//истиные входы }; //определения функци //добавление элемента template<class Key, class T> void Multimap<Key,T>::insert(const pair<key_type,mopped_type> a) { v.push_back(a); sort(v.begin(),v.end()); /* cout <<"nachalo vuvoda"<<endl; vector<pair<key_type,mopped_type> >::iterator it; for(it=v.begin();it!=v.end();++it) { cout <<it->first<<' '<<it->second<<endl; } cout <<"konec vuvoda"<<endl;*/ //exit(1); } template<class Key, class T> void Multimap<Key,T>::erase(iterator p) { cout <<p->first<<' '<<p->second<<endl; vector<pair<key_type,mopped_type> >::iterator it; for(it=v.begin();it!=v.end();++it) { if(&(*it)==p) { //cout <<"da"<<endl;//exit(1); it=v.erase(it); } } } template<class Key,class T> typename Multimap<Key,T>::iterator Multimap<Key,T>::find(const key_type& k) { cout <<"mu v find"<<endl; //cout <<k<<endl; vector<pair<key_type,mopped_type> >::iterator it; for(it=v.begin();it!=v.end();++it) { if(it->first==k) return &(*it); } return 0; } template<class Key,class T> typename Multimap<Key,T>::const_iterator Multimap<Key,T>::find(const key_type& k) const { cout <<"mu v find const"<<endl;exit(1); } template<class Key,class T> typename Multimap<Key,T>::equal_r Multimap<Key,T>::equal_range(const key_type& k) { cout <<"mu v equal_range"<<endl; vector<pair<key_type,mopped_type> >::iterator it; equal_r rez; int c(0); for(it=v.begin();it!=v.end();++it) { if(it->first==k) { rez.first=&(*it); //cout <<"da"<<endl;exit(1); for(;it!=v.end();++it) { if(it->first!=k) { rez.second=&(*it); break; } } break; } } return rez; } #endif |
Файл main.cpp:
|
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 |
#include <iostream> using std::cout; using std::endl; #include <string> using std::string; #include "Multimap.h" int main() { cout <<"mu v hash_map"<<endl; Multimap<string,int> m; cout <<"m.size()= "<<m.size()<<endl; m.insert(pair<string,int>("hellow",33)); m.insert(pair<string,int>("hellow1",331)); m.insert(pair<string,int>("hellow2",10)); m.insert(pair<string,int>("hellow2",20)); m.insert(pair<string,int>("hellow3",333)); m.insert(pair<string,int>("hellow2",30)); m.insert(pair<string,int>("hellow2",40)); //m.insert(pair<string,int>("hellow3",333)); cout <<"m.size()= "<<m.size()<<endl; Multimap<string,int>::iterator it; it=m.find("hellow"); cout <<it->first<<' '<<it->second<<endl; m.erase(it); cout <<"m.size()= "<<m.size()<<endl; pair<Multimap<string,int>::iterator,Multimap<string,int>::iterator > rez; rez=m.equal_range("hellow2"); cout <<rez.first->first<<' '<<rez.first->second<<endl; for(it=rez.first;it!=rez.second;++it) { cout <<it->first<<' '<<it->second<<endl; } return 0; } |
Ну а теперь шаблон Multiset. Я решил set не делать, потому что он примерно такой будет, только будет отличатся тем что будем делать проверку есть ли элемент уже или нету, ну я что то примитивное сделал, конечно это гомнокодец.
Файл Multiset.h:
|
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 |
//klacc hash_map #ifndef MULTIMAP_H #define MULTIMAP_H #include <iostream> using std::cout; using std::endl; #include <cstdlib> using std::exit; #include <vector> using std::vector; #include <utility> using std::pair; #include <algorithm> using std::sort; //Начало класса hash_map template<class T> class Multiset { public: //как map за исключением typedef size_t size_type;//из функции Hash видно что size_t нужно, а не int typedef T mopped_type; typedef T* iterator; typedef const T* const_iterator; typedef pair<iterator,iterator> equal_r; //конструктор по умолчанию Multiset(const T& dv=T(), size_type n=0) :default_value(),v(n){} //добавление элемента void insert(mopped_type a); //для итераторов iterator begin(){return &*v.begin();} iterator end(){return &*(v.end()-1);} //этой фигни нету пока iterator find(const mopped_type&); const_iterator find(const mopped_type&) const; //... void erase(iterator position);//удаление указуемого элемента size_type size() const {return v.size();}//число элементов private://внутреннее представление const T default_value;//умолчательное значение используется операцией [] vector<mopped_type> v;//истиные входы }; //определения функци //добавление элемента template<class T> void Multiset<T>::insert(const mopped_type a) { v.push_back(a); } template<class T> void Multiset<T>::erase(iterator p) { cout <<"mu v erase"<<endl;exit(1); } template<class T> typename Multiset<T>::iterator Multiset<T>::find(const mopped_type& k) { cout <<"mu v find"<<endl;exit(1); } template<class T> typename Multiset<T>::const_iterator Multiset<T>::find(const mopped_type& k) const { cout <<"mu v find const"<<endl;exit(1); } #endif |
и файл main.cpp:
|
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 |
#include <iostream> using std::cout; using std::endl; #include <string> using std::string; #include "Multiset.h" int main() { cout <<"mu v Multiset"<<endl; Multiset<int> m; m.insert(4); m.insert(5); m.insert(4); cout <<"m.size()= "<<m.size()<<endl; Multiset<int>::iterator it; it=m.begin(); cout <<"*it= "<<*it<<endl; ++it; cout <<"*it= "<<*it<<endl; it=m.end(); cout <<"*it= "<<*it<<endl; for(it=m.begin();it!=m.end()+1;++it) { cout <<*it<<' '; } cout <<endl; return 0; } |
Конечно я без хэшей сделал, даже тему не поднимал не смотре, да ну его в баню парится очень много, там так с ходу не разберешь, да и нужно оно мне, когда понадобится тогда буду смотреть, а так ну его нафиг, не охота разбирать, на этом хватит.
[youtube]http://www.youtube.com/watch?v=SI-WoaN2psU[/youtube]