【C++】vector介绍及使用-Toy模板网

这篇具有很好参考价值的文章主要介绍了【C++】vector介绍及使用。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

🚀 作者简介：一名在后端领域学习，并渴望能够学有所成的追梦人。
🚁 个人主页：不良
🔥 系列专栏：🛸C++ 🛹Linux
📕 学习格言：博观而约取，厚积而薄发
🌹 欢迎进来的小伙伴，如果小伙伴们在学习的过程中，发现有需要纠正的地方，烦请指正，希望能够与诸君一同成长！ 🌹

认识vector

【C++】vector介绍及使用,C++,c++,开发语言

vector 是一个类模板，可以根据不同的模板参数实例化出存储不同数据的类。 vector 类可以用来管理数组，与 string 类不同的是，string只能管理 char 类型的数组，而vector可以管理任意类型的数组，vector 类相当于一个动态增长的顺序表。

类模板中有两个参数：第一个是数据类型，第二个是空间配置器。

1.vector是表示可变大小数组的序列容器。

2.vector就像数组一样，vector也采用连续存储空间来存储元素，也就意味着可以采用下标对vector的元素进行访问，和数组一样高效。

3.vector与普通数组的不同是vector的大小是可以动态改变的，而且它的大小会被容器自动处理。

4.vector分配空间策略：vector会分配一些额外的空间以适应可能的增长，因此存储空间比实际需要的存储空间更大。不同的库采用不同

的策略权衡空间的使用和重新分配。但是无论如何，重新分配后都要保证在末尾插入一个元素的时候是在常数时间的复杂度下完成的。因

此，vector占用了更多的存储空间，为了获得管理存储空间的能力，以一种有效的方式动态增长。

5.与其它动态序列容器相比（deque, list and forward_list），vector在访问元素的时候更加高效，在末尾添加和删除元素相对高效。对

于其它不在末尾的删除和插入操作，效率更低。

vector的常用接口

vector的构造函数

(constructor)构造函数声明	接口说明
vector()	无参构造
vector(size_type n, const value_type& val = value_type())	构造并初始化 n 个 val
vector(const vector& x)	拷贝构造
vector(InputIterator first, InputIterator last)	使用迭代器进行初始化构造

vector(InputIterator first, InputIterator last)构造函数是用迭代器区间去初始化，这里的迭代器叫InputIterator，根据特性属性，迭代器可以分为单向迭代器、双向迭代器、随机迭代器；vector中的迭代器是随机迭代器。

单向迭代器相当于单链表，只能读取下一个节点不能读取上一个节点；双向迭代器相当于双向链表，既能读取下一个节点又能读取上一个节点；随机迭代器和双向迭代器性质相同。

我们在这里只需要知道vector可以传任意类型的迭代器，因为这是一个模板，只要类型匹配都可以传，string类的迭代器也可以传给vector，其他的类也可以传。

构造函数的使用：

构造一个int类型的空容器：

//构造一个int类型的空容器
vector<int> v1;//调用无参构造函数
for (auto e : v1)
{
    cout << e;
}
//空
cout << endl;

构造一个含有n个val的int容器：

//构造一个含有n个val的int容器
vector<int> v2(10, 2);
for (auto e : v2)
{
    cout << e;
}
//输出2222222222
cout << endl;

拷贝构造：

//拷贝构造
vector<int> v3(v2);
for (auto e : v3)
{
    cout << e;
}
//输出2222222222
cout << endl;

使用迭代器进行拷贝构造：

//使用迭代器进行拷贝构造
vector<int> v4(v2.begin(), v2.end());
for (auto e : v4)
{
	cout << e;
}
//输出2222222222
cout << endl;
//也可以使用迭代器区间构造函数将string类对象中内容初始化构造
string s1("hello");
vector<char> v5(s1.begin(), s1.end());
for (auto e : v5)
{
	cout << e;
}
//输出hello
cout << endl;

扩展：

能不能用vector替代string？

不能，差别蛮大的。

string字符串结尾有\0，而vector没有，C就不好兼容了。

vector比较大小和string不同，string是按ASCII值比，vector考虑长度。

string有+=运算符重载还有find函数，而vector没有，vector满足不了string的需求。

迭代器函数

函数	接口说明
begin+end	获取第一个数据位置的iterator/const_iterator，获取最后一个数据的下一个位置的iterator/const_iterator
rbegin+rend	获取最后一个数据位置的reverse_iterator，获取第一个数据前一个位置的 reverse_iterator

vector中的迭代器和string类中的迭代器刚开始指向的位置和遍历方向相同：

【C++】vector介绍及使用,C++,c++,开发语言

begin()+end()函数

获取第一个数据位置的iterator/const_iterator，获取最后一个数据的下一个位置的iterator/const_iterator

我们可以使用迭代器遍历数组元素：

begin() + end()函数遍历：

#include<iostream>
#include <vector>
using namespace std;
int main()
{
	vector<int> v1(10,6);
	vector<int>::iterator it = v1.begin();
	while (it != v1.end())
	{
		cout << (*it);
		it++;
	}
	//输出6666666666
	cout << endl;
    return 0;
}

rbegin()+rend()函数

获取最后一个数据位置的reverse_iterator，获取第一个数据前一个位置的 reverse_iterator

rbegin() + rend()函数遍历：

#include<iostream>
#include <vector>
using namespace std;
int main()
{
	vector<int> v1(10,6);
	vector<int>::reverse_iterator rit = v1.rbegin();
	while (rit != v1.end())
	{
		cout << (*rit);
		rit++;
	}
	//输出6666666666
	cout << endl;
    return 0;
}

容量和空间增长

函数	接口说明
size	获取有效数据个数
capacity	获取容量
empty	判断是否为空
resize	改变 vector 的 size
reserve	改变vector的capacity

size函数

获取有效数据个数

#include<iostream>
#include <vector>
using namespace std;
int main()
{
	vector<int> v1(10,6);
	cout << v1.size() << endl;//10
}

capacity函数

获取当前容器的最大容量

#include<iostream>
#include <vector>
using namespace std;
int main()
{
	vector<int> v1(10,6);
	cout << v1.capacity() << endl;//10
}

empty函数

判断数组是否为空，返回值为bool类型，为空返回真；不为空返回假。

#include<iostream>
#include <vector>
using namespace std;
int main()
{
	vector<int> v1(10,6);
	cout << v1.empty() << endl;//0
}

resize函数

改变 vector 的 size

resize规则：
1、当所给值大于容器当前的size时，将size扩大到该值，如果第二个参数未具体给出，扩大后的数据元素值默认为0，默认将capacity也扩大到当前值。
2、当所给值小于容器当前的size时，将size缩小到该值，不影响capacity值。

#include<iostream>
#include <vector>
using namespace std;
int main()
{
	vector<int> v1(10,6);
	cout << v1.size() << endl;//未改变size大小之前的size值为10
	cout << v1.capacity() << endl;//capacity值为10

	v1.resize(20);//将size扩大到20
	cout << v1.size() << endl;//改变size大小之后的size值为20
	cout << v1.capacity() << endl;//capacity值为20

	v1.resize(15);//比之前size小
	cout << v1.size() << endl;//改变size大小之后的size值为15
	cout << v1.capacity() << endl;//capacity值为20
}

reserve函数

改变vector的capacity

reserve规则：
1、当所给值大于容器当前的capacity时，将capacity扩大到该值。
2、当所给值小于容器当前的capacity时，什么也不做。

#include<iostream>
#include <vector>
using namespace std;
int main()
{
	vector<int> v1(10,6);
	cout << v1.size() << endl;//size值为10
	cout << v1.capacity() << endl;//capacity值为10

	v1.reserve(20);//将capacity扩大到20
	cout << v1.size() << endl;//size值为10
	cout << v1.capacity() << endl;//改变之后的capacity值为20

	v1.reserve(15);//比之前capacity小不改变capacity大小
	cout << v1.size() << endl;//size值为10
	cout << v1.capacity() << endl;//改变之后的capacity值不变
}

capacity的代码在vs和g++下分别运行会发现，vs下capacity是按1.5倍增长的，g++是按2倍增长的。不能认为在任何情况下vector增容都是2倍，具体增长多少是根据具体的需求定义的。vs是PJ版本STL，g++是SGI版本STL。
reserve只负责开辟空间，resize在开空间的同时还会进行初始化。

vector的增删改查

函数	接口说明
push_back	尾插
pop_back	尾删
insert	在指定迭代器位置插入一个或多个元素
erase	删除指定迭代器位置或区间的元素
swap	交换两个容器的数据空间
[]运算符重载	通过下标方式访问数组元素

push_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;
	}
	//输出1234
	cout << endl;
}

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;
	}
	//输出1234
	cout << endl;

	v1.pop_back();//尾删
	v1.pop_back();//尾删
	for (auto e : v1)
	{
		cout << e;
	}
	//输出12
	cout << endl;
}

insert函数

//在指定的迭代器位置插入val，并且返回指定的迭代器位置
iterator insert (iterator position, const value_type& val);
//在指定的迭代器位置后插入n个val值
void insert (iterator position, size_type n, const value_type& val);

示例：

#include<iostream>
#include <vector>
using namespace std;
int main()
{
	vector<int> v1(2,3);
	vector<int>::iterator it = v1.insert(v1.begin(), 100);
	for (auto e : v1)
	{
		cout << e << " ";
	}
	//输出100 3 3
	cout << endl;
	v1.insert(it, 3, 200);
	for (auto e : v1)
	{
		cout << e << " ";
	}
	//输出200 200 200 100 3 3
	cout << endl;
}

erase函数

//删除指定迭代器位置的元素
iterator erase (iterator position);
//删除指定迭代器区间的元素，左闭右开
iterator erase (iterator first, iterator last);

示例：

#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 << " ";
	}
	//输出1 2 3 4
	cout << endl;

	v1.erase(v1.begin() + 1);//删除下标为1的元素
	for (auto e : v1)
	{
		cout << e << " ";
	}
	//输出1  3 4
	cout << endl;

	v1.erase(v1.begin(),v1.begin() + 2);//删除下标为[0,2)之间的元素
	for (auto e : v1)
	{
		cout << e << " ";
	}
	//输出 4
	cout << endl;
}

当我们想头删头插的时候可以使用erase和insert，但是vector并不推荐使用insert和erase，要挪动数据。

swap函数

使用swap函数交换两个容器的数据空间，实现两个容器的交换。

void swap (vector& x);

示例：

#include<iostream>
#include <vector>
using namespace std;
int main()
{
	vector<int> v1(3, 2);
	vector<int> v2(3, 6);
	v1.swap(v2);//交换v1，v2的数据空间
}

[]运算符重载

vector中实现了[]运算符重载，可以通过[]+下标的方式对容器当中的元素进行访问。

#include<iostream>
#include <vector>
using namespace std;
int main()
{
	vector<int> v1(3, 2);
	for (size_t i = 0; i < v1.size(); i++)
	{
		cout << v1[i] << " ";
	}
}

我们除了可以使用[]+下标的方式访问容器中的元素，还可以通过迭代器和范围for来访问，只要容器支持迭代器就支持范围for。

#include<iostream>
#include <vector>
using namespace std;
int main()
{
	vector<int> v1(3, 2);
    //范围for
	/*for (auto e : v1)
	{
		cout << e << " ";
	}*/
    //迭代器访问
    vector<int>::iterator it = v1.begin();
    while(it != v1.end())
    {
        cout << *it;
        it++;
    }
}

我们还可以使用at访问，区别就是下标访问[]断言，at访问抛异常。

迭代器失效问题

迭代器的主要作用就是让算法能够不用关心底层数据结构，在vector和string类中其底层实际就是一个指针，或者是对指针进行了封装。迭代器失效，就是指迭代器底层对应指针所指向的空间被销毁了，而使用一块已经被释放的空间，如果继续使用已经失效的迭代器，程序可能会崩溃。

会引起其底层空间改变的操作，都有可能是迭代器失效，比如：resize、reserve、insert、assign、push_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 << " ";
	}
	//输出1 2 3 4
	cout << endl;
	
	vector<int>::iterator pos = v1.begin() + 2;//获取下标为2的位置的迭代器

	v1.insert(pos, 10);//在下标为2的地方插入10
	for (auto e : v1)
	{
		cout << e << " ";
	}
	//输出1 2 10 3 4
	cout << endl;
	//插入之后我们想删除元素2
	v1.erase(pos);//error，此时迭代器就已经失效了
}

此时运行结果：

【C++】vector介绍及使用,C++,c++,开发语言

说明此时迭代器使用过一次以后已经失效了，代码中本意是在下标为2的位置插入10，然后将2删除，但是此时迭代器使用过一次之后已经失效了，所以不能删除成功。

解决方法：在迭代器每次使用前，都要对迭代器重新进行赋值。

所以上述代码的解决方法是在插入后再次接收返回值，重新对pos进行赋值。

#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 << " ";
	}
	//输出1 2 3 4
	cout << endl;
	
	vector<int>::iterator pos = v1.begin() + 2;//获取下标为2的位置的迭代器

	pos = v1.insert(pos, 10);//在下标为2的地方插入10,返回pos还是下标为2的位置
	for (auto e : v1)
	{
		cout << e << " ";
	}
	//输出1 2 10 3 4
	cout << endl;
	//插入之后删除下标为2的位置即删除10
	v1.erase(pos);
    for (auto e : v1)
	{
		cout << e << " ";
	}
	//输出1 2 3 4
	cout << endl;
}

再看下面代码中存在的迭代器失效问题：

#include<iostream>
#include <vector>
using namespace std;
int main()
{	
	vector<int> v1;
	for (size_t i = 0; i <= 6; i++)
	{
		v1.push_back(i); //插入数据
	}
	vector<int>::iterator it = v1.begin();
	while (it != v1.end())
	{
		if (*it % 2 == 0) //删除容器当中的全部偶数
		{
			v1.erase(it);
		}
		it++;
	}
}

过程如下：

当it指向2的时候*it % 2 == 0成立，删除该位置之后，it就指向3，然后再it++，此时it直接指向4，要注意的是删除之后v.end()的位置也会跟着发生改变：

【C++】vector介绍及使用,C++,c++,开发语言

it指向4时，满足*it % 2 == 0成立，删除该位置之后，it指向5，然后再it++，此时it指向6：

【C++】vector介绍及使用,C++,c++,开发语言

it指向6时，满足*it % 2 == 0成立，删除6之后，v.end()和it指向同一个位置，然后it再++，此时已经超出了数组的范围，迭代器访问到了不属于容器的内存空间，所以程序崩溃。而且在迭代器遍历容器中的元素进行判断时，并没有对1、3、5元素进行判断。

解决方法：可以接收erase函数的返回值（erase函数返回之前要删除的迭代器位置），该位置的元素已经更新，当元素被删除后使用返回后的迭代器继续判断该位置的元素是否要删除。

#include<iostream>
#include <vector>
using namespace std;
int main()
{	
	vector<int> v1;
	for (size_t i = 1; i <= 6; i++)
	{
		v1.push_back(i);
	}
	vector<int>::iterator it = v1.begin();
	while (it != v1.end())
	{
		if (*it % 2 == 0) //删除容器当中的全部偶数
		{
			it = v1.erase(it);//删除后更新迭代器
		}
		else
		{
			it++;//是奇数++
		}
	}
}

vector常见题目

只出现一次的数字

题目：只出现一次的数字

给你一个非空整数数组 nums ，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。

你必须设计并实现线性时间复杂度的算法来解决此问题，且该算法只使用常量额外空间。

示例 1 ：

输入：nums = [2,2,1]
输出：1

示例 2 ：

输入：nums = [4,1,2,1,2]
输出：4

示例 3 ：

输入：nums = [1]
输出：1

提示：

1 <= nums.length <= 3 * 10的4次方
-3 * 10的4次方 <= nums[i] <= 3 * 10的4次方
除了某个元素只出现一次以外，其余每个元素均出现两次。

思路：

当两个相同的数异或时，异或结果为0，当两个不同的数异或时结果不为0；题中只有一个数出现1次，其他都出现2次，我们可以将数组中的所有数都异或这样最后的异或结果就是只出现一次的那个数。

我们可以通过范围for遍历，或者迭代器遍历等。

代码：

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

时间复杂度：O(N)

空间复杂度：O(1)

杨辉三角

题目：杨辉三角

给定一个非负整数 *numRows，*生成「杨辉三角」的前 numRows 行。

在「杨辉三角」中，每个数是它左上方和右上方的数的和。

示例 1:

输入: numRows = 5
输出: [[1],[1,1],[1,2,1],[1,3,3,1],[1,4,6,4,1]]

示例 2:

输入: numRows = 1
输出: [[1]]

提示:

1 <= numRows <= 30

思路：

先定义一个二维数组并将数组大小设置为numRows，然后将数组中每行设置为指定大小并初始化为0；

将每行的第一个和最后一个设置为1，再遍历将二维数组中其他等于0的vv[i][j] = vv[i-1][j-1] + vv[i-1][j];进行处理（方法一）。

我们也可以采用方法二，在for循环中就将不等于0的排除在外。

代码：

class Solution {
public:
    //vector<vector<int>>是二维数组
    vector<vector<int>> generate(int numRows) {
        vector<vector<int>> vv;//先定义一个二维数组
        //vv.resize(numRows);//将二维数组的大小设置为numRows
         vv.resize(numRows,vector<int>());//使用匿名对象来初始化,将二维数组的大小设置为numRows
        //设置二维数组中每行有多少个
        for(size_t i = 0; i < numRows; i++)
        {
            vv[i].resize(i+1,0);//生成并且将初始值都设置为0
            //每行的第一个和最后一个都是1
            vv[i][0] = vv[i][vv[i].size() - 1] = 1;
        }
        //再将其他值为0的进行处理
        //方法一：
        //遍历，将数组中等于0的处理掉
        for(size_t i = 0; i < numRows; i++)
        {
            for(size_t j = 0; j < vv[i].size(); j++)
            {
                if(vv[i][j] == 0)
                {
                    vv[i][j] = vv[i-1][j-1] + vv[i-1][j];
                }
            }
        }

        //方法2：
        //直接从第2行开始处理
        /*for(size_t i = 2; i < numRows; i++)
        {
            //在for循环中将每行中的第一个和最后一个排除出去
            for(size_t j = 1; j < vv[i].size() - 1;j++)
            {
                vv[i][j] = vv[i-1][j-1] + vv[i-1][j];
            }
        }*/
        return vv;
    }
};

时间复杂度：O(N * N)

空间复杂度：O(1)

如果这题使用C语言解决就比较麻烦：

使用C语言解要开辟一个二维数组，先创建一个指针数组，然后再通过一个for循环控制每个指针开辟的空间。

【C++】vector介绍及使用,C++,c++,开发语言

接口：

int** generate(int numRows, int* returnSize, int** returnColumnSizes)

int* returnSize外面的实参是个整形，int** returnColumnSizes外面是个一级指针，所以要分别用一级指针和二级指针来做参数，改变接口外面的内容。

代码实现：

int** generate(int numRows, int* returnSize, int** returnColumnSizes) {
    int** ret = malloc(sizeof(int*) * numRows);//开辟一个指针数组，每个元素为指针，指向一个int类型的数组
    *returnSize = numRows;//将二维数组的行数赋值，不可缺少的一步
    *returnColumnSizes = malloc(sizeof(int) * numRows); //是一个整形数组，开辟一个具有numRows个元素的空间，用来存储每行有多少个元素
    for (int i = 0; i < numRows; ++i) 
    {
    	//开始一行一行的遍历
        ret[i] = malloc(sizeof(int) * (i + 1)); //指针数组中每个指针指向的数组元素中的个数为i+1个
        (*returnColumnSizes)[i] = i + 1;// 表示第i行中数据元素个数
        ret[i][0] = ret[i][i] = 1; //两边的都是1
        for (int j = 1; j < i; ++j) {
            ret[i][j] = ret[i - 1][j] + ret[i - 1][j - 1];//计算中间的。
        }
    }
    return ret;
}

returnSize是二维数组的行数，要在接口函数内赋值；而且二维数组中每一行的个数有可能是乱的，二级指针int** returnColumnSizes用来存储返回的那个数组中元素个数。要开辟一个一维数组，存储每层的元素个数，一维数组需要自己malloc，如果传个一级指针过来在接口内赋值给一级指针，形参的改变不会影响实参，所以为了返回外面定义的指针，参数需要使用二级指针类型，把二级指针解引用拿到外面定义指针的地址，赋值才能把接口内一维数组的地址通过参数传递出去。

在C++中可以直接使用vector<vector<int>>就能搞定:

【C++】vector介绍及使用,C++,c++,开发语言