网站的图片做多大尺寸,长沙做网站企业,angular 做的网站,佛山百度关键词seo外包map和set封装 文章目录 map和set封装设计问题#xff08;知其所以然#xff09;为什么要对iterator进行封装#xff1f;为什么要引入Self Ref Ptr这些模板参数#xff1f;为什么是试图从non_const转变为const#xff0c;而不是const转为non_const如何解决 为什么说能加con…map和set封装 文章目录 map和set封装设计问题知其所以然为什么要对iterator进行封装为什么要引入Self Ref Ptr这些模板参数为什么是试图从non_const转变为const而不是const转为non_const如何解决 为什么说能加const把const加上增加构造函数解决set调用红黑树实现插入时iterator的转换解决方法 unordered_map/set封装为什么迭代器中指向哈希表的指针要加const为什么可以加const为什么指针要加const为什么可以加const不会影响对哈希表的增加删除吗 老生常谈的问题两个由const引发的bug 设计问题知其所以然
为什么要对iterator进行封装
是否需要分装和指向的类型有关
如果迭代器指向的是内置类型不需要分装如果是自定义类型则需要重载一系列操作符因此需要分装 在STL的实现中string的实现就没有用到封装是因为string的迭代器为char* 进行*解引用等操作时不需要重载 为什么要引入Self Ref Ptr这些模板参数
这里和list的底层实现道理一致
因为迭代器有const 和non_const两种而不同的迭代器种类要有不同的返回值类型也就是说如果我们不传入模板参数很多函数要写两次返回值类型不同造成代码的冗余
templateclass Tclass list{.......public:typedef list_iteratorT, T, T* iterator;typedef list_iteratorT, const T, const T* const_iterator;typedef Reverse_Iteratoriterator, T, T* reverse_iterator;typedef Reverse_Iteratorconst_iterator,const T,const T* const_reverse_iterator;}
下面的注释可以帮助理解如何解决冗余 templateclass T,class Ref,class Ptrclass list_iterator{typedef listNodeT Node;public:Node* _pnode;list_iterator(Node* pnode):_pnode(pnode){}//const T 或 T Ref operator*(){return _pnode-_val;//-结构体指针访问结构体成员变量的方式}//const T* 或 T*Ptr operator-(){return (_pnode-_val);}typedef list_iteratorT, Ref, Ptr Self;//iterator 或 const_iteratorSelf operator(){_pnode _pnode-_next;return *this;}.......}为什么是试图从non_const转变为const而不是const转为non_const class Set{private:struct setKeyofT{...}RBTreeK, K, setKeyofT _t;public://底层是对树的封装typedef typename RBTreeK, K, setKeyofT::const_iterator iterator;//两个迭代器都是const迭代器typedef typename RBTreeK, K, setKeyofT::const_iterator const_iterator;iterator begin(){return _t.begin();}const_iterator begin()const{return _t.begin();}iterator end(){return _t.end();//此行报错}const_iterator end()const{return _t.end();}s.Insert(3);s.Insert(1);s.Insert(6);s.Insert(5);s.Insert(9);s.Insert(4);auto it s.begin();while (it ! s.end()){cout *it ;it;}cout endl;报错原因无法转变树中的迭代器需要自己实现转变 为什么是试图从non_const转变为const 此时调用的是第一个begin 返回的是树的iterator但是set的iterator相当于树的const_iterator,类型不匹配而且不能自动发生转换因此报错
如何解决
set在STL中源码是这样解决的 这样写非常的巧妙大佬不愧是大佬:
这样传进来的_t就有const修饰调用的是RBTree中const_iterator begin()const可以满足和set中constiterator的配对
解决了上述转化的问题 此时只需要写一个就可以满足要求多了是重复的会报错 typedef typename RBTreeK, K, setKeyofT::const_iterator iterator;typedef typename RBTreeK, K, setKeyofT::const_iterator const_iterator;iterator begin()const{return _t.begin();}/*const_iterator begin()const{return _t.begin();}*/为什么说能加const把const加上
因为权限可以缩小普通对象是可以调用的但如果不加constconst对象就无法调用
增加构造函数解决set调用红黑树实现插入时iterator的转换
templateclass K
class Set
{RBTreeK, K, setKeyofT _t;
public:typedef typename RBTreeK, K, setKeyofT::const_iterator iterator;typedef typename RBTreeK, K, setKeyofT::const_iterator const_iterator;pairiterator, bool Insert(const K k){return _t.Insert(k);}
};map可以正常调用而set不行因为_t调用的红黑树的insert返回的是普通itereator,但是set的iterator实际上是const_iterator所以报错。要想办法转换 解决方法 构造一个转换的函数拿iterator构造成const_iterator 大佬还是大佬再来膜拜一下大佬的思路
struct _TreeIterator
{.....typedef _TreeIteratorT,Ref,Ptr Self;//迭代器本身受Ref和Ptr影响typedef _TreeIteratorT, T, T* iterator;//始终是普通迭代器在 _TreeIterator中封装了一个普通迭代器(的类型)_TreeIterator(const iterator it)//支持传入普通迭代器调用构造函数:_node(it._node){}}当这个迭代器被实例化为const迭代器这是一个构造函数当实例化为普通迭代器这是一个拷贝构造
unordered_map/set封装
为什么迭代器中指向哈希表的指针要加const为什么可以加const
为什么指针要加const
HashTable中const对象调用迭代器传入的指针是const类型会造成权限的放大
const_iterator end()const
{return const_iterator(nullptr, this);//因为是const,所以this是const
}为什么可以加const不会影响对哈希表的增加删除吗
迭代器里不用修改哈希表哈希表的修改是基于Node改变Node不为const
老生常谈的问题
为什么要在迭代器中增加不受传值影响的iterator迭代器类型不是对象 因为set的两个迭代器都是const迭代器但返回的时候是哈希表中的普通迭代器因为是自定义类型需要添加构造函数实现转换同map和set 两个由const引发的bug 图一加上const以后323行调用的end函数为const对象调用的返回对象为cosnt_iteratorconst_iterator不能转换为iterator 图二多加了一个const在初始化的时候出现错误const const T*
