1. Vector基础概念与核心设计
在C++标准模板库(STL)中，vector是最常用的动态数组容器之一。与普通数组相比，vector能够自动管理内存，在运行时动态调整大小，同时保持了数组随机访问的高效性。理解vector的内部实现机制，对于提升C++编程能力和解决实际问题具有重要意义。
vector的核心设计思想是"动态扩容+连续存储"。它通过三个关键指针维护内部状态：
_start：指向数组首元素的指针_finish：指向最后一个元素的下一个位置_endofstorage：指向当前分配内存空间的末尾
这种设计使得vector具有以下特性：
- 随机访问时间复杂度O(1)
- 尾部插入/删除平均时间复杂度O(1)
- 自动内存管理，减少手动分配/释放的麻烦
- 内存局部性好，缓存命中率高
注意：vector在中间位置插入/删除元素效率较低(O(n))，因为需要移动后续所有元素。这是连续存储结构的固有特性。
2. Vector的基本结构与构造函数实现
2.1 类模板定义与成员变量
vector作为类模板，可以存储任意类型的元素。基础结构定义如下：
cpp复制template<class T>
class vector {
public:
typedef T* iterator;
typedef const T* const_iterator;
private:
iterator _start; // 指向数据块起始位置
iterator _finish; // 指向最后一个元素的下一个位置
iterator _endofstorage; // 指向分配内存的末尾
};
2.2 构造函数实现
2.2.1 默认构造函数
最简单的构造函数创建一个空vector：
cpp复制vector()
: _start(nullptr)
, _finish(nullptr)
, _endofstorage(nullptr)
{}
2.2.2 填充构造函数
创建包含n个相同元素的vector：
cpp复制vector(size_t n, const T& val = T())
: _start(nullptr)
, _finish(nullptr)
, _endofstorage(nullptr)
{
reserve(n); // 预分配空间
for(size_t i = 0; i < n; ++i) {
push_back(val); // 逐个添加元素
}
}
2.2.3 范围构造函数
通过迭代器范围构造vector：
cpp复制template <class InputIterator>
vector(InputIterator first, InputIterator last)
: _start(nullptr)
, _finish(nullptr)
, _endofstorage(nullptr)
{
while(first != last) {
push_back(*first);
++first;
}
}
2.2.4 拷贝构造函数
实现深拷贝的拷贝构造函数：
cpp复制vector(const vector<T>& v)
: _start(nullptr)
, _finish(nullptr)
, _endofstorage(nullptr)
{
vector<T> tmp(v.begin(), v.end());
swap(tmp);
}
技巧：使用"拷贝-交换"惯用法实现拷贝构造，既保证了异常安全，又简化了代码。
3. Vector的迭代器与容量操作
3.1 迭代器实现
vector的迭代器本质是指针的封装：
cpp复制iterator begin() { return _start; }
iterator end() { return _finish; }
const_iterator begin() const { return _start; }
const_iterator end() const { return _finish; }
3.2 容量相关操作
3.2.1 基础容量查询
cpp复制size_t size() const { return _finish - _start; }
size_t capacity() const { return _endofstorage - _start; }
bool empty() const { return _start == _finish; }
3.2.2 reserve操作
调整vector的容量：
cpp复制void reserve(size_t n) {
if(n > capacity()) {
size_t old_size = size();
T* new_start = new T[n];
// 拷贝原有元素
for(size_t i = 0; i < old_size; ++i) {
new_start[i] = _start[i];
}
// 释放旧空间
delete[] _start;
// 更新指针
_start = new_start;
_finish = _start + old_size;
_endofstorage = _start + n;
}
}
3.2.3 resize操作
调整vector的大小：
cpp复制void resize(size_t n, const T& val = T()) {
if(n < size()) {
_finish = _start + n;
} else {
if(n > capacity()) {
reserve(n);
}
while(_finish != _start + n) {
*_finish = val;
++_finish;
}
}
}
注意：resize可能导致元素构造或析构，对于自定义类型可能有性能开销。
4. Vector的元素访问与修改操作
4.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];
}
T& front() { return *_start; }
T& back() { return *(_finish - 1); }
4.2 元素添加与删除
4.2.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;
}
4.2.2 pop_back实现
cpp复制void pop_back() {
assert(!empty());
--_finish;
}
4.2.3 insert实现
cpp复制iterator insert(iterator pos, const T& val) {
assert(pos >= begin() && pos <= end());
if(_finish == _endofstorage) {
size_t offset = pos - _start;
size_t new_capacity = capacity() == 0 ? 4 : capacity() * 2;
reserve(new_capacity);
pos = _start + offset;
}
iterator end = _finish;
while(end > pos) {
*end = *(end - 1);
--end;
}
*pos = val;
++_finish;
return pos;
}
4.2.4 erase实现
cpp复制iterator erase(iterator pos) {
assert(pos >= begin() && pos < end());
iterator it = pos;
while(it < _finish - 1) {
*it = *(it + 1);
++it;
}
--_finish;
return pos;
}
经验：insert和erase操作在vector中间位置效率较低，如果需要频繁在中间位置插入删除，考虑使用list或deque。
5. Vector的扩容策略与性能优化
5.1 扩容机制详解
vector的扩容通常采用"倍增策略"，即每次空间不足时，容量扩大为原来的2倍。这种策略的优点是：
- 均摊时间复杂度为O(1)
- 减少了频繁重新分配内存的开销
- 平衡了内存使用和性能
5.2 性能优化技巧
-
预分配空间：如果知道元素的大致数量，提前调用reserve()可以避免多次扩容。
cpp复制vector<int> v; v.reserve(1000); // 预分配1000个元素的空间 -
移动语义：对于C++11及以上，实现移动构造函数和移动赋值运算符可以提升性能。
cpp复制vector(vector&& v) noexcept : _start(v._start) , _finish(v._finish) , _endofstorage(v._endofstorage) { v._start = v._finish = v._endofstorage = nullptr; } -
emplace_back：C++11引入的emplace_back可以直接在容器内构造对象，避免临时对象的创建和拷贝。
cpp复制template <class... Args> void emplace_back(Args&&... args) { if(_finish == _endofstorage) { size_t new_capacity = capacity() == 0 ? 4 : capacity() * 2; reserve(new_capacity); } new (_finish) T(std::forward<Args>(args)...); ++_finish; }
5.3 常见问题与解决方案
-
迭代器失效问题：
- 扩容操作会使所有迭代器、指针和引用失效
- 插入/删除操作会使当前位置及之后的迭代器失效
- 解决方案：避免在操作过程中保存旧的迭代器
-
内存泄漏：
- 确保在析构函数中正确释放内存
- 实现完整的RAII管理
-
异常安全：
- 保证基本异常安全（无资源泄漏）
- 尽量实现强异常安全（操作失败时对象状态不变）
6. Vector的完整实现与测试
6.1 完整类定义
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<T>& v);
vector(vector&& v) noexcept;
// 析构函数
~vector();
// 赋值操作
vector<T>& operator=(vector<T> v);
// 迭代器
iterator begin();
iterator end();
const_iterator begin() const;
const_iterator end() const;
// 容量
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& front();
T& back();
// 修改操作
void push_back(const T& val);
void pop_back();
iterator insert(iterator pos, const T& val);
iterator erase(iterator pos);
void clear();
// 工具函数
void swap(vector<T>& v);
private:
iterator _start;
iterator _finish;
iterator _endofstorage;
};
6.2 测试用例示例
cpp复制void test_vector() {
// 基本功能测试
vector<int> v1;
assert(v1.empty());
v1.push_back(1);
v1.push_back(2);
v1.push_back(3);
assert(v1.size() == 3);
assert(v1[0] == 1 && v1[1] == 2 && v1[2] == 3);
// 拷贝构造测试
vector<int> v2(v1);
assert(v2.size() == 3);
assert(v2[0] == 1 && v2[1] == 2 && v2[2] == 3);
// 插入删除测试
v2.insert(v2.begin() + 1, 5);
assert(v2[1] == 5);
v2.erase(v2.begin());
assert(v2[0] == 5);
// 扩容测试
vector<int> v3;
for(int i = 0; i < 100; ++i) {
v3.push_back(i);
}
assert(v3.size() == 100);
assert(v3.capacity() >= 100);
std::cout << "All tests passed!" << std::endl;
}
在实际项目中，vector的实现还需要考虑更多边界条件和优化策略，但以上代码已经涵盖了最核心的功能。理解这些实现细节，对于深入掌握C++内存管理和数据结构设计非常有帮助。