Vector 的模拟实现：从基础到高级

1. 引言

std::vector 是 C++ 中最常用的动态数组容器。为了更好地理解其内部机制，我们将从头实现一个功能更完整的 vector，并逐步优化它。本文不仅会实现基本功能，还会深入探讨一些高级特性，例如异常安全性、迭代器支持和自定义分配器。

2. vector的核心设计

根据 STL 中 vector 的设计。一个 vector 的核心是动态数组，它需要以下成员变量：

• _start ：指向动态数组当前存储元素的第一个位置。
• _finish ：指向动态数组当前存储元素的最后一个位置。
• _end_of_storage ：指向动态数组容量的最后一个位置。

具体的代码实现路径如下：

template<class T>
class vector
{
public: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;}//构造函数vector(){}//类模板的成员函数，也可以是一个函数模板template <class InputIterator>vector(InputIterator first,InputIterator last){while (first != last){push_back(*first);++first;}}vector(size_t n, const T& val = T()){reserve(n);for (size_t i = 0;i < n; i++){push_back(val);}}/*vector(int n, const T& val = T()){reserve(n);for (int i = 0; i < n; i++){push_back(val);}}*/vector(std::initializer_list<T> il){reserve(il.size());for (auto& e : il){push_back(e);}}vector(const vector<T>& v){reserve(v.capacity());for (auto& e : v){push_back(e);}}void swap(vector<T>& tmp){// std 需要在上面将 std域展开std::swap(_start, tmp._start);std::swap(_finish, tmp._finish);std::swap(_endofstorage, tmp._endofstorage);}vector<T>& operator=(vector<T> v){swap(v);return *this;}~vector(){if (_start){delete[] _start;_start = _finish = _endofstorage = nullptr;}}T& operator[](size_t i){assert(i < size());return _start[i];}const T& operator[](size_t i) const{assert(i < size());return _start[i];}size_t size() const{return _finish - _start;}size_t capacity() const{return _endofstorage - _start;}void resize(size_t n, T val = T()){if (n <= size()){_finish = _start + n;}else{reserve(n);while (_finish < _start + n){*_finish = val;++_finish;}}}void reserve(size_t n){if (n > capacity()){size_t oldSize = size();T* tmp = new T[n];if (_start){for (size_t i = 0; i < oldSize; i++){tmp[i] = _start[i];}delete[] _start;}_start = tmp;_finish = _start + oldSize;_endofstorage = _start + n;}}void push_back(const T& x){insert(_finish, x);}bool empty(){return _start == _finish;}void pop_back(){assert(!empty());--_finish;}iterator insert(iterator pos,const T& x){assert(pos >= _start && pos <= _finish);if (_finish == _endofstorage){size_t len = pos - _start;reserve(capacity() == 0 ? 4 : capacity() * 2);pos = _start + len;}iterator i = _finish - 1;while (i >= pos){*(i + 1) = *i;--i;}*pos = x;++_finish;return pos;}iterator erase(iterator pos){assert(pos >= _start && pos < _finish);iterator i = pos + 1;while (i < _finish){*(i - 1) = *i;++i;}_finish--;return pos;}private:iterator _start = nullptr;iterator _finish = nullptr;iterator _endofstorage = nullptr;
};

3. vector的常用接口介绍

3.1 构造函数和析构函数

3.1.1 默认构造函数

初始化一个空的 vector。

template <typename T>
Vector<T>::Vector() : (nullptr), size(0), capacity(0) {}

3.1.2 带初始容量的构造函数

允许用户指定初始容量。

template <typename T>
Vector<T>::Vector(size_t initial_capacity): data(new T[initial_capacity]), size(0), capacity(initial_capacity) {}

3.1.3 析构函数

释放动态分配的内存。

template <typename T>
Vector<T>::~Vector() {delete[] data;
}

3.2 拷贝构造函数和拷贝赋值运算符

3.2.1 拷贝构造函数

深拷贝另一个 vector 的内容。

template <typename T>
Vector<T>::Vector(const Vector& other): data(new T[other.capacity]), size(other.size), capacity(other.capacity) {for (size_t i = 0; i < size; ++i) {data[i] = other.data[i]; // 调用 T 的拷贝构造函数}
}

3.2.2 拷贝赋值运算符

先释放当前资源，再深拷贝另一个 vector 的内容。

template <typename T>
Vector<T>& Vector<T>::operator=(const Vector& other) {if (this != &other) {// 创建一个临时对象Vector temp(other);// 交换当前对象和临时对象的内容std::swap(data, temp.data);std::swap(size, temp.size);std::swap(capacity, temp.capacity);}return *this;
}

3.5 数组长度调整和动态扩容

3.5.1 调整大小（resize）

resize 函数用于调整 vector 的大小。如果新大小大于当前容量，则需要扩容；如果新大小小于当前大小，则只需调整 size 。

template <typename T>
void Vector<T>::resize(size_t new_size) {if (new_size > capacity) {// 如果新大小大于当前容量，需要扩容reserve(new_size);}if (new_size > size) {// 如果新大小大于当前大小，初始化新增元素for (size_t i = size; i < new_size; ++i) {data[i] = T(); // 使用默认构造函数初始化新元素}}size = new_size; // 更新大小
}

3.5.2 缩减容量（shrink_to_fit）

shrink_to_fit 函数用于将 vector 的容量缩减到当前大小，以节省内存。

template <typename T>
void Vector<T>::shrink_to_fit() {if (size < capacity) {// 创建一个临时数组，容量为当前大小T* new_data = new T[size];for (size_t i = 0; i < size; ++i) {new_data[i] = std::move(data[i]); // 移动元素到新数组}// 释放旧数组delete[] data;// 更新指针和容量data = new_data;capacity = size;}
}

注意：这个函数不常用。因为这个函数是请求把多余的内存还给系统，不一定会成功。

3.5.3 动态扩容（reserve）

reserve 函数用于确保 vector 的容量至少为指定值。如果当前容量不足，则扩容。

template <typename T>
void Vector<T>::reserve(size_t new_capacity) {if (new_capacity <= capacity) return; // 如果容量足够，直接返回// 创建新数组T* new_data = new T[new_capacity];for (size_t i = 0; i < size; ++i) {new_data[i] = std::move(data[i]); // 移动元素到新数组}// 释放旧数组delete[] data;// 更新指针和容量data = new_data;capacity = new_capacity;
}

说明：

• 如果 new_capacity <= capacity，直接返回。如果当前数组容量大于新的数组容量，那么就会直接返回。
• 否则，创建一个新数组，容量为 new_capacity。再使用 std::move 将元素从旧数组移动到新数组。释放旧数组，并更新 data和capacity。

3.6 添加元素

3.6.1 添加左值元素

将元素拷贝到 vector 的头部。

template <typename T>
void Vector<T>::insert(const T& value) {if (size >= capacity) {reserve(capacity == 0 ? 4 : capacity * 2);}data[size++] = value;
}

3.6.2 添加右值元素

将元素拷贝到 vector 的末尾。

template <typename T>
void Vector<T>::push_back(const T& value) {if (size >= capacity) {reserve(capacity == 0 ? 1 : capacity * 2);}data[size++] = value;
}

3.7 删除元素

3.7.1 删除指定位置元素

删除指定位置元素。

iterator erase(iterator pos)
{assert(pos >= _start && pos < _finish);iterator i = pos + 1;while (i < _finish){*(i - 1) = *i;++i;}_finish--;return pos;
}

3.7.2 尾删

删除尾部位置的元素。

void pop_back()
{assert(!empty());--_finish;
}

注意：erase尽量少用。由于erase可以删除任意位置的元素，所以会涉及到大量的数组容量更改操作。这会大幅降低程序效率。

3.8 元素访问

3.8.1 通过下标访问元素

T& operator[](size_t i)
{assert(i < size());return _start[i];
}

3.9 迭代器支持

iterator begin()
{return _start;
}iterator end()
{return _finish;
}const_iterator begin() const
{return _start;
}const_iterator end() const
{return _finish;
}

4. 总结

通过这个详细的实现，我们深入了解了 std::vector 的核心机制，包括动态扩容、拷贝/移动语义、迭代器支持等。

希望这篇博客对你有所帮助！如果有任何问题或建议，欢迎留言讨论。

5. 附录

5.1 测试用例

	void test_vector01(){vector<int> v1;v1.push_back(1);v1.push_back(2);v1.push_back(3);v1.push_back(4);for (auto ch : v1){cout << ch << " ";}cout << endl;for (int i = 0; i < v1.size(); i++){cout << v1[i] << " ";}cout << endl;v1.pop_back();for (auto ch : v1){cout << ch << " ";}cout << endl;// pop_back只能尾删，v1.pop_back(1)行不通;int n = *v1.begin();cout << n << endl;vector<int>::iterator it1 = v1.begin();vector<int>::iterator it2 = v1.end();while (it1 != it2){cout << *it1++ << " ";}cout << endl;}void test_vector02(){vector<int> v1;v1.push_back(1);v1.push_back(2);v1.push_back(3);v1.push_back(4);for (auto e : v1){cout << e << " ";}cout << endl;// 第一种使用迭代器在指定位置插入数字v1.insert(v1.begin() + 1, 26);for (auto e : v1){cout << e << " ";}cout << endl;}void test_vector03(){vector<int> v1;v1.push_back(1);v1.push_back(2);v1.push_back(3);v1.push_back(4);vector<int>::iterator it1 = v1.begin();vector<int>::iterator it2 = v1.end();auto x = 0;cin >> x;// 第二种使用迭代器 在指定位置插入指定倍数的数字auto it = find(it1, it2, x);if (it != it2){it = v1.insert(it, 10 * x);cout << *it << endl;}for (auto e : v1){cout << e << " ";}cout << endl;}void test_vector04(){vector<int> v1;// 这一遍是模拟实现的// 这里必须使用系统自带的vector，不然程序会报错中止//std::vector<int> v1;// 这里就是编译器自带的v1.push_back(1);v1.push_back(2);v1.push_back(3);v1.push_back(4);int x;cin >> x;auto it = find(v1.begin(), v1.end(), x);// 删除指定位置的数while (it != v1.end()){v1.erase(it);}for (auto e : v1){cout << e << " ";}cout << endl;}void test_vector05(){vector<int> v1;v1.push_back(1);v1.push_back(2);v1.push_back(3);v1.push_back(4);v1.push_back(4);v1.push_back(23);v1.push_back(42);v1.push_back(33);v1.push_back(533);v1.push_back(234);v1.push_back(23454);v1.push_back(534534534);for (auto e : v1){cout << e << " ";}cout << endl;// 要求删除所有的偶数auto it = v1.begin();while (it != v1.end()){if (*it % 2 == 0){// erase返回删除位置下一个位置// 失效的迭代器，更新以后再去访问v1.erase(it);}else {it++;}}for (auto e : v1){cout << e << " ";}cout << endl;}void test_vector06(){vector<int> v1;v1.push_back(1);v1.push_back(2);v1.push_back(3);v1.push_back(4);for (auto e : v1){cout << e << " ";}cout << endl;// 将v1的size改为20，自动填充0v1.resize(20);for (auto e : v1){cout << e << " ";}cout << endl;// 也可以指定数字。只是已经填充进去的数字无法更改v1.resize(25, 1);for (auto e : v1){cout << e << " ";}cout << endl;v1.resize(2);for (auto e : v1){cout << e << " ";}cout << endl;}void test_vector07(){vector<int> v1;v1.push_back(1);v1.push_back(2);v1.push_back(3);v1.push_back(4);for (auto e : v1){cout << e << " ";}cout << endl;vector<int> v2(v1);for (auto e : v2){cout << e << " ";}cout << endl;vector<int> v3{ 1,2,3,4,5 };v1 = v3;for (auto e : v3){cout << e << " ";}cout << endl; for (auto e : v1){cout << e << " ";}cout << endl;}void test_vector08(){vector<int> v1;v1.push_back(1);v1.push_back(2);v1.push_back(3);v1.push_back(4);for (auto e : v1){cout << e << " ";}cout << endl;vector<int> v2(v1.begin(), v1.end());for (auto e : v2){cout << e << " ";}cout << endl;std::string s1("hello world");vector<int> v3(s1.begin(),s1.end());// 打印的是ASSIC码值for (auto e : v3){cout << e << " ";}cout << endl;// 行不通//vector<int> v4(10, 1);//vector<double> v5(10, 1.1);//for (auto e : v4)//{//	cout << e << " ";//}//cout << endl;///*for (auto e : v5)//{//	cout << e << " ";//}//cout << endl;*/}void test_vector09(){vector<string> v1;v1.push_back("1111111111111111");v1.push_back("1111111111111111");v1.push_back("1111111111111111");v1.push_back("1111111111111111");v1.push_back("1111111111111111");for (auto e : v1){cout << e << " ";}cout << endl;}
}