网站怎么才能被搜到,国家高新技术企业有多少家,济南做网站的机构有哪些,女包建设网站前的市场分析之前模拟了string,vector#xff0c;再到现在的list#xff0c;list的迭代器封装最让我影响深刻。本次模拟的list是双向带头节点的循环链表#xff0c;该结构虽然看起来比较复杂#xff0c;但是却非常有利于我们做删除节点的操作#xff0c;结构图如下。 由于其节点结构特…之前模拟了string,vector再到现在的listlist的迭代器封装最让我影响深刻。本次模拟的list是双向带头节点的循环链表该结构虽然看起来比较复杂但是却非常有利于我们做删除节点的操作结构图如下。 由于其节点结构特点使得头插头删尾插尾删的时间复杂度为O(1),因为我们只需要改变两边节点的指针链接即可。
节点类 先来个开胃小菜了解了解节点类该类比较简单。由于每个节点既要存储数据又要存储前后节点指针所以我们封装一个结构体用的struct而不是class, 因为我们在后面的函数需要访问节点存储的节点指针成员来达到遍历的效果所以用的是struct。至于封装性别人也不敢直接访问我节点存的指针变量举个例子如果他拿到了我的节点指针ptr,访问成员用ptr-(成员名字)问题就在成员名字每个人实现的类名函数名那都是五花八门这就导致这段访问成员的代码就不具有平台移值性。
template class T struct list_node{typedef list_nodeT node; 这里记忆一下node是节点类型名的重命名后面还有很多重命名免得搞混了。list_node(const T valT())T()是一个匿名对象当我们未传对象初始化时可用一个匿名对象来初始化value:_next(nullptr), _prev(nullptr) 用初始化列表来初始化因为_val存的若是自定义类型, _val(val) 想要调用非默认构造函数得用初始化列表。 {;}node* _next;node* _prev;T _val;};
链表正向迭代器类: 不知道还记不记得string和vector的迭代器string的iterator就是char*的重命名而vector则是T*的重命名那为什么list的迭代器不能把node*直接typedef呢然后begin()函数返回哨兵位的下一个节点地址end()函数返回哨兵位节点地址。假设我们就这样实现list的迭代器然后结合下面的使用场景。
my_list::listint::iterator it l1.begin();
while (it ! l1.end())
{it;
} 大家有没有想过it到哪去了呢?是下一个节点吗?当然不是啦链表的每个节点都是孤立的你怎么能到下一个节点呢?当时我立马就想到运算符重载了在重载函数内部指针是往后走还是往前走又或者是到指针变成下一个节点地址那不都是我们实现者说了算。冷静冷静运算符重载首要原则就是操作数应该是自定义类型所有类型的指针都是内置类型所以节点指针它就没办法重载运算符所以我们要把节点指针封装成类这样我们才可以对这个类进行运算符重载使得it调用类内重载函数到下一个节点。
templateclass T,class Ref,class Ptr Ref和Ptr这两个模板参数是为了实现const迭代器struct _list_iterator 使其成员函数可在类外访问{typedef list_nodeT node;typedef _list_iteratorT,Ref,Ptr Self;_list_iterator(node* pnodenullptr)//用一个node指针初始化其成员:_node(pnode){;}//无析构函数,迭代器不能释放节点_list_iterator(const Self l)//临时对象的引用例如接受begin():_node(l._node){;}Self operator()//this指针是个迭代器类型的指针{_node _node-_next;return (*this);}Self operator(int)首先这两个运算符重载还构成函数重载编译默认给前置多传一个参数使其调用这个函数如果你把这两个函数参数换一下前置去掉int,后置加上int你就会发现前置会去调用后置的函数因为编译器还是用参数匹配或者函数名修饰规则来找函数。{Self tmp (*this);_node _node-_next;return (tmp);}Self operator--(){_node _node-_prev;return *this;}Self operator--(int){Self tmp (*this);_node _node-_prev;return tmp;} bool operator!(const Self l)//要加const因为外部可能是与end()比较{return (_node ! l._node);}bool operator(const Self l){return (_node l._node);//判断迭代器内部的node指针是否相等}因为普通迭代器就一两个成员函数的返回值不同比较简单的方法是用模板参数Ref控制返回const T还是返回TRef operator*(){return (_node-_val);//返回节点数据}//用类封装节点指针,使其可以重载,*等运算符node* _node;};
我们实现的const迭代器并不是直接对迭代器类加个const而是对特定的函数返回值做const修饰所以迭代器成员函数无需加const. -重载针对的是节点数据为自定义类型AA类型存着一个变量_val,的时候比如有一个类实例化对象为it, 我们希望重载-,使得下面的能调用到自定义类型内的变量it-_val但是it-返回的只是节点存的整个结构体A的地址我们应该用it--_val才访问到_val而且这个重载也只能返回地址如果返回的是一个结构体对象我们就要it-.(这有个点操作符)_val才能访问更加奇怪
但是当我们去测试的时候发现我们仅仅用it-_val即可访问实际上是编译器会帮我们多加一个-为了保证重载运算符的可读性只能这样改了。还有如果节点存的数据成员是内置类型我想应该是不可以用-重载的你想返回的是int*, 但-必须是指向类的。 Ptr operator-()const第三模板参数原因控制返回const T*或T*数据不可修改{return operator*(); }
反向迭代器类 针对list链表我们可以直接定义一个反向迭代器类叫reverse_iterator反向迭代器中的成员函数只有,--和正向迭代器不一样所以看完正向迭代器的成员函数也就能理解反向迭代器的成员 *解引用重载都是返回节点数据-重载都是调用operator*()重载再取地址。
namespace my_list
{templateclass iterator, class Ref, class Ptrclass reverse_iterator{public:typedef reverse_iteratoriterator, Ref, Ptr Self;reverse_iterator(iterator it):_it(it)显示调用正向迭代器的拷贝构造{;}reverse_iterator(const Self l):_it(l._it){;}Self operator() 复用正向迭代器_it的--函数{_it--;return (*this);}Self operator(int){Self tmp (*this);_it--;return (tmp);}Self operator--() 复用正向迭代器_it的函数{_it;return *this;}Self operator--(int){Self tmp (*this);_it;return tmp;}bool operator!(const Self l){return (_it ! l._it); 此处调用的是正向迭代器内部的比较}bool operator(const Self l){return (_it l._it);}Ref operator*(){iterator tmp _it;return *(--tmp);}Ptr operator-(){return operator*();}private:iterator _it;};
}链表类 我们知道目前设计的链表节点会保存前后位置的指针这意味着链表类只需要管理头节点指针即可管理所有链表节点有哨兵位则保存哨兵位地址没有则保存第一个节点的地址。
templateclass Tclass list{typedef list_nodeT node;//设为私有,不让外部通过该处访问public:typedef _list_iteratorT, T, T* iterator;//设为公有typedef _list_iteratorT, const T, const T* const_iterator;调用const迭代器就传const T和const T*控制函数返回值不被修改就达到const迭代器作用了下面这两个迭代器的typedef顺序不能改
不然可能会将reverse_iteratorconst_iterator, const T, const T*中的reverse_iterator识别为已经typedef的reverse_iteratoriterator, T, T*typedef reverse_iteratorconst_iterator, const T, const T* const_reverse_iterator;typedef reverse_iteratoriterator, T, T* reverse_iterator;reverse_iterator rbegin(){return ((reverse_iterator)end());}const_reverse_iterator rbegin() const{return (const_reverse_iterator)end();}reverse_iterator rend(){return (reverse_iterator)begin();}const_reverse_iterator rend() const{return (const_reverse_iterator)begin();}iterator begin(){return _phead-_next;//返回匿名对象}iterator end(){return _phead;}const_iterator begin()const{return _phead-_next;//返回匿名对象}const_iterator end()const 要加const要让const listT调用该函数返回const迭代器{return _phead;}void Createhead(){_phead new node;_phead-_next _phead;_phead-_prev _phead;}list(){Createhead();}list(const listT l)//list的拷贝构造{Createhead();for (auto c : l){push_back(c);}}list(size_t n, const T value T()){Createhead();while (n--){push_back(value);}}list(int n, const T value T()){Createhead();while (n--){push_back(value);}}templateclass inputiteratorlist(inputiterator first, inputiterator last) 用一段迭代器区间初始化{Createhead();while (first ! last){push_back(*first);first;}}void swap(listint lt){std::swap(_phead, lt._phead);}listT operator(listint lt)//listint可用list代替{swap(lt);return *this;}~list(){clear();delete _phead;_phead nullptr;}void clear(){iterator it begin();while (it ! end()){it erase(it);}}void push_front(const T value T()){insert(begin(), value);}void push_back(const T value T()){//node* newnode new node(value);//node* tail _phead-_prev;链接新节点,注意链接关系//tail-_next newnode;//newnode-_prev tail;//newnode-_next _phead;//_phead-_prev newnode;insert(end(), value);}iterator insert(iterator pos, const T value T()){node* newnode new node(value);node* pose pos._node;node* cur pose-_prev;cur-_next newnode;newnode-_prev cur;newnode-_next pose;pose-_prev newnode;return newnode;}void pop_back(){erase(--end());}void pop_front(){erase(begin());}size_t size()const{int n 0;iterator it begin();while (it ! end()){it;n;}return n;}bool empty()const{return size() 0;}iterator erase(iterator pos){node* pose pos._node;//迭代器it是一个类访问成员变量用.操作符pos._node pos._node-_next;node* cur pose-_prev;cur-_next pose-_next;pose-_next-_prev cur;delete pose;return pos;}private:node* _phead;};
}
上述我们封装了四个类虽然一下子不知道如何说清楚为什么要分开描述如果都挤在一起那肯定是有点冗余类本质是用来描述的个人认为一种类应该是只描述一种对象的如果一个类既描述链表节点又描述链表我感觉对于我后续的实现会很麻烦。
