LinkMap(チェーンマップ)

キー-Value(キーの値ペア):
Mapマッピングはセットであり、その記憶ユニットはキーペアであり、実際には正確にはキーの情報だけが必要であり、値の情報はキーと関連しているので、GRASP原則によれば、マッピングクラスではなくキーと結合されるべきである.

#pragma once
/*
*LinkMap（      ）
*  ：    
*  ：19-8-30
*/
// 
template
struct MapValue{
    Value value;
};

// 
template
struct MapKey{
    MapKey* next;
    MapKey* prev;
    Key key;
    MapValue* value;
};

Map(説明):
実際にはチェーンマップとチェーンテーブルはほぼ同じで、チェーンマップのデータタイプが異なる.
大きな違いは、実は、サブコマンダーの実装と演算子の再負荷であり、Mapは中括弧を載せて、Mapは配列のように値付けと作成ができますが、まだ違いがあります.

にマッピングされた［］の中は、下付きではなくキーである.

[]にあるキーは必ずしも存在する必要はありません.存在しない場合、この演算子はこのようなキーを作成します.

template
class LinkMap{
private:
	MapKey* head;			//    
	MapKey* tail;			//    
	int size;							//     

public:
	LinkMap();							//      （         ）
	LinkMap(const LinkMap& linkmap);	//      
	~LinkMap();							//    
	void Destroy();						//    

	int getSize();						//      
	bool isEmpty();						//        

	/**************ITREATOR**************/
	class Iterator{
	private:
		MapKey* i_PtrKey;					//          
	public:
		Iterator(MapKey* mapkey = nullptr);//   
		Key getKey() const;
		Value getValue() const;

		Key operator*() const;
		Iterator& operator++();
		Iterator operator++(int);
		Iterator& operator--();
		Iterator operator--(int);
		bool operator==(const Iterator& other) const;
		bool operator!=(const Iterator& other) const;
	};

	typename LinkMap::Iterator begin();		//          
	typename LinkMap::Iterator end();		//          
	typename LinkMap::Iterator over();		//          

	

	/******************GET*****************/
	Value& operator[](const Key& key);													//        
	typename LinkMap::Iterator Insert(const Key& key, const Value& value);	//    
	void deleteMap(const Key& key);														//    Key    
	Value find(const Key& Key)const;													//  Key   Value 

};

Map(実現):

/*************         ***************/

/*    */
template
LinkMap::Iterator::Iterator(MapKey* mapkey = nullptr){
	this->i_PtrKey = mapkey;
};

/*  Key */
template
Key LinkMap::Iterator::getKey() const{
	return i_PtrKey->key;
};

/*  Value */
template
Value LinkMap::Iterator::getValue() const{
	return i_PtrKey->value->value;
};

/*      Key   */
template
Key LinkMap::Iterator::operator*() const{
	return i_PtrKey;
}

/*  ++*/
template
typename LinkMap::Iterator& 
	LinkMap::Iterator::operator++(){
		if (i_PtrKey == nullptr)
			return Iterator(nullptr);
		i_PtrKey = i_PtrKey->next;
		return *this;
}

/*  ++*/
template
typename LinkMap::Iterator
	LinkMap::Iterator::operator++(int){
		if (i_PtrKey == nullptr)
			return Iterator(nullptr);
		MapKey* newMapKey = i_PtrKey;
		i_PtrKey = i_PtrKey->next;
		return Iterator(newMapKey);
}

/*  --*/
template
typename LinkMap::Iterator&
LinkMap::Iterator::operator--(){
	if (i_PtrKey == nullptr)
		return Iterator(nullptr);
	i_PtrKey = i_PtrKey->prev;
	return *this;
}

/*  --*/
template
typename LinkMap::Iterator
LinkMap::Iterator::operator--(int){
	if (i_PtrKey == nullptr)
		return Iterator(nullptr);
	MapKey* newMapKey = i_PtrKey;
	i_PtrKey = i_PtrKey->prev;
	return Iterator(newMapKey);
}

/*       */
template
bool LinkMap::Iterator::operator==(const Iterator& other) const{
	if (this->i_PtrKey == nullptr || other.i_PtrKey == nullptr){
		if (this->i_PtrKey == nullptr && other.i_PtrKey == nullptr)
			return true;
		return false;
	}
	else if (this->i_PtrKey->key == other.i_PtrKey->key){
		return true;
	}
	return false;
}

/*        */
template
bool LinkMap::Iterator::operator!=(const Iterator& other) const{
	if (this->i_PtrKey == nullptr || other.i_PtrKey == nullptr){
		if (this->i_PtrKey == nullptr && other.i_PtrKey == nullptr)
			return false;
		return true;
	}
	else if (this->i_PtrKey->key != other.i_PtrKey->key){
		return true;
	}
	return false;
}




/******************LinkMap    ********************/
/*          */
template
typename LinkMap::Iterator LinkMap::begin(){
	return Iterator(this->head);
}

//          
template
typename LinkMap::Iterator LinkMap::end(){
	return Iterator(this->tail);
}

//          
template
typename LinkMap::Iterator LinkMap::over(){
	return Iterator(this->tail->next);
}

/*      （   ）*/
template
LinkMap::LinkMap(){
	head = tail = nullptr;
	size = 0;
}

/*      */
template
LinkMap::LinkMap(const LinkMap& linkmap){

}

/*    */
template
LinkMap::~LinkMap(){
	Destroy();
}

/*    */
template
void LinkMap::Destroy(){
	if (isEmpty())
		return;
	MapKey* tmpMapKey = this->head;
	while (head){
		tmpMapKey = tmpMapKey->next;
		if (head->value != nullptr)
			delete head->value;
		delete head;
		head = tmpMapKey;
	}
	tail = nullptr;
}

/*      */
template
bool LinkMap::isEmpty(){
	if (size == 0)
		return true;
	return false;
}

/*      */
template
int LinkMap::getSize(){
	return size;
}


/*        */
template
Value& LinkMap::operator[](const Key& key){
	MapKey* tmpMapKey = this->head;
	while (tmpMapKey){
		if (tmpMapKey->key == key)
			return tmpMapKey->value->value;
		tmpMapKey = tmpMapKey->next;
	}
	MapKey* newMapKey = new MapKey;
	MapValue* newMapValue = new MapValue;
	newMapKey->next = nullptr;
	newMapKey->key = key;
	newMapKey->value = newMapValue;

	if (head == nullptr){
		newMapKey->prev = nullptr;
		head = tail = newMapKey;
	}
	else{
		newMapKey->prev = tail;
		tail->next = newMapKey;
		tail = newMapKey;
	}
	size++;
	return tail->value->value;
}

/*    */
template
typename LinkMap::Iterator 
	LinkMap::Insert(const Key& key,const Value& value){
	MapKey* tmpMapKey = this->head;
	while (tmpMapKey){
		if (tmpMapKey->key == key){
			tmpMapKey->value->value = value;
			return Iterator(tmpMapKey);
		}
		tmpMapKey = tmpMapKey->next;
	}

	MapKey* newMapKey = new MapKey;
	MapValue* newMapValue = new MapValue;
	newMapKey->next = nullptr;
	newMapKey->key = key;
	newMapKey->value = newMapValue;

	if (head == nullptr){
		newMapKey->prev = nullptr;
		head = tail = newMapKey;
	}
	else{
		newMapKey->prev = tail;
		tail->next = newMapKey;
		tail = newMapKey;
	}
	size++;
	tail->value->value = value;
	return Iterator(tail);
}

/*    Key    */
template
void LinkMap::deleteMap(const Key& key){
	MapKey* tmpMapKey = this->head;
	while (tmpMapKey){
		if (tmpMapKey->key == key){
			delete tmpMapKey->value;
			if (tmpMapKey == head){
				head = tmpMapKey->next;
				if (head == tail){
					tail = head;
				}
				else{
					head->prev = nullptr;
				}
			}
			else if(tmpMapKey == tail){
				tail = tmpMapKey->prev;
				tail->next = nullptr;
			}
			else{
				tmpMapKey->prev->next = tmpMapKey->next;
				tmpMapKey->next->prev = tmpMapKey->prev;
			}
			delete tmpMapKey;
			size--;
			return;
		}
		tmpMapKey = tmpMapKey->next;
	}
}

/*  Key   Value */
template
Value LinkMap::find(const Key& Key)const{
	MapKey* tmpMapKey = this->head;
	while (tmpMapKey){
		if (tmpMapKey->key == key){
			return tmpMapKey->value->value;
		}
		tmpMapKey = tmpMapKey->next;
	}
	return Value(0);
}