Контейнер hash_map - C++ - Ответ 4742172

//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

//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

//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;
    }

#include <iostream>
using std::cout;
using std::endl;
 
#include "hash_map.h"
 
int main()
{
    cout <<"Test hash_map"<<endl;
 
    return 0;
}