C29.【C++ Cont】STL库:动态顺序表(vector容器)
目录
1.创建vector
1.基本用法(最常用)
2.高级用法
问题:vector arr[N];和vector> arr;有区别吗?
2.接口
1.size
2.empty
3.begin和end
4.push_back
5.pop_back
4.front和back
5.resize
6.clear
使用动态顺序表可以直接使用STL库的已封装好的vector容器(又称可变长的数组),其底层为可自动扩容的顺序表
1.创建vector
先包含<vector>头文件
格式:vector<任意数据类型> 创建方式
1.基本用法(最常用)
创建一个空的int类型的可变长数组
vector<int> arr;创建一个可以存N个元素的int类型的可变长数组(未初始化,默认每个元素都是0)
const int N = 100;
vector<int> arr(N);//注意是圆括号,不是方括号!!!创建一个可以存N个元素的int类型的可变长数组(已初始化)
const int N = 100;
vector<int> arr(N,10);//每个元素都初始化的值都是10用列表初始化
vector<int> arr = {1, 2, 3, 4, 5};//第二种初始化的方式:用列表初始化注:可以用访问数组元素的方式去访问每个元素 ,例如访问下标为x的元素:arr[x]
2.高级用法
在格式里提到过;vector<任意数据类型> 创建方式 ,< >里面可以放任意的数据类型,甚至是vector自己或其他容器
放string类
vector<string> str;放结构体类
struct Node
{
int data;
struct Node* next;
};
vector<Node> arr;设置成二维数组("套娃"),可变长的数组的每一个元素存着可变长的数组
vector<vector<int>> arr;创建N个vector(即vector数组)
const int N = 5;
vector<int> arr[N];//注意是方括号,不是圆方括号!!!问题:vector<int> arr[N];和vector<vector<int>> arr;有区别吗?
答:
2.接口
1.size
作用:返回有效元素的个数,时间复杂度为
#include <iostream>
#include <vector>
using namespace std;
int main()
{
vector<int> arr={1,2,3,4,5};
cout<<arr.size()<<endl;
return 0;
}运行结果
例如顺序表的遍历
void print(vector<int>& a)//传引用调用,避免拷贝
{
for(int i = 0; i < a.size(); i++)
{
cout << a[i] << " ";
}
}2.empty
作用:返回顺序表是否为空的判断结果,返回类型为bool型;如果为空,返回true;如果不为空,返回false,时间复杂度为
#include <iostream>
#include <vector>
using namespace std;
int main()
{
vector<int> arr;
if (arr.empty())
{
cout<<"为空";
}
else
{
cout<<"不为空";
}
return 0;
}运行结果
3.begin和end
当为非空表时,beign返回起始位置的迭代器(左闭);end返回最后位置的下一个位置的迭代器(右开)
使用迭代器遍历顺序表
#include <iostream>
#include <vector>
using namespace std;
int main()
{
vector<int> arr={1,2,3,4,5};
//i实际类型为vector<int>::iterator,这里写auto让编译器自动推导
for (auto i=arr.begin();i<arr.end();i++)
cout<<*i<<" ";
return 0;
}或者使用范围for
vector<int> arr={1,2,3,4,5};
for (auto a:arr)
cout<<a<<" ";运行结果
注意不能写成cout<<arr[i]<<" ";!!!在C13.【C++ Cont】初识string类字符串的迭代器文章中讲过,访问迭代器指向的值需要解引用(*)
4.push_back
作用:尾插元素,时间复杂度为
#include <iostream>
#include <vector>
using namespace std;
int main()
{
vector<int> arr={1,2,3,4,5};
arr.push_back(6);
for (auto a:arr)
{
cout<<a<<" ";
}
return 0;
}运行结果
5.pop_back
作用:当为非空表时,尾删元素,时间复杂度为
#include <iostream>
#include <vector>
using namespace std;
int main()
{
vector<int> arr={1,2,3,4,5};
arr.pop_back();
for (auto a:arr)
{
cout<<a<<" ";
}
return 0;
}运行结果
注:insert与erase由于时间复杂度过高,竞赛中尽量不使用,这里不作详细介绍
例如283. 移动零 - 力扣（LeetCode）
移动零:
class Solution {
public:
void moveZeroes(vector<int>& nums)
{
int s=0;
vector<int>::iterator i=nums.begin();
while(i<nums.end())
{
if ((*i)==0)
{
nums.erase(i);
s++;
}
else{
i++;
}
}
while(s--)
{
nums.push_back(0);
}
}
}; 
4.front和back
作用:当为非空表时,front返回首元素;back返回尾元素,时间复杂度都为
#include <iostream>
#include <vector>
using namespace std;
int main()
{
vector<int> arr={1,2,3,4,5};
cout<<"首元素:"<<arr.front()<<endl;
cout<<"尾元素:"<<arr.back()<<endl;
return 0;
}运行结果
5.resize
作用:修改resize的大小,可以变大可以变小
如果大于原始的大小,多出来的位置会补上默认值,一般为0;
如果小于原始的大小,相当于把后面的元素全部删掉(相当于多次尾删)
#include <iostream>
#include <vector>
using namespace std;
int main()
{
vector<int> arr={1,2,3,4,5};
arr.resize(10);//10为元素个数
for (auto a:arr)
cout<<a<<" ";
arr.resize(3);
cout<<endl;
for (auto a:arr)
cout<<a<<" ";
return 0;
}运行结果
6.clear
作用:清空vector,底层是遍历整个元素,一个一个删除,时间复杂度为
#include <iostream>
#include <vector>
using namespace std;
int main()
{
vector<int> arr={1,2,3,4,5};
arr.clear();
cout<<arr.size();
return 0;
}运行结果
注:更多的成员函数参见cplusplus官网vector - C++ Reference
