Предыдущий пост -
Следующий пост -

Hash_map основаный на вектор.

Рубрика: C++, Дата: 24 June, 2013, Автор:

Реализуйте hash_map, основанный на vector<map<K,V>*>, так что бы каждый map содержал все ключи с одинаковым хэш-значением.

В общем пришлось повозится, кое какой примерчик сделал, сильно не тестил, но вроде работает гамнокодец.

Файл hash_map.h:

//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;
#include <map>
using std::map;

//делаем определение шаблона функции хеширования
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 T* iterator;
	typedef const Entry* const_iterator;
	typedef pair<iterator,iterator> equal_r;
	
	//конструктор по умолчанию
	hash_map(const T& dv=T(), size_type n=101, const H& hf=H(), const EQ& e=EQ())
		:default_value(dv),no_of_erased(0),hash(hf),eq(e),v1(n),count(0)
	{
		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;
	equal_r equal_range(const key_type& k);
	//...

	void resize(size_type n);//размер хэш таблицы в n
	
	void erase(iterator position);//удаление указуемого элемента

	size_type size() const {return count;}//число элементов

	//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;//равенство
	size_type count;

	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<map<key_type,mopped_type> > v1;
	//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)%v1.size();//хэш
		//cout <<"i= "<<i<<endl;
	
		if(v1[i].size()==0)//нету элементов
		{
			v1[i][k]=default_value;
			
			//не найдено
			if(v1.size()*max_load<=count)//слишком плотное заполнение
			{
				cout <<"ymnoj= "<<v1.size()*max_load<<endl;
				cout <<"mu v b.size()*max_load"<<endl;exit(1);
				resize(v1.size()*grow);//расширяем
				return operator[](k);//рехэшируем
			}
			count++;

			return v1[i][k];
		}
		else//есть элемент, просто вернуть его
		{
			return v1[i][k];
		}
	}//вроде как проверено

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<=v1.size()) return;
		cout <<"s= "<<s<<endl;
		v1.resize(s);
	}

template<class Key, class T, class H,
	class EQ,class A >
		void hash_map<Key,T,H,EQ,A>::erase(iterator p)
	{
		//cout <<"mu tyt"<<endl;exit(1);
		//осуществляем поиск элемента
		vector<map<key_type,mopped_type> >::iterator it;
		for(it=v1.begin();it!=v1.end();++it)
		{
			//cout <<*it<<endl;
			
			if((*it).size()!=0)
			{
				cout <<(*it).size()<<endl;
				cout <<"mu tyt"<<endl;
				map<key_type,mopped_type>::iterator it1=(*it).begin();
				cout <<(*it1).first<<' '<<(*it1).second<<endl;
				if(&(*it1).second==p)
				{
					v1.erase(it);//удаление элемента
					break;
				}
				//exit(1);
			}
			//exit(1);
		}
//		v1.erase(p);
		count--;
	}

template<class Key,class T,class H,
	class EQ,class A>
		typename hash_map<Key,T,H,EQ,A>::iterator
		hash_map<Key,T,H,EQ,A>::find(const key_type& k)
	{
		size_type i=hash(k)%v1.size();//хэш
		
		//поиск среди входов хэшированых
		if(v1[i].size()!=0)
		{
			//cout <<"mu tyt"<<endl;exit(1);
			return &v1[i][k];
		}

		return 0;
	}

template<class Key,class T,class H,
	class EQ,class A>
		typename hash_map<Key,T,H,EQ,A>::const_iterator
		hash_map<Key,T,H,EQ,A>::find(const key_type& k) const
	{
		size_type i=hash(k)%v1.size();//хэш
		
		//поиск среди входов хэшированых
		if(v1[i].size()!=0)
		{
			return &v1[i][k];
		}

		return 0;
	}

template<class Key,class T,class H,
	class EQ,class A>
		typename hash_map<Key,T,H,EQ,A>::equal_r
		hash_map<Key,T,H,EQ,A>::equal_range(const key_type& k)
	{
		size_type i=hash(k)%b.size();//хэш
		pair<iterator,iterator> res;
		//поиск среди входов хэшированых
		int count1(0);

		if(v1[i].size()!=0)//найдено
		{
			res.first=&v[1][k];
			count++;
		}

		if(count==0)
		{
			//cout <<"mu tyt 0"<<endl;
			res.first=0;
			res.second=0;
		}
		else if(count==1)
		{
			//cout <<"mu tyt 1"<<endl;
			//cout <<"res.first->val= "<<res.first->val<<endl;
			res.second=++res.first;
			--res.first;
			//cout <<"end"<<endl;exit(1);
			//res.first--;
		}

		return res;
	}	

#endif

файл hash_map.cpp:

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

Файл main.cpp:

#include <iostream>
using std::cout;
using std::endl;

#include "hash_map.h"

int main()
{
	hash_map<char*,int> h;
	h["hellow"]=3;
	cout <<h["hellow"]<<endl;
	h["priv"]=5;
	cout <<"h.size()= "<<h.size()<<endl;
	hash_map<char*,int>::iterator it;
	it=h.find("hellow");
	cout <<*it<<endl;
	h.erase(it);
	cout <<*it<<endl;//UB левое значение выводится

	return 0;
}

Что попало конечно но зато работает.

[youtube]http://www.youtube.com/watch?v=mXCpavwSd1M[/youtube]

rss