【C++】STL---list

一、list 的介绍

1. list 是可以在常数范围内在任意位置进行插入和删除的序列式容器，并且该容器可以前后双向迭代。
2. list 的底层是双向链表结构，双向链表中每个元素存储在互不相关的独立节点中，在节点中通过指针指向其前一个元素和后一个元素。
3. list 与 forward_list 非常相似：最主要的不同在于 forward_list 是单链表，只能朝前迭代，已让其更简单高效。
4. 与其他的序列式容器相比(array，vector，deque)，list通常在任意位置进行插入、移除元素的执行效率更好。
5. 与其他序列式容器相比，list 和 forward_list 最大的缺陷是不支持任意位置的随机访问，比如：要访问 list 的第6个元素，必须从已知的位置(比如头部或者尾部)迭代到该位置，在这段位置上迭代需要线性的时间开销；list 还需要一些额外的空间，以保存每个节点的相关联信息(对于存储类型较小元素的大 list 来说这可能是一个重要的因素)。

二、list 的模拟实现

list 学习时也要学会查看文档：list 文档介绍，在实际中我们熟悉常见的接口就可以，下面我们直接开始模拟实现，在模拟实现中我们实现的是常见的接口，并且会在实现中讲解它们的使用以及注意事项。

首先跟以往不一样的是，list 是一个个节点连接起来的，所以它不是连续的物理空间，这也就意味着，它不用扩容，每次插入的时候只需要申请一个节点，然后连接起来即可；

其次，list 底层的迭代器实现也跟 string和 vector 不一样，它们两个的迭代器可以说是原生指针，但是 list 的迭代器是要让节点指向下一个节点，所以底层实现也不一样；例如我们想让迭代器 it，往后迭代，就是 ++it，但是底层的实现却不是真的让节点++，因为它们的空间不是连续的，所以我们要把 list 迭代器封装成一个类。

首先我们先创建一个自己的命名空间，把 list 节点的类，list 迭代器的类，list 类都放进去；

1. list 节点类

list 节点类如下，因为是双向链表，所以应该有一个数据，两个指针；

		namespace Young{// list 节点类template <class T>struct list_node{T _data;list_node<T>* _next;list_node<T>* _prev;list_node(const T& x = T()):_data(x),_next(nullptr),_prev(nullptr){}};}

2. list 迭代器类

首先我们先定义一个类模板，其参数有三个，分别是类型、类型的引用(const 和 非const) 、类型的指针(const 和 非const) ；

为什么要定义三个模板参数呢，因为考虑到 const 迭代器，const 迭代器和普通迭代器不是同一个类，不能直接在 iterator 前直接加 const，如 const iterator ，这不是 const 迭代器，因为这里的 const 修饰的是迭代器本身，就是迭代器本身不能修改，但是我们期望的是迭代器本身可以被修改，如 it++、++it，只是期望迭代器指向的内容不能被修改，如 *it = 10、it->10 ；

这就类比 const T* 和 T* const ， const T* 中 const 是修饰指向的内容不能被修改，而 T* const 中 const 修饰的是指针本身不能被修改；而我们需要实现的 const 迭代器 是要满足第一种的，所以 list 中普通迭代器和 const 迭代器 是两个完全不一样的类，应该写成两个类，但是我们可以通过增加两个模板参数 类型的引用(const 和 非const) 、类型的指针(const 和 非const) 来复用普通迭代器，具体实现如下：

		// list 迭代器类template <class T,class Ref,class Ptr>struct __list_iterator{typedef list_node<T> Node;typedef __list_iterator<T, Ref, Ptr> self;Node* _node;// 迭代器构造函数__list_iterator(Node* node):_node(node){}}

首先我们先将节点类起别名为 Node，再将自己的类起别名为 self；迭代器本身也是一个指针，只是它内部实现不一样，所以我们需要一个 _node 节点的指针，构造函数实例化一个节点的指针，比如说 list<int>::iterator it = lt.begin();，这里的 it 就会调构造函数，实例化一个 lt.begin() 节点的指针，其实 lt.begin() 就是指向头节点的指针。

接着我们重载一些迭代器常用的运算符：

（1）前置++

就是让迭代器往后迭代，具体的实现就是让节点的指针指向下一个节点：

			// 前置 ++self& operator++(){_node = _node->_next;return *this;}

（2）后置++

跟前置++的区别就是，后置++需要拷贝，返回++以前的迭代器，所以一般都不用后置++；

			// 后置 ++self operator++(int){self tmp(*this);_node = _node->_next;return tmp;}

（3）前置- -、后置- -

前置- -、后置- - 与 ++ 的区别就是， - -返回上一个节点的迭代器；

			// 前置 --self& operator--(){_node = _node->_prev;return *this;}// 后置--self operator--(int){self tmp(*this);_node = _node->_prev;return tmp;}

（4）!= 和 == 运算符重载

!= 运算符重载就是比较它们的节点是否相等；== 运算符就相反；

			// != 运算符重载   iterator it != lt.begin();bool operator!=(const self& s){return s._node != _node;}// == 运算符重载   iterator it == lt.begin();bool operator==(const self& s) {return s._node == _node;}

（5）* 解引用重载 和 -> 重载

解引用重载 和 -> 重载 就是改变迭代器指向内容的两个运算符，所以我们定义的三个模板参数，就在这里起作用了；比如我们实例化的模板参数是 const 迭代器 的 __list_iterator<T, const T&, const T*>，这里的 const T& 就是 Ref，const T* 就是 Ptr，这里就可以直接用 Ref （解引用重载）和 Ptr（箭头重载） 作返回值；

如果是 非const 迭代器的 __list_iterator<T, T&, T*>，T& 就是 Ref，T* 就是 Ptr；所以就可以根据它们的类型返回对应的迭代器类型，就不需要我们自己写两个迭代器的类了。

			// * 解引用重载Ref operator*(){return _node->_data;}// -> 重载Ptr operator->(){return &_node->_data;}

解引用 和 -> 重载的使用：

假设 list 里面存的类型是一个自定义类型，这个自定义类型中有两个成员变量，那么我们在使用 解引用 和 -> 重载的时候，应该访问哪一个呢？这时候就需要我们指定访问了，如下代码：

		struct AA{AA(int a1 = 0, int a2 = 0):_a1(a1), _a2(a2){}int _a1;int _a2;};void test4(){Young::list<AA> lt;lt.push_back(AA(1, 1));lt.push_back(AA(2, 2));lt.push_back(AA(3, 3));Young::list<AA>::iterator it = lt.begin();while (it != lt.end()){// 使用解引用//cout << (*it)._a1<<" "<<(*it)._a2 << endl;//使用 ->cout << it->_a1 << " " << it->_a2 << endl;++it;}cout << endl;}

上面的 cout << it->_a1 << " " << it->_a2 << endl; 调用了->重载，实际上是 cout << it.operator->()->_a1 << " " << it.operator->()->_a2 << endl;，本来应该是有两个 -> 的，即 it->->_a1 但是这样写可读性不好，所以编译器特殊处理，省略了一个 ->。

3. list 类

list 类首先将 const 迭代器和非 const 迭代器类型起别名为 const_iterator 和 iterator ；成员变量有 _head 哨兵位节点和 _size 记录链表的长度，如下：

		// list 类template <class T>class list{public:typedef list_node<T> Node;typedef __list_iterator<T, T&, T*> iterator;typedef __list_iterator<T, const T&, const T*> const_iterator;private:Node* _head;size_t _size;};

（1）迭代器

注意，begin() 是哨兵位的下一个节点，end() 是哨兵位节点。

begin() 和 end() 返回的类型也是一个迭代器，这里 iterator(_head->_next) 是调用迭代器类的构造函数，构造一个节点的指针返回；也可以写成 _head->_next，因为支持隐式类型的转换；

			// 非 const 迭代器iterator begin(){return iterator(_head->_next);}iterator end(){return iterator(_head);}// const 迭代器const const_iterator begin() const{return const_iterator(_head->_next);}const const_iterator end() const{return const_iterator(_head);}

（2）修改相关的接口

swap()

交换链表数据，需要借助标准库的 swap 函数实现：

			// 交换链表数据void swap(list<T>& lt){std::swap(_head, lt._head);std::swap(_size, lt._size);}

insert()

在 pos 迭代器插入节点；新开一个节点，然后插入指定迭代器的位置，连接好 prev 和 cur 的位置即可；因为 list 的底层结构为带头结点的双向循环链表，因此在 list 中进行插入时是不会导致 list 的迭代器失效的；

			// 插入节点iterator insert(iterator pos, const T& x){Node* newnode = new Node(x);Node* cur = pos._node;Node* prev = cur->_prev;prev->_next = newnode;newnode->_prev = prev;newnode->_next = cur;cur->_prev = newnode;++_size;return newnode;}

erase()

删除 pos 迭代器位置的节点；在删除时迭代器会失效，并且失效的只是指向被删除节点的迭代器，其他迭代器不会受到影响，所以 erase() 函数执行后，it 所指向的节点已被删除，因此 it 无效，在下一次使用 it 时，必须先给其赋值；

			// 删除节点iterator erase(iterator pos){Node* prev = pos._node->_prev;Node* next = pos._node->_next;prev->_next = next;next->_prev = prev;delete pos._node;pos._node->_next = pos._node->_prev = nullptr;--_size;return next;}

push_back、push_front、pop_back、pop_front

只需要复用 insert() 和 erase() 即可，实现如下：

			// 尾插void push_back(const T& x){insert(end(), x);}// 头插void push_front(const T& x){insert(begin(), x);}// 尾删void pop_back(){erase(--end());}// 头删void pop_front(){erase(begin());}

clear()

清空链表数据，删除除了哨兵位的节点即可；

			// 清空链表数据void clear(){iterator it = begin();while (it != end()){it = erase(it);}}		

以上修改接口配合迭代器的使用如下图：

（3）空链表初始化

			// 空链表初始化void empty_init(){_head = new Node;_head->_next = _head;_head->_prev = _head;_size = 0;}

（4）构造函数

构造函数只需要创建一个哨兵位即可；

			// 构造函数list(){empty_init();}

（5）拷贝构造函数

拷贝构造函数直接初始化，然后插入数据即可；

			// 拷贝构造函数 -- lt2(lt1)list(const list<T>& lt){empty_init();for (auto e : lt){push_back(e);}}

（6）赋值运算符重载

现代写法，传参的时候调用拷贝构造，然后交换数据即可；

			// 赋值运算符重载 -- lt2 = lt1list<T>& operator=(list<T> lt){swap(lt);return *this;}

（7）析构函数

清空链表数据之后再释放哨兵位的节点即可；

			// 析构函数~list(){clear();delete _head;_head = nullptr;}

4. 打印容器的接口

（1）打印链表整型的接口

像 vector、list 这些容器都没有重载流插入运算符，所以我们可以自己实现一个打印的接口函数；我们先来实现一下打印链表整型的接口：

		// 打印链表 -- 只能针对 int 类型void print_list(const list<int>& lt){list<int>::const_iterator it = lt.begin();while (it != lt.end()){//*it = 10; errorcout << *it << " ";++it;}cout << endl;}

此接口可以打印链表的数据，但是只能针对 int 类型，我们可以对它进行改造一下，使用模板。

（2）打印 list 的接口

我们学了模板，就可以利用模板实现泛型编程，将类型改为模板的泛型，即可打印 list 中的不同类型，如下：

		// 打印链表 -- 只能打印 list 容器template<typename T>void print_list(const list<T>& lt){typename list<T>::const_iterator it = lt.begin();while (it != lt.end()){//*it = 10; errorcout << *it << " ";++it;}cout << endl;}

这里的模板参数使用了 typedef 关键字，这里必须使用 typedef 关键字，而且在指定类域前还要加上 typedef 关键字，如 typename list<T>::const_iterator it = lt.begin();；因为在模板还没有进行实例化的时候， const_iterator 就到 list<T> 的类域中寻找类型，此时类中还没有实例化参数 T，所以编译器分不清它是类型还是静态变量，不能去 list<T> 里面找，所以在前面加 typedef 关键字就说明它是个类型，编译器在等 list<T> 实例化后，再去类里面去取根据类型去取类型。

但是上面的接口还是不够完美，要是我想打印 vector 呢？那还是不能打印出来，所以我们可以实现一个专门打印容器的接口；

（3）打印容器的接口

我们使用模板参数代表容器，让编译器到指定容器去取它的迭代器即可；

		// 打印容器 -- 能打印各种容器template<typename container>void print_container(const container& con){typename container::const_iterator cit = con.begin();while (cit != con.end()){cout << *cit << " ";++cit;}cout << endl;}

使用如下图：