[ create a new paste ] login | about

Link: http://codepad.org/PFsQMvhV    [ raw code | output | fork ]

C++, pasted on Jan 18:
#include <iostream>

template <typename K,typename V>
class Hash{
	struct Pair{
		K key;
		V val;
		Pair *next;
	};
	Pair **pair_;
	size_t capacity_;
	size_t size_;
	void reallocate();
	
public:
	explicit Hash(const size_t = 1024);
	explicit Hash(const Hash &);
	~Hash();
	
	inline size_t size() const{ return size_; }
	inline size_t capacity() const{ return capacity_; }
	
	bool exists(const K &) const;
	bool remove(const K &);
	V &operator[](const K &);
	
	void dump() const;
};


template <typename K,typename V>
Hash<K,V>::Hash(const size_t capacity) : 
pair_(new Hash::Pair * [capacity]) ,
capacity_(capacity),
size_(0)
{
	for(size_t i=0; i<capacity; ++i) pair_[i] = NULL;
}

template <typename K,typename V>
Hash<K,V>::Hash(const Hash &hash) : 
pair_(new Hash::Pair * [hash.capacity()]) , capacity_(hash.capacity()), size_(hash.size())
{
	size_t n = capacity();
	while(n--){
		if(hash.pair_[n] != NULL){
			pair_[n] = new Hash::Pair();
			pair_[n]->key = hash.pair_[n]->key;
			pair_[n]->val = hash.pair_[n]->val;
			pair_[n]->next = NULL;
			
			Hash::Pair *tmp = hash.pair_[n]->next;
			Hash::Pair *pair = pair_[n];
			
			while(tmp!=NULL){
				pair->next = new Hash::Pair();
				pair->next->key = tmp->key;
				pair->next->val = tmp->val;
				pair->next->next = NULL;
				
				pair = pair->next;
				tmp = tmp->next;
			}
		}else{
			pair_[n] = NULL;
		}
	}
}


template <typename K,typename V>
Hash<K,V>::~Hash()
{
	size_t n = capacity();
	while(n--){
		if(pair_[n] != NULL){
			Hash::Pair *tmp = pair_[n];
			Hash::Pair *next;
			while(tmp != NULL){
				next = tmp->next;
				delete tmp;
				tmp = next;
			}
		}
	}
	
	delete [] pair_;
}


template <typename K,typename V>
bool Hash<K,V>::exists(const K &key) const{
	size_t calc = calcHash(key, capacity());
	Hash::Pair *pair = pair_[calc];
	
	if(pair == NULL) return false; 
	
	while(true){
		if(pair->key == key) return true;
		if(pair->next == NULL) return false;
		pair = pair->next;
	}
}

template <typename K,typename V>
bool Hash<K,V>::remove(const K &key){
	size_t calc = calcHash(key, capacity());
	Hash::Pair *pair = pair_[calc];
	
	if(pair == NULL) return false; 
	if(pair->key == key){
		pair_[calc] = pair->next;
		delete pair;
		size_--;
		return true;
	} 
	
	while(pair->next){
		if(pair->next->key == key){
			Hash::Pair *tmp = pair->next;
			pair->next = pair->next->next;
			delete tmp;
			size_--;
			return true;
		}
		pair = pair->next;
	}
	return false;
}

template <typename K,typename V>
V & Hash<K,V>::operator[](const K &key){
	size_t calc = calcHash(key, capacity());
	
	if(pair_[calc] == NULL){
		 pair_[calc] = new Hash::Pair();
		 pair_[calc]->key = key;
		 pair_[calc]->next = NULL;
		size_++;
		return  pair_[calc]->val;
	}
	
	Hash::Pair *pair = pair_[calc];
	while(true){
		if(pair->key == key) return pair->val;
		if(pair->next == NULL) break;
		pair = pair->next;
	}
	pair->next = new Hash::Pair();
	pair->next->key = key;
	pair->next->next = NULL;
	size_++;
	return pair->next->val;
	
}

template <typename K,typename V>
void Hash<K,V>::dump() const{
	size_t n = 0;
	std::cout << "-----Dump-----" << std::endl;
	while(n < capacity()){
		Hash::Pair *pair = pair_[n];
		while(pair){
			std::cout << "[" << n << "](" << pair << ") " << pair->key << ": "<<  pair->val;
			pair = pair->next;
			if(pair){
				std::cout << " -> ";
			}else{
				std::cout << std::endl;
			}
		}
		n++;
	}
}


size_t calcHash(const std::string &key, const size_t capacity){
	size_t calc = 0;
	const unsigned char *p = reinterpret_cast<const unsigned char *>(key.c_str());
	while(*p){
		calc += calc>>13 ^ calc<<7 ^ *p<<19 ^ *p;
		p++;
	}
	return calc % capacity;
}

size_t calcHash(const int &key, const size_t capacity){
	size_t calc = key;
	calc += calc >> 13 ^ key << 11;
	calc += calc >> 17 ^ key << 5;
	return calc % capacity;
}


int main(){
	Hash<int, int> hash(256);
	
	for(int n=512; n<1024; n += 2){
		hash[n] = n;
	}
	
	Hash<int, int> hash2(hash); // コピー
/*
	hash.dump();
	hash2.dump();
	*/
	
	std::cout << hash.size() << std::endl;
}


Output:
1
2
3
t.cpp: In constructor 'Hash<K, V>::Hash(size_t)':
Line 33: error: expected type-specifier
compilation terminated due to -Wfatal-errors.


Create a new paste based on this one


Comments: