C/C++ 数据结构（四）链表与STL容器
本篇核心知识：链表头结点设计、STL 容器对比（vector /list/forward_list）、迭代器原理与使用、迭代器失效、仿函数、容器常用算法、C++11 新特性、双向链表手写要求、深浅拷贝与容器类型适配
一、链表头结点详解
概念
头结点是链表额外增设的虚拟节点，不存储有效业务数据，专门用于统一链表操作逻辑，分为带头结点和不带头结点两种设计方案。
特性
不带头结点（首元节点）
首节点直接存储有效数据，头指针指向第一个数据节点；
缺陷：在链表头部做插入、删除操作时，必须单独判断边界，代码冗余、易出错。
带头结点（主流设计）
额外开辟一块节点内存，无有效数据；
优势：所有位置的增删操作逻辑完全统一，无需特殊处理头部边界，代码简洁健壮；
额外开销：多占用一个节点的内存空间，属于空间换代码稳定性。
适用场景：工程开发、笔试面试均优先使用带头结点链表。
代码示例（两种链表结构对比）
// 1. 不带头结点单链表 struct Node{ int data; Node* next; }; Node* head = nullptr; // 头指针直接指向数据节点 // 2. 带头结点单链表 struct Node{ int data; Node* next; }; Node* head = new Node(); // 头结点，data无有效数据 head->next = nullptr; // 首数据节点为空拓展
链表排序时，带头结点无需修改头指针指向；不带头结点若交换首节点，必须同步更新头指针，风险更高。
二、STL 核心容器底层与选型对比
概念
C++ STL 容器是基于数据结构封装的通用类模板，不同容器对应不同底层结构，选型核心依据是操作效率、业务场景。
主流容器底层、特性、适用场景
1. vector 动态顺序表（动态数组）
概念
底层为连续内存的顺序表，等价于可自动扩容的动态数组。
特性
优点：支持下标随机访问（(O(1))），尾部追加 / 删除效率极高；
缺点：中间插入、删除元素效率低，后续元素需要整体前移；
扩容机制：内存不足时自动重新开辟更大空间（主流编译器扩容倍数为 2 倍，部分为 1.5 倍），拷贝原数据并释放旧内存，扩容会产生性能损耗；
限制：尽量提前预估容量，减少频繁扩容。
2. list 双向链表
概念
底层为双向循环链表，节点包含前驱prev、后继next两个指针域。
特性
优点：任意位置插入、删除仅修改指针（(O(1))），无数据挪动；
缺点：不支持随机访问，必须遍历查找元素；
内存：节点内存离散，存在指针额外开销。
3. forward_list 单向链表（C++11 新增）
概念
底层为单向链表，仅保留后继指针。
特性
内存开销比 list 更小；
仅支持单向遍历，功能精简，适用于极简场景。
容器选型原则（重点）
频繁查询、尾部增删，极少中间操作 → 优先使用
vector；频繁在任意位置插入 / 删除，查询少 → 优先使用
list；追求极致内存占用、仅单向遍历 → 使用
forward_list。
代码示例 基础使用
#include <vector> #include <list> using namespace std; int main() { // vector 用法（顺序表） vector<int> vec; vec.push_back(10); // 尾部添加，效率高 vec.pop_back(); // 尾部删除，效率高 // list 用法（双向链表） list<int> lst; lst.push_back(20); lst.push_front(30); // 头部插入，效率极高 return 0; }拓展
vector 不能直接看作普通数组，它封装了扩容、内存管理逻辑；list 节点由 STL 自动分配释放，无需手动管理堆内存。
三、迭代器（Iterator）
概念
迭代器是 STL 容器的通用遍历工具，本质是对指针的封装，行为和指针高度相似，是连接算法与容器的桥梁。
核心特性
本质：类模板实现，重载
*、->、++、--、==、!=等运算符；通用能力：所有 STL 容器都可通过迭代器遍历，一套写法适配多容器；
分类：
普通正向迭代器：
begin()（指向首元素）、end()（尾后无效位置，遍历终止标记）；反向迭代器：
rbegin()、rend()，从尾部向前遍历；区间规则：STL 迭代遵循前闭后开
[begin, end)，end不指向有效元素。
1. 迭代器遍历（传统写法）
#include <list> using namespace std; int main() { list<int> lst = {1,2,3,4,5}; // 定义迭代器 list<int> it = lst.begin(); // 遍历：it != end 为终止条件 while(it != lst.end()) { cout << *it << " "; // * 解引用，获取元素值 ++it; } return 0; }2. C++11 范围 for 遍历
概念
底层依旧依赖迭代器，语法更简洁，适合完整遍历容器。
list<int> lst = {1,2,3,4,5}; // 只读遍历 for(auto val : lst) cout << val << " "; // 可修改遍历（加引用） for(auto& val : lst) val += 1;3. 迭代器失效
概念
容器操作后，原有迭代器指向的内存失效，继续使用会引发野指针、程序崩溃。
不同容器失效规则
vector（顺序表）
中间插入 / 删除、触发扩容 → 所有迭代器全部失效；
原因：元素整体挪动 / 内存重新分配，原地址作废。
list（双向链表）
仅被删除节点对应的迭代器失效；
其余迭代器保持有效；
原因：仅修改指针指向，其他节点内存不变。
解决方案
执行增删操作后，重新获取迭代器；使用list::erase时接收返回值（返回下一个有效迭代器）。
list<int> lst = {1,2,3}; auto it = lst.begin(); it = lst.erase(it); // 接收返回值，避免迭代器失效拓展
手写容器（链表 / 顺序表）时，需要自行封装迭代器类，核心就是重载指针相关运算符。
四、模板类与容器类型适配
概念
STL 容器均为类模板，模板参数指定容器存储的数据类型；模板对存储类型有隐性要求。
特性
模板语法：
template<typename T>，T为通用类型占位符；类型约束：
存入容器的类型，必须支持拷贝构造（容器添加元素时会拷贝对象）；
自定义类若包含指针成员，必须实现深拷贝，否则出现内存错误；
推荐用法：存储自定义类型时，优先使用指针，规避浅拷贝问题。
代码示例 模板与类型约束
// 普通类型：天然支持拷贝 list<int> lst1; // 自定义结构体（需保证拷贝合法） struct Person { string name; int age; }; list<Person> lst2; // 存储指针：无需考虑深浅拷贝 list<Person*> lst3;五、仿函数（函数对象）
概念
仿函数是重载了()括号运算符的类 / 结构体，本质是对象，使用语法和普通函数一致，STL 算法中广泛用于自定义比较、判断逻辑。
特性
核心实现：类内重载
operator()；分类：
一元仿函数：接收 1 个参数（用于条件判断，如
remove_if）；二元仿函数：接收 2 个参数（用于大小比较，如
sort排序）；用途：容器排序、条件删除时，自定义规则（默认比较无法满足复杂业务）。
代码示例
示例 1 二元仿函数（自定义排序规则）
#include <list> #include <iostream> using namespace std; // 自定义英雄结构体 struct Hero { string name; int level; // 等级 int hp; // 血量 }; // 二元仿函数：先按等级降序，等级相同按血量降序 struct CompareHero { bool operator()(const Hero& h1, const Hero& h2) { if(h1.level != h2.level) return h1.level > h2.level; return h1.hp > h2.hp; } }; int main() { list<Hero> heroList; // 填充数据 heroList.push_back({"战士", 10, 1000}); heroList.push_back({"法师", 8, 800}); // 传入仿函数对象，自定义排序 heroList.sort(CompareHero()); return 0; }示例 2 一元仿函数（条件删除）
// 一元仿函数：判断血量小于500 struct DelLowHp { bool operator()(const Hero& h) { return h.hp < 500; } }; // 删除符合条件的元素 heroList.remove_if(DelLowHp());拓展
默认排序会调用类型原生比较运算符；自定义类型若无重载</>，必须使用仿函数指定规则。
六、链表常用算法与容器对应方法
1. list 合并操作
特性
list::merge()：要求两个链表已有相同排序规则，合并后依旧有序，仅修改指针，不拷贝数据；
普通拼接：不要求有序，直接串联两个链表。
2. list 去重unique()
特性
默认判断==相等元素；自定义类型需重载相等运算符，或搭配仿函数。
3. 排序底层说明
list底层排序算法为归并排序，专为链表结构优化；
顺序表常用快速排序，二者底层实现不同。
七、C++11 容器新特性补充
1. forward_list 单向链表
C++11 新增精简版链表，仅单向遍历，内存开销更小，功能少于 list。
2. emplace 系列函数
概念
emplace_back/emplace_front直接在容器内存原地构造对象，替代push_back。
特性
push_back：先创建对象，再拷贝到容器（调用拷贝构造）；
emplace：直接调用构造函数原地生成，省去拷贝开销，效率更高。
list<Hero> lst; lst.emplace("射手",9,900); // 原地构造，无拷贝八、手写双向链表（综合实战要求）
整体设计要求
采用带头、带尾结点双向链表，统一边界操作；
节点结构：
数据域 + 前驱指针 prev + 后继指针 next；封装为类模板，适配任意数据类型；
内部封装迭代器（类内嵌套实现）；
实现基础接口：增、删、改、查、遍历、排序。
节点基础结构代码
template<typename T> struct Node { T data; Node<T>* prev; // 前驱 Node<T>* next; // 后继 Node(const T& val) : data(val), prev(nullptr), next(nullptr) {} }; // 双向链表模板类 template<typename T> class DoubleList { private: Node<T>* head; // 头结点 Node<T>* tail; // 尾结点 public: DoubleList(); ~DoubleList(); // 基础接口声明 void push_back(const T& val); void pop_back(); void clear(); // 迭代器、排序等接口自行拓展 };核心注意点
析构函数必须遍历释放所有节点，防止内存泄漏；
双向链表增删时，必须同步修改
prev和next两个指针，防止断链；迭代器嵌套在类内部，设置为
public对外访问。
九、知识点总结 & 重点梳理
容器选型核心
随机访问、尾部操作 →
vector；任意位置频繁增删 →list。
迭代器
本质：封装的指针，前闭后开区间；
失效规则：vector 扩容 / 中间操作全失效，list 仅删除节点迭代器失效。
仿函数
重载
()运算符，用于自定义排序、条件筛选，是 STL 算法核心组件。模板约束
容器存储类型必须支持拷贝，含指针成员优先深拷贝或存储指针。
C++11 优化点
emplace原地构造、范围 for、forward_list单向链表，均为性能 / 语法优化。手写重点
带头双向链表 + 自定义迭代器，是数据结构实操高频大题。