【C++之容器篇】造轮子：模拟实现vector类

前言

vector本质就是一个支持顺序存储数据，并且容量支持修改得到顺序表。但是vector的底层结构实现相比于之前实现的string来说略有不同。string中的底层结构是通过一个指针数组和两个变量来标识数组中数据的变化。vector是通过三个迭代器来标识上述过程。

一、项目结构

1. vector的简介

2. 项目结构

这个项目有两个文件，一个是test.cpp文件，另一个是vector.h文件。test.cpp文件主要是用来测试实现的vector的代码逻辑。vector.h文件主要是模拟实现vector的代码逻辑。

二、vector的底层结构

1. 效果图：
   
   

2. 代码实现

namespace hjt
{// 实现vectortemplate <class T>class vector{public:typedef T* iterator;typedef const T* const_iterator;private:iterator _start;// 指向存储的第一个有效数据iterator _finish;// 指向存储的最后一个有效数据的下一个位置iterator _endofstorage;// 指向能够存储的最后一个位置的下一个位置};
}

代码中是通过三个迭代器来实现底层的。

• _start：指向存储的第一个有效数据
• _finish：指向存储的最后一个有效数据的下一个位置
• _endofstorage： 指向能够存储的最后一个位置的下一个位置
  其实这个实现方法和string中的实现方法其实差不多，相当于_start表示空间的起始地址，_finish表示有效数据的个数，_endofstorage表示vector的实际容量。

三、默认成员函数(Member functions)

1. 构造函数

(1)无参构造函数

• 代码

	// 无参构造函数vector():_start(nullptr),_finish(nullptr),_endofstorage(nullptr){}

• 练习：

int main()
{hjt::vector<int> v1;hjt::vector<char> v2;hjt::vector<double> v3;hjt::vector<string> v4;return 0;
}

分析：v1表示一个存储int类型的vector对象，v2表示一个存储char类型的vector对象，v3表示一个存储double类型的vector对象，v4表示一个存储string类型对象的vector对象。

(2)使用n个值来构造对象

• 代码1：

	// 构造函数：使用n个值来构造对象vector(size_t n, const T& val = T()):_start(nullptr), _finish(nullptr), _endofstorage(nullptr){while (n--){push_back(val);}}

• 代码2：

	// 构造函数：使用n个值来构造对象vector(int n, const T& val = T()):_start(nullptr), _finish(nullptr), _endofstorage(nullptr){while (n--){push_back(val);}}

(3)使用一段迭代器区间来进行初始化

• 代码：

	// 构造函数：使用一段迭代器区间来进行初始化template <class InputIterator>vector(InputIterator left, InputIterator right){while (left < right){push_back(*left);left++;}}

(4)测试构造函数

• 测试代码：

void test_vector1()
{// 测试构造函数hjt::vector<int> v1;v1.push_back(1);v1.push_back(2);v1.push_back(3);v1.push_back(4);v1.push_back(5);v1.push_back(6);v1.push_back(7);hjt::vector<int>::iterator vit = v1.begin();while (vit != v1.end()){cout << *vit << " ";vit++;}cout << endl;hjt::vector<int> v2(6, 6);hjt::vector<int>::iterator vit2 = v2.begin();while (vit2 != v2.end()){cout << *vit2 << " ";vit2++;}cout << endl;hjt::vector<int> v3(v1.begin(), v1.end());hjt::vector<int>::iterator vit3 = v3.begin();while (vit3 != v3.end()){cout << *vit3 << " ";vit3++;}cout << endl;}

运行结果：

2. 拷贝构造函数（现代写法）

• 代码：

// 拷贝构造函数vector(const vector<T>& v):_start(nullptr), _finish(nullptr), _endofstorage(nullptr){vector<T> tmp(v.begin(), v.end());swap(tmp);}

• 测试代码：

void test_vector2()
{// 测试拷贝构造函数hjt::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);// 打印vfor (auto& e : v){cout << e << " ";}cout << endl;// 调用构造函数hjt::vector<int> v1(v);hjt::vector<int> v2 = v1;// 打印v1for (auto& e : v1){cout << e << " ";}cout << endl;// 打印v2for (auto& e : v2){cout << e << " ";}cout << endl;}

运行结果：

3. 析构函数

• 代码：

// 析构函数~vector(){if (_start){delete[]_start;_start = _finish = _endofstorage = nullptr;}}

4. 赋值运算符重载函数（现代写法）

• 代码：

	// 赋值运算符重载函数vector<T>& operator=(vector<T> v){swap(v);return *this;}

• 测试代码：

void test_vector3()
{// 测试拷贝构造函数hjt::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);// 打印vfor (auto& e : v){cout << e << " ";}cout << endl;// 调用赋值运算符重载函数hjt::vector<int> v1;v1 = v;hjt::vector<int> v2;v2 = v1;// 打印v1for (auto& e : v1){cout << e << " ";}cout << endl;// 打印v2for (auto& e : v2){cout << e << " ";}cout << endl;}

运行结果：

四、迭代器(Iterators)

1. 普通对象的正向迭代器

• 代码：

// 普通迭代器iterator begin(){return _start;}iterator end(){return _finish;}

• 代码：使用

2. const 对象的正向迭代器

• 代码：

// const迭代器const_iterator begin() const{return _start;}const_iterator end() const{return _finish;}

五、容量接口(Capacity)

1. size()

• 代码：

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

2. capacity()

• 代码：

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

3. reserve()

• 代码：

// 扩容void reserve(size_t n){if (n > capacity()){size_t sz = size();T* tmp = new T[n];if (_start){memcpy(tmp, _start, sizeof(T) * size());delete[]_start;}_start = tmp;_finish = _start + sz;_endofstorage = _start + n;}}

4. resize()

• 测试代码：

int main()
{hjt::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);for (auto& e : v){cout << e << " ";}cout << endl;cout << "size:" << v.size() << endl;cout << "capacity:" << v.capacity() << endl;v.resize(100,6);for (auto& e : v){cout << e << " ";}cout << endl;cout << "size:" << v.size() << endl;cout << "capacity:" << v.capacity() << endl;return 0;
}

运行结果：

• 测试代码2：

int main()
{hjt::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);for (auto& e : v){cout << e << " ";}cout << endl;cout << "size:" << v.size() << endl;cout << "capacity:" << v.capacity() << endl;v.resize(3, 6);for (auto& e : v){cout << e << " ";}cout << endl;cout << "size:" << v.size() << endl;cout << "capacity:" << v.capacity() << endl;return 0;
}

运行结果：

• 测试代码3：

int main()
{hjt::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);for (auto& e : v){cout << e << " ";}cout << endl;cout << "size:" << v.size() << endl;cout << "capacity:" << v.capacity() << endl;for (auto& e : v){cout << e << " ";}cout << endl;v.reserve(60);cout << "size:" << v.size() << endl;cout << "capacity:" << v.capacity() << endl;for (auto& e : v){cout << e << " ";}cout << endl;v.resize(50, 6);for (auto& e : v){cout << e << " ";}cout << endl;cout << "size:" << v.size() << endl;cout << "capacity:" << v.capacity() << endl;return 0;
}

运行结果：

六、元素访问接口(Element access)

1. operator[](size_t pos)

(1)const T& operator[](size_t pos)

• 代码：

	T& operator[](size_t pos){return _start[pos];}

• 测试代码：

int main()
{hjt::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);for (size_t i = 0; i < v.size(); i++){cout << v[i] << " ";}cout << endl;return 0;
}

运行结果：

(2)const T& operator[](size_t pos) const

• 代码：

	const T& operator[](size_t pos) const{return _start[pos];}

• 测试代码：

2. at(size_t pos)

(1)T& at(size_t pos)

• 代码：

		T& at(size_t pos){return _start[pos];}

• 测试代码：

int main()
{hjt::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);for (size_t i = 0; i < v.size(); i++){cout << v.at(i) << " ";}cout << endl;return 0;
}

运行结果：

3. front()

• 代码：

// frontT& front() const{return *_start;}

4. back()

• 代码：

// back()T& back() const{return *(_finish - 1);}

测试：

int main()
{hjt::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);cout << "front:" << v.front() << endl;cout << "back:" << v.back() << endl;
}

运行结果：

七、修改接口(Modifiers)

1. push_back(const T& x)

• 代码：

// 尾插void push_back(const T& x){if (_finish == _endofstorage){// 需要进行扩容reserve(capacity() == 0 ? 4 : capacity() * 2);}*_finish = x;_finish++;}

• 测试：

// 测试尾插
int main()
{hjt::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);hjt::vector<int>::iterator vit = v.begin();while (vit != v.end()){cout << *vit << " ";vit++;}cout << endl;cout << v.size() << endl;cout << v.capacity() << endl;for (auto e : v){cout << e << " ";}cout << endl;return 0;
}

运行结果：

2. pop_back()

• 代码：

// 尾删void pop_back(){assert(_finish > _start);_finish--;}

• 测试代码：

int main()
{hjt::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);hjt::vector<int>::iterator vit = v.begin();while (vit != v.end()){cout << *vit << " ";vit++;}cout << endl;v.pop_back();v.pop_back();v.pop_back();for (auto& e : v){cout << e << " ";}cout << endl;return 0;
}

运行结果：

没有数据继续删除：

3. iterator insert(iterator pos,T val = T()))

1. 在实现insert函数的时候需要注意迭代器的问题，因为在实现insert的时候可能会进行扩容，根据扩容的底层原理，我们知道，扩容之后的空间和扩容前的空间是不一样的，扩容之后会将原来的空间进行释放，而原来的迭代器指向的是原来空间的位置，所以当原来空间释放之后，原来的迭代器就变成了一个野指针，也就是所谓的迭代器失效了，此时如果再去访问原来的迭代器就是访问野指针，程序就会崩溃。因此我们在实现insert的时候，如果需要进行扩容，则需要在扩容的时候将迭代器进行更新，防止出现野指针。
2. 在使用insert函数的时候可能会出现迭代器意义变化的情况，比如：在1，2，3，4，5，6中的偶数前插入20，第一个偶数是2，此时调用insert函数插入20之后会返回一个迭代器，这个迭代器指向的是新插入的20，而不是原来指向的2，所以这种情况下调用insert函数之后，需要更新迭代器的位置到当前位置的下一个位置，这样才能够使迭代器保持原来的意义。

• 代码：

// insert()iterator insert(iterator pos, T val = T()){assert(pos >= _start && pos <= _finish);if (_finish == _endofstorage){// 扩容// 如果需要进行扩容，注意更新迭代器，否则会导致迭代器失效size_t n = pos - _start;reserve(capacity() == 0 ? 4 : capacity() * 2);pos = _start + n;}// 挪动数据iterator end = _finish - 1;while (end >= pos){*(end + 1) = *end;end--;}// 插入数据*pos = val;_finish++;return pos;}

• 测试代码1：

void test_vector4()
{// 测试inserthjt::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);// 打印vfor (auto& e : v){cout << e << " ";}cout << endl;// 头插10v.insert(v.begin(), 10);// 打印vfor (auto& e : v){cout << e << " ";}cout << endl;// 在6前面插入10hjt::vector<int>::iterator pos = find(v.begin(), v.end(), 6);if (pos != v.end()){// 找到了，位置为:posv.insert(pos, 10);}// 打印vfor (auto& e : v){cout << e << " ";}cout << endl;// 尾插10v.insert(v.end(), 10);// 打印vfor (auto& e : v){cout << e << " ";}cout << endl;
}

运行结果：

• 测试代码2：在偶数前插入66

void test_vector5()
{// 测试inserthjt::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);// 打印vfor (auto& e : v){cout << e << " ";}cout << endl;// 在偶数前面插入20hjt::vector<int>::iterator vit = v.begin();while (vit != v.end()){if (*vit % 2 == 0){vit = v.insert(vit, 20);vit++;}vit++;}// 打印vfor (auto& e : v){cout << e << " ";}cout << endl;
}
}

运行结果：

4. iterator erase(iterator pos)

在删除函数中，我们一般不考虑缩容方案，所以一般不会出现野指针越界的问题，但是很容易会发生迭代器的意义发生变化的问题。比如：删除1，2，3，4，5，6中所有的偶数的时候，第一个偶数是2，当删除2之后，erase函数会返回一个迭代器，这个迭代器指向的是删除元素的下一个位置，在外面如果迭代器继续遍历下一个位置，那么就会将之前删除元素的下一个元素跳过，所以可能引发程序的逻辑异常。解决方案有两种：

1. 在遍历的过程中，如果发生删除，则迭代器不需要指向下一个位置（erase函数已经更新），没有发生删除时才指向下一个位置。
2. 在遍历的过程中，无论是否发生删除，每次都向前走一步，但是如果发生删除，迭代器需要先向后走一步。

• 代码：

// eraseiterator erase(iterator pos){assert(pos >= _start && pos < _finish);// 挪动数据iterator begin = pos + 1;while (begin < _finish){*(begin - 1) = *begin;begin++;}_finish--;return pos;}

• 测试代码1：

void test_vector6()
{// 测试erasehjt::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);// 打印vfor (auto& e : v){cout << e << " ";}cout << endl;// 头删v.erase(v.begin());// 打印vfor (auto& e : v){cout << e << " ";}cout << endl;// 删除5hjt::vector<int>::iterator pos = find(v.begin(), v.end(), 5);if (pos != v.end()){v.erase(pos);}// 打印vfor (auto& e : v){cout << e << " ";}cout << endl;// 尾删v.erase(v.end() - 1);// 打印vfor (auto& e : v){cout << e << " ";}cout << endl;
}

运行结果：

• 测试代码2：删除所有偶数

void test_vector7()
{// 测试erasehjt::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);// 打印vfor (auto& e : v){cout << e << " ";}cout << endl;// 删除所有偶数hjt::vector<int>::iterator vit = v.begin();while (vit != v.end()){if (*vit % 2 == 0){vit = v.erase(vit);vit--;}vit++;}// 打印vfor (auto& e : v){cout << e << " ";}cout << endl;
}

运行结果：

八、vector中更深层次的深浅拷贝问题

在学习vector中更深层次的深浅拷贝问题之前，我们首先来学习一道经典的题目：构造一个杨辉三角。

1. 杨辉三角

• 题目：
  
• 提交代码：

class Solution {
public:vector<vector<int>> generate(int numRows) {// 确定容器vector<vector<int>> vv;// 确定容器的大小：根据杨辉三角的行数进行确定vv.resize(numRows);// 根据杨辉三角的每一行中的元素个数确定容器中每个vector存放多少个intfor(size_t i = 0;i<vv.size();i++){vv[i].resize(i+1,0);}// 将每一行中的第一个元素和最后一个元素初始化成1for(size_t i = 0;i<vv.size();i++){for(size_t j = 0;j<vv[i].size();j++){if(j == 0||j == vv[i].size()-1){vv[i][j] = 1;}}}// 处理不是1的元素for(size_t i = 0;i<vv.size();i++){for(size_t j = 0;j<vv[i].size();j++){if(vv[i][j]!=1){vv[i][j] = vv[i-1][j-1]+vv[i-1][j];}}}return vv;}
};

• 提交结果：
  

解题思路：
本题其实是需要一个二维数组，所以我们采用vector<vector>的类型的容器来存储杨辉三角。首先需要根据用户输入的杨辉三角的行数来确定容器的大小，接下来根据杨辉三角每一行的元素个数确定，vector<vector>中的每一个vector存放多少个int，这个过程使用一个for循环+v.resize()进行开空间和初始化。接下来将每一行中的第一个元素和最后一个元素赋值成1，最后处理最后其他元素。
对于vector<vector>类型的遍历方法：采用两重循环，比如：上面的二重循环中，第一层循环第一次i = 0,所以vv[i] = vv[0]也就是找到vv中的第一个vector，接下来进入第二层循环，这个循环是从j = 0开始，知道j<vv[i].size()结束，也就是会将这个vector中的所有int类型的数据遍历完才会结束，当第一个vector遍历结束时，第一个内层for循环结束，所以接下来i = 1，vv[i] = vv[1]，开始找到vv中的第二个vector重复上述过程。

当我们在VS中使用我们自己的vector的时候发生了下面现象：

• 代码1：构造一个5行的杨辉三角

class Solution {
public:hjt::vector<hjt::vector<int>> generate(int numRows) {// 确定容器hjt::vector<hjt::vector<int>> vv;// 确定容器的大小：根据杨辉三角的行数进行确定vv.resize(numRows);// 根据杨辉三角的每一行中的元素个数确定容器中每个vector存放多少个intfor (size_t i = 0; i < vv.size(); i++){vv[i].resize(i + 1, 0);}// 将每一行中的第一个元素和最后一个元素初始化成1for (size_t i = 0; i < vv.size(); i++){for (size_t j = 0; j < vv[i].size(); j++){if (j == 0 || j == vv[i].size() - 1){vv[i][j] = 1;}}}// 处理不是1的元素for (size_t i = 0; i < vv.size(); i++){for (size_t j = 0; j < vv[i].size(); j++){if (vv[i][j] != 1){vv[i][j] = vv[i - 1][j - 1] + vv[i - 1][j];}}}return vv;}
};void test_vector8()
{hjt::vector<hjt::vector<int>> vv = Solution().generate(5);for (auto& e : vv){for (auto& e1 : e){cout << e1 << " ";}cout << endl;}cout << endl;}

运行结果：

分析结果：通过上面的运行结果：我们想要构造一个5行的杨辉三角，结果，前四行全部是随机值，然后第五行是正常的。

• 代码2：构造一个4行的杨辉三角

void test_vector9()
{hjt::vector<hjt::vector<int>> vv = Solution().generate(4);for (auto& e : vv){for (auto& e1 : e){cout << e1 << " ";}cout << endl;}cout << endl;}

运行结果：

分析：当我们构造的是一个4行的杨辉三角时，程序竟然能够正常给我们构造出来，从4到5的区别就是需要一个扩容的过程，显然，需要vector<vector>不需要进行扩容时，程序就能够正常帮助我们构造出杨辉三角，所以显然是我们实现的扩容函数中的逻辑出现问题。

通过仔细分析：我们在扩容函数中拷贝原来空间中的数据到新空间时，使用的是memcpy()函数，memcpy()函数使用的是浅拷贝机制，所以，假如原来空间中有四个vector，那么memcpy()函数就会将原来的四个vector中的_start,_finish,_endofstorage指针分别拷贝到新空间中对应的vector中的_start,_finish,_endofstorage，所以，原来的四个vector中的_start,_finish,_endofstorage指针和新空间中对应的vector中的_start,_finish,_endofstorage分别指向的是同一块空间的同一个位置，在扩容的时候，我们知道，我们会将原来空间进行释放，所以原来的数据将全部丢失，对应的指针全部变成野指针，所以就会出现上面的现象，前四行的数据是随机值，然后访问野指针的时候出现数组越界，所以程序崩溃。
正确的处理方法：实现深拷贝

• 扩容函数代码：

void reserve(size_t n){if (n > capacity()){// 需要进行扩容size_t sz = size();// 需要先保存有效数据个数，以便后面更新_finishiterator tmp = new T[n];if (_start){for (size_t i = 0; i < size(); i++){*(tmp + i) = *(_start + i);}delete[] _start;}_start = tmp;_finish = _start + sz;_endofstorage = _start + n;}}

运行结果：