从零开始手写STL库：Map

从零开始手写STL库–Map的实现Github链接miniSTL文章目录从零开始手写STL库–Map的实现一、Map是什么二、Set要包含什么函数总结一、Map是什么std::map是基于红黑树构建的数组结构能够储存键和值这样的数据对并且不允许重复元素的存在二、Set要包含什么函数基于本流程中实现过的红黑树封装一层就可以了不过这里额外实现一下std::map的访问方式也就是at和operator[]的实现正常的封装一下插入删除查找等函数templatetypenameKey,typenameValueclassmyMap{private:myRedBlackTreeKey,ValuerbTree;public:Map():rbTree(){}~Map(){}voidinsert(constKeykey,constValuevalue){rbTree.insert(key,value);}voiderase(constKeykey){rbTree.remove(key);}size_tsize(){returnrbTree.getSize();}boolempty()const{returnrbTree.empty();}boolcontains(constKeykey){returnrbTree.at(key)!nullptr;}};关于at的实现则调用红黑树的查找函数如下Valueat(constKeykey){Value*foundValrbTree.at(key);if(foundVal){return*foundVal;}else{throwstd::out_of_range(Key not found);}}同样的operator[]的重构也调用at函数如下Valueoperator[](constKeykey){Value*foundValrbTree.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()(constmyKeya,constmyKeyb)const{returna.keyb.key;}};std::mapmyKey,int,myComparemyMap;或者structmyKey{intkey;booloperator(constmyKeyother)const{returnkeyother.key;}};std::mapmyKey,intmyMap;