【C++从0到王者】第十二站：vector基本使用

一、vector基本介绍

如下图所示，从这里我们可以得知，vector其实本质是一个动态增长的顺序表，是一个可以改变容量大小的数组。也就是说它与string的本质是一样的，而vector这个英文翻译成中文是向量的意思
就像数组一样，vector的元素使用连续的存储位置，这意味着也可以使用指向其元素的常规指针上的偏移量来访问它们的元素，并且与数组一样高效。但与数组不同的是，它们的大小可以动态变化，容器会自动处理它们的存储。
在内部，vector使用动态分配的数组来存储它们的元素。这个数组可能需要重新分配，以便在插入新元素时增加大小，这意味着分配一个新数组并将所有元素移动到其中。就处理时间而言，这是一个相对昂贵的任务，因此，vector不会在每次向容器中添加元素时重新分配。
相反，vector容器可以分配一些额外的存储空间，以适应可能的增长，因此容器的实际容量可能大于包含其元素严格所需的存储空间(即其大小)。库可以实现不同的增长策略，以平衡内存使用和重新分配，但在任何情况下，重新分配应该只发生在对数增长的大小间隔内，以便在向量末尾插入单个元素时可以提供平摊的常数时间复杂度(参见push_back)。
因此，与数组相比，向量消耗更多的内存，以换取以有效的方式管理存储和动态增长的能力。
与其他动态序列容器(deque、lists和forward_lists)相比，vector可以非常高效地访问其元素(就像数组一样)，并且可以相对高效地从其末端添加或删除元素。对于涉及在末尾以外的位置插入或删除元素的操作，它们的性能比其他操作差，并且迭代器和引用的一致性不如列表和forward_lists。

二、vector的基本使用

我们首先来大致浏览以下vector的接口，其实我们也能够大概理解这些接口的意思

我们可以大概的使用一些这些接口，如下所示

void testvector1()
{vector<int> v;v.push_back(1);v.push_back(2);v.push_back(3);v.push_back(4);for (size_t i = 0; i < v.size(); i++){cout << v[i] << " ";}cout << endl;vector<int>::iterator vit = v.begin();while (vit != v.end()){cout << *vit << " ";vit++;}cout << endl;
}

处理加入内置类型之外，我们也可以加入string，vector等类类型

void testvector2()
{vector<string> v;string name("zhangsan");v.push_back(name);v.push_back(string("lisi"));v.push_back("wangwu");vector<vector<int>> vv;
}

在上述代码中，我们相对vector<string>插入一个string的方式可以有很多种，比如先构造一个string，然后尾插他，比如直接插入匿名对象，比如直接插入字符串，让这个字符串进行隐式类型转换构造欻string以后然后在插入进去

我们甚至还可以定义vector<vetor<int>>这种套娃的形式，其实这个形式本质就是一个二维数组

三、vector<char> 和string的区别

显而易见是肯定不可以相互替代

1. 首先string和vector<char>在结构上就有所区别,string它会主动加上\0，而vector是不会的，这样一来，vector其实是不是那么跟c语言进行兼容的
2. 其次string的接口是更加丰富的。string还有+=，比较大小的接口这些都是有实际意义的。而对于vector对于比较大小是没有意义的，虽然库里面也支持了比较大小。
3. string还有插入一个字符，插入字符串等更加丰富的接口，而vector要针对于各种类型，所以它就没有这么多接口

总而言之，即以下两点

1. string要求最后又\0，可以更好的兼容C语言
2. string有很多他的专用接口函数

所以说，vector和string有各自存在的价值的

四、vector接口介绍

1.vector的模板参数

如下图所示，vector的模板参数有以下两个，一个是T，决定vector里面的数据是什么类型的，一个是缺省的模板参数，这个是一个内存池，库里面自动提供了，当然我们一般用这个也就够了，不会自己去写的

2.构造函数

如下所示，有如下几种构造函数
allocator是一个内存池，他也是一个缺省参数，我们暂时不管他

不难看出，第一个是一个无参的构造函数，第二个是n个val的构造，第三个是一个迭代器区间进行初始化，第四个是拷贝构造函数

下面是前两个的使用

void testvector3()
{vector<int> v1;vector<int> v2(10, 1);vector<string> v3(10, "****");for (auto e : v2){cout << e << " ";}cout << endl;for (auto e : v3){cout << e << " ";}cout << endl;
}

对于第三个构造函数，我们注意到他其实是一个模板，也就是说，他可以使用任意一个迭代器进行初始化。只要类型匹配即可。

void testvector3()
{vector<int> v1;vector<int> v2(10, 1);vector<string> v3(10, "****");for (auto e : v2){cout << e << " ";}cout << endl;for (auto e : v3){cout << e << " ";}cout << endl;vector<int> v4(v2.begin(), v2.end());for (auto e : v4){cout << e << " ";}cout << endl;vector<string> v5(v3.begin(), v3.end());for (auto e : v5){cout << e << " ";}cout << endl;string s("hello world");vector<char> v6(s.begin(), s.end());for (auto e : v6){cout << e << " ";}cout << endl;//数组名其实就是一个天然的迭代器int a[] = { 1,2,3,4 };vector<int> v7(a, a + 4);for (auto e : v7){cout << e << " ";}cout << endl;
}

除此之外，我们知道。stl有容器和算法，而算法中比如说sort他就是支持各种类型的容器进行排序,因为其是用模板的，对某一个迭代器区间进行排序

我们可以去使用一下，如下所示，库里面默认是排升序，即<,我们如果要排升序的话，可以直接使用greater<int>对象。这个类型库里面已经定义好了，我们直接用就可以，也可以直接用他的匿名对象

void testvector4()
{vector<int> v;v.push_back(151);v.push_back(1);v.push_back(1511);v.push_back(12);v.push_back(11);v.push_back(10);for (auto e : v){cout << e << " ";}cout << endl;sort(v.begin(), v.end());for (auto e : v){cout << e << " ";}cout << endl;//greater<int> gt;//sort(v.begin(), v.end(), gt);sort(v.begin(), v.end(), greater<int>());for (auto e : v){cout << e << " ";}cout << endl;}

还有如下的使用等

void testvector5()
{string s("hello world");sort(s.begin(), s.end());cout << s << endl;int a[] = { 456,12,11,151 };sort(a, a + 4);for (auto e : a){cout << e << " ";}cout << endl;
}

3.迭代器

他有如下的几种迭代器

下面是正向迭代器，前者支持读写，后者只读

下面是反向迭代器，前置支持读写，后者只读

正向迭代器的使用很简单，我们现在来看一下反向迭代器的使用

void testvector6()
{vector<int> v;v.push_back(151);v.push_back(1);v.push_back(1511);v.push_back(12);v.push_back(11);v.push_back(10);for (auto e : v){cout << e << " ";}cout << endl;sort(v.rbegin(), v.rend());for (auto e : v){cout << e << " ";}cout << endl;//greater<int> gt;//sort(v.rbegin(), v.rend(), gt);sort(v.rbegin(), v.rend(), greater<int>());for (auto e : v){cout << e << " ";}cout << endl;
}

不难得出，反向迭代器可以直接排降序。

4.size和max_size

如下是size这个接口，他的作用是返回当前元素的个数。这个还是比较常用的一个接口

如下是max_size，这个接口在实际中并无太大的用处，他的功能是返回vector所能容纳的最大元素数。

5.resize和reserve

这两个接口与string是类似的，resize是开空间+填数据，而reserve仅仅只是开空间，不改变size的值。

下面是我们容易犯的一个错误

void testvector7()
{vector<int> v;v.reserve(10);for (int i = 0; i < 10; i++){v[i] = i;}
}

这里出现错误的原因其实就是因为我们混淆了reserve和resize，reserve他改变的仅仅只是capacity，不会去改变size，这样一来的话，我们就会产生越界现象。自然就会报错了。

我们应该使用resize

当然如果我们非要使用reserve的话，其实我们可以直接使用push_back接口，想必大家都是可以理解的

6.operator[]和at

这两个接口他与string中的接口也是类似的道理，他们两个也是存在区别的，operator[]接口他比较暴力，是使用断言的。而at中的接口他是比较温柔一点的，他是使用抛异常的方式，异常是可以捕获的

断言的缺陷就是只在debug环境下生效，在release下不生效

7.front和back

同样的与string类似，一个是访问第0个数据，一个是访问最后一个数据。这两个接口完全可以由operator[]运算符重载进行替代，存在一些冗余，但是其实还好。

8.data

data这个接口与string中的c_str接口是十分类似的，data返回的是内部的数组指针。c_str其实也是返回内部的字符串数组指针。

9.push_back和pop_back

这两个接口就比较简单了，分别为尾插和尾删。比较容易理解

需要注意的是，在vector中并没有提供头插头删这两个接口，因为这两个接口的效率是比较低的。一般是很少使用的

10.insert和erase

虽然并没有提供头插头删这两个接口，但是c++提供了insert和erase这个接口，同样的类比的方法，我们可以知道，insert可以在任意一个位置进行插入，erase用于在任意位置删除一个数据

我们可以简单的去使用一下

void testvector8()
{vector<int> v;v.resize(10);for (int i = 0; i < 10; i++){v[i] = i;}for (auto e : v){cout << e << " ";}cout << endl;//头删v.erase(v.begin());for (auto e : v){cout << e << " ";}cout << endl;//头插v.insert(v.begin(), 100);for (auto e : v){cout << e << " ";}cout << endl;//删除第三个位置v.erase(v.begin() + 2);for (auto e : v){cout << e << " ";}cout << endl;
}

假如我们现在想要删除值为5的数据，但是我们发现vector里面并没有find。事实上find在算法库里面是有的。而string中有find的一个原因就是因为string中对find的要求比较多样化，有可能是查找一个子串，有可能是查找某个字符。功能需求比较特殊，而vector是不需要写的。
他需要接收一个迭代器区间，然后在这个区间中找到目标值。

	//删除数值为5的数据，但是不知道5在哪里vector<int>::iterator pos = find(v.begin(), v.end(), 5);if(pos != v.end()){v.erase(pos);}for (auto e : v){cout << e << " ";}cout << endl;

那么如果一个vector中涉及到很多个5，我们都想删掉，我们该如何操作呢？我们很容易就想当然的以为这样就可以了
结果我们发现程序崩溃了，这里其实涉及到迭代器失效的问题了。我们后序在详细说明

11.assign

如下图所示，assign这个函数的作用主要就是赋值。他会将原来的vector里面的数据给清掉，然后对其进行赋值

void testvector9()
{vector<int> v(10, 0);for (auto e : v){cout << e << " ";}cout << endl;v.assign(10, 1);for (auto e : v){cout << e << " ";}cout << endl;
}

12.swap和clear

如下所示，swap即交换两个vector里面的东西

clear的作用是清掉vector里面的数据

五、几道经典例题

1.只出现一次的数字

力扣136：只出现一次的数字

题解：

这道题目是很简单的一道题，直接异或即可，使用C++的做法如下所示

class Solution {
public:int singleNumber(vector<int>& nums) {int val=0;for(int i=0;i<nums.size();i++){val^=nums[i];}return val;}
};

2.杨辉三角

力扣118：杨辉三角

题解：
这道题题目也是很简单，逻辑上没有任何难度，但是结构上难度较大
如果使用C语言的话，那么他的参数是很复杂的。因为杨辉三角其实就是一个二维数组，二维数组我们就得自己模拟一个二维数组来实现。要开二维数组，得先开一个指针数组，每个指针都要指向一个空间。而我们如果要返回的话，我们就得返回一个指针这个指针数组的指针，这个指针的类型就是int**。

除此之外还有两个输入型参数，一个是数组的行数，一个是数组的列数，由于数组的列数也是变化的，所以其实还是要传一个数组，这个数组我们直接传入的是一个指针，我们在这个指针所指向的空间中开一块数组空间在这里面进行填值。

所以这道题使用C语言结构上是非常之繁琐的

而如果使用C++的话，那么我们就无需自己开空间了，我们直接使用vector<vector<int>>就可以很方便的开好二维数组。极大的简化了结构上的难度。

class Solution {
public:vector<vector<int>> generate(int numRows) {vector<vector<int>> v;v.resize(numRows);for(int i=0;i<numRows;i++){v[i].resize(i+1,0);v[i][0]=v[i][i]=1;}for(int i=2;i<v.size();i++){for(int j=1;j<v[i].size();j++){if(v[i][j]==0){v[i][j]=v[i-1][j]+v[i-1][j-1];}}}return v;}
};

3.电话号码的字母组合

力扣17：电话号码的字母组合

题解：

这道题其实确实有些复杂。它是一道典型的多路递归。比二叉树的还要复杂。
我们这样确定思路，题目中已经给出了电话号码组合，而每一个数字又对应着一个字符串的组合。我们先想办法把这些字符串给取出来。取出来以后，我们开始拿这三个字符去与下面的字符进行组合。此处相当于三路递归。为了方便，我们直接写成循环形式。
就这样写成递归的形式，然后就可以顺利的取出所有的字符组合了。
当我们的层数刚好等于电话号码的个数的时候，也就意味着，该结束本层递归了。

class Solution {string SArr[10]={"","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};
public:void Combination(vector<string>& v,string digits,int level,string s){if(level==digits.size()){v.push_back(s);return ;}int num=digits[level]-'0';string str=SArr[num];for(int i=0;i<str.size();i++){Combination(v,digits,level+1,s+str[i]);}}vector<string> letterCombinations(string digits) {vector<string> v;if(digits.empty()){return v;}Combination(v,digits,0,"");return v;}
};

---

好了本期内容就到这里了
如果对你有帮助的话，不要忘记点赞加收藏哦！！！