1. 从零开始理解vector的底层架构
在C++标准库中,vector是最常用的动态数组容器之一。作为一名长期使用C++进行开发的工程师,我经常需要深入理解其底层实现原理。今天我们就来拆解SGI版本的vector实现,这个版本相比其他实现更加清晰易懂,非常适合学习。
首先我们来看vector最核心的三个成员变量,它们构成了vector的骨架:
cpp复制template <class T>
class vector {
private:
T* _start; // 指向数组首元素
T* _finish; // 指向最后一个元素的下一个位置
T* _end_of_storage; // 指向存储空间末尾的下一个位置
};
这三个指针变量各司其职:
_start:永远指向数组的第一个元素,相当于数组名_finish:指向最后一个有效元素的下一个位置,所以_finish - _start就是当前元素个数_end_of_storage:指向已分配内存空间的末尾,表示当前容器的最大容量
这种设计有几个精妙之处:
- 通过指针运算可以快速获取大小和容量:
size() = _finish - _start,capacity() = _end_of_storage - _start - 迭代器就是普通指针,不需要额外封装
- 内存管理更加直观,扩容时只需要关注这三个指针
提示:理解这三个指针的关系是掌握vector实现的关键。可以把它们想象成书架的标记:
_start是第一个书架,_finish是最后一本有书的书架,_end_of_storage是整个书架的尽头。
2. 迭代器实现解析
2.1 非const迭代器
vector的迭代器本质上就是原生指针,这也是vector被称为"伪容器"的原因之一。它的迭代器实现极其简单:
cpp复制typedef T* iterator;
iterator begin() { return _start; }
iterator end() { return _finish; }
这种设计带来了极高的效率,因为:
- 没有额外的封装层,直接操作指针
- 与C风格数组完全兼容
- 支持所有指针运算(++, --, +, -等)
2.2 const迭代器
为了保证const安全性,我们需要提供const版本的迭代器:
cpp复制typedef const T* const_iterator;
const_iterator begin() const { return _start; }
const_iterator end() const { return _finish; }
const迭代器的关键点:
- 不能通过const迭代器修改元素值
- 可以与非const迭代器共存,编译器会根据上下文自动选择
- 所有const成员函数都应返回const迭代器
在实际工程中,我经常看到开发者忽略const迭代器的实现,这会导致很多const正确性问题。记住:良好的const习惯是高质量C++代码的标志。
3. 构造函数的实现艺术
3.1 无参构造函数
无参构造是最简单的构造函数,创建一个空vector:
cpp复制vector()
: _start(nullptr)
, _finish(nullptr)
, _end_of_storage(nullptr)
{}
这里有几个值得注意的点:
- 所有指针初始化为nullptr,表示空容器
- 不分配任何内存,遵循"延迟分配"原则
- size()和capacity()都为0
经验:现代C++实践中,无参构造函数应该尽量轻量,避免不必要的内存分配。
3.2 迭代器区间构造
这是一个非常强大的构造函数,可以从任何迭代器范围构造vector:
cpp复制template <class InputIterator>
vector(InputIterator first, InputIterator last) {
// 计算元素数量
size_t n = distance(first, last);
// 分配空间
_start = new T[n];
_finish = _start + n;
_end_of_storage = _finish;
// 拷贝元素
T* cur = _start;
while (first != last) {
*cur++ = *first++;
}
}
这个构造函数的精妙之处在于:
- 它是模板函数,可以接受任何类型的迭代器(数组指针、其他容器的迭代器等)
- 使用distance计算元素数量,避免多次遍历
- 一次性分配足够空间,避免重复扩容
在实际项目中,我经常用这个构造函数在不同容器间转换数据,非常方便。
3.3 n个值构造
这个构造函数有两个重载版本,必须同时存在:
cpp复制// 版本1:n个默认值
vector(size_t n, const T& value = T()) {
_start = new T[n];
_finish = _start + n;
_end_of_storage = _finish;
for (size_t i = 0; i < n; ++i) {
_start[i] = value;
}
}
// 版本2:防止与迭代器版本冲突
vector(int n, const T& value = T()) {
_start = new T[n];
_finish = _start + n;
_end_of_storage = _finish;
for (int i = 0; i < n; ++i) {
_start[i] = value;
}
}
为什么需要两个版本?因为当T是int时,vector(5, 2)会与迭代器版本产生歧义。编译器无法确定5和2是迭代器还是n和value。第二个版本专门处理int参数,解决了这个问题。
4. 拷贝控制成员
4.1 拷贝构造函数
拷贝构造需要深拷贝,避免多个vector共享同一块内存:
cpp复制vector(const vector<T>& v) {
// 分配相同大小的空间
_start = new T[v.capacity()];
_finish = _start + v.size();
_end_of_storage = _start + v.capacity();
// 逐个拷贝元素
for (size_t i = 0; i < v.size(); ++i) {
_start[i] = v._start[i];
}
}
关键点:
- 必须分配新内存,不能直接复制指针
- 要拷贝capacity而不仅仅是size
- 元素需要逐个拷贝,调用T的拷贝赋值运算符
4.2 赋值运算符
现代C++中,赋值运算符通常采用"拷贝+交换"技术:
cpp复制vector<T>& operator=(vector<T> v) {
swap(v);
return *this;
}
void swap(vector<T>& v) {
std::swap(_start, v._start);
std::swap(_finish, v._finish);
std::swap(_end_of_storage, v._end_of_storage);
}
这种实现有几个优势:
- 参数是值传递,自动调用拷贝构造函数
- 交换操作非常高效,只是交换指针
- 异常安全,所有操作要么全完成,要么全不完成
- 旧资源会随着临时对象v的析构自动释放
经验:这种"拷贝+交换"技术适用于大多数资源管理类,是C++中的惯用法。
4.3 析构函数
析构函数负责释放所有资源:
cpp复制~vector() {
if (_start) {
delete[] _start;
_start = _finish = _end_of_storage = nullptr;
}
}
注意事项:
- 检查_start是否为null,避免重复释放
- 使用delete[]而不是delete,因为分配的是数组
- 将指针置为nullptr是个好习惯,可以防止悬空指针
5. 容量相关操作
5.1 size和capacity
这两个基础函数通过指针运算实现:
cpp复制size_t size() const { return _finish - _start; }
size_t capacity() const { return _end_of_storage - _start; }
bool empty() const { return _start == _finish; }
5.2 reserve实现
reserve用于预分配内存,避免频繁扩容:
cpp复制void reserve(size_t n) {
if (n > capacity()) {
// 分配新空间
T* new_start = new T[n];
// 计算当前元素数量
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 + n;
}
}
实现细节:
- 只有请求的容量大于当前容量时才处理
- 需要手动拷贝元素,因为T可能是复杂类型
- 必须先分配新空间再释放旧空间,保证异常安全
- 最后更新所有指针
5.3 resize实现
resize用于调整元素数量:
cpp复制void resize(size_t n, const T& value = T()) {
if (n < size()) {
// 缩小size
_finish = _start + n;
} else if (n > size()) {
// 需要扩容
if (n > capacity()) {
reserve(n);
}
// 填充新元素
while (_finish != _start + n) {
*_finish++ = value;
}
}
}
注意事项:
- 缩小size时只需要移动_finish指针
- 扩大size时可能需要扩容
- 新元素使用提供的value初始化,默认为T()
- 必须考虑所有三种情况:n < size,size < n <= capacity,n > capacity
6. 元素访问操作
6.1 operator[]实现
提供const和非const两个版本:
cpp复制T& operator[](size_t pos) {
assert(pos < size());
return _start[pos];
}
const T& operator[](size_t pos) const {
assert(pos < size());
return _start[pos];
}
关键点:
- 使用assert检查边界,在调试时捕获越界访问
- 非const版本返回引用,允许修改元素
- const版本返回const引用,保证const安全
6.2 front和back
这两个函数提供首尾元素的快捷访问:
cpp复制T& front() {
assert(!empty());
return *_start;
}
const T& front() const {
assert(!empty());
return *_start;
}
T& back() {
assert(!empty());
return *(_finish - 1);
}
const T& back() const {
assert(!empty());
return *(_finish - 1);
}
7. 修改操作实现
7.1 push_back实现
push_back是vector最常用的操作之一:
cpp复制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;
}
扩容策略分析:
- 初始容量为0时,分配4个元素空间
- 之后每次按2倍扩容,这是时间和空间的平衡点
- 扩容操作代价高昂,应该尽量避免频繁扩容
经验:在知道元素数量的情况下,提前reserve可以显著提高性能。
7.2 pop_back实现
pop_back相对简单:
cpp复制void pop_back() {
assert(!empty());
--_finish;
}
注意:
- 必须检查非空,否则会下溢
- 只是移动指针,不会释放内存
- 被移除元素的析构函数会被调用
7.3 insert实现
insert在指定位置插入元素:
cpp复制iterator insert(iterator pos, const T& x) {
assert(pos >= begin() && pos <= end());
if (_finish == _end_of_storage) {
// 扩容会导致迭代器失效,需要保存偏移量
size_t offset = pos - _start;
reserve(capacity() == 0 ? 4 : capacity() * 2);
pos = _start + offset; // 重新计算pos
}
// 移动元素
iterator end = _finish;
while (end > pos) {
*end = *(end - 1);
--end;
}
// 插入新元素
*pos = x;
++_finish;
return pos;
}
实现细节:
- 检查pos的有效性
- 扩容前保存偏移量,因为扩容会使所有迭代器失效
- 从后向前移动元素,避免覆盖
- 返回指向新元素的迭代器,符合STL惯例
7.4 erase实现
erase移除指定位置的元素:
cpp复制iterator erase(iterator pos) {
assert(pos >= begin() && pos < end());
// 从前向后移动元素
iterator begin = pos;
while (begin < _finish - 1) {
*begin = *(begin + 1);
++begin;
}
--_finish;
return pos;
}
注意事项:
- 检查pos的有效性
- 从前向后移动元素覆盖要删除的元素
- 返回指向下一个元素的迭代器
- 被删除元素的析构函数会被调用
8. 常见问题与性能优化
8.1 迭代器失效问题
vector的以下操作会使所有迭代器失效:
- 任何导致扩容的操作(push_back、insert等)
- erase和pop_back会使被删除元素及其后的迭代器失效
解决方案:
- 在可能扩容的操作后,不要保留旧的迭代器
- 使用索引代替迭代器,扩容后可以重新计算
- 必要时使用reserve预分配空间
8.2 异常安全保证
良好的vector实现应该提供基本的异常安全保证:
- 如果元素拷贝抛出异常,容器应保持有效状态
- 析构函数不应该抛出异常
- swap操作应该提供不抛异常保证
8.3 性能优化技巧
根据我的实践经验,优化vector性能的几个关键点:
- 预分配空间:在知道元素数量的情况下,提前调用reserve
- 选择合适的扩容因子:2倍是通用选择,但特定场景可以调整
- 使用emplace_back代替push_back:避免不必要的拷贝
- 考虑使用移动语义:减少深拷贝开销
9. 完整实现与测试
将上述所有部分组合起来,就得到了一个完整的vector实现。为了验证正确性,应该编写全面的测试用例,包括:
- 各种构造方式的测试
- 边界条件测试(空vector、满vector等)
- 异常安全测试
- 性能基准测试
在实际项目中,我通常会先编写测试用例,再实现功能,确保每个功能都有对应的测试验证。