本篇核心知识链表头结点设计、STL 容器对比vector /list/forward_list、迭代器原理与使用、迭代器失效、仿函数、容器常用算法、C11 新特性、双向链表手写要求、深浅拷贝与容器类型适配一、链表头结点详解概念头结点是链表额外增设的虚拟节点不存储有效业务数据专门用于统一链表操作逻辑分为带头结点和不带头结点两种设计方案。特性不带头结点首元节点首节点直接存储有效数据头指针指向第一个数据节点缺陷在链表头部做插入、删除操作时必须单独判断边界代码冗余、易出错。带头结点主流设计额外开辟一块节点内存无有效数据优势所有位置的增删操作逻辑完全统一无需特殊处理头部边界代码简洁健壮额外开销多占用一个节点的内存空间属于空间换代码稳定性。适用场景工程开发、笔试面试均优先使用带头结点链表。代码示例两种链表结构对比// 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 单向链表C11 新增概念底层为单向链表仅保留后继指针。特性内存开销比 list 更小仅支持单向遍历功能精简适用于极简场景。容器选型原则重点频繁查询、尾部增删极少中间操作 → 优先使用vector频繁在任意位置插入 / 删除查询少 → 优先使用list追求极致内存占用、仅单向遍历 → 使用forward_list。代码示例 基础使用#include vector #include list using namespace std; int main() { // vector 用法顺序表 vectorint vec; vec.push_back(10); // 尾部添加效率高 vec.pop_back(); // 尾部删除效率高 // list 用法双向链表 listint 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() { listint lst {1,2,3,4,5}; // 定义迭代器 listint it lst.begin(); // 遍历it ! end 为终止条件 while(it ! lst.end()) { cout *it ; // * 解引用获取元素值 it; } return 0; }2. C11 范围 for 遍历概念底层依旧依赖迭代器语法更简洁适合完整遍历容器。listint lst {1,2,3,4,5}; // 只读遍历 for(auto val : lst) cout val ; // 可修改遍历加引用 for(auto val : lst) val 1;3. 迭代器失效概念容器操作后原有迭代器指向的内存失效继续使用会引发野指针、程序崩溃。不同容器失效规则vector顺序表中间插入 / 删除、触发扩容 → 所有迭代器全部失效原因元素整体挪动 / 内存重新分配原地址作废。list双向链表仅被删除节点对应的迭代器失效其余迭代器保持有效原因仅修改指针指向其他节点内存不变。解决方案执行增删操作后重新获取迭代器使用list::erase时接收返回值返回下一个有效迭代器。listint lst {1,2,3}; auto it lst.begin(); it lst.erase(it); // 接收返回值避免迭代器失效拓展手写容器链表 / 顺序表时需要自行封装迭代器类核心就是重载指针相关运算符。四、模板类与容器类型适配概念STL 容器均为类模板模板参数指定容器存储的数据类型模板对存储类型有隐性要求。特性模板语法templatetypename TT为通用类型占位符类型约束存入容器的类型必须支持拷贝构造容器添加元素时会拷贝对象自定义类若包含指针成员必须实现深拷贝否则出现内存错误推荐用法存储自定义类型时优先使用指针规避浅拷贝问题。代码示例 模板与类型约束// 普通类型天然支持拷贝 listint lst1; // 自定义结构体需保证拷贝合法 struct Person { string name; int age; }; listPerson lst2; // 存储指针无需考虑深浅拷贝 listPerson* 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() { listHero 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底层排序算法为归并排序专为链表结构优化顺序表常用快速排序二者底层实现不同。七、C11 容器新特性补充1. forward_list 单向链表C11 新增精简版链表仅单向遍历内存开销更小功能少于 list。2. emplace 系列函数概念emplace_back/emplace_front直接在容器内存原地构造对象替代push_back。特性push_back先创建对象再拷贝到容器调用拷贝构造emplace直接调用构造函数原地生成省去拷贝开销效率更高。listHero lst; lst.emplace(射手,9,900); // 原地构造无拷贝八、手写双向链表综合实战要求整体设计要求采用带头、带尾结点双向链表统一边界操作节点结构数据域 前驱指针 prev 后继指针 next封装为类模板适配任意数据类型内部封装迭代器类内嵌套实现实现基础接口增、删、改、查、遍历、排序。节点基础结构代码templatetypename T struct Node { T data; NodeT* prev; // 前驱 NodeT* next; // 后继 Node(const T val) : data(val), prev(nullptr), next(nullptr) {} }; // 双向链表模板类 templatetypename T class DoubleList { private: NodeT* head; // 头结点 NodeT* tail; // 尾结点 public: DoubleList(); ~DoubleList(); // 基础接口声明 void push_back(const T val); void pop_back(); void clear(); // 迭代器、排序等接口自行拓展 };核心注意点析构函数必须遍历释放所有节点防止内存泄漏双向链表增删时必须同步修改prev和next两个指针防止断链迭代器嵌套在类内部设置为public对外访问。九、知识点总结 重点梳理容器选型核心随机访问、尾部操作 →vector任意位置频繁增删 →list。迭代器本质封装的指针前闭后开区间失效规则vector 扩容 / 中间操作全失效list 仅删除节点迭代器失效。仿函数重载()运算符用于自定义排序、条件筛选是 STL 算法核心组件。模板约束容器存储类型必须支持拷贝含指针成员优先深拷贝或存储指针。C11 优化点emplace原地构造、范围 for、forward_list单向链表均为性能 / 语法优化。手写重点带头双向链表 自定义迭代器是数据结构实操高频大题。
C/C++ 数据结构（四）链表与STL容器
发布时间：2026/6/14 3:01:57
本篇核心知识链表头结点设计、STL 容器对比vector /list/forward_list、迭代器原理与使用、迭代器失效、仿函数、容器常用算法、C11 新特性、双向链表手写要求、深浅拷贝与容器类型适配一、链表头结点详解概念头结点是链表额外增设的虚拟节点不存储有效业务数据专门用于统一链表操作逻辑分为带头结点和不带头结点两种设计方案。特性不带头结点首元节点首节点直接存储有效数据头指针指向第一个数据节点缺陷在链表头部做插入、删除操作时必须单独判断边界代码冗余、易出错。带头结点主流设计额外开辟一块节点内存无有效数据优势所有位置的增删操作逻辑完全统一无需特殊处理头部边界代码简洁健壮额外开销多占用一个节点的内存空间属于空间换代码稳定性。适用场景工程开发、笔试面试均优先使用带头结点链表。代码示例两种链表结构对比// 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 单向链表C11 新增概念底层为单向链表仅保留后继指针。特性内存开销比 list 更小仅支持单向遍历功能精简适用于极简场景。容器选型原则重点频繁查询、尾部增删极少中间操作 → 优先使用vector频繁在任意位置插入 / 删除查询少 → 优先使用list追求极致内存占用、仅单向遍历 → 使用forward_list。代码示例 基础使用#include vector #include list using namespace std; int main() { // vector 用法顺序表 vectorint vec; vec.push_back(10); // 尾部添加效率高 vec.pop_back(); // 尾部删除效率高 // list 用法双向链表 listint 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() { listint lst {1,2,3,4,5}; // 定义迭代器 listint it lst.begin(); // 遍历it ! end 为终止条件 while(it ! lst.end()) { cout *it ; // * 解引用获取元素值 it; } return 0; }2. C11 范围 for 遍历概念底层依旧依赖迭代器语法更简洁适合完整遍历容器。listint lst {1,2,3,4,5}; // 只读遍历 for(auto val : lst) cout val ; // 可修改遍历加引用 for(auto val : lst) val 1;3. 迭代器失效概念容器操作后原有迭代器指向的内存失效继续使用会引发野指针、程序崩溃。不同容器失效规则vector顺序表中间插入 / 删除、触发扩容 → 所有迭代器全部失效原因元素整体挪动 / 内存重新分配原地址作废。list双向链表仅被删除节点对应的迭代器失效其余迭代器保持有效原因仅修改指针指向其他节点内存不变。解决方案执行增删操作后重新获取迭代器使用list::erase时接收返回值返回下一个有效迭代器。listint lst {1,2,3}; auto it lst.begin(); it lst.erase(it); // 接收返回值避免迭代器失效拓展手写容器链表 / 顺序表时需要自行封装迭代器类核心就是重载指针相关运算符。四、模板类与容器类型适配概念STL 容器均为类模板模板参数指定容器存储的数据类型模板对存储类型有隐性要求。特性模板语法templatetypename TT为通用类型占位符类型约束存入容器的类型必须支持拷贝构造容器添加元素时会拷贝对象自定义类若包含指针成员必须实现深拷贝否则出现内存错误推荐用法存储自定义类型时优先使用指针规避浅拷贝问题。代码示例 模板与类型约束// 普通类型天然支持拷贝 listint lst1; // 自定义结构体需保证拷贝合法 struct Person { string name; int age; }; listPerson lst2; // 存储指针无需考虑深浅拷贝 listPerson* 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() { listHero 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底层排序算法为归并排序专为链表结构优化顺序表常用快速排序二者底层实现不同。七、C11 容器新特性补充1. forward_list 单向链表C11 新增精简版链表仅单向遍历内存开销更小功能少于 list。2. emplace 系列函数概念emplace_back/emplace_front直接在容器内存原地构造对象替代push_back。特性push_back先创建对象再拷贝到容器调用拷贝构造emplace直接调用构造函数原地生成省去拷贝开销效率更高。listHero lst; lst.emplace(射手,9,900); // 原地构造无拷贝八、手写双向链表综合实战要求整体设计要求采用带头、带尾结点双向链表统一边界操作节点结构数据域 前驱指针 prev 后继指针 next封装为类模板适配任意数据类型内部封装迭代器类内嵌套实现实现基础接口增、删、改、查、遍历、排序。节点基础结构代码templatetypename T struct Node { T data; NodeT* prev; // 前驱 NodeT* next; // 后继 Node(const T val) : data(val), prev(nullptr), next(nullptr) {} }; // 双向链表模板类 templatetypename T class DoubleList { private: NodeT* head; // 头结点 NodeT* tail; // 尾结点 public: DoubleList(); ~DoubleList(); // 基础接口声明 void push_back(const T val); void pop_back(); void clear(); // 迭代器、排序等接口自行拓展 };核心注意点析构函数必须遍历释放所有节点防止内存泄漏双向链表增删时必须同步修改prev和next两个指针防止断链迭代器嵌套在类内部设置为public对外访问。九、知识点总结 重点梳理容器选型核心随机访问、尾部操作 →vector任意位置频繁增删 →list。迭代器本质封装的指针前闭后开区间失效规则vector 扩容 / 中间操作全失效list 仅删除节点迭代器失效。仿函数重载()运算符用于自定义排序、条件筛选是 STL 算法核心组件。模板约束容器存储类型必须支持拷贝含指针成员优先深拷贝或存储指针。C11 优化点emplace原地构造、范围 for、forward_list单向链表均为性能 / 语法优化。手写重点带头双向链表 自定义迭代器是数据结构实操高频大题。
