【C++】vector 深度剖析及模拟实现

1.0 std 库 vector 源码：

官方文档：vector

成员变量：

template<class T>
class vector
{
public:typedef T* iterator;private:iterator _start;iterator _finish;iterator _endofstorage;
};

1.1 vector 类的基本结构与迭代器

类定义与成员变量

template<class T>
class vector
{
public:typedef T* iterator;              // 普通迭代器类型typedef const T* const_iterator;  // const迭代器类型private:iterator _start;         // 指向数组首元素iterator _finish;        // 指向最后一个元素的下一个位置iterator _endofstorage;  // 指向存储空间末尾的下一个位置
};

• vector 使用三个指针来管理动态数组：

  • _start：指向数组的第一个元素

  • _finish：指向最后一个元素之后的位置（即当前元素数量的末尾）

  • _endofstorage：指向已分配内存的末尾之后的位置（即当前容量的末尾）

构造函数与析构函数

// 默认构造函数
vector():_start(nullptr),_finish(nullptr),_endofstorage(nullptr)
{}// 析构函数
~vector()
{delete[] _start;  // 释放动态分配的内存_start = _finish = _endofstorage = nullptr;  // 指针置空
}

• 默认构造函数初始化所有指针为 nullptr

• 析构函数释放动态分配的内存并重置所有指针

迭代器访问方法

// 普通正向迭代器
iterator begin() { return _start; }
iterator end() { return _finish; }// 只读正向迭代器
const_iterator begin() const { return _start; }
const_iterator end() const { return _finish; }

• 提供迭代器访问方法，使 vector 支持范围 for 循环和标准库算法

• const 版本确保 const 对象只能进行只读访问

1.2 容量管理

容量查询方法

// 获取元素数量
size_t size() const { return _finish - _start; }// 获取当前容量
size_t capacity() const { return _endofstorage - _start; }

• size() 返回当前元素数量

• capacity() 返回当前分配的内存容量

扩容机制

// 扩容方法
void reserve(size_t n)
{size_t sz = size();  // 提前计算当前大小if (n > capacity()){T* tmp = new T[n];  // 分配新内存if (_start)  // 防止第一次分配内存时 memcpy 出错{// 这里使用 memcpy 是有问题的，只能对内置类型// 的vector进行扩容，具体问题和解决方案在// 后续“memcpy：更深一层次的深浅拷贝问题”memcpy(tmp, _start, sizeof(T) * sz);  // 拷贝数据delete[] _start;  // 释放旧内存}_start = tmp;_finish = tmp + sz;_endofstorage = tmp + n;}
}

• reserve 方法用于预分配内存，避免多次重新分配

• 需要提前计算 size()，因为重新分配后 _start 会改变

• 注意：使用 memcpy 只能对内置类型进行拷贝，对于自定义类型会有问题

元素访问方法

// 下标运算符重载
T& operator[](size_t i)
{assert(i < size());  // 越界检查return _start[i];
}// const 版本下标运算符
const T& operator[](size_t i) const
{assert(i < size());  // 越界检查return _start[i];
}

• 提供类似数组的随机访问功能

• 包含越界检查，提高代码安全性

resize

/* resize */
// val不能给0，因为不知道T的类型，所以给一个T的缺省值
void resize(size_t n, const T& val = T())
{// 缩小sizeif (n < size())_finish = _start + n;else // 增大size{// 假如需要扩容if (n > capacity()){reserve(n);}while (_finish < _start + n){*_finish = val;++_finish;}}
}

• 可以增大或减小 vector 的大小

• 增大时用指定值填充新元素（默认为 T 类型的默认值）

• 缩小时只是调整 _finish 指针，不释放内存

1.3 添加与删除元素

push_back

// 尾插元素
void push_back(const T& x)
{// 空间不足时扩容if (_finish == _endofstorage){size_t newcapacity = capacity() == 0 ? 2 : capacity() * 2;reserve(newcapacity);}*_finish = x;  // 在末尾位置添加元素++_finish;     // 更新末尾指针
}// 也可以直接借助insert完成尾插
void push_back(const T& x) { insert(_finish, x); }

• 当容量不足时自动扩容（通常翻倍）

• 在尾部添加元素并更新指针

insert

// pos位置插入
void insert(iterator pos, const T& x)
{assert(pos <= _finish);  // 检查位置有效性// 空间不够就增容if (_finish == _endofstorage){// 记下pos相对于_start的位置size_t n = pos - _start;size_t newcapacity = capacity() == 0 ? 2 : capacity() * 2;reserve(newcapacity);// 空间增容导致原pos迭代器失效，更新迭代器位置pos = _start + n;}// 后移元素iterator end = _finish - 1;while (end >= pos)  // 依次把pos及pos后面的数据往后挪1位{*(end + 1) = *end;--end;}*pos = x;    // 插入新元素++_finish;   // 更新末尾指针
}

• 插入操作需要移动后续元素，时间复杂度为 O(n)

• 扩容会导致迭代器失效，需要重新计算位置

erase

// 删除指定位置元素
iterator erase(iterator pos)
{assert(pos < _finish);  // 检查位置有效性iterator it = pos;while (it < _finish)  // 将后续元素前移{*it = *(it + 1);++it;}--_finish;  // 更新末尾指针return pos;  // 返回删除后该位置的迭代器
}// 尾删
void pop_back() { erase(_finish - 1); }

• 删除操作需要移动后续元素，时间复杂度为 O(n)

• 返回删除后位置的迭代器，便于连续删除操作

1.4 拷贝构造与赋值重载

拷贝构造函数

/* 拷贝构造函数 */
vector(const vector<T>& v)
{_start = new T[v.capacity()];_finish = _start;_endofstorage = _start + v.capacity();// 拷贝数据for (size_t i = 0; i < v.size(); ++i){*_finish = v[i];++_finish;}
}

更简洁的写法：

/* 拷贝构造函数（更简洁的写法） */
vector(const vector<T>& v):_start(nullptr),_finish(nullptr),_endofstorage(nullptr)
{reserve(v.capacity());        // 直接把空间开好，避免增容for (const auto& e : v)        // 把 v 的数据直接一个个push_back进去push_back(e);
}

• 实现深拷贝，避免多个 vector 共享同一内存

• 先预分配足够空间，然后逐个拷贝元素

赋值重载

/* 赋值重载 */
vector<T>& operator=(const vector<T>& v)
{if (this != &v)        // 防止自己赋值给自己{delete[] _start;_start = new T[v.capacity()];memcpy(_start, v._start, sizeof(T) * v.size());_finish = _start + v.size();_endofstorage = _start + v.capacity();}return *this;
}

赋值重载更简洁的写法：

/* 赋值重载更简洁的写法(现代写法) */
vector<T>& operator=(vector<T> v)
{swap(v);return *this;
}

• 使用"拷贝-交换"技术实现赋值运算符

• 参数通过值传递自动调用拷贝构造函数

• 交换内容后，临时对象 v 在函数结束时自动析构

深浅拷贝问题

为什么我们需要深拷贝？

/* 深浅拷贝问题 */
void test_vector4()
{vector<int> v1;v1.push_back(1);v1.push_back(2);v1.push_back(3);v1.push_back(4);// 如果我们自己没有实现深拷贝的拷贝构造，就会发生和string类一样的浅拷贝问题// 两个vector对象的指针指向同一块空间，最后析构时同一块空间被重复释放，发生了错误// 所以我们需要自己实现深拷贝vector<int> v2(v1);for (size_t i = 0; i < v1.size(); ++i){cout << v2[i] << " ";}cout << endl;// 赋值同理vector<int> v3;v3.push_back(10);v3.push_back(20);v3.push_back(30);v3.push_back(40);v1 = v3;print_vector(v1);for (auto e : v1){cout << e << " ";}cout << endl;
}

1.5 memcpy导致的更深一层次的深浅拷贝问题

受篇幅限制，这里给出文章链接：【C++】memcpy导致的深拷贝问题-CSDN博客

1.6 使用示例

遍历与修改

void test_vector1()
{vector<int> v;v.push_back(1);v.push_back(2);v.push_back(3);v.push_back(4);// 使用迭代器遍历和修改vector<int>::iterator it = v.begin();while (it != v.end()){*it += 1;cout << *it << " ";++it;}cout << endl;// 范围for循环for (auto& e : v){e -= 1;cout << e << " ";}cout << endl;// 下标访问for (size_t i = 0; i < v.size(); ++i){cout << v[i] << " ";}cout << endl;
}

插入与删除

void test_vector2()
{vector<int> v;v.push_back(1);v.push_back(2);v.push_back(3);v.push_back(4);v.push_back(5);v.push_back(6);v.insert(v.begin(), 0);  // 在开头插入0// 删除所有偶数vector<int>::iterator it = v.begin();while (it != v.end()){if (*it % 2 == 0){it = v.erase(it);  // 删除元素并更新迭代器}else{++it;}}
}