当前位置：首页 > news >正文

C++ vector底层实现大揭秘

news 2026/4/25 10:20:52

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{事务回滚} $$