目录
专栏：C++学习笔记
C++ 中的 list 是一个强大的容器，特别适用于需要频繁插入和删除元素的场景。本文将详细介绍 list 容器，包括其介绍、使用方法、实现原理以及与 vector 容器的对比。
1. list 的介绍及使用
1.1 list 的介绍
知识点：
list 是一种序列式容器，底层实现为双向链表。双向链表中的每个元素存储在独立的节点中，节点通过指针互相连接，可以在常数时间内在任意位置进行插入和删除操作。与 forward_list 的单链表不同，list 支持双向迭代。与其他序列式容器（如 array、vector、deque）相比，list 在插入和删除操作方面表现更优，但不支持随机访问。
小李的理解：
list 就像一条双向街道上的车队，每辆车（节点）都有前后两个链接，指向前后两辆车。你可以轻松地在任何地方插入或删除一辆车，而不需要移动其他车。但是，如果你想找到某辆车，就需要从头或尾开始，一辆辆查找，比较费时。
1.2 list 的使用
1.2.1 list 的构造
知识点：
list 提供多种构造方法，包括创建空的 list，创建包含多个相同元素的 list，使用区间构造 list 以及拷贝构造等。
小李的理解：
构造 list 就像创建不同类型的车队，你可以创建一个空车队，或者一个全是同样车的车队，还可以用现有的车队来创建新的车队。
代码示例：
#include <list>
#include <iostream>
int main() {
// 创建一个空的 list
std::list<int> empty_list;
// 创建一个包含 5 个值为 10 的元素的 list
std::list<int> filled_list(5, 10);
// 使用区间构造 list
int arr[] = {1, 2, 3, 4, 5};
std::list<int> range_list(arr, arr + 5);
// 打印 filled_list 的元素
for(int n : filled_list) {
std::cout << n << " ";
}
std::cout << std::endl;
return 0;
}
这个程序首先创建一个空的
list，然后创建一个包含 5 个值为 10 的list，接着用数组中的元素构造一个list。最后打印filled_list的元素，显示 5 个 10。
1.2.2 list 迭代器的使用
知识点：
list 的迭代器类似于指针，指向 list 中的节点。你可以使用迭代器遍历 list，访问或修改元素。
小李的理解：
迭代器就像你走在车队中的一个人，你可以走到每辆车旁边查看里面的东西，或者往回走查看后面的车。
代码示例：
#include <list>
#include <iostream>
int main() {
std::list<int> my_list = {1, 2, 3, 4, 5};
// 正向迭代
for (auto it = my_list.begin(); it != my_list.end(); ++it) {
std::cout << *it << " ";
}
std::cout << std::endl;
// 反向迭代
for (auto rit = my_list.rbegin(); rit != my_list.rend(); ++rit) {
std::cout << *rit << " ";
}
std::cout << std::endl;
return 0;
}
这个程序创建一个包含 5 个整数的
list。正向迭代器遍历list，从头到尾打印元素，反向迭代器遍历list，从尾到头打印元素。
1.2.3 list 的容量
知识点：
你可以使用 empty() 函数检查 list 是否为空，使用 size() 函数获取 list 中的元素个数。
小李的理解：
这就像你检查车队中是否有车，以及数一数车队中有多少辆车。
代码示例：
#include <list>
#include <iostream>
int main() {
std::list<int> my_list = {1, 2, 3, 4, 5};
// 检查是否为空
if (my_list.empty()) {
std::cout << "List is empty" << std::endl;
} else {
std::cout << "List is not empty" << std::endl;
}
// 获取大小
std::cout << "List size: " << my_list.size() << std::endl;
return 0;
}
程序首先检查
list是否为空，显然my_list不为空，然后打印list的大小，显示有 5 个元素。
1.2.4 list 的元素访问
知识点：
你可以使用 front() 函数访问 list 的第一个元素，使用 back() 函数访问 list 的最后一个元素。
小李的理解：
这就像你想看看车队的第一辆车和最后一辆车里装了什么东西。
代码示例：
#include <list>
#include <iostream>
int main() {
std::list<int> my_list = {1, 2, 3, 4, 5};
// 访问第一个和最后一个元素
std::cout << "First element: " << my_list.front() << std::endl;
std::cout << "Last element: " << my_list.back() << std::endl;
return 0;
}
程序分别打印
list的第一个和最后一个元素，显示 1 和 5。
1.2.5 list 的修改操作
知识点：
list 提供丰富的修改操作，包括在头部和尾部插入和删除元素，插入和删除特定位置的元素，交换两个 list 的内容以及清空 list。
小李的理解：
这就像你可以在车队的任何位置加车或减车，甚至可以交换两队车里的车，或者把整个车队清空。
代码示例：
#include <list>
#include <iostream>
int main() {
std::list<int> my_list = {1, 2, 3, 4, 5};
// 插入和删除操作
my_list.push_front(0); // 在前面插入 0
my_list.push_back(6); // 在后面插入 6
my_list.pop_front(); // 删除第一个元素
my_list.pop_back(); // 删除最后一个元素
// 插入和删除特定位置的元素
auto it = my_list.begin();
++it; // 指向第二个元素
my_list.insert(it, 100); // 在第二个位置插入 100
it = my_list.begin();
++it;
my_list.erase(it); // 删除第二个位置的元素
// 交换和清空 list
std::list<int> another_list = {10, 20, 30};
my_list.swap(another_list);
my_list.clear();
return 0;
}
以下是程序在各步之后的状态：
my_list初始为{1, 2, 3, 4, 5}- 插入 0 和 6 后为
{0, 1, 2, 3, 4, 5, 6}- 删除第一个和最后一个元素后为
{1, 2, 3, 4, 5}- 在第二个位置插入 100 后为
{1, 100, 2, 3, 4, 5}- 删除第二个位置的元素后为
{1, 2, 3, 4, 5}- 与
another_list交换后my_list为{10, 20, 30}- 清空后
my_list为空
1.2.6 list 迭代器失效
知识点：
在 list 中，插入操作不会导致迭代器失效，删除操作会使指向被删除节点的迭代器失效。
小李的理解：
就像你从车队中移走一辆车时，那个位置的指示牌（迭代器）也被移走了，但其他位置的指示牌不受影响。
代码示例：
#include <list>
#include <iostream>
int main() {
std::list<int> my_list = {1, 2, 3, 4, 5};
auto it = my_list.begin();
while (it != my_list.end()) {
it = my_list.erase(it); // 删除元素后，更新迭代器
}
return 0;
}
这个程序将删除
list中的所有元素，最后my_list为空。每次删除一个元素后，迭代器指向下一个元素，直到
list清空。
2. list 的模拟实现
知识点：
实现一个简化版本的 list，需要理解其底层结构和接口的含义。以下是一个简化的 list 实现示例：
小李的理解：
模拟实现 list 就像你自己动手造一辆汽车，你需要理解汽车的每个部件和它们如何协同工作。
代码示例：
#include <iostream>
template<typename T>
class Node {
public:
T data;
Node* prev;
Node* next;
Node(T val) : data(val), prev(nullptr), next(nullptr) {}
};
template<typename T>
class List {
private:
Node<T>* head;
Node<T>* tail;
public:
List() : head(nullptr), tail(nullptr) {}
void push_back(T val) {
Node<T>* newNode = new Node<T>(val);
if (!tail) {
head = tail = newNode;
} else {
tail->next = newNode;
newNode->prev = tail;
tail = newNode;
}
}
void print() {
Node<T>* temp = head;
while (temp) {
std::cout << temp->data << " ";
temp = temp->next;
}
std::cout << std::endl;
}
~List() {
Node<T>* temp;
while (head) {
temp = head;
head = head->next;
delete temp;
}
}
};
int main() {
List<int> my_list;
my_list.push_back(1);
my_list.push_back(2);
my_list.push_back(3);
my_list.print();
return 0;
}
这个程序手动实现了一个简单的
list，并添加了 3 个元素。最终打印出list中的所有元素。
3. list 与 vector 的对比
知识点：
底层结构：
vector：动态顺序表，连续内存空间。list：双向链表，不连续。随机访问：
vector：支持，效率为 O(1)。list：不支持，效率为 O(N)。插入和删除：
vector：效率低，时间复杂度为 O(N)。list：效率高，时间复杂度为 O(1)。空间利用率：
vector：高，连续空间，缓存利用率高。list：低，节点动态分配，容易造成内存碎片。迭代器：
vector：原生指针。list：封装的节点指针。迭代器失效：
vector：插入时可能失效，删除时当前迭代器失效。list：插入不会失效，删除时当前迭代器失效。使用场景：
vector：高效存储，随机访问。list：频繁插入和删除操作。
小李的理解：
vector 就像一块连续的停车场，每辆车（元素）都紧挨着，如果你要在中间插入或删除一辆车，就需要挪动很多车。而 list 就像一列火车，每节车厢（元素）独立，可以随意插入或移除车厢，但要找到某个特定车厢就得一节一节地找。
总结
C++ 中的
list容器是一个基于双向链表的序列式容器，适用于需要频繁插入和删除操作的场景，但不支持随机访问。list提供了多种构造方法和丰富的操作接口，包括插入、删除、访问等。与vector相比，list在插入和删除操作上更高效，但在随机访问和空间利用率上较差。
