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

Hash_multimap.

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

Имеется некоторая реализация hash_map, Реализуйте hash_multimap, hash_set и hash_multiset.

Здесь будем реализовывать hash_multimap, это будет такой же шаблон как и hash_map, только нужно сделать как то ему поддержку не уникальных элементов, это нужно сделать так что бы нескольким одинаковым ключам можно было присвоить разные значения. В этом шаблоне должны быть не уникальные элементы.

В общем немного разобравшись в теме, я решил сделать просто шаблон для multimap, set и multiset без всяких там хэшей, потому что это тема сильно большая и за один час не вникнешь в нее, поэтому я уже сделал шаблон как бы своего multimap, производительность ничего я не проверял, мне оно шас нафиг не нужно.

Файл Multimap.h:

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

#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:

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

#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]

rss