vector
头文件
#include<vector>
向量的定义:
vector<int> vec;//定义一个vec型的向量a
vector<int> vec(5); //定义一个初始大小为5的向量
vector<int> vec(5,1); //初始大小为5,值都为1的向量
二维数组:
vector<vector<int>> vec(100);
vector<vector<int>> vec(100,vector<int>(100,0)); //定义100行100列值均为0的二维vector数组
vector的下标和数组一样从0开始的
-
vec.size(); //返回向量的实际大小
-
vec.begin(); //返回向量的开始指针的位置
-
vec.end(); //返回向量的结束指针的下一个位置
-
vec.push_back(x); //在对象末尾插入数据x
-
vec.pop_back(); //在对象末尾删除数据
-
vec.clear(); //清除对象中的所有数据
-
vec.at(i); //访问容器中第i个数的值
-
vec[i]: //访问容器中第i个数的值
-
vec.back(): //返回最后一个元素的值
在第i+1个数前面插入一个数x:
vec.insert(vec.begin()+i,x);
删除第i+1个数:
vec.erase(vec.begin()+i);
以上删除,插入操作复杂度都是log(n)的,因为vector下标是从0开始的,所以下标为i的数实际上就是第i+1个数
排序操作:
sort(vec.begin(),vec.end()); //默认从小到大排序
sort(vec.begin(),vec.end(),cmp); //自己定义的排序方式
查找元素个数:
count(vec.begin(),vec.end(),'a'); //返回数组中字符a的个数
count_if(vec.begin(),vec.end(),compare); //返回符合一定条件compare(自己定义)的的元素个数
#include<algorithm>
结合vector使用的库函数
lower_bound();
upper_bound();
unique();//判重
1.lower_bound(a,a+len,x);
二分查找有序表中第一个大于等于x的数的位置
仅适用于升序序的有序表,如果是降序序的有序表,则需要重载:
lower_bound(a,a+len,x,greater<int>());
返回有序表中第一个小于等于x的数的位置,仅适用于降序序的有序表
2.upper_bound(a,a+len,x);
二分查找有序表中第一个大于x的数的位置
仅适用于非降序的有序表,如果是非升序的有序表,则需要重载:
upper_bound(a,a+n+len,x,greater());
返回有序表中第一个小于x的数的位置,仅适用于非升序的有序表
3.unique(a,a+len):
STL的去重函数,他的时间复杂度和手动去重(先排序,后去重)一样,都是nlog(n),但是他的原理和手动去重不一样,他是把重复的元素放到序列的末尾,序列的前k个数都是不重复的有效元素,所以输出的时候只需要输出有效长度就可以了。
PS:因为是判断当前元素是否等于上一个元素,所以要去重的容器必须是经过排序的有序容器。
unique返回值为去重以后vector中没有重复元素的下一个位置的迭代器。
int k=unique(a,a+len)-a;//得到有效长度for(int i=1;i<=k;i++) //输出有效长度内的元素printf("%d ",a[i]);