在上一期内容中，我们一起深入探讨了 vector 容器的模拟实现细节，也重点剖析了迭代器失效这一 “老大难” 问题 —— 想必大家已经感受到，作为连续存储的线性容器，vector 在随机访问时的高效优势十分突出，但在插入、删除（尤其是中间位置）场景下，却因数据迁移存在难以避免的性能损耗。

而今天，我们要迎来的 “新主角”——list 容器，恰好能在这些场景中展现独特优势。作为双向循环链表的 STL 实现，list 无需连续内存空间，插入删除操作仅需调整指针指向，时间复杂度可降至 O (1)；但与此同时，它也牺牲了 vector 的随机访问能力，用法上与 vector 存在明显差异。

接下来，我们就从 list 的基础结构入手，一步步拆解它的初始化、增删查改、遍历等核心操作，帮大家彻底搞懂 “什么时候该用 list”“怎么用对 list”，让 C++ 容器的学习版图再添一块关键拼图。

目录

1.list的介绍及使用

list的介绍

list模板参数介绍

核心特性

与其他容器的对比

list的使用

list的构造

list 的默认构造

list 的 n 个 val 的构造

list 的拷贝构造

list 的迭代器区间构造

完整示例代码

list iterator的使用

正向迭代器与反向迭代器简介

正向迭代器示例

反向迭代器示例

list cpacity 与 list element access

empty() 方法

size() 方法

front() 方法

back() 方法

综合注意事项

list modifiers

push_front（头插）

pop_front（头删）

push_back（尾插）

pop_back（尾删）

insert（任意位置插入）

erase（任意位置删除）

swap

clear

通用注意事项

结语

---

1.list的介绍及使用

list的介绍

list模板参数介绍

前面我们学习了模板参数和vector ， string 现在再看list的模板参数想必也已经有了一定的理解了，从参数列表我们不难看出第一个模板参数 T ，决定了list存储的数据类型，而第二个这里我们暂时不做介绍，后续将会为大家介绍这个参数的作用。  

list是 C++ 标准模板库（STL）中的序列容器，基于双向链表实现。

这里可能有的小伙伴不知道什么是双向链表，我简单科普一下

双向链表的基本概念

双向链表是一种线性数据结构，每个节点包含三个部分：

• 数据域：存储节点的值。
• 前驱指针（prev）：指向前一个节点的地址。
• 后继指针（next）：指向后一个节点的地址。

与单向链表不同，双向链表支持双向遍历（从头到尾或从尾到头）。

双向链表的特点

1. 双向访问：可以从任意节点向前或向后遍历链表。
2. 插入和删除高效：在已知节点位置时，插入或删除操作的时间复杂度为 O(1)（无需从头遍历）。
3. 额外空间开销：每个节点需额外存储前驱指针，占用更多内存。

双向链表的操作

插入节点

• 头部插入：新节点的 next 指向原头节点，原头节点的 prev 指向新节点。
• 中间插入：调整相邻节点的 prev 和 next 指针，确保逻辑连贯。
• 尾部插入：新节点的 prev 指向原尾节点，原尾节点的 next 指向新节点。

删除节点

• 调整目标节点前后节点的指针，跳过待删除节点，并释放其内存。

核心特性

• 插入与擦除：能在序列任意位置进行 ** 常数时间（\(O(1)\)）** 的插入和擦除操作，这是因为双向链表只需修改节点的前后指针，无需像数组（如vector）那样移动大量元素。
• 双向迭代：支持双向遍历，可从前往后或从后往前访问元素。

与其他容器的对比

• 和forward_list：forward_list是单向链表，仅支持单向迭代，但更节省空间、更高效；而list支持双向迭代，灵活性更强。
• 和数组、vector、deque：
  • 优势：在已获取迭代器的位置进行插入、提取、移动元素时，表现通常更优，适合排序等频繁操作元素位置的算法。
  • 劣势：无法通过位置直接随机访问元素（如要访问第 6 个元素，需从开头 / 结尾迭代到该位置，时间复杂度为\(O(n)\)）；且每个元素需额外存储前后链接信息，会消耗更多内存（对大量小元素的列表，内存开销更明显）。

list的物理结构大致如下图所示，可以看到list的每个结点（哨兵位除外）都由两个指针和一个数据位组成，即一个next（指向下一个结点）一个prev（指向上一个结点），_date（用来存储数据）

list的使用

在介绍list的使用时我们依旧从构造函数，iterator，插入与删除，以及list成员的访问这几个模块一一为大家介绍

list的构造

构造函数主要为大家介绍这几个常用的构造函数，其他的构造函数，大家感兴趣可以自行去了解，其中第五个涉及到C++11的右值引用，这个在我们学到C++11时会为大家介绍，接下来为大家介绍list的构造函数

list 的默认构造

默认构造会创建一个空的 list 对象，不包含任何元素。

#include <list>
std::list<int> lst1; // 默认构造，创建一个空的 list

易错点提示

• 默认构造的 list 大小为 0，直接访问元素（如 lst1.front()）会导致未定义行为。
• 初始化后建议检查 empty() 或 size() 避免越界操作。

---

list 的 n 个 val 的构造

构造一个包含 n 个值为 val 的元素的 list。若 val 省略，则使用默认值（如 int 为 0）。

std::list<int> lst2(5, 42);    // 5 个元素，每个值为 42
std::list<std::string> lst3(3); // 3 个元素，每个值为空字符串

易错点提示

• 若 val 是复杂对象（如类实例），频繁拷贝可能影响性能，建议使用移动语义或 emplace。
• 避免误用语法：std::list<int> lst(5); 表示 5 个 0，而非容量为 5。

---

list 的拷贝构造

通过另一个同类型 list 拷贝构造新 list，新旧 list 独立存储元素。

std::list<int> lst4 = {1, 2, 3};
std::list<int> lst5(lst4);      // 拷贝构造，lst5 内容为 {1, 2, 3}

易错点提示

• 深拷贝问题：若元素是指针，拷贝构造仅复制指针而非指向的对象。
• 性能开销：大列表拷贝可能耗时，建议使用移动构造（std::move）优化。

---

list 的迭代器区间构造

通过迭代器范围 [first, last) 构造 list，元素类型需兼容。

std::vector<int> vec = {10, 20, 30};
std::list<int> lst6(vec.begin(), vec.end()); // 从 vector 构造 list

易错点提示

• 迭代器失效风险：若原容器在构造期间被修改，可能导致未定义行为。
• 类型兼容性：区间元素类型必须可隐式转换为 list 的元素类型，否则需显式转换。

---

完整示例代码

#include <iostream>
#include <list>
#include <vector>

int main() {
    // 默认构造
    std::list<int> lst1;
    std::cout << "lst1 size: " << lst1.size() << std::endl; // 输出 0

    // n 个 val 构造
    std::list<int> lst2(3, 7);
    for (int x : lst2) std::cout << x << " "; // 输出 7 7 7

    // 拷贝构造
    std::list<int> lst3 = {1, 2, 3};
    std::list<int> lst4(lst3);
    lst4.push_back(4); // 不影响 lst3

    // 迭代器区间构造
    std::vector<double> vec = {1.1, 2.2, 3.3};
    std::list<int> lst5(vec.begin(), vec.end()); // 隐式转换 double→int
    for (int x : lst5) std::cout << x << " "; // 输出 1 2 3

    return 0;
}

list iterator的使用

上面为大家介绍完了list的构造函数，下面我们开始学习list的迭代器，经过前面的学习我们可以暂时将迭代器理解为一个指针，它指向list中的某个结点。

这里我们分别为大家介绍list的正向迭代器与反向迭代器

正向迭代器与反向迭代器简介

正向迭代器（iterator）和反向迭代器（reverse_iterator）是C++ STL中用于遍历容器的工具。正向迭代器从容器的起始位置向末尾移动，反向迭代器从容器的末尾向起始位置移动。

正向迭代器示例

正向迭代器通过begin()和end()获取，常用于顺序遍历容器。

#include <iostream>
#include <vector>

int main() {
    std::vector<int> vec = {1, 2, 3, 4, 5};
    
    // 使用正向迭代器遍历
    for (auto it = vec.begin(); it != vec.end(); ++it) {
        std::cout << *it << " ";
    }
    std::cout << std::endl;
    
    return 0;
}

易错点

1. 越界访问：如果迭代器超出end()，解引用会导致未定义行为。

   auto it = vec.end();
   std::cout << *it; // 错误！
   

2. 修改容器导致迭代器失效：在遍历过程中修改容器（如插入或删除元素）可能导致迭代器失效。

   for (auto it = vec.begin(); it != vec.end(); ++it) {
       if (*it == 3) {
           vec.erase(it); // 可能导致迭代器失效
       }
   }
   

反向迭代器示例

反向迭代器通过rbegin()和rend()获取，常用于逆序遍历容器。

#include <iostream>
#include <vector>

int main() {
    std::vector<int> vec = {1, 2, 3, 4, 5};
    
    // 使用反向迭代器遍历
    for (auto rit = vec.rbegin(); rit != vec.rend(); ++rit) {
        std::cout << *rit << " ";
    }
    std::cout << std::endl;
    
    return 0;
}

易错点

1. 反向迭代器的解引用：rbegin()指向的是容器的最后一个元素，rend()指向的是第一个元素的前一个位置。

   auto rit = vec.rend();
   std::cout << *rit; // 错误！
   

2. 与正向迭代器混用：反向迭代器和正向迭代器不能直接比较或混用。

   auto it = vec.begin();
   auto rit = vec.rbegin();
   if (it == rit) { // 编译错误
   }
   

3. 修改容器导致迭代器失效：与正向迭代器类似，修改容器可能导致反向迭代器失效。（这里就不为大家举例了，正向迭代器已经介绍过）

1. begin 与 end 为正向迭代器，对迭代器执行 ++ 操作，迭代器向后移动

2. rbegin(end) 与 rend(begin) 为反向迭代器，对迭代器执行 ++ 操作，迭代器向前移动

list cpacity 与 list element access

empty() 方法

作用：检查列表是否为空，返回布尔值（true表示空，false表示非空）。
代码示例：

#include <iostream>
#include <list>

int main() {
    std::list<int> lst1 = {1, 2, 3};
    std::list<int> lst2;  // 空列表

    std::cout << "lst1 is empty? " << lst1.empty() << std::endl;  // 输出 0 (false)
    std::cout << "lst2 is empty? " << lst2.empty() << std::endl;  // 输出 1 (true)
    return 0;
}

易错点：

• 误用 empty() 和 size() == 0：两者功能相同，但 empty() 的时间复杂度为 O(1)，性能更优。
• 未初始化列表时默认为空，直接调用 empty() 会返回 true。

---

size() 方法

作用：返回列表中元素的数量。
代码示例：

#include <iostream>
#include <list>

int main() {
    std::list<int> lst = {10, 20, 30};
    std::cout << "Size: " << lst.size() << std::endl;  // 输出 3
    lst.pop_back();
    std::cout << "Size after pop: " << lst.size() << std::endl;  // 输出 2
    return 0;
}

易错点：

• 频繁调用 size() 可能影响性能（某些实现中时间复杂度为 O(n)）。
• 与 empty() 混淆：size() > 0 逻辑等价于 !empty()，但后者更清晰。

---

front() 方法

作用：返回第一个元素的引用（列表非空时）。
代码示例：

#include <iostream>
#include <list>

int main() {
    std::list<int> lst = {5, 6, 7};
    std::cout << "First element: " << lst.front() << std::endl;  // 输出 5

    // 修改第一个元素
    lst.front() = 100;
    std::cout << "Modified first element: " << lst.front() << std::endl;  // 输出 100
    return 0;
}

易错点：

• 列表为空时调用 front() 会导致未定义行为（可能崩溃）。
• 返回的是引用，直接修改会影响原列表。

---

back() 方法

作用：返回最后一个元素的引用（列表非空时）。
代码示例：

#include <iostream>
#include <list>

int main() {
    std::list<std::string> lst = {"apple", "banana", "cherry"};
    std::cout << "Last element: " << lst.back() << std::endl;  // 输出 "cherry"

    // 修改最后一个元素
    lst.back() = "grape";
    std::cout << "Modified last element: " << lst.back() << std::endl;  // 输出 "grape"
    return 0;
}

易错点：

• 列表为空时调用 back() 会导致未定义行为。
• 与 front() 混淆：尤其在使用双向迭代器时需注意方向。

---

综合注意事项

1. 空列表检查：调用 front() 或 back() 前必须确保列表非空，否则需添加条件判断：

   if (!lst.empty()) {
       auto value = lst.back();  // 安全操作
   }
   

2. 性能差异：优先使用 empty() 而非 size() 检查是否为空。
3. 引用有效性：通过 front() 或 back() 获取的引用在元素被删除后失效。

list modifiers

push_front（头插）

向列表头部插入一个元素。

list<int> lst = {2, 3};
lst.push_front(1);  // lst变为{1, 2, 3}

易错点：

• 在空列表上调用push_front是安全的，但需确保后续操作不会越界。
• 性能优于insert(begin())，因为push_front是O(1)操作。

---

pop_front（头删）

删除列表头部元素。

list<int> lst = {1, 2, 3};
lst.pop_front();  // lst变为{2, 3}

易错点：

• 空列表调用pop_front会导致未定义行为，需先检查!lst.empty()。
• 被删除的元素不会被返回，若需获取值，应先通过front()访问。

---

push_back（尾插）

向列表尾部插入一个元素。

list<int> lst = {1, 2};
lst.push_back(3);  // lst变为{1, 2, 3}

易错点：

• 与push_front类似，空列表调用安全。
• 性能优于insert(end())，因push_back是O(1)操作。

---

pop_back（尾删）

删除列表尾部元素。

list<int> lst = {1, 2, 3};
lst.pop_back();  // lst变为{1, 2}

易错点：

• 空列表调用会导致未定义行为，需先检查!lst.empty()。
• 若需获取被删除的值，应通过back()提前保存。

---

insert（任意位置插入）

在指定位置插入一个或多个元素。

list<int> lst = {1, 3};
auto it = lst.begin();
advance(it, 1);          // 移动到第二个位置
lst.insert(it, 2);       // lst变为{1, 2, 3}
lst.insert(it, 2, 4);    // 插入两个4，lst变为{1, 4, 4, 2, 3}

易错点：

• 迭代器失效问题：插入不会使其他迭代器失效，但需注意it本身可能因容器修改而失效。
• 性能：插入位置越靠后，移动元素的开销越大（但链表插入总体是O(1)）。

---

erase（任意位置删除）

删除指定位置或范围的元素。

list<int> lst = {1, 2, 3, 4};
auto it = lst.begin();
advance(it, 1);         // 移动到第二个位置
it = lst.erase(it);     // 删除2，it指向3，lst变为{1, 3, 4}
lst.erase(it, lst.end());  // 删除从3到末尾，lst变为{1}

易错点：

• 迭代器失效：被删除的迭代器会失效，但返回的迭代器指向下一个有效位置。
• 需确保删除范围合法，避免[start, end)越界。

---

swap

交换两个列表的内容。

list<int> lst1 = {1, 2};
list<int> lst2 = {3, 4};
lst1.swap(lst2);  // lst1变为{3, 4}，lst2变为{1, 2}

易错点：

• 交换操作是O(1)复杂度，仅交换内部指针，不会导致元素移动或复制。
• 迭代器不会失效，但会指向交换后的容器中的元素。

---

clear

清空列表所有元素。

list<int> lst = {1, 2, 3};
lst.clear();  // lst变为空

易错点：

• 清空后size()变为0，但capacity()可能不变（链表无预分配内存概念）。
• 所有迭代器均失效，需重新获取。

---

通用注意事项

• 迭代器失效：insert和erase可能影响迭代器，需通过返回值更新迭代器位置。
• 性能：链表操作通常为O(1)，但频繁的内存分配可能影响性能，可考虑预分配节点。
• 范围检查：使用advance或next移动迭代器时，需确保不越界。

结语

到这里，咱们关于 list 基础使用的讲解就暂告一段落啦。相信大家通过今天的内容，已经能熟练掌握 list 的初始化、元素增删改查、遍历等核心操作，也对它 “双向链表” 的特性在实际场景中的优势有了初步感知 —— 比如在频繁插入删除时比 vector 更高效的表现。

不过，list 的知识点可不止 “会用” 这么简单。就像我们学会了用工具，却还没搞懂工具的 “内部构造” 一样，下一期，我们会深入底层，带大家亲手拆解 list 的模拟实现：从节点结构的定义，到链表的创建、销毁、节点插入删除的逻辑，一步步搞清楚 list 是如何 “工作” 的；更关键的是，我们还会重点剖析 list 迭代器失效的 “坑”—— 比如哪些操作会导致迭代器失效、失效后会引发什么问题，以及该如何规避，帮大家彻底打通从 “会用” 到 “懂原理” 的关键一环。

感兴趣的小伙伴记得持续关注，咱们下期一起揭开 list 底层和迭代器的神秘面纱，把这个容器的知识点学深学透～