前言：
在上期，我们学习了STL库中的第一个容器--vector ，今天我将给大家介绍的是 库中的另外一个容器--List。其实，有了之前学习 vector 的知识，对于List 的学习成本就很低了。
（一）基本介绍
1、基本概念
- list 是可以在常数范围内在任意位置进行插入和删除的序列式容器，并且该容器可以前后双向迭代。
- list 的底层是双向链表结构，双向链表中每个元素存储在互不相关的独立节点中，在节点中通过指针指向 其前一个元素和后一个元素。
2、list 与 forward_list 的比较
list与forward_list非常相似，最主要的区别如下：
- 最主要的不同在于forward_list是单链表，只能朝前迭代，已让其更简单高效。
3、特点
与其他的序列式容器相比(array，vector，deque)，list通常在任意位置进行插入、移除元素的执行效率更好。
与其他序列式容器相比，list 和 forward_list 最大的缺陷是不支持任意位置的随机访问：
- 比如：要访问list 的第6个元素，必须从已知的位置(比如头部或者尾部)迭代到该位置，在这段位置上迭代需要线性的时间开销；
- list还需要一些额外的空间，以保存每个节点的相关联信息(对于存储类型较小元素的大list来说这 可能是一个重要的因素)
（二）list的使用
list的文档介绍：文档介绍
list中的接口比较多，此处类似，只需要掌握如何正确的使用，然后再去深入研究背后的原理，已达到可扩展 的能力。以下为list中一些常见的重要接口。
1、list的构造
2、 list iterator的使用
此处，大家可暂时将迭代器理解成一个指针，该指针指向list中的某个节点。
- 1. begin与end为正向迭代器，对迭代器执行++操作，迭代器向后移动
- 2. rbegin(end)与rend(begin)为反向迭代器，对迭代器执行++操作，迭代器向前移动
3、list capacity
4、list element access
5、list modifiers
- list中还有一些操作，需要用到时大家可参阅list的文档说明。
6、list的迭代器失效
前面已经跟大家说过，此处大家可将迭代器暂时理解成类似于指针，迭代器失效即迭代器所指向的节点的无效，即该节点被删除了。
1、失效时机
因为list的底层结构为带头结点的双向循环链表，因此在list中进行插入时是不会导致list的迭代器失效的，只有在删除时才会失效，并且失效的只是指向被删除节点的迭代器，其他迭代器不会受到影响。
⚔️ 注意 ⚔️
迭代器有两种实现方式，具体应根据容器底层数据结构实现：
- 1️⃣原生指针：比如：vector的迭代器就是原生指针；
- 2️⃣将原生指针进行封装，因迭代器使用形式与指针完全相同，迭代器就是自定义类型对原生指针的封装，模拟指针的行为。
2、list与vector迭代器失效对比：
在C++中，当使用STL容器中的元素并且对容器进行修改时，可能会导致迭代器失效。在这种情况下，如果试图继续使用已经失效的迭代器，则程序可能会产生未定义的行为。
1️⃣vector
在使用vector容器时，添加或删除元素可能会导致迭代器失效。
- 这是因为vector容器内部使用动态数组实现，当容器中的元素数量超过了其内存分配的大小时，就需要重新分配一块更大的内存，并将原有元素拷贝到新的内存中；
- 此时，原有的迭代器就无法正确指向其对应的元素，因为元素的位置已经改变了；
- 同样的情况也发生在删除元素时，因为删除元素后，后面的元素会向前移动，导致原有的迭代器失效。
2️⃣list
插入元素不会导致迭代器失效， 删除元素时，只会导致当前迭代 器失效，其他迭代器不受影响。
void Test() { int array[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 0 }; list<int> ll(array, array+sizeof(array)/sizeof(array[0])); auto it = ll.begin(); while (it != ll.end()) { // erase()函数执行后，it所指向的节点已被删除，因此it无效 //在下一次使用it时，必须先给其赋值 ll.erase(it); ++it; } } // 改正 void Test() { int array[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 0 }; list<int> ll(array, array+sizeof(array)/sizeof(array[0])); auto it = ll.begin(); while (it != ll.end()) { ll.erase(it++); // it = ll.erase(it); } }
（三）list的模拟实现
要模拟实现list，必须要熟悉list的底层结构以及其接口的含义，通过上面的学习以及之前对vector和string的学习，我相信大家对于这些内容已基本掌握，现在我们来模拟实现list。
1、代码展示
⚔️ 如果大家还有不懂的，可以参考我上一篇文章：vector的基本实现 ⚔️
- 接下来我直接给出代码（这里实现的风格跟上篇实现vector稍微不一样）：
#pragma once namespace zp { template<typename T> class List { private: struct Node { T _data; Node* _prev; Node* _next; Node(const T& x, Node* p = nullptr, Node* n = nullptr) :_data(x) , _prev(p) , _next(n) {} }; public: class Iterator { public: Iterator(Node* n = nullptr) :node(n) {} T& operator*() { return node->_data; } Iterator& operator++() { node = node->_next; return *this; } Iterator operator++(int) { Iterator tmp = *this; node = node->_next; //++(*this); return tmp; } Iterator& operator--() { node = node->_prev; return *this; } Iterator operator--(int) { Iterator tmp = *this; node = node->_prev; return tmp; } bool operator==(const Iterator& x) const { return node == x.node; } bool operator!=(const Iterator& x) const { return !(*this == x); } private: Node* node; friend class List<T>; }; public: List() :head(new Node(T())) , tail(head) {} ~List() { clear(); delete head; head = nullptr; } 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()); } Iterator begin() const { return head->_next; } Iterator end() const { return tail; } bool empty() const { return head->_next == tail; } void clear() { while (!empty()) { erase(begin()); } } Iterator insert(Iterator it, const T& x) { Node* tmp = it.node; Node* newNode = new Node(x, tmp->_prev, tmp); tmp->_prev->_next = newNode; tmp->_prev = newNode; return newNode; } Iterator erase(Iterator pos) { Node* tmp = pos.node; Iterator res(tmp->_next); tmp->_prev->_next = tmp->_next; tmp->_next->_prev = tmp->_prev; delete tmp; return res; } private: Node* head; Node* tail; }; void print_list(const list<int>& lt) { list<int>::const_iterator it = lt.begin(); while (it != lt.end()) { cout << *it << " "; ++it; } cout << endl; } void test_1() { list<int> ll; ll.push_back(1); ll.push_back(2); ll.push_back(3); ll.push_back(4); ll.push_back(5); list<int>::iterator it = ll.begin(); while (it != ll.end()) { (*it) *= 2; cout << *it << " "; ++it; } cout << endl; list<int>::iterator pos = find(ll.begin(), ll.end(), 4); if (pos != ll.end()) { ll.insert(pos, 10); } for (auto& e : ll) { cout << e << " "; } cout << endl; it = ll.begin(); ++it; ll.erase(it); } void test_2() { list<int> ll; ll.push_back(1); ll.push_back(2); ll.push_back(3); ll.push_back(4); ll.push_back(5); for (auto e : ll) { cout << e << " "; } cout << endl; auto pos = ll.begin(); ++pos; ll.insert(pos, 20); for (auto e : ll) { cout << e << " "; } cout << endl; ll.push_back(100); ll.push_front(1000); for (auto e : ll) { cout << e << " "; } cout << endl; ll.pop_back(); ll.pop_front(); for (auto e : ll) { cout << e << " "; } cout << endl; } void test_3() { list<int> ll; ll.push_back(1); ll.push_back(2); ll.push_back(3); ll.push_back(4); ll.push_back(5); for (auto e : ll) { cout << e << " "; } cout << endl; ll.clear(); for (auto e : ll) { cout << e << " "; } cout << endl; ll.push_back(0); ll.push_back(5); ll.push_back(10); ll.push_back(15); for (auto e : ll) { cout << e << " "; } cout << endl; } }
- 上述代码我定义了一个List类，其中包含了一个嵌套的Node结构体用于表示双向链表的节点。使用模板实现泛型数据类型，可以存储任意类型的数据。List类还包含了一个嵌套的【Iterator】类，用于遍历双向链表。
2、注意事项
1️⃣【】不能实现访问操作
前面已经说过list是链表的结果，因此大家不难理解为什么在list下【】不能访问元素。由于list采用的是链接存储而不是连续存储，所以本质上它不支持下标方式（也就是按偏移量）访问。
2️⃣sort()
其次就是list的排序操作，我们还是对比之前学习的vector
在 C++ 中，【list 】和 【vector 】是两种不同的数据结构，它们都提供了 sort() 函数来对其中的元素进行排序。但是，它们的底层实现不同，因此其 sort() 函数的效率也不同
①vector
- 对于
vector来说，它是一个基于连续内存空间的动态数组，其元素存储在连续的内存块中，因此可以通过指针算术运算等方式快速访问其中的元素。 - 由于其元素是连续存储的，因此对其进行排序时可以使用标准库提供的
std::sort()算法，该算法时间复杂度为 O(NlogN)，其中 N 为元素个数。因此，vector的sort()函数效率较高。
②list
- 而对于
list来说，它是一个基于双向链表的容器，其元素并不是连续存储的，因此不能像vector那样直接进行指针算术运算访问其中的元素。 - 由于其底层实现的原因，
list并没有提供sort()函数，但是可以通过调用标准库提供的std::list::sort()成员函数来对其中的元素进行排序。 - 该函数采用的是归并排序（Merge Sort）算法，时间复杂度为 O(NlogN)。
- 由于归并排序需要频繁的进行链表节点的指针操作，因此相较于
vector的sort()函数而言，list的sort()函数效率较低。
接下来，我们通过代码来简单的看看到底怎么样
- 代码一：
void test_op() { srand(time(0)); const int N = 1000000; vector<int> v; v.reserve(N); list<int> lt2; for (int i = 0; i < N; ++i) { auto e = rand(); v.push_back(e); lt2.push_back(e); } int begin1 = clock(); sort(v.begin(), v.end()); //对vector进行sort，调用的是算法里的快排 int end1 = clock(); int begin2 = clock(); lt2.sort(); //对list也进行sort int end2 = clock(); printf("vector sort:%d\n", end1 - begin1); printf("list sort:%d\n", end2 - begin2); }
解释说明：
- 首先我们给出一个测试用例 N（我这里赋值的为100w），产生了100w 个随机值；
- 其中一个放到vector里面，一个放到list里面；
- 分别对list和vector进行sort，对比它们的性能看差别有多大
- 注意：是在release模式下进行查看
结果如下：
结果：
- 经过几次反复的验证，我们可以发现，vector的效率比list 的效率打上三四倍的样子，如果在工程里这是一个巨大的差距
- 代码二：
void test_op() { srand(time(0)); const int N = 1000000; vector<int> v; v.reserve(N); list<int> lt1; list<int> lt2; for (int i = 0; i < N; ++i) { auto e = rand(); lt1.push_back(e); lt2.push_back(e); } // 拷贝到vector排序，排完以后再拷贝回来 int begin1 = clock(); for (auto e : lt1) { v.push_back(e); } sort(v.begin(), v.end()); size_t i = 0; for (auto& e : lt1) { e = v[i++]; } int end1 = clock(); int begin2 = clock(); lt2.sort(); int end2 = clock(); printf("vector sort:%d\n", end1 - begin1); printf("list sort:%d\n", end2 - begin2); }
解释说明：
- 我这里给出两个list；
- 对于给出的list1，我们先把它拷贝到vector中，排序完成之后在拷贝回来；
- 而对于list2，我们直接进行sort排序；
- 对比上述的两个操作，看效率如何
结果如下：
结果：
- 不难发现，list1拷贝到vector里面在排，排序完成之后在拷贝回来都比list2要快，因此不难发现list下sort() 的效率较差。因此很少用，在上述实现中也没有写。
小结
- 对于需要频繁进行元素访问操作的情况，建议使用
vector； - 而对于需要频繁进行元素插入、删除和排序等操作的情况，建议使用
list。
（四）list与vector的对比
（五）总结
到此，便是本期的全部知识内容了，感谢大家的阅读与支持！！！
