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

struct St.

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

Дана структура данных, описывающая строкоподобную сущность:

struct St
{
int size;
char type_indicator;
char* buf; //указывает на size символов
St(const char* p); //выделяет память под буфер и заполняет его
}

Создайте 1000 объектов типа St и используйте их в качестве ключей для hash_map. Измерьте производительность такого hash_map. Напишите хэш-функцию (Hash; параграф 17.6.2.3) специально для ключа St.

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

Файл 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 <cstring>
using std::strcmp;

struct St
{
	int size;
	char type_indicator;
	char* buf; //указывает на size символов
	St(const char* p) //выделяет память под буфер и заполняет его
	{
		size=strlen(p);
		type_indicator='c';
		buf=new char[size+1];
		strcpy(buf,p);
		cout <<buf<<endl;
		//exit(1);
	}
	bool operator==(const St& a)const
	{
		if(strcmp(a.buf,buf)==0)
			return true;

		return false;
	}
};

//делаем определение шаблона функции хеширования
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;
	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),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;
	equal_r equal_range(const key_type& k);
	//...

	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();//хэш
		//cout <<"i= "<<i<<endl;
		for(Entry* p=b[i];p;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;
	}

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)%b.size();//хэш
		
		//поиск среди входов хэшированых
		for(Entry* p=b[i];p;p=p->next)//поиск среди входов хэшированых в i
			if(eq(k,p->key))//найдено
			{
				if(p->erased)//проверка что не стерта
				{
					return 0;
				}
				return p;
			}
		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)%b.size();//хэш
		
		//поиск среди входов хэшированых
		for(Entry* p=b[i];p;p=p->next)//поиск среди входов хэшированых в i
			if(eq(k,p->key))//найдено
			{
				if(p->erased)//проверка что не стерта
				{
					return 0;
				}
				return p;
			}
		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 count(0);
		for(Entry* p=b[i];p;p=p->next)//поиск среди входов хэшированых в i
		{
			if(eq(k,p->key))//найдено
			{
				if(p->erased)//проверка что стерта
				{
					continue;
				}
				res.first=p;
				count++;
			}
		//	cout <<"mu tyt"<<endl;
		}
		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;
}

template<> size_t Hash<St>::operator()(const St& key)const
{
	size_t res=0;
	
	char* p=key.buf;
	while(*p) 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;
}

template<>bool equal_to<St>::operator()(const St& key1,const St& key2)const
{
	return key1==key2;
}

Файл main.cpp:

#include <iostream>
using std::cout;
using std::endl;
#include <cstring>
using std::strlen;
using std::strcpy;
#include <cstdlib>
using std::exit;
#include <string>
using std::string;

#include "hash_map.h"

/*struct St
{
	int size;
	char type_indicator;
	char* buf; //указывает на size символов
	St(const char* p) //выделяет память под буфер и заполняет его
	{
		size=strlen(p);
		type_indicator='c';
		buf=new char[size+1];
		strcpy(buf,p);
		cout <<buf<<endl;
		//exit(1);
	}
	bool operator==(const St& a)
	{
		if(strcmp(a.buf,buf)==0)
			return true;

		return false;
	}
};*/

int main()
{
	St S("hello");
	cout <<S.size<<' '<<S.type_indicator<<endl;
	cout <<S.buf<<endl;

	hash_map<St,int> h;
	for(int i=0;i<1000;i++)
	{
		string st="";
		int n=i;
		while(n>0)
		{
			st+=n/10+'0';
			n/=10;
		}

		cout <<st<<endl;
		St a(st.c_str());
		h[a]=i;
	}

	return 0;
}

Снова получился гомнокодец, но увы ничего не поделаешь, какой получился такой получился.

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

rss