STL详解 - vector的模拟实现

目录

一、整体设计

1.1 核心结构

1.2 迭代器实现

二、核心接口实现

2.1 构造函数系列

🌴默认构造

🌴迭代器范围构造

🌴元素填充构造

2.2 拷贝控制

🌵拷贝构造函数

🌵赋值运算符（现代写法）

2.3 析构函数

三、容量管理

 3.1 size

3.2 capacity 

3.3 reserve 扩容

3.4 resize 调整大小

四、辅助函数

4.1 下标访问

4.2 empty 

五、 插入与删除

5.1 insert 插入

5.2 push_back

5.3 pop_back

5.4 erase 删除

六、源码

七、测试示例

---

一、整体设计

1.1 核心结构

vector 的核心是通过动态内存管理实现一个动态数组。它维护了三个指针：

• _start：指向数组的起始位置。

• _finish：指向数组的当前结束位置（即最后一个元素的下一个位置）。

• _endofstorage：指向分配的内存的结束位置（即最大容量）。

通过这三个指针，vector 可以动态调整数组的大小，同时支持高效的随机访问和插入/删除操作。

template<class T>
class vector 
{
private:T* _start = nullptr;      // 数据起始位置T* _finish = nullptr;     // 数据结束位置T* _endofstorage = nullptr; // 容量结束位置
};

1.2 迭代器实现

        通过原生指针实现随机访问迭代器：提供 begin 和 end 方法，支持迭代器访问 vector 的元素。

typedef T* iterator;
typedef const T* const_iterator;iterator begin()
{return _start;
}
iterator end()
{return _finish;
}// const版本
const_iterator begin() const
{return _start;
}
const_iterator end() const
{return _finish;
}

二、核心接口实现

2.1 构造函数系列

🌴默认构造

默认构造函数初始化一个空的 vector，所有指针都初始化为 nullptr。 

vector() // 使用编译器生成的默认构造
{
}

---

🌴迭代器范围构造

通过迭代器范围构造一个 vector，逐个将元素插入到新 vector 中。模板参数支持各类迭代器，包括原生指针。

template<class InputIterator>
vector(InputIterator first, InputIterator last)
{while (first != last){push_back(*first);// 逐个插入元素++first;}
}

---

🌴元素填充构造

构造一个包含 n 个元素的 vector，每个元素初始化为 val。通过 reserve 分配足够的内存，并逐个插入元素。

vector(size_t n, const T& val = T())
{reserve(n);for (size_t i = 0; i < n; i++){push_back(val);}
}

注意：需额外提供int版本避免类型推导冲突：

vector(int n, const T& val = T()) 
{reserve(n);for (size_t i = 0; i < n; i++){push_back(val);}
}

2.2 拷贝控制

🌵拷贝构造函数

拷贝构造函数通过 reserve 分配与原 vector 相同的容量，并逐个复制元素。这样可以确保新 vector 的容量和内容与原 vector 一致。

vector(const vector<T>& v) 
{reserve(v.capacity());for (auto e : v) // 范围for遍历{  push_back(e);   // 深拷贝每个元素}
}

---

🌵赋值运算符（现代写法）

赋值运算符通过 swap 实现，先将右值的 vector 与当前 vector 交换，然后返回当前 vector 的引用。这种方式称为 "拷贝并交换"，可以避免自我赋值的问题。

vector<T>& operator=(vector<T> v) // 传值拷贝临时对象
{ swap(v);            // 交换资源return *this;       // 自动释放原内存
}

swap 函数用于交换两个 vector 的内容。通过交换指针，可以高效地完成交换操作，而无需复制数据。 

void swap(vector<T> v)
{std::swap(_start, v._start);std::swap(_finish, v._finish);std::swap(_endofstorage, v._endofstorage);
}

---

2.3 析构函数

析构函数释放分配的内存，并将指针置为 nullptr，避免悬空指针。

~vector()
{delete[] _start;// 释放数组空间_start = _finish = _endofstorage = nullptr;// 置空防野指针
}

三、容量管理

3.1 size

返回当前 vector 的大小，即 _finish - _start。

size_t size() const
{return _finish - _start;
}

3.2 capacity 

返回 vector 的当前容量，即 _endofstorage - _start。

size_t capacity() const
{return _endofstorage - _start;
}

3.3 reserve 扩容

reserve 用于分配至少 n 个元素的内存。如果当前容量不足，则分配新的内存，将旧数据复制到新内存中，然后释放旧内存。

关键点：必须逐个拷贝元素保证深拷贝，直接内存拷贝(memcpy)会导致浅拷贝问题。

void reserve(size_t n) 
{if (n > capacity()) {size_t old_size = size();  // 保存原元素个数T* tmp = new T[n];         // 申请新空间// 深拷贝旧元素（不能用memcpy）for (size_t i = 0; i < old_size; ++i) {tmp[i] = _start[i];  // 调用T的赋值运算符}delete[] _start;  // 释放旧空间// 更新指针_start = tmp;_finish = tmp + old_size;_endofstorage = tmp + n;}
}

3.4 resize 调整大小

resize 用于调整 vector 的大小。如果新大小大于当前大小，则分配更多内存并填充默认值；如果新大小小于当前大小，则直接调整 _finish 指针。

void resize(size_t n, const T& val = T()) 
{if (n > size())  // 扩容部分{     reserve(n);while (_finish < _start + n) {*_finish = val;  // 填充默认值++_finish;}} else // 缩容部分{              _finish = _start + n; // 逻辑缩容，物理容量不变}
}

四、辅助函数

4.1 下标访问

operator[] 提供随机访问功能，通过索引访问 vector 的元素。

T& operator[](size_t pos)
{assert(pos < size());// 越界检查return _start[pos];
}
const T& operator[](size_t pos) const
{assert(pos < size());// 越界检查return _start[pos];
}

4.2 empty 

empty 判断 vector 是否为空，即 _start 和 _finish 是否相等。

void empty()
{return _start == _finish;
}

五、 插入与删除

5.1 insert 插入

insert 在指定位置插入一个元素。如果内存不足，则通过 reserve 扩容。插入时需要将插入点之后的元素向后移动，为新元素腾出空间。

迭代器失效处理：扩容后需重新计算pos位置

void insert(iterator pos, const T& val) 
{assert(pos >= _start && pos <= _finish);// 空间不足时扩容if (_finish == _endofstorage) {size_t len = pos - _start;  // 保存相对位置reserve(capacity() == 0 ? 4 : capacity() * 2);pos = _start + len;         // 解决迭代器失效}// 后移元素iterator it = _finish - 1;while (it >= pos) {*(it + 1) = *it;  // 从后向前搬移--it;}*pos = val;     // 插入新元素++_finish;      // 更新大小
}

5.2 push_back

push_back 是在 vector 的末尾插入一个元素，可以复用 insert 实现。

void push_back(const T& val)
{//if (_finish == _endofstorage)//{//	reserve(capacity() == 0 ? 4 : capacity() * 2);//}//*_finish = val;//_finish++;insert(end(), val);// 复用insert逻辑
}

5.3 pop_back

pop_back 删除 vector 的最后一个元素，可以复用 erase 实现。

void pop_back()
{//assert(!empty());//--_finish;erase(--end());// 复用erase逻辑
}

5.4 erase 删除

erase 删除指定位置的元素。删除时需要将删除点之后的元素向前移动，填补空缺。

void erase(iterator pos) 
{assert(pos >= _start && pos < _finish);// 前移元素iterator it = pos + 1;while (it < _finish) {*(it - 1) = *it;  // 从前向后搬移++it;}--_finish;  // 更新大小
}

六、源码

#pragma once#include <assert.h>
#include <iostream>
using namespace std;namespace lv
{template<class T>class vector{public:// 定义迭代器类型typedef T* iterator;typedef const T* const_iterator;// 返回迭代器，指向 vector 的起始位置iterator begin(){return _start;}// 返回迭代器，指向 vector 的结束位置（即最后一个元素的下一个位置）iterator end(){return _finish;}// 常量版本的 begin 和 end，用于 const 对象const_iterator begin() const{return _start;}const_iterator end() const{return _finish;}// 默认构造函数，初始化一个空的 vectorvector(){_start = nullptr;_finish = nullptr;_endofstorage = nullptr;}// 拷贝构造函数，通过 reserve 分配与原 vector 相同的容量，并逐个复制元素vector(const vector<T>& v){reserve(v.capacity());for (auto e : v){push_back(e);}}// 交换两个 vector 的内容，通过交换指针实现高效交换void swap(vector<T> v){std::swap(_start, v._start);std::swap(_finish, v._finish);std::swap(_endofstorage, v._endofstorage);}// 赋值运算符，通过 "拷贝并交换" 的方式实现，避免自我赋值问题vector<T>& operator=(vector<T> v){swap(v);return *this;}// 通过迭代器范围构造 vector，逐个插入元素template<class InputIterator>vector(InputIterator first, InputIterator last){while (first != last){push_back(*first);++first;}}// 构造一个包含 n 个元素的 vector，每个元素初始化为 valvector(size_t n, const T& val = T()){reserve(n);for (size_t i = 0; i < n; i++){push_back(val);}}// 析构函数，释放分配的内存，并将指针置为 nullptr~vector(){delete[] _start;_start = _finish = _endofstorage = nullptr;}// 返回 vector 的当前大小（即元素个数）size_t size() const{return _finish - _start;}// 返回 vector 的当前容量（即分配的内存量）size_t capacity() const{return _endofstorage - _start;}// 通过索引访问 vector 的元素，带断言检查索引是否越界T& operator[](size_t pos){assert(pos < size());return _start[pos];}// 常量版本的 operator[]，用于 const 对象const T& operator[](size_t pos) const{assert(pos < size());return _start[pos];}// 分配至少 n 个元素的内存，如果当前容量不足，则重新分配内存并复制旧数据void reserve(size_t n){if (n > capacity()){size_t old_size = size();T* tmp = new T[n];for (size_t i = 0; i < old_size; ++i){tmp[i] = _start[i];}delete[] _start;_start = tmp;_finish = tmp + old_size;_endofstorage = tmp + n;}}// 调整 vector 的大小，如果新大小大于当前大小，则分配更多内存并填充默认值void resize(size_t n, const T& val = T()){if (n > size()){reserve(n);while (_finish < _start + n){*_finish = val;++_finish;}}else{_finish = _start + n;}}// 在指定位置插入一个元素，如果内存不足则扩容void insert(iterator pos, const T& val){assert(pos >= _start);assert(pos <= _finish);if (_finish == _endofstorage){size_t len = pos - _start;reserve(capacity() == 0 ? 4 : capacity() * 2);pos = _start + len;}iterator it = _finish - 1;while (it >= pos){*(it + 1) = *it;--it;}*pos = val;++_finish;}// 在 vector 的末尾插入一个元素，通过调用 insert 实现void push_back(const T& val){insert(end(), val);}// 删除 vector 的最后一个元素，通过调用 erase 实现void pop_back(){erase(--end());}// 删除指定位置的元素，将删除点之后的元素向前移动void erase(iterator pos){assert(pos >= _start);assert(pos < _finish);iterator it = pos + 1;while (it < _finish){*(it - 1) = *it;++it;}--_finish;}// 判断 vector 是否为空，即 start 和 finish 是否相等void empty(){return _start == _finish;}private:// 指向 vector 起始位置的指针iterator _start = nullptr;// 指向 vector 结束位置的指针（即最后一个元素的下一个位置）iterator _finish = nullptr;// 指向分配内存结束位置的指针（即最大容量）iterator _endofstorage = nullptr;};// 打印 vector 的内容void print_vector(const vector<int>& v){auto it = v.begin();while (it < v.end()){cout << *it << " ";it++;}cout << endl;}// 测试 vector 的功能void test_vector1(){//......}
}

七、测试示例

#include <iostream>
#include <cassert>
using namespace std;void test_vector()
{// 测试默认构造函数和基本的 push_back 操作{vector<int> v;assert(v.empty());assert(v.size() == 0);assert(v.capacity() == 0);v.push_back(1);v.push_back(2);v.push_back(3);assert(v.size() == 3);assert(v.capacity() >= 3);assert(v[0] == 1);assert(v[1] == 2);assert(v[2] == 3);}// 测试拷贝构造函数{vector<int> v1;v1.push_back(10);v1.push_back(20);v1.push_back(30);vector<int> v2(v1);assert(v2.size() == 3);assert(v2[0] == 10);assert(v2[1] == 20);assert(v2[2] == 30);}// 测试赋值运算符{vector<int> v1;v1.push_back(100);v1.push_back(200);vector<int> v2;v2 = v1;assert(v2.size() == 2);assert(v2[0] == 100);assert(v2[1] == 200);}// 测试迭代器构造函数{vector<int> v1;v1.push_back(1);v1.push_back(2);v1.push_back(3);vector<int> v2(v1.begin(), v1.end());assert(v2.size() == 3);assert(v2[0] == 1);assert(v2[1] == 2);assert(v2[2] == 3);}// 测试插入操作{vector<int> v;v.push_back(1);v.push_back(2);v.push_back(3);v.insert(v.begin() + 1, 10);assert(v.size() == 4);assert(v[0] == 1);assert(v[1] == 10);assert(v[2] == 2);assert(v[3] == 3);v.insert(v.begin(), 20);assert(v.size() == 5);assert(v[0] == 20);assert(v[1] == 1);assert(v[2] == 10);assert(v[3] == 2);assert(v[4] == 3);}// 测试删除操作{vector<int> v;v.push_back(1);v.push_back(2);v.push_back(3);v.push_back(4);v.erase(v.begin() + 1);assert(v.size() == 3);assert(v[0] == 1);assert(v[1] == 3);assert(v[2] == 4);v.pop_back();assert(v.size() == 2);assert(v[0] == 1);assert(v[1] == 3);}// 测试 resize 和 reserve{vector<int> v;v.push_back(1);v.push_back(2);v.resize(5);assert(v.size() == 5);assert(v[0] == 1);assert(v[1] == 2);assert(v[2] == 0); // 默认值assert(v[3] == 0);assert(v[4] == 0);v.resize(3);assert(v.size() == 3);assert(v[0] == 1);assert(v[1] == 2);assert(v[2] == 0);v.reserve(10);assert(v.capacity() >= 10);}// 测试边界条件{vector<int> v;assert(v.empty());assert(v.size() == 0);try{v[0]; // 应该抛出断言错误assert(false);}catch (...){assert(true);}v.push_back(1);v.erase(v.begin());assert(v.empty());}cout << "All tests passed!" << endl;
}