Hexo
0%

stl

Posted on In ,
Symbols count in article: 1.8k Reading time ≈ 2 mins.

stl容器

vector

动态分配内存

1
2
3
4
5
6
vector<int>v1(3);
v1.insert();//在迭代器位置插入元素
v1.erase();//在迭代器或区间删除元素
v1.push_back();
v1.pop_back();

array

固定长度的数组数据结构

1
2
3
4
5
array<int,3> v0;
v0.fill(1);//以指定值填充容器
v0.front();//第一个元素
v0.back();//最后一个元素
v0.data();

deque

双端队列

1
2
3
4
5
6
7
8
deque<int>v0;
v0.front();
v0.back();
v0.insert();
v0.push_front();
v0.pop_front();
v0.push_back();
v0.pop_back();

set

本身时排好序的

1
2
3
4
5
6
7
8
9
10
set<int>s;
s.insert();
s.erase(x);//删除值为x的元素
s.erase(pos);//删除迭代器为pos的元素
s.erase(frist,last);//删除区间元素
s.count(x);
s.find(x);
//O(logn)
s.lower_bound(x);//返回指向首个不小于给定键的元素的迭代器。如果不存在这样的元素，返回 end()
s.upper_bound(x);//返回指向首个大于给定键的元素的迭代器。如果不存在这样的元素，返回 end()

set 在默认情况下的比较函数为 <。然而在某些特殊情况下，我们希望能自定义 set 内部的比较方式。

1
2
3
4
struct cmp{
	bool operator()(int a,int b){return a>b};
};
set<int,cmp>s;

multiset

可以看成一个序列，插入一个数，删除一个数都能够在O(logn)的时间内完成，而且他能时刻保证序列中的数是有序的，而且序列中可以存在重复的数。

priority_queue

1
2
priority_queue<int>que;//从大到小
priority_queue<int,vector<int>,greater<int> >que;//从小到大

函数

二分查找

找到返回1，找不到返回0

1
binary_search(数组名+n1，数组名+n2，值);

lower_bound

在一个有序序列中进行二分查找，返回指向第一个 大于等于 x 的元素的位置的迭代器。如果不存在这样的元素，则返回尾迭代器

1
lower_bound(v.begin(),v.end(),x);

upper_bound

在一个有序序列中进行二分查找，返回指向第一个 大于 x 的元素的位置的迭代器。如果不存在这样的元素，则返回尾迭代器

1
upper_bound(v.begin(),v.end(),x);

next_permutation

将当前排列更改为 全排列中的下一个排列。如果当前排列已经是 全排列中的最后一个排列（元素完全从大到小排列），函数返回 false 并将排列更改为 全排列中的第一个排列（元素完全从小到大排列）；否则，函数返回 true

1
2
3
4
do{

}
while(next_permutation(v.begin(),v.end()))

string

1
2
3
4
5
6
7
8
string s;
s.find('x');//第一次出现x字符的位置
s.find('x',pos);//从pos位置起第一次出现x字符
s.substr(pos,len);//从pos位置开始截取最多len个字符组成的字符串
s.erase(index，count);//从index位置开始的count个字符删除，count可省略
s.insert(index,count,ch);//从index处连续插入count次字符串ch，count可省略即为1次
s.replace(pos,count,str);//从pos开始的count个字符替换为str
s.replace(first,last,str);//从[first,last)的子串替换为str