从零开始手写STL库：Map

从零开始手写STL库–Map的实现

Github链接：miniSTL

一、Map是什么

std::map是基于红黑树构建的数组结构，能够储存键和值这样的数据对，并且不允许重复元素的存在

二、Set要包含什么函数

基于本流程中实现过的红黑树，封装一层就可以了

不过这里额外实现一下std::map的访问方式，也就是at和operator[]的实现

正常的封装一下插入删除查找等函数：

template<typenameKey,typenameValue>classmyMap{private:myRedBlackTree<Key,Value>rbTree;public:Map():rbTree(){}~Map(){}voidinsert(constKey&key,constValue&value){rbTree.insert(key,value);}voiderase(constKey&key){rbTree.remove(key);}size_tsize(){returnrbTree.getSize();}boolempty()const{returnrbTree.empty();}boolcontains(constKey&key){returnrbTree.at(key)!=nullptr;}};

关于at的实现则调用红黑树的查找函数，如下：

Value&at(constKey&key){Value*foundVal=rbTree.at(key);if(foundVal){return*foundVal;}else{throwstd::out_of_range("Key not found");}}

同样的，operator[]的重构也调用at函数，如下：

Value&operator[](constKey&key){Value*foundVal=rbTree.at(key);if(foundVal)return*foundVal;else{Value defaultValue;rbTree.insert(key,defaultValue);return*rbTree.at(key);}}

不同的在于，如果operator[]访问发现没有这个元素，会将该元素插入进树中

这里也是符合STL库的使用规范的，因为在STL库中，虽然at和[]都可以访问元素，但是原理是不同的

在vector中：
at()访问会做边界检查，如果越界会抛出异常，相对来说安全
operator[]不会，即便是越界也会返回一个引用，只是这个引用必然是错误的，基于该返回值做什么操作都有些危险

在map中：
operator[]会检查元素是否存在，如果不存在就插入该元素，并返回引用

所以这里的实现就将这一过程复现了，关于operator[]的知识点，在Effective STL的第二十四条中也有介绍：Effective STL

有关map的插入效率问题，可以串联起来看

总结

map的查找删除搜索效率一样，都是O(logn)，这是由于它是由红黑树为底层构建的

还需要注意一个问题：如果std::map的键类型是自定义类型，需要怎么做？

答案是重载operator<或者定义比较函数，不过根据Effective STL的意见，更合适的方式是定义比较函数

不过两者均可，不考虑别的程序员可能误解代码的情况下，使用哪个方法都可以，如：

structmyCompare{booloperator()(constmyKey&a,constmyKey&b)const{returna.key<b.key;}};std::map<myKey,int,myCompare>myMap;

或者：

structmyKey{intkey;booloperator<(constmyKey&other)const{returnkey<other.key;}};std::map<myKey,int>myMap;