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

前言

        本文主要介绍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>.空间容量相关接口

• 扩容方面：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的增删查改

（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：

• 先说一下我的思路，我是先将数据进行排序，然后每三个一组进行检查是否三个完全相等，只要遇到不相等的一组就进一步判断，确定返回值。
• 说到排序，这里需要介绍算法库中的排序算法：sort
• 
• sort 是一个函数模版，模版参数就是迭代器，只不过这里是随机迭代器，关于这点后面文章会详细讲到。我们使用 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;
	};
}

总结

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