C++ vector容器底层深度剖析与模拟实现
1. 底层数据结构
vector的底层实现是一个动态数组，核心由三个指针控制：
start：指向数组首元素finish：指向最后一个元素的下一个位置end_of_storage：指向数组预留空间的末尾
存储关系满足： $$ \text{size} = \text{finish} - \text{start} $$ $$ \text{capacity} = \text{end_of_storage} - \text{start} $$
2. 关键特性
- 连续存储：元素在内存中连续排列，支持$O(1)$随机访问
- 动态扩容：当$\text{size} == \text{capacity}$时触发扩容
- 新容量 = 旧容量 $\times 2$ (常见策略)
- 过程：分配新内存 $\rightarrow$ 拷贝元素 $\rightarrow$ 释放旧内存
- 迭代器失效：插入/删除操作可能导致迭代器失效
3. 核心操作时间复杂度
| 操作 | 时间复杂度 |
|---|---|
push_back() | 均摊$O(1)$ |
pop_back() | $O(1)$ |
operator[] | $O(1)$ |
insert() | $O(n)$ |
4. 模拟实现代码
template <typename T> class Vector { private: T* _start = nullptr; // 数组起始位置 T* _finish = nullptr; // 最后一个元素的下一个位置 T* _end_of_storage = nullptr; // 内存块末尾 void reallocate(size_t new_cap) { T* new_start = new T[new_cap]; size_t sz = size(); // 拷贝元素 for (size_t i = 0; i < sz; ++i) { new_start[i] = _start[i]; } // 释放旧内存 delete[] _start; // 更新指针 _start = new_start; _finish = _start + sz; _end_of_storage = _start + new_cap; } public: // 构造函数 Vector() = default; explicit Vector(size_t n, const T& val = T()) { _start = new T[n]; _finish = _start + n; _end_of_storage = _finish; for (size_t i = 0; i < n; ++i) { _start[i] = val; } } // 析构函数 ~Vector() { delete[] _start; _start = _finish = _end_of_storage = nullptr; } // 容量操作 size_t size() const { return _finish - _start; } size_t capacity() const { return _end_of_storage - _start; } bool empty() const { return _start == _finish; } // 元素访问 T& operator[](size_t pos) { return _start[pos]; } const T& operator[](size_t pos) const { return _start[pos]; } T& front() { return *_start; } T& back() { return *(_finish - 1); } // 内存管理 void reserve(size_t new_cap) { if (new_cap <= capacity()) return; reallocate(new_cap); } void resize(size_t new_size, const T& val = T()) { if (new_size < size()) { _finish = _start + new_size; } else if (new_size > size()) { if (new_size > capacity()) { reallocate(new_size); } for (T* p = _finish; p != _start + new_size; ++p) { *p = val; } _finish = _start + new_size; } } // 元素操作 void push_back(const T& val) { if (_finish == _end_of_storage) { reallocate(capacity() == 0 ? 1 : capacity() * 2); } *_finish = val; ++_finish; } void pop_back() { if (!empty()) --_finish; } void clear() { _finish = _start; } };5. 关键实现细节
扩容策略：
- 初始插入触发首次分配（通常为1元素空间）
- 后续扩容按指数增长（$2^n$），保证均摊时间复杂度为$O(1)$
- 扩容成本：$O(n)$拷贝 + $O(n)$析构
类型安全：
- 通过模板支持泛型
- 构造/析构时自动调用元素类型的构造函数和析构函数
异常安全：
- 实际STL实现需处理以下情况： $$ \text{内存分配失败} \rightarrow \text{std::bad_alloc} $$ $$ \text{元素拷贝抛出异常} \rightarrow \text{事务回滚} $$
6. 优化建议
- 移动语义：C++11后应实现移动构造/赋值函数
- emplace操作：直接原地构造元素，避免拷贝
- 自定义分配器：支持特殊内存管理策略
- SSO优化：对小对象使用栈缓冲区（如MSVC实现）
注：完整STL vector还需实现迭代器、插入删除操作、异常安全保证等特性，本实现聚焦核心机制。实际开发中建议直接使用标准库vector。
