?个人主页:秦jh_-CSDN博客
? 系列专栏:https://blog.csdn.net/qinjh_/category_12575764.html?spm=1001.2014.3001.5482
目录
前言
list的常见接口
对迭代器的封装
节点
重载->
const迭代器
list与vector的对比
反向迭代器
反向迭代器完整代码
list完整代码
前言
? hello! 各位铁子们大家好哇。
今日更新了list的相关内容
? 欢迎大家关注?点赞?收藏⭐️留言?
list的底层是双向链表结构,双向链表中每个元素存储在互不相关的独立节点中,在节点中通过指针指向其前一个元素和后一个元素。
list的常见接口
对迭代器的封装
因为list的空间不是连续的,不能用原生指针,必须对其进行封装。
节点
重载->
当数据是自定义类型时,想通过->访问,就必须重载。
const迭代器
用const迭代器,需要重新弄一个类,而const迭代器跟普通迭代器基本一样,只修改了部分,如果为此就重新弄一个类,代码就太冗余了。
下面是进行的优化:
本质相当于写了一个类模板,编译器实例化生成了两个类。
list与vector的对比
反向迭代器
反向迭代器的++就是正向迭代器的--,反向迭代器的--就是正向迭代器的++,因此反向迭代器的实现可以借助正向迭代器,即:反向迭代器内部可以包含一个正向迭代器,对正向迭代器的接口进行 包装即可。
反向迭代器完整代码
#pragma once //所以容器的反向迭代器//迭代器适配器namespace qjh{//vector<T>::iteratortemplate<class Iterator,class Ref,class Ptr> //给谁的正向迭代器,就适配出对应的反向迭代器struct ReverseIterator {typedef ReverseIterator<Iterator, Ref, Ptr> Self;Iterator _it;ReverseIterator(Iterator it):_it(it){}Ref operator*(){Iterator tmp = _it; //不能修改_it,得用临时变量放回return *(--tmp);}Ptr operator->(){//return _it->;//return _it.operator->();return &(operator*());}Self& operator++(){--_it;return *this;}Self& operator--(){++_it;return *this;}bool operator!=(const Self& s){return _it != s._it;}};}
list完整代码
#pragma once#include<assert.h>#include"ReverseIterator.h"namespace qjh{template<class T>struct ListNode //需要全部被公开,用struct{ListNode<T>* _next;ListNode<T>* _prev;T _data;ListNode(const T& x=T()):_next(nullptr),_prev(nullptr),_data(x){}};template<class T,class Ref,class Ptr>struct ListIterator //对指针进行封装,因为结点的空间不是连续的{typedef ListNode<T> Node;typedef ListIterator<T,Ref,Ptr> Self; Node* _node;ListIterator(Node* node):_node(node){}//*it//T& operator*()Ref operator*(){ return _node->_data;}//T* operator->()Ptr operator->(){return&_node->_data;}//++itSelf& operator++(){_node = _node->_next;return *this;}//it++Self& operator++(int){Self tmp(*this);_node = _node->_next;return tmp;}//--itSelf& operator--(){_node = _node->_prev;return *this;}//it--Self& operator--(int){Self tmp(*this);_node = _node->_prev;return tmp;}bool operator!=(const Self& it){return _node != it._node;}bool operator==(const Self& it){return _node == it._node;}};//template<class T>//struct ListConstIterator //对指针进行封装,因为结点的空间不是连续的//{//typedef ListNode<T> Node;//typedef ListConstIterator<T> Self;//Node* _node;//ListConstIterator(Node* node)//:_node(node)//{}////*it//const T& operator*()//{//return _node->_data;//}//const T* operator->()//{//return&_node->_data;//}////++it//Self& operator++()//{//_node = _node->_next;//return *this;//}////it++//Self& operator++(int)//{//Self tmp(*this);//_node = _node->_next;//return tmp;//}////--it//Self& operator--()//{//_node = _node->_prev;//return *this;//}////it--//Self& operator--(int)//{//Self tmp(*this);//_node = _node->_prev;//return tmp;//}//bool operator!=(const Self& it)//{//return _node != it._node;//}//bool operator==(const Self& it)//{//return _node == it._node;//}//};template<class T>class list{typedef ListNode<T> Node;public:/*typedef ListIterator<T> iterator;typedef ListConstIterator<T> const_iterator;*/typedef ListIterator<T,T&,T*> iterator;typedef ListIterator<T,const T&,const T*> const_iterator;typedef ReverseIterator<iterator, T&, T*> reverse_iterator;typedef ReverseIterator<const_iterator, const T&, const T*> const_reverse_iterator;reverse_iterator rbegin(){return reverse_iterator(end());}reverse_iterator rend(){return reverse_iterator(begin());}iterator begin(){return iterator(_head->_next);}iterator end(){return iterator(_head);}//const迭代器需要迭代器指向的内容不能修改!const iterator不是我们需要的const迭代器//const 迭代器本身可以++等操作const_iterator begin() const{return const_iterator(_head->_next);}const_iterator end() const{return const_iterator(_head);}void empty_init(){_head = new Node;_head->_next = _head;_head->_prev = _head;_size = 0;}list(){empty_init();}list(initializer_list<int> il){empty_init();for (auto& e : il){push_back(e);}}//lt2(lt1)list(const list<T>& lt){empty_init();for (auto& e : lt){push_back(e);}}void swap(list<T>& lt){std::swap(_head, lt._head);std::swap(_size, lt._size);}//lt1=lt3list<T>& operator=(list<T> lt){swap(lt);return *this;}void clear(){iterator it = begin();while (it != end()){it = erase(it);}}~list(){clear();delete _head;_head = nullptr;}//void push_back(const T& x)//{//Node* newnode = new Node(x);//Node* tail = _head->_prev;//tail->_next = newnode;//newnode->_prev = tail;//newnode->_next = _head;//_head->_prev = newnode;//}void push_back(const T& x){insert(end(), x);}void push_front(const T& x){insert(begin(), x);}void pop_back(){erase(--end());//迭代器不能-1,只能用-- }void pop_front(){erase(begin());}void insert(iterator pos, const T& val){Node* cur = pos._node;Node* newnode = new Node(val);Node* prev = cur->_prev;prev->_next = newnode;newnode->_prev = prev;newnode->_next = cur;cur->_prev = newnode;_size++;}iterator erase(iterator pos) //节点失效了,需要返回下一个节点{Node* cur = pos._node;Node* prev = cur->_prev;Node* next = cur->_next;prev->_next = next;next->_prev = prev;delete cur;_size--;return iterator(next); //匿名对象}size_t size() const{return _size;}bool empty(){return _size == 0;}private:Node* _head;size_t _size;};void test_list1(){list<int> lt;lt.push_back(1);lt.push_back(2);lt.push_back(3);lt.push_back(4);lt.push_back(5);list<int>::iterator it = lt.begin();while (it != lt.end()){cout << *it << " ";++it;}cout << endl;lt.push_front(10);lt.push_front(20);lt.push_front(30);for (auto e : lt){cout << e << " ";}cout << endl;lt.pop_back();lt.pop_back();lt.pop_front();lt.pop_front();for (auto e : lt){cout << e << " ";}cout << endl;}struct A{int _a1;int _a2;A(int a1 = 0, int a2 = 0):_a1(a1),_a2(a2){}}; void test_list2(){list<A> lt;A aa1(1, 1);A aa2 = { 1, 1 };lt.push_back(aa1);lt.push_back(aa2);lt.push_back(A(2,2));lt.push_back({3,3});lt.push_back({4,4});list<A>::iterator it = lt.begin();while (it != lt.end()){ //cout << (*it)._a1 << ":" << (*it)._a2 << endl;//cout << it->_a1 << ":" << it->_a2 << endl; //如果要遍历自定义类型,就要重载->,编译器为了可读性,省略了一个->cout << it.operator->()->_a1 << ":" << it.operator->()->_a2 << endl;++it;}cout << endl;}void PrintList(const list<int>& clt){list<int>::const_iterator it = clt.begin();while (it != clt.end()){//*it += 10; cout << *it << " ";++it;}cout << endl;}void test_list3(){list<int> lt;lt.push_back(1);lt.push_back(2);lt.push_back(3);lt.push_back(4);lt.push_back(5);PrintList(lt);list<int> lt1(lt);PrintList(lt1);}}