List容器三大核心
迭代器类，结点类，链表类
我们在创建链表的时候，会去调用结点类，产生一个新节点，迭代器类又会运用这些结点类
进行封装模拟指针的行为
结点类
//结点类 template<class T> struct list_node { list_node<T>* _prev;//声明类型 list_node<T>* _next; T _data; list_node(const T& val = T()) //用const引用匿名对象的话会延长生命周期 :_prev(nullptr) ,_next(nullptr) ,_data(val) { } };
迭代器类
//迭代器类,其实就是对原生指针进行封装 //模拟指针 template<class T, class Ref,class Ptr > struct _list_iterator { typedef list_node<T> node; typedef _list_iterator<T,Ref,Ptr> self; //这里为什么要定义一个self呢 //这是因为后面的迭代器在++ -- //等运算的时候返回的是迭代器 node* _node; _list_iterator(node* p) :_node(p) { } Ref operator*()//我们的迭代器是可以解引用的 //得到的是data { return _node->_data; } Ptr operator->()//不重载const迭代器 { return &_node->_data; } self& operator++() { _node = _node->_next; return *this; } self& operator--() { _node = _node->_prev; return *this; } self& operator++(int) { //后置++，先用在++ self tmp(*this); _node = _node->_next; return tmp; } //加int是为了区分 //因为前置和后置的运算符一样 //语法规定加int是后置++ self& operator--(int) { //后置-- self tmp(*this); _node = _node->_prev; return tmp; } bool operator!=(const self& s) //比较的是相同类型的指针 { return _node != s._node; } bool operator==(const self& s) { return _node == s._node; } };
这里我们的Ref代表的是引用类型，Ptr是代表指针类型
链表类
//list源码本身是一个带头双向循环链表 //但是list的核心还有一个是迭代器的封装，迭代器类 template<class T> class list { typedef list_node<T> node; //这里其实就已经声明了结点类的类型了 //对结点类的模板的结点类型重命名 public: typedef _list_iterator<T,T&,T*> iterator; //这里其实就已经声明了结点类的类型了 //对迭代器类的模板的迭代器类型重命名 /*typedef const _list_iterator const_iterator;*/ //对const迭代器类的模板的迭代器类型重命名 //但是这是错误的，因为我们这是修饰的是迭代器不能修改 typedef _list_iterator<T, const T&, const T*> const_iterator; iterator begin() { return iterator(_head->_next); } const_iterator begin() const { return const_iterator(_head->_next); } iterator end() //指向尾部节点的下一个节点 //那么就是头结点 { return iterator(_head); } const_iterator end() const //const对象返回const迭代器 { return const_iterator(_head); } //迭代器区间构造list //函数模板 template<class iterator> list(iterator first,iterator last) { empty_init(); while (first != last)//重载了迭代器 { push_back(*first); ++first; } } list() //无参构造 { //指向自己 /*_head = new node; _head->_next = _head; _head->_prev = _head;*/ empty_init(); } void swap(list<T>& tmp) { std::swap(_head,tmp->_head); } //拷贝构造 list(const list<T>& it) { empty_init(); list<T> tmp(it.begin(),it.end()); swap(tmp); } //重载list链表运算符= list<T>& operator=(list<T> val) //传值，我们不改变他，不过这里传值的时候 //去调用了拷贝构造，而我们的节点都是new出来的 //其实这就说明了我们的传值过来数据已经在堆上了 //所以要注意 //但是因为已经创建好了对象，那么可以把头结点 //连接到新链表上 { swap(val); return *this; } void empty_init() { _head = new node; _head->_next = _head; _head->_prev = _head; } void push_back(const T& val) { /*node* tail = _head->prev; node* new_node = new node; tail->next = new_node; new_node->prev = tail new_node->next = _head; _head->prev = new_node;*/ insert(end(),val); } void push_front(const T& val) { insert(begin(),val); } void pop_back() { erase(--end()); } void pop_front() { erase(begin()); } void insert(iterator pos, const T& val) //用迭代器进行插入 //在pos位置之前插入,需要存下地址 { node* cur = pos._node; node* prev = cur->_prev;//找到pos位置之前的节点 node* new_node = new node(val); prev->_next = new_node; new_node->_prev = prev; new_node->_next = cur; cur->_prev = new_node; } void erase(iterator pos) //删除pos位置的节点 { assert(pos != end()); node* cur = pos._node;//节点类是在封装迭代器类里 node* prev = pos._node->_prev; node* next = pos._node->_next; prev->_next = next; next->_prev = prev; delete cur; } ~list() { clear(); delete _head; _head = nullptr; } void clear() //不用const //const的对象的const的迭代器 //指的是迭代器里的内容不能修改 //也就不能去释放 { iterator it = begin(); while (it != end()) { erase(it++); } } void print_list() { node* cur = _head; while (cur->_next != _head) { std::cout << cur->_next->_data<<" "; cur = cur->_next; } std::cout << std::endl; } private: node* _head; }; }
整体
template<class T> struct list_node { list_node<T>* _prev;//声明类型 list_node<T>* _next; T _data; list_node(const T& val = T()) //用const引用匿名对象的话会延长生命周期 :_prev(nullptr) ,_next(nullptr) ,_data(val) { } }; //迭代器类,其实就是对原生指针进行封装 //模拟指针 template<class T, class Ref,class Ptr > struct _list_iterator { typedef list_node<T> node; typedef _list_iterator<T,Ref,Ptr> self; //这里为什么要定义一个self呢 //这是因为后面的迭代器在++ -- //等运算的时候返回的是迭代器 node* _node; _list_iterator(node* p) :_node(p) { } Ref operator*()//我们的迭代器是可以解引用的 //得到的是data { return _node->_data; } Ptr operator->()//不重载const迭代器 { return &_node->_data; } self& operator++() { _node = _node->_next; return *this; } self& operator--() { _node = _node->_prev; return *this; } self& operator++(int) { //后置++，先用在++ self tmp(*this); _node = _node->_next; return tmp; } //加int是为了区分 //因为前置和后置的运算符一样 //语法规定加int是后置++ self& operator--(int) { //后置-- self tmp(*this); _node = _node->_prev; return tmp; } bool operator!=(const self& s) //比较的是相同类型的指针 { return _node != s._node; } bool operator==(const self& s) { return _node == s._node; } }; //list源码本身是一个带头双向循环链表 //但是list的核心还有一个是迭代器的封装，迭代器类 template<class T> class list { typedef list_node<T> node; //这里其实就已经声明了结点类的类型了 //对结点类的模板的结点类型重命名 public: typedef _list_iterator<T,T&,T*> iterator; //这里其实就已经声明了结点类的类型了 //对迭代器类的模板的迭代器类型重命名 /*typedef const _list_iterator const_iterator;*/ //对const迭代器类的模板的迭代器类型重命名 //但是这是错误的，因为我们这是修饰的是迭代器不能修改 typedef _list_iterator<T, const T&, const T*> const_iterator; iterator begin() { return iterator(_head->_next); } const_iterator begin() const { return const_iterator(_head->_next); } iterator end() //指向尾部节点的下一个节点 //那么就是头结点 { return iterator(_head); } const_iterator end() const //const对象返回const迭代器 { return const_iterator(_head); } //迭代器区间构造list //函数模板 template<class iterator> list(iterator first,iterator last) { empty_init(); while (first != last)//重载了迭代器 { push_back(*first); ++first; } } list() //无参构造 { //指向自己 /*_head = new node; _head->_next = _head; _head->_prev = _head;*/ empty_init(); } void swap(list<T>& tmp) { std::swap(_head,tmp->_head); } //拷贝构造 list(const list<T>& it) { empty_init(); list<T> tmp(it.begin(),it.end()); swap(tmp); } //重载list链表运算符= list<T>& operator=(list<T> val) //传值，我们不改变他，不过这里传值的时候 //去调用了拷贝构造，而我们的节点都是new出来的 //其实这就说明了我们的传值过来数据已经在堆上了 //所以要注意 //但是因为已经创建好了对象，那么可以把头结点 //连接到新链表上 { swap(val); return *this; } void empty_init() { _head = new node; _head->_next = _head; _head->_prev = _head; } void push_back(const T& val) { /*node* tail = _head->prev; node* new_node = new node; tail->next = new_node; new_node->prev = tail new_node->next = _head; _head->prev = new_node;*/ insert(end(),val); } void push_front(const T& val) { insert(begin(),val); } void pop_back() { erase(--end()); } void pop_front() { erase(begin()); } void insert(iterator pos, const T& val) //用迭代器进行插入 //在pos位置之前插入,需要存下地址 { node* cur = pos._node; node* prev = cur->_prev;//找到pos位置之前的节点 node* new_node = new node(val); prev->_next = new_node; new_node->_prev = prev; new_node->_next = cur; cur->_prev = new_node; } void erase(iterator pos) //删除pos位置的节点 { assert(pos != end()); node* cur = pos._node;//节点类是在封装迭代器类里 node* prev = pos._node->_prev; node* next = pos._node->_next; prev->_next = next; next->_prev = prev; delete cur; } ~list() { clear(); delete _head; _head = nullptr; } void clear() //不用const //const的对象的const的迭代器 //指的是迭代器里的内容不能修改 //也就不能去释放 { iterator it = begin(); while (it != end()) { erase(it++); } } void print_list() { node* cur = _head; while (cur->_next != _head) { std::cout << cur->_next->_data<<" "; cur = cur->_next; } std::cout << std::endl; } private: node* _head; }; }
