C++ STL 之 vector 与 list 深度解析

C++ STL 之 vector 与 list 深度解析：从使用到模拟实现

前言

C++ STL（标准模板库）提供了多种高效的容器，其中 vector 和 list 是最常用、也最具代表性的两个序列式容器。它们分别基于动态数组和双向链表实现，适用于不同的业务场景。本文将带你从基础使用到底层模拟，全面掌握这两个容器的核心知识。

一、vector 详解

1.1 vector 基本介绍

vector 是一个动态数组，支持随机访问，在尾部插入和删除元素效率高，但在中间或头部插入删除元素需要搬移数据，效率较低。

1.2 vector 的构造方式

vector<int> v1; // 无参构造
vector<int> v2(5, 10); // 5个值为10的元素
vector<int> v3(v2); // 拷贝构造
vector<int> v4(v2.begin(), v2.end()); // 迭代器区间构造

1.3 迭代器的使用

vector<int>::iterator it = v.begin();
while (it != v.end()) {
cout << *it << " ";
++it;
}

1.4 容量相关接口

扩容机制：VS 下约为 1.5 倍，g++ 下为 2 倍。

1.5 增删查改操作

v.push_back(1); // 尾插
v.pop_back(); // 尾删
v.insert(pos, val); // 指定位置插入
v.erase(pos); // 删除指定位置
v[0] = 100; // 下标访问

1.6 迭代器失效问题

• 扩容操作（如 reserve、push_back）可能导致原空间被释放，迭代器失效。
• 删除操作（如 erase）会导致被删元素及其后迭代器失效。

// 错误示例
auto it = v.begin();
while (it != v.end()) {
if (*it % 2 == 0) v.erase(it); // it 失效
++it;
}

// 正确写法
while (it != v.end()) {
if (*it % 2 == 0) it = v.erase(it);
else ++it;
}

1.7 vector 的模拟实现关键点

• 使用动态数组 _start、_finish、_end_of_storage 三个指针管理空间。
• 实现 reserve、resize、push_back、pop_back、insert、erase 等接口。
• 注意深拷贝问题：不能使用 memcpy 拷贝自定义类型对象，否则会引发浅拷贝导致的资源泄漏或崩溃。

二、list 详解

2.1 list 基本介绍

list 是带头结点的双向循环链表，不支持随机访问，但在任意位置插入和删除元素非常高效。

2.2 list 的构造方式

list<int> l1; // 空链表
list<int> l2(5, 10); // 5个值为10的节点
list<int> l3(l2); // 拷贝构造
list<int> l4(l2.begin(), l2.end()); // 迭代器区间构造

2.3 迭代器的使用

list<int>::iterator it = l.begin();
while (it != l.end()) {
cout << *it << " ";
++it;
}

2.4 常用操作接口

2.5 迭代器失效问题

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

auto it = l.begin();
while (it != l.end()) {
l.erase(it++); // 正确写法
}

2.6 list 的模拟实现关键点

• 节点结构：prev、next、data。
• 实现正向迭代器和反向迭代器（复用正向迭代器）。
• 实现 insert、erase、push_back 等接口。

三、vector 与 list 的对比

四、总结

• vector 和 list 是 STL 中最基础也最重要的两个序列容器。
• 理解它们的底层结构和迭代器行为，是写出高效、安全 C++ 代码的关键。
• 在实际开发中，应根据访问频率、插入删除位置等因素选择合适的容器。

建议：多做 OJ 练习，如“杨辉三角”、“只出现一次的数字”、“删除有序数组重复项”等，巩固对 vector 的使用。

希望这篇博客能帮助你更清晰地理解 vector和 list 的原理与使用。欢迎收藏、点赞、转发，让更多人受益！