C++算法
C++ STL Vector 模拟实现与核心原理解析
C++ 标准库 vector 的模拟实现，涵盖动态数组内存管理、三指针模型、深拷贝机制、迭代器失效处理及扩容策略优化。通过手写代码深入理解 STL 设计哲学、模板编程与异常安全原则，解决面试中常见的底层原理问题。
C++ 标准库 vector 的模拟实现，涵盖动态数组内存管理、三指针模型、深拷贝机制、迭代器失效处理及扩容策略优化。通过手写代码深入理解 STL 设计哲学、模板编程与异常安全原则，解决面试中常见的底层原理问题。
在 C++ 编程中，vector 是最常用也最重要的容器之一。作为一个动态数组，它结合了数组的随机访问效率和动态扩容的灵活性。
#pragma once
#include <assert.h>
#include <list>
#include <string>
namespace bit {
template <class T>
class vector {
public:
typedef T* iterator;
typedef const T* const_iterator;
// 构造函数族
vector() = default;
vector(const vector<T>& v);
template <class InputIterator>
vector(InputIterator first, InputIterator last);
vector(size_t n, const T& val = T());
// 析构函数
~vector();
// 赋值运算符
vector<T>& operator=(vector<T> v);
// 迭代器
iterator begin();
iterator end();
const_iterator begin() const;
const_iterator end() const;
// 容量操作
void reserve(size_t n);
void resize(size_t n, T val = T());
size_t size() const;
size_t capacity() const;
bool empty() const;
void clear();
// 元素访问
T& operator[](size_t i);
const T& operator[](size_t i) const;
// 修改操作
void push_back(const T& x);
void pop_back();
iterator insert(iterator pos, const T& x);
void erase(iterator pos);
// 工具函数
void swap(vector<T>& v);
private:
// 核心三指针
iterator _start = nullptr; // 指向数据起始
iterator _finish = nullptr; // 指向最后一个有效元素的下一个位置
iterator _end_of_storage = nullptr; // 指向分配空间的末尾
};
}
这是 vector 实现中最精妙的设计之一：
// 内存布局示意图
_start ---------->|0|1|2|3|...||||---有效数据区---|---未用空间---|
_finish -----------^^
_end_of_storage -------------------^
// 计算方法
size() = _finish - _start // 有效元素个数
capacity() = _end_of_storage - _start // 总容量
设计优点：
_finish == _end_of_storage）vector() = default; // C++11 强制生成默认构造
与传统写法的对比：
// 传统写法
vector():_start(nullptr),_finish(nullptr),_end_of_storage(nullptr){}
// 现代写法（推荐）
vector() = default; // 结合成员变量初始化
vector(const vector<T>& v) {
reserve(v.size()); // 第一步：预分配足够空间
for (auto& e : v) { // 第二步：深拷贝每个元素
push_back(e);
}
}
template <class InputIterator>
vector(InputIterator first, InputIterator last) {
while (first != last) { // 关键：使用!=而不是<
push_back(*first); // 解引用获取元素值
++first;
}
}
设计亮点：
!= 而不是 <：list 等容器的迭代器不支持 < 操作InputIterator：可以接受 vector、list、set 等任何容器的迭代器vector(size_t n, const T& val = T()) {
reserve(n); // 预分配空间
for (size_t i = 0; i < n; i++) {
push_back(val); // 插入 n 个 val
}
}
注意：这里使用 size_t 而不是 int，避免与迭代器构造函数产生歧义。
// 错误实现：使用 memcpy
void reserve(size_t n) {
if (n > capacity()) {
size_t old_size = size();
T* tmp = new T[n];
memcpy(tmp, _start, old_size * sizeof(T)); // 问题所在！
delete[] _start;
_start = tmp;
// ...
}
}
问题分析： 当 T 是 string、vector 等包含动态内存的类时：
memcpy 只复制了 string 对象的指针，没有复制字符串内容void reserve(size_t n) {
if (n > capacity()) {
size_t old_size = size();
T* tmp = new T[n]; // 分配新空间
// 关键：循环深拷贝
for (size_t i = 0; i < old_size; i++) {
tmp[i] = _start[i]; // 调用 T::operator=，进行深拷贝
}
delete[] _start; // 释放旧空间（调用每个元素的析构函数）
// 更新指针
_start = tmp;
_finish = tmp + old_size;
_end_of_storage = tmp + n;
}
}
工作原理：
tmp[i] = _start[i] 实际调用 T::operator=(const T&)iterator insert(iterator pos, const T& x) {
// 1. 参数检查
assert(pos >= _start && pos <= _finish);
// 2. 处理可能的扩容（迭代器失效场景）
if (_finish == _end_of_storage) {
// 关键：保存相对偏移量
size_t len = pos - _start; // 计算 pos 相对于_start 的位置
// 扩容操作（会改变_start 的指向）
reserve(capacity() == 0 ? 4 : capacity() * 2);
// 重新计算 pos 在新空间的位置
pos = _start + len; // 修正迭代器
}
// 3. 移动元素
iterator end = _finish - 1;
while (end >= pos) {
*(end + 1) = *end; // 向后移动
--end;
}
// 4. 插入元素
*pos = x;
++_finish;
return pos; // 返回新的有效迭代器
}
// 错误写法：迭代器失效后继续使用
for (auto it = v.begin(); it != v.end(); ++it) {
if (condition(*it)) {
v.erase(it); // it 失效后，下一轮++it 是未定义行为！
}
}
// 正确写法：接收 erase 的返回值
auto it = v.begin();
while (it != v.end()) {
if (condition(*it)) {
it = v.erase(it); // erase 返回下一个有效迭代器
} else {
++it; // 只有不删除时才手动递增
}
}
| 操作 | 是否导致迭代器失效 | 原因 | 解决方案 |
|---|---|---|---|
| push_back | 可能失效 | 扩容时所有迭代器失效 | 扩容后重新获取迭代器 |
| insert | 一定失效 | 扩容或元素移动 | 接收 insert 的返回值 |
| erase | 一定失效 | 元素移动 | 接收 erase 的返回值 |
| reserve | 一定失效 | 内存重新分配 | 避免在 reserve 后使用旧迭代器 |
// 传统写法：需要检查自赋值
vector<T>& operator=(const vector<T>& v) {
if (this != &v) { // 1. 检查自赋值
delete[] _start; // 2. 释放旧空间
// 3. 分配新空间并深拷贝
_start = new T[v.capacity()];
// ... 拷贝逻辑
// 4. 更新指针
_finish = _start + v.size();
_end_of_storage = _start + v.capacity();
}
return *this;
}
缺点：
// 现代写法：优雅且安全
vector<T>& operator=(vector<T> v) { // 关键：传值，调用拷贝构造
swap(v); // 交换资源
return *this; // v 是局部变量，离开作用域自动析构
}
void swap(vector<T>& v) {
std::swap(_start, v._start);
std::swap(_finish, v._finish);
std::swap(_end_of_storage, v._end_of_storage);
}
优点分析：
void push_back(const T& x) {
// 检查是否需要扩容
if (_finish == _end_of_storage) {
// 成倍扩容策略
size_t new_capacity = capacity() == 0 ? 4 : capacity() * 2;
reserve(new_capacity);
}
// 插入元素
*_finish = x;
++_finish;
}
| 策略 | 扩容因子 | 均摊复杂度 | 空间浪费 | 适用场景 |
|---|---|---|---|---|
| 固定大小 | +N | O(n) | 小 | 内存受限系统 |
| 成倍扩容 | ×2 | O(1) | 中等 | 通用场景（STL 采用） |
| 黄金比例 | ×1.5 | O(1) | 较小 | 内存敏感场景 |
STL 选择×2 的原因：
// 使用前预分配，避免多次扩容
vector<int> v;
v.reserve(1000); // 一次性分配足够空间
for (int i = 0; i < 1000; ++i) {
v.push_back(i); // 避免多次扩容拷贝
}
// 1. 移动语义支持（C++11）
vector(vector&& v) noexcept;
vector& operator=(vector&& v) noexcept;
void push_back(T&& x);
// 2. 列表初始化（C++11）
vector(std::initializer_list<T> il);
// 3. 原位构造（C++11）
template <class... Args>
void emplace_back(Args&&... args);
// 4. 数据访问（C++11）
T* data() noexcept;
const T* data() const noexcept;
答：vector 使用动态数组实现，通过三个指针（start、finish、end_of_storage）管理内存，支持随机访问和动态扩容。
答：当 size == capacity 时，vector 会重新分配一块更大的内存（通常是原来的 2 倍），将旧元素拷贝到新空间，然后释放旧空间。
答：迭代器失效指迭代器指向的元素位置变得无效。vector 的 insert、erase、push_back（扩容时）、reserve 等操作都可能导致迭代器失效。
答：浅拷贝只复制指针，深拷贝复制指针指向的内容。vector 必须实现深拷贝，否则多个 vector 对象会共享同一块内存，导致双重释放等问题。
答：在尾部操作是 O(1)，在中间或头部操作是 O(n)，因为需要移动后续元素。
| 操作 | 时间复杂度 | 空间复杂度 | 备注 |
|---|---|---|---|
| 随机访问 | O(1) | O(1) | 支持下标访问 |
| 尾部插入 | 均摊 O(1) | O(n) | 可能触发扩容 |
| 中间插入 | O(n) | O(n) | 需要移动元素 |
| 查找 | O(n) | O(1) | 无序查找 |
通过手写 vector 的实现，我们不仅学会了如何实现一个动态数组容器，更重要的是：
vector 的实现是 C++ 学习的重要里程碑，它融合了 C++ 的多个核心特性：模板、异常、RAII、迭代器等。希望这篇文章能帮助你深入理解 vector，并在实际编程中更加得心应手地使用它。
微信公众号「极客日志」，在微信中扫描左侧二维码关注。展示文案：极客日志 zeeklog
使用加密算法（如AES、TripleDES、Rabbit或RC4）加密和解密文本明文。 在线工具，加密/解密文本在线工具，online
将字符串编码和解码为其 Base64 格式表示形式即可。 在线工具，Base64 字符串编码/解码在线工具，online
将字符串、文件或图像转换为其 Base64 表示形式。 在线工具，Base64 文件转换器在线工具，online
将 Markdown（GFM）转为 HTML 片段，浏览器内 marked 解析；与 HTML转Markdown 互为补充。 在线工具，Markdown转HTML在线工具，online
将 HTML 片段转为 GitHub Flavored Markdown，支持标题、列表、链接、代码块与表格等；浏览器内处理，可链接预填。 在线工具，HTML转Markdown在线工具，online
通过删除不必要的空白来缩小和压缩JSON。 在线工具，JSON 压缩在线工具，online