STL--vector

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]);