【C++】vector的使用练习+模拟实现

目录

前言

一、vector的介绍

二、vector的使用

三、vector的简单练习题

四、模拟实现 vector

1.基本框架

2.功能实现

3.完整代码

总结

---

---

前言

        本文主要介绍C++的【STL】容器之一的 vector，从基本功能介绍，到常用接口使用演示，接着还有 5 道vector使用练习题加强接口使用熟练度，最后模拟实现 vector，加强对 vector 的理解乃至完全掌握。

---

一、vector的介绍 vector是C++【STL】中的一类容器，表示大小可以变化的数组。可以理解为顺序表一样的东西。与string类一样，vector也是一个类模版，第二个参数为空间配置器有默认参数我们先不管，第一个参数就是我们平时实例化时需要传递的元素类型。

比如：

#include <iostream> #include <vector> using namespace std; int main() { //基本类型 vector<int> v1; vector<char> v2; vector<double> v3; //类类型 vector<string> v4; vector<vector<int>> v5;//类似二维数组 //...等 return 0; }

---

二、vector的使用

使用STL的三个境界：能用，明理，能扩展 ，那么下面学习vector，我们也是按照这个方法去学习

 1.vector 的构造

（1）是默认构造，不传参（2）使用 n 个 val 进行初始化构造（3）使用迭代器区间进行构造（4）拷贝构造

除此之外，C++11中还有一种我们常用的构造：

使用 initializer_list<value_type> 类的容器进行构造。是不是看着很陌生，简单演示一下你就知道这是什么了：

initializer_list<value_type> 构造演示：

#include <iostream> #include <vector> using namespace std; int main() { vector<int> v1 = { 1,2,3,4,5,6,7,8 }; for (auto& e : v1) { cout << e << " "; } cout << endl; return 0; }

运行结果：

---

扩展：  使用大括号括起来的一串数字进行初始化 { 1,2,3,4,5,6,7,8 }这个大括号括起来的容器名就叫 initializer_list，它也是一个容器，不过该容器比较特殊，下面我们简单介绍一些该容器

initializer_list 介绍：

首先它也是一个类模版，并且只需要传递一个类型的参数它不支持修改类的接口，它的接口非常简单，如下：除了基本的构造外，就只有迭代器的接口和 size 接口，因此该容器就我们目前看来，仅用作遍历和对其他容器进行赋值

我们也可以直接声明并使用该容器：

#include <iostream> #include <vector> using namespace std; int main() { initializer_list<int> l1 = { 1,2,3,4,5,6 }; for (auto& e : l1) { cout << e << " "; } cout << endl; return 0; }

 运行结果：

---

2.vector的遍历 （1）首先，vector 重载了 [ ] 运算符

普通版本和重载的const版本返回的是下标 n 对应元素的引用

因此可以使用 [ ] 进行遍历：

#include <iostream> #include <vector> using namespace std; int main() { vector<int> v1 = { 10,9,8,7,6,5 }; for (size_t i = 0; i < v1.size(); i++) { cout << v1[i] << " "; } cout << endl; }

运行结果：

---

（2）迭代器遍历

关于迭代器的详细介绍在上一篇string中，因为STL很多设计都是互通的，因此不再赘述。以下演示正向的普通迭代器

演示：

#include <iostream> #include <vector> using namespace std; int main() { vector<int> v1 = { 1,2,3,4,5,6 }; vector<int>::iterator it = v1.begin();//可以简写为: auto it = v1.begin() while (it != v1.end()) { cout << *it << " "; ++it; } cout << endl; return 0; }

运行结果：

---

（3）范围for遍历

请记住，只要容器支持了迭代器，那么它就支持范围for，我们模拟实现的迭代器，它也会自动支持范围for，因为范围for的底层就是迭代器实现的。

#include <iostream> #include <vector> using namespace std; int main() { vector<int> v1 = { 4,5,6,7,8,9,10 }; for (auto& e : v1) { cout << e << " "; } cout << endl; return 0; }

运行结果：

---

3.常用接口介绍

有了 string 接口使用的基础，这一块学起来就很快

<1>.空间容量相关接口 容量空间接口说明size获取数据个数capacity获取容量大小empty判断是否为空resize改变vector的sizereserve改变vector的capacityshrink_to_fit缩容使capcity尽量接近size大小 扩容方面：capacity的代码在vs和g++下分别运行会发现，vs下capacity是按1.5倍增长的，g++是按 2 倍增长的。这个问题经常会考察，不要固化的认为，vector增容都是2倍，具体增长多少是根据具体的需求定义的。vs是PJ版本STL，g++是SGI版本STL。reserve只负责开辟空间，如果确定知道需要用多少空间，reserve可以缓解vector增容的代 价缺陷问题。resize在开空间的同时还会进行初始化，影响size。

测试扩容代码： （vs）

#include <iostream> #include <vector> using namespace std; // 测试vector的默认扩容机制 void TestVectorExpand() { size_t sz; vector<int> v; sz = v.capacity(); cout << "making v grow:\n"; for (int i = 0; i < 100; ++i) { v.push_back(i); if (sz != v.capacity()) { sz = v.capacity(); cout << "capacity changed: " << sz << '\n'; } } } int main() { TestVectorExpand(); return 0; }

运行结果：

---

（1）size ，capacity 和 empty

#include <iostream> #include <vector> using namespace std; int main() { vector<int> v1; for (int i = 0; i < 50; i++) { v1.push_back(i); } cout << v1.empty() << endl; cout << "szie: " << v1.size() << endl; cout << "capacity: " << v1.capacity() << endl; return 0; }

运行结果：

---

（2）resize

声明：

两个版本，第二个版本的 val 是当 n > size 时，给新空间初始化的值

演示：

#include <iostream> #include <vector> using namespace std; int main() { vector<int> v1 = { 1,2,3,4 }; for (auto& e : v1) { cout << e << " "; } cout << endl; //n < size,删除数据 v1.resize(2); for (auto& e : v1) { cout << e << " "; } cout << endl; //n > size（大于capacity就会扩容） v1.resize(10, 8); for (auto& e : v1) { cout << e << " "; } cout << endl; return 0; }

运行结果：

---

（3）reserve、shrink_to_fit

只能扩容，不能缩容，用于提前开空间避免多次扩容消耗效率用于缩容

演示：

#include <iostream> #include <vector> using namespace std; int main() { vector<int> v1 = { 1,2,3,4 }; cout << "capacity: " << v1.capacity() << endl; v1.reserve(10); cout << "capacity: " << v1.capacity() << endl; v1.shrink_to_fit(); cout << "capacity: " << v1.capacity() << endl; return 0; }

运行结果：

---

<2>.vector的增删查改 vector增删查改接口说明push_back尾插pop_back尾删find查找。（注意这个是算法模块(std)实现，不是vector的成员接口）insert在position之前插入valerase删除position位置的数据swap交换两个vector的数据空间

（1）push_back、pop_back

#include <iostream> #include <vector> using namespace std; int main() { 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.pop_back();//尾删 v1.pop_back();//尾删 for (auto& e : v1) { cout << e << " "; } cout << endl; return 0; }

运行结果：

---

（2）find

注意该 find 是算法库中的 find，vector并没有像 string 一样实现 find 接口，string 是因为字符串查找很多时候并不是对单一字符的查找，所以 string 单独实现了 find 的接口用于满足多样化的需求。而对于 vector ，乃至后面的STL容器如 list、栈和队列等，都是使用统一的算法库中的find。算法库中的find，是在一段迭代器区间中寻找 val。成功返回指定的迭代器位置，失败则返回last，也就是end()返回的的位置

演示：

#include <iostream> #include <vector> using namespace std; int main() { vector<int> v1 = { 84,26,96,51,7 }; auto it = find(v1.begin(), v1.end(), 96); if(it != v1.end()) { cout << *it << endl; } return 0; }

运行结果：

---

（3）insert、erase

插入的位置都是以迭代器进行控制（1）是在指定位置插入一个val（2）是在指定位置插入 n 个 val（3）是在指定位置插入一个迭代器区间

erase删除元素第一个是删除一个指定位置的元素，第二个是删除一个迭代器区间的数据

演示：

#include <iostream> #include <vector> using namespace std; int main() { //插入 vector<int> v1 = { 1,2,3,4 }; v1.insert(v1.end(), 5); for (auto& e : v1) { cout << e << " "; } cout << endl; v1.insert(v1.begin(), 3, 8); v1.insert(v1.end(), 5); for (auto& e : v1) { cout << e << " "; } cout << endl; //删除 v1.erase(v1.begin()); for (auto& e : v1) { cout << e << " "; } cout << endl; v1.erase(v1.begin() + 3, v1.end()); for (auto& e : v1) { cout << e << " "; } cout << endl; return 0; }

运行结果：

---

（4）swap

底层就是互换指针，效率高

和 string 一样重载了全局的swap，这样可以直接 swap(v1,v2) 进行调用了，底层一样是指针交换，效率高。

演示：

#include <iostream> #include <vector> using namespace std; int main() { vector<int> v1 = { 1,2,3,4 }; vector<int> v2 = { 99,88,77,44 }; cout << "交换前v1: "; for (auto& e : v1) { cout << e << " "; } cout << endl; cout << "交换前v2: "; for (auto& e : v2) { cout << e << " "; } cout << endl; swap(v1, v2);//交换 cout << "交换后v1: "; for (auto& e : v1) { cout << e << " "; } cout << endl; cout << "交换后v2: "; for (auto& e : v2) { cout << e << " "; } cout << endl; return 0; }

运行结果：

---

4.小结

以上接口能满足我们大部分的需求了，当然 vector 还有一部分接口，比如：

关系运算符重载的接口：赋值运算符重载：等等，还有像 at、assign等，不常用，但需要时我们可直接查阅资料即可。

---

三、vector的简单练习题 1.杨辉三角：

链接：118. 杨辉三角 - 力扣（LeetCode）

思路：

使用二维数组进行实现，也就是 vector<vector<int>> v，这样 v 的每个元素都是一个 vector<int> 对象，可以对每个元素进行长度控制。初始化时将所有元素初始化为1，接着从第三行开始计算，使用嵌套循环，无需计算开头和结尾处，这一点在循环上进行限制，计算公式 v[i][j] = v[i-1][j] + v[i-1][j-1]；

题解：

class Solution { public: vector<vector<int>> generate(int numRows) { vector<vector<int>> vv(numRows, vector<int>()); //数据全初始化为1 for(size_t i=0; i<vv.size(); ++i) { vv[i].resize(i+1, 1); } //遍历二维数组，计算数值 for(size_t i=0; i<vv.size(); ++i) { for(size_t j=1; j<vv[i].size()-1; ++j) { vv[i][j] = vv[i-1][j]+vv[i-1][j-1]; } } return vv; } };

---

2.只出现一次的数字I

链接：136. 只出现一次的数字 - 力扣（LeetCode）

思路：

这题比较简单，只是一道开胃菜，只要我们知道两个相同的数异或就会等于0，并且0异或任意数还是等于任意数即可。

题解：

class Solution { public: int singleNumber(vector<int>& nums) { int ret = 0; for(auto e : nums) { ret = ret^e; } return ret; } };

---

3.只出现一次的数字II

链接：137. 只出现一次的数字 II - 力扣（LeetCode）

思路1：

先说一下我的思路，我是先将数据进行排序，然后每三个一组进行检查是否三个完全相等，只要遇到不相等的一组就进一步判断，确定返回值。说到排序，这里需要介绍算法库中的排序算法：sortsort 是一个函数模版，模版参数就是迭代器，只不过这里是随机迭代器，关于这点后面文章会详细讲到。我们使用 sort 时只需要传递需要排序的迭代器区间就行。sort 的底层大概是快排可能还融合了其他的排序算法，总之效率肯定高。题目要求时间复杂度为O(n)，空间复杂度为O(1)，虽然排序消耗了一定性能，但是进过测试可以跑过

题解1：

class Solution { public: int singleNumber(vector<int>& nums) { sort(nums.begin(), nums.end());//排序 int index = 0; while (index < nums.size() - 1) { //每三个一判断 if (nums[index] != nums[index + 1] || nums[index + 1] != nums[index + 2]) { return nums[index] == nums[index + 1] ? nums[index + 2] : nums[index]; } index += 3;//每次跳3个 } //这里说明最后不足以凑成3个，那么就只有1个数据 return nums[index]; } };

思路2：

这个不太容易想到，它既满足了时间复杂度O(n)的要求，又满足了空间复杂度O(1)的要求。首先通过上一道题，我们联想到2进制层面，观察 3 5 3 3 这四个数的二进制位：我们观察得到，3 3 3的二进制中，只要出现1的一列，就有3个1，我们仔细想想也能发现，每3个相同的数的二进制，当二进制的某一位为1时，那么这一列就会出现3个1，也就是3的倍数，我们将所有的数以二进制进行对齐排列，我们会发现，除去只出现一次的那个数，剩下二进制出现1的一列，出现1的总和就是3的倍数。那么加上哪个只出现一次的数，当二进制的某一列的1的总数不能被3整除时，那么就说明该列多了一个1，那么接下来，我们就可以一步一步复刻出这个只出现一次的数。我们用total记录所有数二进制每一列1的总和，如果 total 能够被3整除，那么说明只出现一次的数在该位置是一定是0，否则，该位置是一定是1，我们将32个二进制位一位一位复原，就能复刻出只出现一次的那个数。最后返回该数即可。

题解：

class Solution { public: int singleNumber(vector<int>& nums) { int ans = 0; for (int i = 0; i < 32; ++i) { // 统计该每个数字第i个比特位为1的总数 int total = 0; for (int num: nums) { total += ((num >> i) & 1); } // 如果total能够被3整除，说明只出现一次的数字在该位置上一定是0 // 否则在该位置上一定是1 if (total % 3) { ans |= (1 << i); } } return ans; } };

---

4.只出现一次的数字III

链接：260. 只出现一次的数字 III - 力扣（LeetCode）

思路：

首先，根据题目，元素的个数肯定是2的倍数，还是先排序，排序后，开始开始遍历，每次遍历两个，将两个数进行异或运算，通过结果是否为0判断两个数是否相同。也就是下图：当然，这只是第一种情况，还有第二种情况，数据已经排好序，如：1,2,2,3，这时候如果按照上面思路就会返回1,2，不符合题意，而这时候，我们就需要控制下标，将每次跳过两个数的起点下标+1，当然遇到两个数不相等时需要进一步判断具体哪个数是需要返回的，这时候我们就通过将第二个数与第三个数进行比较，如果第二个数与第三个数相等，就说明第一个数是需要返回的数，这时候将第一个数尾插到待返回的vector中，并且重新设置下标继续遍历，反之如果第二个数与第三个数不相等，也就是上图中的情况，直接返回这两个不相等的数。

题解：

class Solution { public: vector<int> singleNumber(vector<int>& nums) { sort(nums.begin(), nums.end());//先排序 vector<int> ret;//设置返回值 size_t i = 0;//外置，后面有用 for(; i<nums.size()-1; i+=2)//下标i要小于倒数第二个数，避免越界 { int num = nums[i]^nums[i+1];//异或 if(num!=0) { if(i+2<nums.size()-1 && nums[i+2]==nums[i+1]) { ret.push_back(nums[i]); i=i+1; continue; } ret = {nums[i],nums[i+1]}; break; } } //i是最后一位下标说明最后一位数就是待返回数 if(i == nums.size()-1) { ret.push_back(nums[i]); } return ret; } };

---

5.删除有序数组中的重复项

链接：26. 删除有序数组中的重复项 - 力扣（LeetCode）

思路：

最后以一道较简单的题结束练习吧。根据题意，数据已有序，需删除重复项，为了保证时间效率，我们先不在原数组中操作删除数据，我们先创建一个数组 v，将不重复项全部尾插到 v，最后计算 v 的大小 k，利用循环将原数组的前 k 个数改为数组 v 中的值。

 题解：

class Solution { public: int removeDuplicates(vector<int>& nums) { vector<int> v; for(size_t i = 0; i < nums.size()-1; i++) { if(nums[i]!=nums[i+1]) { v.push_back(nums[i]); } } //无论最后两个数是否相等，最后一个数必然需要插入 v.push_back(nums[nums.size()-1]); int k = v.size(); for(size_t i=0; i<k; i++) { nums[i]=v[i]; } return k; } };

---

四、模拟实现 vector

注意：因为实现顺序的不同，同一个接口在后面会有优化和改动，模拟的最终结果在最后，中间是实现的思路过程

1.基本框架 我们前面实现 string 时，类的基本成员变量为：char*str、size_t size、size_t capacity。但是 vector 就不一样了。

我们可以查阅官方实现 vector 的源码：

源码中，vector 的成员变量为：也就是三个迭代器变量

iterator start; iterator finish; iterator end_of_storage;

继续查找迭代器定义：

本质其实就是对指针的封装重命名（指针在源码中是被封装成类的） ：

typedef T value_type; typedef value_type* pointer; typedef value_type* iterator;

我们看一下源码中的构造（部分）：

vector() : start(0), finish(0), end_of_storage(0) {} vector(size_type n, const T& value) { fill_initialize(n, value); }

我们再继续查看 size() 和 capacity，看看它们是怎么返回元素个数和容量的：

size_type size() const { return size_type(end() - begin()); } size_type capacity() const { return size_type(end_of_storage - begin()); }

我们发现：它们是通过指针相减来计算元素个数和容量大小的

---

更多的源码内容我们不再继续看了，接下来正式开始模拟实现基本框架：

基本框架模拟：

#pragma once #include <iostream> #include <assert.h> using namespace std; namespace txp { template<class T> class vector { public: typedef T* iterator;//迭代器 typedef const T* const_iterator;//const迭代器 //默认构造 vector() {} //默认析构 ~vector() { if (_start) { delete[] _start; _start = _finish = _endofstorage = nullptr; } } private: iterator _start = nullptr; iterator _finish = nullptr; iterator _endofstorage = nullptr; }; } 对于 vector 的模拟，我们同原版一样采用模版类进行实现，为了与原版 vector 区分，因此我们需要使用命名空间 namespce 进行隔离。迭代器，我们就直接使用指针进行重命名。定义三个成员变量，_start 指向第一个元素地址，_finish 指向最后一个元素的下一个空间地址，_endofstorage 指向空间容量的末尾地址。默认构造就什么都不传，使用默认值初始化，析构就销毁堆空间。

---

2.功能实现 （1）迭代器、size() 、capacity() 和 [ ]运算符重载 //迭代器 iterator begin() { return _start; } iterator end() { return _finish; } const_iterator begin() const { return _start; } const_iterator end() const { return _finish; } //返回size size_t size() const { return _finish - _start; } //返回capacity size_t capacity() const { return _endofstorage - _start; } //重载[] 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]; } 这几个实现起来简单明了，不过多解释

---

（2）reserve 和 push_back //reserve void reserve(size_t n) { if (n > capacity()) { size_t oldSize = size(); T* tmp = new T[n]; if (_start) { memcpy(tmp, _start, sizeof(T) * oldSize);对于string一类来说，存在浅拷贝问题 } delete[] _start; _start = tmp; _finish = _start + oldSize; _endofstorage = _start + n; } } //push_back void push_back(const T& x) { //原始写法 if (_finish == _endofstorage) { reserve(capacity() == 0 ? 4 : capacity() * 2); } *_finish = x; ++_finish; } reserve 只有一个参数 n ，并且只在 n>capacity 时才起作用进行扩容，扩容这里有第一个坑，就是 size() 大小，这里设置变量 oldSize 就是记录原空间大小，因为如果不记录原空间大小，当我们 delete[] _start 后，原空间销毁，此时 _finish 的更新就会出现问题，因为原空间消失，而 size() 又需要根据 _finish 地址来确定，因此无法更新 _finish，所以设置参数 oldSize 用来帮助 _finish 进行更新。而空间内容拷贝使用函数 memcpy 就是第二个大坑，这里是关于深拷贝的问题，我们待会儿再解释和解决这个问题push_back，在我们没有实现 insert 之前，先采用原始写法，判断是否需要扩容和尾插元素。push_back 扩容策略是第一次开4个空间，后面2倍扩容

解释第二个大坑，深拷贝问题：

如果我们使用 memcpy 进行空间拷贝，在以下情况就会报错：

#include "vector.h" int main() { txp::vector<string> v1; v1.push_back("11111111"); v1.push_back("11111111"); v1.push_back("11111111"); v1.push_back("11111111"); v1.push_back("11111111"); for (auto& e : v1) { cout << e << " "; } cout << endl; return 0; }

运行结果：

原因解释：

首先，当我们尾插到第五个数据时，就需要扩容，问题就是 memcpy 是按照字节进行复制的，而 vector 的底层是三个指针，这时 memcpy 就只会将地址复制过来，而指针指向的空间的内容就没有复制，这就是浅拷贝的问题。示意图：

解决方法：

//reserve 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; } } 使用 for 循环进行拷贝，这样的好处就是对于类类型，它门会调用对应的赋值运算符重载函数，不会导致浅拷贝。

---

（3）insert 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; }

迭代器失效问题： 

首先说明这是修正后的版本，这里需要解释的就是迭代器失效问题。这里有两个迭代器失效的问题insert 插入数据，很多时候时候就需要扩容，扩容我们调用 reserve，reserve 会更新 _start,_finish,_endofstorage，但是参数中的 pos 就没有更新，pos 指向空间被销毁了，这就是迭代器失效问题。解决方法就是上面的，先计算原 pos 与 _start 直接的长度扩容后更新 pos。其实前面 reserve 中更新 _finish 也是迭代器失效的问题。第二个迭代器失效的问题就是返回值了，你可能会好奇为什么返回值是一个迭代器，而且返回的是 pos 的位置。观察仔细的同学前面就可能已经发现官方的 insert 也是有返回值的。

第二个迭代器失效的场景：

void test2() { 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); if (it != v1.end()) { //更新it it = v1.insert(it, x * 10); cout << *it << endl; } } 如果我们不更新 it 你猜会发生什么，it 指向的原空间会因为 insert 中的扩容而销毁。当我们解引用 it 的时候程序就会崩溃。所以解决方法就是设置返回值。

push_back 优化：

//push_back void push_back(const T& x) { //复用写法 insert(_finish, x); } 复用写法，减少代码量。

---

（4）补充构造函数 //initializer_list<value_type> il构造 vector(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);//push_back就包括了开空间和扩容 } } //迭代器构造 //类模版的成员函数，也可以写成模版函数，支持范围更广 template <class InputIterator> vector(InputIterator first, InputIterator last) { reserve(last - first); while (first != last) { push_back(*first); ++first; } } //n个val初始化构造 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); } } 支持initializer_list<value_type> 构造后，就可以在初始化时使用大括号连续初始化了，提前开空间提升效率，push_back进行拷贝赋值。拷贝构造同理，使用 push_back 即可，push_back 就包含了开空间扩容等操作。迭代器构造，迭代器构造为什么要写成模版函数，因为可以支持其他容器的迭代器区间进行初始化，下面可以演示一下： #include "vector.h" int main() { string s1 = "abcdef"; txp::vector<int> v1(s1.begin(), s1.end()); for (auto& e : v1) { cout << e << " "; } cout << endl; return 0; }

运行结果：

接着我们看第四个构造，使用 n 个 val 进行初始化构造，第二个参数可以调用 T() 当缺省参数，T() 可以是所有类的匿名对象，包括内置类型也可以这样使用，因为 c++ 中哪怕内置类型也有构造函数。因为 c++ 有模版，所以相当于将c语言中的内置类型全升级成了类。这里有个疑惑，为什么要写两个差不多的这样的构造？因为如果我们没有写重载的 n 个 val 的构造，那么当我们声明：vector<int> v(6,1); 时，因为 size_t 和 int 是有区别的，我们知道有函数模版存在时，会调用类型最接近的函数，那么因为 size_t 与 int 的区别，所以会调用到上面的迭代器模版函数，这时候迭代器就会初始化为 int，当 *int 时就会报错。这种情况只有 int 有，其他如 double 等就不会调用到迭代器模版，因为 vector<int> v(6,1) 中，6和1都是 int 类型，1换成double类时，迭代器就不能匹配两个参数了，因此会调用到 n 个 val 的构造，此时 int 会强转为 size_t。解决方法就是重载一个 int 类型的 n 个 val 构造。

---

（5）swap、= 重载、empty和pop_back //swap交换 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; } //判空 bool empty() const { return _start == _finish; } //尾删 void pop_back() { assert(!empty()); --_finish; } swap 交换其实就是交换底层迭代器地址就行。赋值运算符重载这里选择的是代码量最小的现代写法，首先参数 v 没有写成引用，这样传参时会调用拷贝构造，这样 v 就复制了一份vector对象，而 v 正好是当前对象需要的，因此调用 swap 交换两者，当前对象就完成了赋值，并且 v 因为是形参，出了函数就会自动调用析构销毁，所以正好将当前对象的原空间销毁了。一举两得，最后返回当前对象即可。empty 判空只需要检查地址，pop_back 尾删只需要移动_finish指针即可。

---

（6）erase 和 resize //erase，第二种迭代器失效的地方 iterator erase(iterator pos) { assert(pos >= _start && pos < _finish); iterator i = pos + 1; while (i < _finish) { *(i - 1) = *i; ++i; } --_finish; return pos; }

首先说明 erase：

挪动数据示意图：从后向前挪覆盖 pos 位置数据，最后 -- _finish 删除最后一个元素

这里要说的是第二种迭代器失效：

这里也是为什么 erase 有返回值的原因：

返回值为 pos ，也就是被删除数据的原位置。在下面场景中，如果没有返回值更新，程序就会崩溃： void test3() { txp::vector<int> v1; v1.push_back(1); v1.push_back(2); v1.push_back(3); v1.push_back(4); v1.push_back(5); int x; cin >> x; auto it = find(v1.begin(), v1.end(), x); if (it != v1.end()) { it = v1.erase(it); cout << *it << endl;//第二种迭代器失效 } } 虽然，我们这里实现的 vector 即使不更新 it 也不会有问题，因为不涉及扩容等造成原指针指向的空间销毁问题。但是 vs 官方的 vector 这里就会报错，它不允许你使用失效的迭代器，迭代器失效不一定是指原空间被销毁，也可能是指对象发生变化。如果不使用返回值更新 it 的话，即使不报错，在一些场景下也会有逻辑错误问题，比如以下场景：

场景：删除数组中所有的偶数 

#include "vector.h" void test1() { txp::vector<int> v1; v1.push_back(1); v1.push_back(2); v1.push_back(2); v1.push_back(3); v1.push_back(4); v1.push_back(5); v1.push_back(2); for (auto& e : v1) { cout << e << " "; } cout << endl; auto it = v1.begin(); while (it != v1.end()) { if (*it % 2 == 0) { v1.erase(it);//假如不更新it ++it; } ++it; } for (auto& e : v1) { cout << e << " "; } cout << endl; } int main() { test1(); return 0; }

运行结果：

很明显，存在逻辑错误没有删除所有的偶数

正确的写法：

#include "vector.h" void test1() { txp::vector<int> v1; v1.push_back(1); v1.push_back(2); v1.push_back(2); v1.push_back(3); v1.push_back(4); v1.push_back(5); v1.push_back(2); for (auto& e : v1) { cout << e << " "; } cout << endl; auto it = v1.begin(); while (it != v1.end()) { if (*it % 2 == 0) { it = v1.erase(it); } else { ++it; } } for (auto& e : v1) { cout << e << " "; } cout << endl; } int main() { test1(); return 0; }

运行结果：

---

resize：

//resize void resize(size_t n, T val = T()) { if (n < size()) { //删除数据 _finish = _start + n; } else { //无论是否需要扩容，直接调用reserve检查 reserve(n); //新空间初始化 while (_finish < _start + n) { *_finish = val; ++_finish; } } }  resize 有删除元素又有扩容的功能，因此通过 if 判断 n 是否大于size来分为两种情况，而参数 val 则是当增大size或者扩容时，给新空间初始化的值，当然可以不传，因此有缺省参数，缺省参数依旧使用 T() 匿名对象来赋值。当 n < size 时，需要删除元素，此时只需要修改 _finish 指向的位置即可，当 n >= size 时就需要判断是否扩容了，直接调用 reserve 即可，然后就是根据 val 为新空间赋值。

---

3.完整代码

vector 更多的接口没有一一实现，主要实现常用接口帮助我们更加了解这些接口，使用起来更加顺手。

#pragma once #include <iostream> #include <assert.h> using namespace std; namespace txp { template<class T> class vector { public: typedef T* iterator;//迭代器 typedef const T* const_iterator;//const迭代器 //默认构造 vector() {} //initializer_list<value_type> il构造 vector(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);//push_back就包括了开空间和扩容 } } //迭代器构造 //类模版的成员函数，也可以写成模版函数，支持范围更广 template <class InputIterator> vector(InputIterator first, InputIterator last) { reserve(last - first); while (first != last) { push_back(*first); ++first; } } //n个val初始化构造 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); } } //默认析构 ~vector() { if (_start) { delete[] _start; _start = _finish = _endofstorage = nullptr; } } //swap交换 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; } iterator begin() { return _start; } iterator end() { return _finish; } const_iterator begin() const { return _start; } const_iterator end() const { return _finish; } //返回size size_t size() const { return _finish - _start; } //返回capacity size_t capacity() const { return _endofstorage - _start; } //重载[] 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]; } //reserve 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; } } //insert，解决迭代器失效问题：1.重新赋值pos，2.返回值 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; } //push_back void push_back(const T& x) { //复用写法 insert(_finish, x); } //判空 bool empty() const { return _start == _finish; } //尾删 void pop_back() { assert(!empty()); --_finish; } //erase，第二种迭代器失效的地方 iterator erase(iterator pos) { assert(pos >= _start && pos < _finish); iterator i = pos + 1; while (i < _finish) { *(i - 1) = *i; ++i; } --_finish; return pos; } //resize void resize(size_t n, T val = T()) { if (n < size()) { //删除数据 _finish = _start + n; } else { //无论是否需要扩容，直接调用reserve检查 reserve(n); //新空间初始化 while (_finish < _start + n) { *_finish = val; ++_finish; } } } private: iterator _start = nullptr; iterator _finish = nullptr; iterator _endofstorage = nullptr; }; }

---

总结

        以上就是本文的全部内容了，感谢你的支持。