【STL】list的底层原理及其实现

list的介绍

1. list是可以在常数范围内在任意位置进行插入和删除的序列式容器，并且该容器可以前后双向迭代。
2. list的底层是用双向链表实现的（线性），每个元素都存在相互独立的节点中，每个节点都有一个指针分别指向前一个节点和后一个节点。
3. 因为底层结构是链表，list的插入和删除操作是非常高效的，这与vector容器相反。但是由于链表的结构特点，list的各个节点之间的物理地址是不连续的，也就导致了任意访问某个节点的效率较低。
4. 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 Iteratoriterator begin();iterator end();const_iterator begin();const_iterator end();///// List Capacitysize_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()

1. begin与end为正向迭代器，对迭代器执行++操作，迭代器向后移动
2. 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 Capacitysize_t size()const {return sz;}bool empty()const {return sz == 0;}private:pNode head;size_t sz;};
}