一、list的概念引入
1.vector与list的对比
为什么会有list?
补充vector的缺点存在的
vector缺点:
1.头部和中部的插入删除效率低,O(N)因为需要挪动数据。
2.插入数据空间不够需要增容。增容需要开新空间、拷贝数据、会付出很大的代价。
优点:
1、支持下标的随机访问。间接的就很好的支持排序、二分查找、堆算法等等。
list出厂就是为了解决vector的缺陷
优点:
1.list头部、中间插入不再需要挪动数据,效率高。O(1)
2.list插入数据是新增节点,不需要增容
缺点:
不支持随机访问。
2.关于struct和class的使用
C++中的struct和class的唯一区别在于默认访问权限(即你不写public、private这种访问限定符)不同,struct默认为共有(public),而class默认为私有(private),一般情况,成员部分私有,部分公有,就用class,所有成员都开放或共有,就用struct
所以下文写的节点和迭代器类都用struct是因为,struct中的成员函数都默认为公有理,也不用写public了,但是你用class就要写个public
3.list的迭代器失效问题
list本质:带头双向循环链表
支持操作接口的角度分迭代器的类型:单向(forward_list)、双向(list)、随机(vector)
从使用场景的角度分迭代器的类型:(正向迭代器、反向迭代器)+const迭代器
二、list的模拟实现
1.list三个基本函数类
list本质是一个带头双向循环链表:
模拟实现list,要实现下列三个类
1) 模拟实现结点类
2) 模拟实现迭代器的类
3) 模拟实现list主要功能的类
list的类的模拟实现其基本功能(增删等操作)要建立在迭代器类和节点类均已实现好的情况下才得以完成。
2.list的结点类实现
因为list的本质为带头双向循环链表,所以其每个结点都要确保有下列成员:
1.前驱指针
2.后继指针
3.data值存放数据
而结点类的内部只需要实现一个构造函数即可。
template<class T> struct _list_node { listnode<T>* _next; listnode<T>* _prev; T _data; listnode(const T& val=T()) :_next(nullptr) ,_prev(nullptr) ,_data(val) {} };
为什么是_list_node<T>?
首先,C++中用struct定义是可不加struct,重点是这里用了一个类模板,类模板的类名不是真正的类型且类模板不支持自动推类型,即_list_node不是真正的类型,定义变量时,_list_node<T>这种才是真正的类型,也就是用类模板定义变量时必须指定对应的类型。
注:结构体模板或类模板在定义时可不加<T>,但使用时必须加<T>。
3.list的迭代器类的实现
因为list其本质就是带头双向循环链表,而链表的物理空间是不连续的,是通过结点的指针顺次链接,我们不能向先前的string和vector一样直接解引用还是结点,结点指针++还是结点指针,而string和vector的物理空间是连续的,所以这俩不需要实现迭代器类,可以直接使用。
为了能让list像vector一样接应用后访问对应节点中的值,++访问到下一个数据,我们需要单独写一个迭代器类的接口实现,在其内部进行封装补齐相应的功能,而这就要借助运算符重载来完成。
注:迭代器封装后是想模拟指针的行为
3.1 基本框架
template<class T,class Ref,class Ptr> struct _list_iterator { typedef _list_node<T> Node; typedef _list_iterator<T, Ref, Ptr>Self; Node* _node; };
1)迭代器类模板为什么要三个参数?
若只有普通迭代器的话,一个class T参数就够了,但因为有const迭代器原因,需要加两个参数,两个参数明Ref(reference:引用)和Ptr(pointer:指针),名字怎么起都行,但这种有意义的名字很推荐的,即这两个参数一个让你传引用,一个让你传指针,具体等到下文讲到const迭代器再说
2)迭代器类到底是什么?
迭代器类就是一个结点的指针变量_node,但是因为我们要运算符重载等一些列操作,不得不把迭代器写成类,完成哪些操作,list的迭代器才能正确的++到下一个位置,解引用访问节点的值。
3)结点指针和迭代器的区别?
当他们都指向同一个结点,那么在物理内存中他们都存的是这个结点地址,物理上是一样的,但是他们的类型不一样,他们的意义就不一样。比如*cur是一个指针的解引用,取到的值是结点;*it是去调用迭代器中“ * ”的运算符重载operator*,返回值是结点中存的值。
类型决定了对空间的解释权
3.2 构造函数
_list_iterator(Node* node) :_node(node) {}
3.3 operator*
Ref operator*() { return _node->_data; }
1)返回值为什么是Ref?
Ref是模板参数,因为迭代器类的模板参数Ref传入的要么是T&,要么是const T&,就是为了const迭代器和普通迭代器的同时实现,底层就是这么实现的,意义就是一个只读,一个可读可写
注:比如之前讲的vector的迭代器,*it(假设it是迭代器变量)就是拿到对应的值,那么list的迭代器也要同理,解引用迭代器就是为了访问对应位置的值,那么list只要通过迭代器返回对应结点的值就好了。
3.4 operator->
Ptr operator->() { return &_node->_data; }
1)为什么需要operator->?
本质因为自定义类型需要,那需从list存的类型是个自定义类型说起,以Date类说明。若list存了个自定义类型的Date类,就无法打印,因为我们并没有重载Date类的operator<<,若是内置类型的话才可以正常输出,那写一个operator<<重载吗?不,因为你无法确定要用那些类,也不能每个类都写operator<<,怎么半?我们访问Date类本质是想访问它内置类型(int)的_year,_month,_day吧,那我们不妨写个专属于自定义类型的operator-> (因为内置类型只需要*it就可以直接输出了,但自定义类型不可以直接输出),利用operator->直接访问类的成员变量,而内置类型可以直接输出
故从根源上解决问题:在迭代器中实现个operator->:
(Ptr是迭代器的模板参数,我们用来作为T*或const T*的)
3.5 operator前置++和后置++和--
Self& operator++() { _node = _node->_next; return *this; } Self operator++(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; }
1)迭代器++对于list是什么意思?
迭代器++的意思就是想让其指向下一个节点,--正好相反,为了区分前置和后置++(--),我们会用函数重载,也就是多一个“没用的”参数:int,这个参数没什么用,只是为了区分++和--
3.6 operator==与operator!=
bool operator!=(const Self& it) { return _node != it._node; } bool operator==(const Self& it) { return _node == it._node; }
两个迭代器怎么比较的?
迭代器中就一个成员变量_node,结点指针,只要比较当前结点指针是否相同即可,这个操作在判断迭代器是否走到头有用。
问题:迭代器的拷贝构造、赋值和析构函数需要我们实现吗?
答:不需要
因为迭代器存的就是一个节点指针,而节点是属于链表list的,那么它的释放应有list来实现,那么迭代器的析构也无需我们自己写了。总而言之,迭代器并不涉及从堆上开空间,使用系统提供的浅拷贝就可以了。
4、list类的实现
在节点类和迭代器类都实现的前提下,就可实现list主要功能:增删等操作的实现
4.1 基本框架
template<class T> class list { typedef _list_node<T> Node; public: typedef _list_iterator<T, T&, T*>iterator; typedef _list_iterator<T, const T&, const T*> const_iterator; private: Node* _head; };
const_iterator(const迭代器的介绍)
我们知道const_iterator在begin()和end()中的返回值是需要用到的,其主要作用就是当迭代器只读时使用,因为普通迭代器和const迭代器的实现区别仅仅在于成员函数的返回值不同,难道重写一遍吗?不用,我们模板参数多两个就好了,一个是引用class Ref(T&或const T&),一个是指针class Ptr(T*或const T*),当Ref时const T&就是const迭代器的调用,这就利用模板实现了两个迭代器的同时实现。
4.2 构造函数
list() { _head = new Node; _Head->_next = _head; _head->_prev = _head; }
我们开辟一个头结点,然后使其处于一个对应的初始状态即可。
4.3 begin()和end()
iterator begin() { //第一个位置应该是头节点的下一个节点 return iterator(head->_next);//用匿名对象构造iterator类型的 } iterator end() { return iterator(_head); } const_iterator begin()const { return const_iterator(head->next); } const_iterator end()const { return const_iterator(_head); }
1)关于匿名构造的理解
比如iterator(_head->next);iterator是一个类模板类型(它被typedef过),那不应该实例化一个对象再构造吗?这里没有用是因为这里是匿名对象的构造,这里这么用比较方便。
4.4拷贝构造
list(const list<T>& It) { _head = new Node; _head->_next = _head; _head->_prev = _head; for (auto e : lt) { push_back(e); } }
解释:list的拷贝构造跟vector不同,它的拷贝是拷贝一个个节点(因为不连续的物理空间),那么我们可以用迭代器拿到list的一个个节点【上面是传统写法】
现代写法:
template<class Inputerator> list(Inputerator first, Inputerator last) { _pHead = new Node(); _pHead->next = _pHead; _pHead->prev = _pHead; while (first != last) { push_back(*first); first++; } } //拷贝构造(现代写法) list(const list<T>& L) { _pHead = new Node(); _pHead->next = _pHead; _pHead->prev = _pHead; list<T> tmp(L.begin(), L.end()); swap(_pHead, tmp._pHead); }
1)为什么有的拷贝构造需要初始化,operator=不需要?
以string 的模板实现为例
4.5 clear
void clear() { iterator it = begin(); while (it != end()) { it = erase(it); } }
1) it=erase(it)什么意思
防止迭代器失效,因为erase返回的是被删除位置的下一个位置,比如删除pos位置的,pos位置被删除后,这个位置的迭代器就失效了,那就无法通过++找到后面的位置了,所以我们通过erase返回值来更新一下迭代器位置,即更新到被删除位置的下一个位置
4.6 operator=
list<T>& operator=(list<T> lt) { swap(_head, lt._head); return *this; }
4.7 析构函数
~list() { clear(); delete _head; _head = nullptr; }
4.8 insert
iterator insert(iterator pos, const T& x) { Node* newnode = new Node(x); //找到pos位置的指针和pos之前的指针 Node* cur = pos._node; Node* prev = cur->_prev; //prev newnode cur prev->_next = newnode; newnode->_prev = prev; newnode->_next = cur; cur->_prev = newnode; //返回新插入元素的迭代器位置 return iterator(newnode); }
1)返回参数为什么是iterator?
本质是为了防止迭代器失效问题
注:insert指的是插入到指定位置的前面
4.9 push_back和push_front
void push_back(const T& x) { Node* tail = head->prev; Node* newnode = new Node(x); tail->_next = newnode; newnode->_prev = tail; newnode->_next = _head; _head->_prev = newnode; }
4.10 erase
iterator erase(iterator pos) { assert(pos != end()) { Node* cur = pos._node; Node* prev = cur->_prev; NOde* next = cur->_next; prev->_next = next; next->_prev = prev; delete cur; return iterator(next); } }
返回值问题
erase的返回值,返回的是被删除位置的下一个位置,库里面这么规定,本质是因为删除元素一定会导致此位置的迭代器失效,故返回被删除位置的下一个位置可以更新迭代器
4.11pop_back和pop_front
void pop_back() { erase(--end()); } void pop_front() { erase(begin()); }
三、源代码
#pragma once #include <iostream> using namespace std; namespace lf { template <class T> struct listNode { T Data; listNode<T>* _next; listNode<T>* _prev; listNode(const T& val = T()) :Data(val) ,_next(nullptr) ,_prev(nullptr) {} }; template <class T,class Ref,class Ptr> struct list_Iterator { typedef listNode<T> node; typedef list_Iterator<T, Ref, Ptr> Self; node* _node; list_Iterator(node* node) :_node(node) {} Ref operator*() { return _node->Data; } Ptr operator->() { return &_node->Data; } Self operator++() { _node = _node->_next; return *this; } Self operator++(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& it)const { return _node != it._node; } bool operator==(const Self& it)const { return _node == it._node; } }; template <class T> class list { typedef listNode<T> node; public: typedef list_Iterator<T, T&, T*> iterator; typedef list_Iterator<T, const T&, const T*> const_iterator; iterator begin() { return iterator(_head->_next); } iterator end() { return iterator(_head); } 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; } list() { empty_init(); } list(const list<T>& lt) { empty_init(); for (auto e : lt) { push_back(e); } } ~list() { clear(); delete _head; _head = nullptr; } list<T>& operator=(list<T> lt) { swap(_head, lt._head); return *this; } void clear() { iterator it = begin(); while (it != end()) { it = erase(it); } } // prev head next 2 head 1 iterator erase(iterator pos) { node* cur = pos._node; node* prev = cur->_prev; node* next = cur->_next; prev->_next = next; next->_prev = prev; delete cur; cur = nullptr; return iterator(next); } // 1 2 newnode head void insert(iterator pos,const T& val) { node* newnode = new node(val); node* cur = pos._node; node* prev = cur->_prev; newnode->_next = cur; cur->_prev = newnode; prev->_next = newnode; newnode->_prev = prev; } void push_back(T val) { insert(end(), val); } void pop_back() { erase(--end()); } private: node* _head; }; void test_list1() { list<int> lt1; list<int>::iterator it = lt1.begin(); lt1.insert(it, 1); lt1.push_back(2); lt1.push_back(3); //lt1.pop_back(); list<int>::iterator it1 = lt1.end(); //lt1.erase(--it1); /*for (auto _begin = lt1.begin(), _end = lt1.end(); _begin != _end; ++_begin) { cout << *_begin << " "; }*/ lt1.clear(); for (auto e : lt1) { cout << e << " "; } //cout << *it << endl; } void test_list2() { list<int> lt; lt.push_back(1); lt.push_back(2); lt.push_back(3); list<int> lt1(lt); lt.push_back(4); lt.push_back(5); lt.push_back(6); lt.push_back(7); lt1 = lt; lt.operator=(lt1); for (auto e : lt) { cout << e << " "; } cout << endl; for (auto e : lt1) { cout << e << " "; } cout << endl; } };