LinkMap (链式映射) 数据结构

Key-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 = https://www.it610.com/article/new MapValue; newMapKey->next = nullptr; newMapKey->key = key; newMapKey->value = https://www.it610.com/article/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 = https://www.it610.com/article/value; return Iterator(tmpMapKey); } tmpMapKey = tmpMapKey->next; } MapKey* newMapKey = new MapKey; MapValue* newMapValue = https://www.it610.com/article/new MapValue; newMapKey->next = nullptr; newMapKey->key = key; newMapKey->value = https://www.it610.com/article/newMapValue; if (head == nullptr){ newMapKey->prev = nullptr; head = tail = newMapKey; } else{ newMapKey->prev = tail; tail->next = newMapKey; tail = newMapKey; } size++; tail->value->value = https://www.it610.com/article/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); }