1. Vector基础与核心设计解析
在C++标准模板库(STL)中,vector是最常用且最重要的容器之一。作为一个动态数组,vector完美平衡了数组的随机访问效率和动态扩容的灵活性。我们先从内存布局角度理解vector的核心设计:
cpp复制template<class T>
class vector
{
private:
iterator _start; // 指向数组首元素
iterator _finish; // 指向最后一个元素的下一个位置
iterator _endofstorage; // 指向分配内存的末尾
};
这三个指针构成了vector的"黄金三角",它们的分工非常明确:
_start和_finish之间是已使用的空间(size)_start和_endofstorage之间是总容量(capacity)- 当
_finish == _endofstorage时触发扩容
这种设计有几个精妙之处:
- 计算size和capacity只需指针相减,时间复杂度O(1)
- 扩容时只需比较
_finish和_endofstorage,无需维护额外计数器 - 迭代器就是原生指针,最大化访问效率
关键细节:
_finish指向的是最后一个元素的下一个位置,这种"左闭右开"的设计与STL迭代器规范完全一致,使得算法可以统一处理各种容器。
2. 构造函数实现详解
2.1 基础构造函数实现
vector提供了多种构造函数以适应不同初始化场景,我们先看最基础的无参构造:
cpp复制vector()
:_start(nullptr)
,_finish(nullptr)
,_endofstorage(nullptr)
{}
这种"三空指针"的初始化状态是vector的起点。当首次插入元素时,才会真正分配内存。这种延迟分配策略节省了不必要的内存开销。
2.2 拷贝构造的现代写法
拷贝构造函数展示了C++11后的现代写法:
cpp复制vector(const vector<T>& v)
:_start(nullptr)
,_finish(nullptr)
,_endofstorage(nullptr)
{
vector tmp(v.begin(), v.end());
swap(tmp);
}
这里有几个值得注意的技术点:
- 先初始化空容器,保证异常安全
- 利用迭代器构造临时对象tmp
- 通过swap交换资源,避免深拷贝
- tmp在析构时会自动释放旧资源
这种写法比传统的手动元素拷贝更安全高效,也是STL容器推荐的实现方式。
2.3 区间构造的模板技巧
区间构造函数是一个函数模板,可以接受任意迭代器类型:
cpp复制template <class InputIterator>
vector(InputIterator first, InputIterator last)
:_start(nullptr)
,_finish(nullptr)
,_endofstorage(nullptr)
{
while (first != last) {
push_back(*first);
++first;
}
}
这个实现看似简单,但暗含重要特性:
- 模板参数
InputIterator可以是原生指针、其他容器的迭代器等 - 通过
*first和++first的接口约定实现泛型编程 - 逐个插入保证强异常安全(如果抛出异常,容器保持有效状态)
3. 迭代器系统实现
3.1 常规迭代器
vector的迭代器就是原生指针的简单封装:
cpp复制typedef T* iterator;
typedef const T* const_iterator;
iterator begin() { return _start; }
iterator end() { return _finish; }
const_iterator begin() const { return _start; }
const_iterator end() const { return _finish; }
这种设计使得:
- 迭代器操作完全等同于指针操作
- 支持随机访问(+=, -=, []等操作)
- 与算法库完美配合(如std::sort)
3.2 反向迭代器
反向迭代器通过适配器模式实现:
cpp复制typedef std::reverse_iterator<iterator> reverse_iterator;
reverse_iterator rbegin() { return reverse_iterator(end()); }
reverse_iterator rend() { return reverse_iterator(begin()); }
反向迭代器实际上是在常规迭代器上封装了方向逻辑,当执行++操作时,内部实际执行--操作。
4. 容量管理机制
4.1 容量与大小查询
cpp复制size_t size() const { return _finish - _start; }
size_t capacity() const { return _endofstorage - _start; }
bool empty() const { return _start == _finish; }
这些基础查询操作都是O(1)复杂度,直接通过指针运算实现。
4.2 reserve扩容策略
reserve是vector性能优化的关键:
cpp复制void reserve(size_t n) {
if (n > capacity()) {
size_t old_size = size();
iterator tmp = new T[n];
if (_start) {
std::copy(_start, _finish, tmp);
delete[] _start;
}
_start = tmp;
_finish = _start + old_size;
_endofstorage = _start + n;
}
}
关键点分析:
- 只有请求容量大于当前容量时才处理
- 先分配新内存再拷贝元素,保证异常安全
- 使用std::copy保证元素正确复制(特别是非平凡类型)
- 严格更新三个指针,保持一致性
经验法则:当预先知道元素数量时,先reserve可以避免多次扩容,显著提升性能。
4.3 resize行为控制
resize改变的是元素数量而非容量:
cpp复制void resize(size_t n, const T& val = T()) {
if (n < size()) {
_finish = _start + n;
} else {
reserve(n);
while (_finish != _start + n) {
*_finish = val;
++_finish;
}
}
}
resize的两种模式:
- 缩小:直接调整
_finish指针,元素被逻辑删除 - 扩大:可能需要扩容,并用默认值填充新增位置
5. 元素访问接口
5.1 随机访问操作符
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];
}
这种实现:
- 提供const和非const两个版本
- 使用assert检查边界(调试阶段捕获错误)
- 直接指针运算,效率最高
5.2 安全的at访问
cpp复制T& at(size_t pos) {
if (pos >= size())
throw std::out_of_range("vector::at");
return _start[pos];
}
与operator[]的区别:
- 抛出异常而非assert,适合生产环境
- 有轻微性能开销(异常处理机制)
6. 增删元素实现
6.1 push_back的扩容策略
cpp复制void push_back(const T& val) {
if (_finish == _endofstorage) {
size_t new_capacity = capacity() == 0 ? 4 : capacity() * 2;
reserve(new_capacity);
}
*_finish = val;
++_finish;
}
扩容策略要点:
- 初始容量为0时,分配4个元素空间
- 之后每次按2倍扩容,平摊时间复杂度为O(1)
- 先扩容再插入,保证异常安全
6.2 insert实现与迭代器失效
cpp复制iterator insert(iterator pos, const T& val) {
assert(pos >= begin() && pos <= end());
if (_finish == _endofstorage) {
size_t offset = pos - _start;
reserve(capacity() ? capacity() * 2 : 4);
pos = _start + offset; // 重新计算pos
}
iterator end = _finish - 1;
while (end >= pos) {
*(end + 1) = *end;
--end;
}
*pos = val;
++_finish;
return pos;
}
关键注意事项:
- 扩容会导致迭代器失效,需要重新计算pos
- 元素后移从尾部开始,避免覆盖
- 返回新的迭代器,符合STL规范
6.3 erase与迭代器失效
cpp复制iterator erase(iterator pos) {
assert(pos >= begin() && pos < end());
iterator begin = pos + 1;
while (begin != _finish) {
*(begin - 1) = *begin;
++begin;
}
--_finish;
return pos;
}
erase的特点:
- 元素前移覆盖要删除的元素
- 不释放内存,只调整
_finish指针 - 返回下一个有效迭代器
7. 性能优化技巧
7.1 移动语义支持
C++11后应添加移动构造和移动赋值:
cpp复制vector(vector&& v) noexcept
:_start(v._start)
,_finish(v._finish)
,_endofstorage(v._endofstorage)
{
v._start = v._finish = v._endofstorage = nullptr;
}
vector& operator=(vector&& v) noexcept {
if (this != &v) {
swap(v);
}
return *this;
}
移动操作的优势:
- 直接接管资源,无需拷贝
- 标记为noexcept,便于标准库优化
- 源对象置空,保证安全
7.2 emplace_back高效插入
cpp复制template <class... Args>
void emplace_back(Args&&... args) {
if (_finish == _endofstorage) {
reserve(capacity() ? capacity() * 2 : 4);
}
new (_finish) T(std::forward<Args>(args)...);
++_finish;
}
与push_back的区别:
- 直接在目标位置构造,避免临时对象
- 完美转发参数,效率更高
- 需要显式调用析构函数(如果类型复杂)
8. 常见问题与解决方案
8.1 迭代器失效场景
vector操作可能导致迭代器失效的情况:
- 插入元素导致扩容:所有迭代器失效
- 插入元素未扩容:插入点之后的迭代器失效
- 删除元素:删除点之后的迭代器失效
最佳实践:修改操作后应重新获取迭代器,避免使用旧的迭代器
8.2 内存管理陷阱
常见内存问题:
- 未实现拷贝构造/赋值导致浅拷贝
- 扩容时未正确复制元素
- 析构时未正确释放内存
解决方案:
- 遵循Rule of Three/Five
- 使用RAII管理资源
- 编写完善的单元测试
8.3 性能优化建议
提升vector性能的方法:
- 预分配足够容量(reserve)
- 优先使用emplace_back而非push_back
- 避免在中间位置频繁插入删除
- 考虑使用移动语义减少拷贝
9. 完整实现示例
以下是vector核心接口的完整实现:
cpp复制template<class T>
class vector {
public:
// 迭代器相关
typedef T* iterator;
typedef const T* const_iterator;
// 构造/析构
vector();
vector(size_t n, const T& val = T());
template<class InputIterator>
vector(InputIterator first, InputIterator last);
vector(const vector& v);
vector(vector&& v) noexcept;
~vector();
// 容量相关
size_t size() const;
size_t capacity() const;
bool empty() const;
void reserve(size_t n);
void resize(size_t n, const T& val = T());
// 访问相关
T& operator[](size_t pos);
const T& operator[](size_t pos) const;
T& at(size_t pos);
const T& at(size_t pos) const;
T& front();
const T& front() const;
T& back();
const T& back() const;
// 修改相关
void push_back(const T& val);
void pop_back();
iterator insert(iterator pos, const T& val);
iterator erase(iterator pos);
void clear();
// 迭代器
iterator begin();
iterator end();
const_iterator begin() const;
const_iterator end() const;
// C++11
template <class... Args>
void emplace_back(Args&&... args);
private:
iterator _start;
iterator _finish;
iterator _endofstorage;
void reallocate(size_t new_capacity);
};
这个实现涵盖了vector最核心的功能,可以作为学习模板和容器设计的优秀范例。