list的介绍
- list是可以在常数范围内在任意位置进行插入和删除的序列式容器，并且该容器可以前后双向迭代。
- list的底层是用双向链表实现的（线性），每个元素都存在相互独立的节点中，每个节点都有一个指针分别指向前一个节点和后一个节点。
- 因为底层结构是链表，list的插入和删除操作是非常高效的，这与vector容器相反。但是由于链表的结构特点，list的各个节点之间的物理地址是不连续的，也就导致了任意访问某个节点的效率较低。
- list的空间消耗会比vector大（存储相同个数的元素），因为每个节点还需要给前后指针开空间。
list的整体结构设计
list可以分为三部分：一个是list类本身，一个是节点类，一个是迭代器类。
list类的成员变量一般只有头节点（哨兵），除了负责初始化以外还负责声明和定义插入删除功能。
ListNode节点类封装了list的元素以及前后节点的指针，还负责new出节点时的初始化。
Iterator迭代器类封装了指向节点的指针ListNode*,还负责重载++、–、！=等运算符。为什么要在迭代器内部重载呢？
跟vector不同的是，由于list迭代器指向的是一个节点，且节点间物理地址不连续，向前移动或者向后移动都不能用指针直接去加减。
list的节点类
// List的节点类 template<class T> struct ListNode { ListNode(const T& val = T()); ListNode<T>* _pPre; ListNode<T>* _pNext; T _val; };
list的迭代器类
template<class T, class Ref, class Ptr> class ListIterator { typedef ListNode<T>* PNode; typedef ListIterator<T, Ref, Ptr> Self; public: ListIterator(PNode pNode = nullptr); ListIterator(const Self& l); T& operator*(); T* operator->(); Self& operator++(); Self operator++(int); Self& operator--(); Self& operator--(int); bool operator!=(const Self& l); bool operator==(const Self& l); private: PNode _pNode; };
list类
template<class T> class list { typedef ListNode<T> Node; typedef Node* PNode; public: typedef ListIterator<T, T&, T*> iterator; typedef ListIterator<T, const T&, const T&> const_iterator; public: /// // List的构造 list(); list(int n, const T& value = T()); template <class Iterator> list(Iterator first, Iterator last); list(const list<T>& l); list<T>& operator=(const list<T> l); ~list(); /// // List Iterator iterator begin(); iterator end(); const_iterator begin(); const_iterator end(); /// // List Capacity size_t size()const; bool empty()const; };
list的构造
list有四个构造函数：无参构造、拷贝构造、连续赋值构造、迭代器构造。
//构造的list中包含n个值为val的元素 list (size_type n, const value_type& val = value_type()) //构造空的list，初始化哨兵节点 list() //拷贝构造 list (const list& x) //用[first, last)区间中的元素构造list list (InputIterator first, InputIterator last)
代码模拟实现：
void Empty_Init() { head = new Node; head->_pre = head; head->_next = head; head->_val = -1; sz = 0; } //构造 list() { Empty_Init(); } list(size_t n, const T& value = T()) { Empty_Init(); for (size_t i = 0; i < n; i++) { push_back(value); } sz = n; } //拷贝构造 list(const list<T>& lt) { Empty_Init(); for (auto& it : lt) { push_back(it); } } //迭代器构造 template <class IIterator> list(IIterator first, IIterator last) { Empty_Init(); while (first != last) { push_back(*first); first++; } }
list节点类的实现
节点类的成员变量就是前后指针以及节点的元素值。此外还需注意构造节点时的初始化工作。
template<class T> class ListNode { public: ListNode(const T& val = T()) :_val(val) , _pre(nullptr) , _next(nullptr) { } ListNode<T>* _pre; ListNode<T>* _next; T _val; };
list 迭代器Iterator的使用以及实现
Iterator的使用
在上面iterator类的声明中我们可以看到，不同的容器其迭代器的实现方式是不一样的。在string和vector中的iterator本质是一个指针。但是list的迭代器是一个像指针的类。
//返回第一个元素或最后一个的迭代器 begin() end() //rbegin返回第一个元素的reverse_iterator,即end位置，rend返回最后一个元素下一个位置的 //reverse_iterator,即begin位置 rbegin() rend()
- begin与end为正向迭代器，对迭代器执行++操作，迭代器向后移动
- rbegin(end)与rend(begin)为反向迭代器，对迭代器执行++操作，迭代器向前移动
代码演示：
Iterator的底层实现
先实现一个正向的迭代器类。因为涉及到存在const修饰迭代器指向的节点，所以在设计迭代器的时候需要同时设计出const版本（const是修饰节点，不是迭代器本身）。这里我们可以使用模板，模板里面有三个类型：节点数据类型、引用类型、指针类型。
值得注意的是，由于我们需要在迭代器类里访问节点Node类型的成员变量，所以可以将Iterator设为Node类的友元类，或者开放Node类的权限。
迭代器的构造函数的实现：
ListIterator(Node* node) :_node(node) {}
我这里设计的比较简单，只实现了单参的构造函数，可以支持基本的隐式类型转换。
重载*:
Ref operator* () { return _node->_val; }
重载迭代器的移动操作符++、--:
Self& operator++() { _node = _node->_next; return *this; } Self& operator++(int) {//后置++ Self temp(*this); _node = _node->_next; return temp; } Self& operator--() { _node = _node->_pre; return *this; } Self& operator--(int) {//后置-- Self temp(_node); _node = _node->_pre; return temp; }
重载->：
Ptr operator ->() { return &_node->_val; }
由于我们想把迭代器当指针使用，重载->是必要的，那么为什么是返回节点元素的地址呢？其实当我们在使用迭代器->时，编译器会自动优化成->->。比如我们的节点元素类型是一个类，我们有时需要访问节点元素类中的成员变量，此时希望通过迭代器->能直接访问到。
观察以下代码：
其中t是一个结构体类型，当我们用list存这样的节点并试图遍历节点中的a1的值时，(*it)得到的是t类型，如果我们想要输出t中的a1，就必须写成（*it）.a1。
我们希望迭代器能像指针一样，it->a1这样就能直接访问a1的元素，于是我们重载一个->,这个->的作用其实等价于it->->a1也就是it.operator->()->a1。这是编译器帮我们优化了。
反向迭代器
方向迭代器和普通的迭代器功能基本一致，只不过由于起始位置是在哨兵位，解引用时需要先往前面移动一个节点再返回其节点元素值
Ref operator* () { Self temp(_node); temp++; return temp._node->_val; }
此外移动的方向也和普通迭代器相反，是向节点的前一个节点方向移动。
Self& operator--() { _node = _node->_next; return *this; } Self& operator--(int) {//后置-- Self temp(*this); _node = _node->_next; return temp; } Self& operator++() { _node = _node->_pre; return *this; } Self& operator++(int) {//后置++ Self temp(_node); _node = _node->_pre; return temp; }
其它功能和普通迭代器几乎一致。
list与vector的比较
list和vector各种代表着的是链表和数组。它们之间的具体区别其实在前面已经讲过了。
链表的优缺点
顺序表的优缺点
迭代器的区别：
vector的迭代器是原生态指针，list的迭代器是对原生态指针(节点指针)进行封装。
vector在插入元素时，要给所有的迭代器重新赋值，因为插入元素有可能会导致重新扩容，致使原来迭代器失效，删除时，当前迭代器需要重新赋值否则会失效。
而list插入元素不会导致迭代器失效，删除元素时，只会导致当前迭代器失效，其他迭代器不受影响
实现list类
#define _CRT_SECURE_NO_WARNINGS 1 #include<assert.h> #include<iostream> namespace bite { //节点 template<class T> class ListNode { public: ListNode(const T& val = T()) :_val(val) , _pre(nullptr) , _next(nullptr) { } ListNode<T>* _pre; ListNode<T>* _next; T _val; }; //反向迭代器 template<class T, class Ref, class Ptr> class ReserveListIterator { public: typedef ListNode<T> Node; typedef ReserveListIterator<T, Ref, Ptr> Self; ReserveListIterator(Node* node) :_node(node) {} //重载 Ref operator* () { Self temp(_node); temp++; return temp._node->_val; } Self& operator--() { _node = _node->_next; return *this; } Self& operator--(int) {//后置-- Self temp(*this); _node = _node->_next; return temp; } Self& operator++() { _node = _node->_pre; return *this; } Self& operator++(int) {//后置++ Self temp(_node); _node = _node->_pre; return temp; } bool operator!=(const Self& p) { return _node != p._node; } //T*/const T* Ptr operator ->() { return &_node->_val; } bool operator==(const Self& p) { return _node == p._node; } Node* _node; }; //迭代器 template<class T, class Ref, class Ptr>//T表示节点数据类型，Ref表示T&、Ptr表示T*类型 class ListIterator { public: typedef ListNode<T> Node; typedef ListIterator<T, Ref, Ptr> Self; ListIterator(Node* node) :_node(node) {} //重载 Ref operator* () { return _node->_val; } Self& operator++() { _node = _node->_next; return *this; } Self& operator++(int) {//后置++ Self temp(*this); _node = _node->_next; return temp; } Self& operator--() { _node = _node->_pre; return *this; } Self& operator--(int) {//后置-- Self temp(_node); _node = _node->_pre; return temp; } bool operator!=(const Self& p) { return _node != p._node; } //T*/const T* Ptr operator ->() { return &_node->_val; } bool operator==(const Self& p) { return _node == p._node; } Node* _node; }; template<class T> class list { public: //节点 typedef ListNode<T> Node; typedef Node* pNode; //迭代器 typedef ListIterator<T, T&, T*> Iterator; typedef ListIterator<T, const T&, const T*> const_Iterator; typedef ReserveListIterator<T, T&, T*> Reserve_Iterator; typedef ReserveListIterator<T, const T&, const T*> const_Reserve_Iterator; public: void Empty_Init() { head = new Node; head->_pre = head; head->_next = head; head->_val = -1; sz = 0; } //构造 list() { Empty_Init(); } list(size_t n, const T& value = T()) { Empty_Init(); for (size_t i = 0; i < n; i++) { push_back(value); } sz = n; } //拷贝构造 list(const list<T>& lt) { Empty_Init(); for (auto& it : lt) { push_back(it); } } //迭代器构造 template <class IIterator> list(IIterator first, IIterator last) { Empty_Init(); while (first != last) { push_back(*first); first++; } } //析构 ~list() { Iterator it = begin(); while (it != end()) { it = erase(it); } delete head; sz = 0; } void swap(list<T> lt) { std::swap(lt.head, head); std::swap(sz, lt.sz); } //普通迭代器 Iterator begin() { return head->_next; } Iterator end() { return head; } //const迭代器 const_Iterator begin() const { return head->_next; } const_Iterator end() const { return head; } //反向迭代器 Reserve_Iterator rbegin() { return head; } Reserve_Iterator rend() { return head->_next; } const_Reserve_Iterator rbegin() const { return head; } const_Reserve_Iterator rend() const { return head->_next; } //插入 void insert(Iterator pos, const T& val) { Node* newnode = new Node(val); Node* cur = pos._node; newnode->_pre = cur->_pre; newnode->_next = cur; cur->_pre->_next = newnode; cur->_pre = newnode; sz++; } //删除 Iterator erase(Iterator pos) { assert(sz > 0); Node* cur = pos._node; Node* t = cur->_next; cur->_pre->_next = cur->_next; cur->_next->_pre = cur->_pre; delete cur; sz--; return t; } //尾插 void push_back(const T& val) { insert(end(), val); //size++; } //操作符重载 list<T>& operator = (list<T> lt) { swap(lt); return *this; } // List Capacity size_t size()const { return sz; } bool empty()const { return sz == 0; } private: pNode head; size_t sz; }; }
