Контейнер hash_map

#include <iostream>     // std::cout
#include <algorithm>    // std::fill
#include <vector>       // std::vector
 
struct Entry
{
 
};
 
int main () {
  std::vector<Entry*> b;
    std::fill<std::vector<Entry*>::iterator,int>(b.begin(),b.end(),0);
 
  //Отак когда то нету ошибки
    /*std::vector<Entry*>::iterator it;
        for(it=b.begin();it!=b.end();++it)
            *it=0;*/
 
  return 0;
}

template<class _FwdIt,
    class _Ty> inline
    void _Fill(_FwdIt _First, _FwdIt _Last, const _Ty& _Val)
    {   // copy _Val through [_First, _Last)
    for (; _First != _Last; ++_First)
        *_First = _Val;
    }

#include <iostream>     // std::cout
#include <algorithm>    // std::fill
#include <vector>       // std::vector
 
struct Entry {};
 
int main ()
{
    std::vector<Entry*> b;
    std::fill(b.begin(), b.end(), nullptr);
 
    return 0;
}

#include <iostream>     // std::cout
#include <algorithm>    // std::fill
#include <vector>       // std::vector
 
struct Entry
{
    //explicit Entry(const int x) : a(x) {}
    //operator int() const {return a; }
    int a;
};
 
int main () {
  std::vector<Entry*> b(10);
    std::fill<std::vector<Entry*>::iterator,Entry*>(b.begin(),b.end(),0);
 
  //Отак когда то нету ошибки
    std::vector<Entry*>::iterator it;
        for(it=b.begin();it!=b.end();++it)
            std::cout << *it;
 
  return 0;
}

#include <iostream>     // std::cout
#include <algorithm>    // std::fill
#include <vector>       // std::vector
 
struct Entry {};
 
int main ()
{
    std::vector<Entry*> b(10);
    std::fill(b.begin(), b.end(), (Entry*)0);
 
    return 0;
}

//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;
#include <algorithm>
using std::fill;
 
//делаем определение шаблона функции хеширования
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>
{
    bool operator()(const T& key1,const T& key2) const;
};
 
 
//Начало класса 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;
    //делаем объявление
    struct Entry;
    typedef Entry* iterator;
    typedef const Entry* 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());//резервирует память для роста
    }
 
    //установка умолчания
    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),erased(false),next(n){}
    };
    vector<Entry> v;//истиные входы
    vector<Entry*> b;//хешь таблица указатели внутрь v
    //...
 
};
 
//определения функци
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)
    {
        size_type i=hash(k)%b.size();//хэш
 
        for(Entry* p=b[i];p;p->next)//поиск среди входов хэшированых в i
            if(eq(k,p->key))//найдено
            {
                if(p->erased)//повторная вставка
                {
                    p->erased=false;
                    no_of_erased--;
                    return p->val=default_value;
                }
                return p->val;
            }
        
        //не найдено
        if(b.size()*max_load<=v.size())//слишком плотное заполнение
        {
            cout <<"mu v b.size()*max_load"<<endl;exit(1);
            resize(b.size()*grow);//расширяем
            return operator[](k);//рехэшируем
        }
        
        v.push_back(Entry(k,default_value,b[i]));//добавляем Entry
        b[i]=&v.back();//указываем на новый элемент
 
        return b[i]->val;
    }//вроде как проверено
 
template<class Key, class T, class H,
    class EQ,class A >
        void hash_map<Key,T,H,EQ,A>::resize(size_type s)
    {
        size_type i=v.size();
        if(s<=b.size()) return;
 
        while(no_of_erased)//реально устраняет удаленные элементы
        {
            if(v[--i].erased)
            {
                v.erase(v.begin()+i);//передаем указатель
                --no_of_erased;
            }
        }
 
        b.resize(s);
    
        fill<vector<Entry*>::iterator,Entry*>(b.begin(),b.end(),0);//обнуляем входы (параграф 18.6.6)
 
        v.reserve(s*max_load);//если v нуждается в памяти, делаем это сейчас
 
        for(size_type i=0;i<v.size();i++)//рехэширование
        {
            size_type ii=hash(v[i].key)%b.size();//хэширование
            v[i].next=b[ii];//связь
            b[ii]=&v[i];
        }
    }
 
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;
    }
 
#endif

//opredelenie hash_map
 
#include "hash_map.h"
 
#include <iostream>
using std::cout;
using std::endl;
#include <cstdlib>
using std::exit;
#include <cstring>
using std::strcmp;
 
//несколько специализаций функции Hash
template<class T>size_t Hash<T>::operator()(const T& key)const
{
    size_t res=0;
    
    sizt_t len=sizeof(T);
    const char* p=reinterpret_cast<const char*>(&key);
 
    while(len--) res=(res<<1)^*p++;
    return res;
}
 
typedef char* Pchar; //char как тип Pchar
template<> size_t Hash<Pchar>::operator()(const Pchar& key)const
{
    size_t res=0;
    
    Pchar p=key;
    while(*p) res=(res<<1)^*p++;
    return res;
}
 
template<> size_t Hash<string>::operator()(const string& key)const
{
    size_t res=0;
    typedef string::const_iterator CI;
 
    CI p=key.begin();
    CI end=key.end();
 
    while(p!=end)res=(res<<1)^*p++;
    return res;
}
 
//специализация для equal_to
 
template<class T>bool equal_to<T>::operator()(const T& key1,const T& key2)const
{
    return key1==key2;
}
 
template<>bool equal_to<Pchar>::operator()(const Pchar& key1,const Pchar& key2) const
{
    if(strcmp(key1,key2)==0)
        return true;
    
    return false;
}
 
template<>bool equal_to<string>::operator()(const string& key1,const string& key2)const
{
    return key1==key2;
}

#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<char*, int> h;
 
    cout <<"h.size()= "<<h.size()<<endl;
    h["hellow"]=35;
    h["gacpada"]=44;
    cout <<"h.size()= "<<h.size()<<endl;//2
    
    h.resize(108);
 
    cout <<"h['hellow']= "<<h["hellow"]<<endl;
    cout <<"h['gacpada']= "<<h["gacpada"]<<endl;
 
    return 0;
}

//  template<class In>hash_map(In first, In last, const T& dv=T(), size_type n=101,
//      const H& hf=H(), const EQ&=EQ()){}