C++之list类的代码及其逻辑详解（上）

1. list介绍及使用方法

list是标准库提供的容器，它的底层实现是双向链表。借助双向链表的结构，list能够高效地在任意位置进行元素的插入和删除操作，不过在元素的随机访问方面效率欠佳。

1. 双向链表结构：链表的每个节点都存有指向前驱节点和后继节点的指针，这使得它在插入和删除操作上十分高效。
2. 动态内存分配：std::list会依据实际需要动态地分配内存，所以它的大小能够在运行时动态改变。
3. 不支持随机访问：无法像数组或者std::vector那样通过下标（如list[5]）直接访问元素，要访问元素只能通过迭代器逐个遍历。
4. 插入和删除操作高效：在链表的任意位置进行插入和删除操作，时间复杂度都是 O (1)。
5. 迭代器稳定性：在对std::list进行插入或删除操作时，除了被删除的元素对应的迭代器会失效，其他迭代器都不会受到影响。

2. list的常用接口

2.1 迭代器操作

接口名称 作用 operator* 解引用迭代器，返回当前元素的引用。 operator-> 通过迭代器访问元素的成员（用于自定义类型）。 operator++ 前置 / 后置递增迭代器，指向下一个元素。 operator-- 前置 / 后置递减迭代器，指向前一个元素。 operator!= 判断两个迭代器是否不相等（用于循环终止条件）。 operator== 判断两个迭代器是否相等。

示例代码：

int main() { std::list myList = {1, 2, 3, 4}; for (auto it = myList.begin(); it != myList.end(); ++it) { std::cout << *it << \" \"; // 输出：1 2 3 4 }}

2.2 容器操作

接口名称 作用 begin() 返回指向第一个元素的迭代器。 end() 返回指向末尾（最后一个元素的下一个位置）的迭代器。 empty() 判断容器是否为空（注意：你提到的 empty_init() 可能是笔误）。 swap(list& x) 交换两个 list 的内容（常数时间复杂度）。 clear() 清空容器中的所有元素。 size() 返回容器中的元素个数。

示例代码：

list a = {1, 2};list b = {3, 4, 5};bool isEmpty = a.empty(); // falsea.swap(b); // a = {3, 4, 5}, b = {1, 2}a.clear(); // a 为空size_t s = b.size(); // s = 2

2.3 元素插入与删除

接口名称 作用 push_back(const T& x) 在容器尾部插入元素 x。 push_front(const T& x) 在容器头部插入元素 x。 insert(iterator pos, const T& x) 在迭代器 pos 前插入元素 x，返回新元素的迭代器。 erase(iterator pos) 删除迭代器 pos 指向的元素，返回下一个元素的迭代器。

示例代码：

list myList = {2, 4};myList.push_back(6); // myList = {2, 4, 6}myList.push_front(1); // myList = {1, 2, 4, 6}auto it = myList.begin();++it; // it 指向 2myList.insert(it, 3); // myList = {1, 3, 2, 4, 6}it = myList.begin();myList.erase(it); // 删除 1，myList = {3, 2, 4, 6}

1. 迭代器失效：

   • erase(pos) 会使被删除元素的迭代器失效。
   • insert(pos, x) 不会使任何迭代器失效。
   • 删除或插入元素后，建议重新获取迭代器。

2. 性能特点：

   • push_back()、push_front()、insert() 的时间复杂度均为 O (1)。
   • erase() 的时间复杂度为 O (1)，但需先定位到元素（定位可能需要 O (n)）。

完整示例

#include #include int main() { std::list myList; // 插入元素 myList.push_back(10); myList.push_front(5); myList.insert(++myList.begin(), 7); // {5, 7, 10} // 删除元素 myList.erase(++myList.begin()); // {5, 10} // 遍历 for (auto it = myList.begin(); it != myList.end(); ++it) { std::cout << *it << \" \"; // 输出：5 10 } // 交换与清空 std::list temp = {1, 2, 3}; myList.swap(temp);  // myList = {1, 2, 3} myList.clear();  // myList 为空 return 0;}