阅读量:0
目录
专栏：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在插入和删除操作上更高效，但在随机访问和空间利用率上较差。
