目录

1. list 的介绍及使用

1.1 list 的介绍

知识点：

小李的理解：

1.2 list 的使用

1.2.1 list 的构造

知识点：

小李的理解：

代码示例：

1.2.2 list 迭代器的使用

知识点：

小李的理解：

代码示例：

1.2.3 list 的容量

知识点：

小李的理解：

代码示例：

1.2.4 list 的元素访问

知识点：

小李的理解：

代码示例：

1.2.5 list 的修改操作

知识点：

小李的理解：

代码示例：

1.2.6 list 迭代器失效

知识点：

小李的理解：

代码示例：

2. list 的模拟实现

知识点：

小李的理解：

代码示例：

3. list 与 vector 的对比

知识点：

小李的理解：

 总结

专栏：C++学习笔记 

上一卷：【C++ 】-vector：新时代动态数组的革新与未来

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  #include   int main() {     // 创建一个空的 list     std::list empty_list;      // 创建一个包含 5 个值为 10 的元素的 list     std::list filled_list(5, 10);      // 使用区间构造 list     int arr[] = {1, 2, 3, 4, 5};     std::list 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  #include   int main() {     std::list 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  #include   int main() {     std::list 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  #include   int main() {     std::list 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  #include   int main() {     std::list 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 another_list = {10, 20, 30};     my_list.swap(another_list);     my_list.clear();      return 0; } 

以下是程序在各步之后的状态：

1. my_list 初始为 {1, 2, 3, 4, 5}
2. 插入 0 和 6 后为 {0, 1, 2, 3, 4, 5, 6}
3. 删除第一个和最后一个元素后为 {1, 2, 3, 4, 5}
4. 在第二个位置插入 100 后为 {1, 100, 2, 3, 4, 5}
5. 删除第二个位置的元素后为 {1, 2, 3, 4, 5}
6. 与 another_list 交换后 my_list 为 {10, 20, 30}
7. 清空后 my_list 为空

1.2.6 list 迭代器失效

知识点：

在 list 中，插入操作不会导致迭代器失效，删除操作会使指向被删除节点的迭代器失效。

小李的理解：

就像你从车队中移走一辆车时，那个位置的指示牌（迭代器）也被移走了，但其他位置的指示牌不受影响。

代码示例：

#include  #include   int main() {     std::list 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   template class Node { public:     T data;     Node* prev;     Node* next;      Node(T val) : data(val), prev(nullptr), next(nullptr) {} };  template class List { private:     Node* head;     Node* tail;  public:     List() : head(nullptr), tail(nullptr) {}      void push_back(T val) {         Node* newNode = new Node(val);         if (!tail) {             head = tail = newNode;         } else {             tail->next = newNode;             newNode->prev = tail;             tail = newNode;         }     }      void print() {         Node* temp = head;         while (temp) {             std::cout << temp->data << " ";             temp = temp->next;         }         std::cout << std::endl;     }      ~List() {         Node* temp;         while (head) {             temp = head;             head = head->next;             delete temp;         }     } };  int main() {     List 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 在插入和删除操作上更高效，但在随机访问和空间利用率上较差。