玖的数学&算法录
0%

算法笔记（00）：STL专题

发表于 更新于
本文字数： 4.4k 阅读时长 ≈ 4 分钟

pair

C++11

定义数对
1
2
3
pair<int,int> a(3,5)
//或者
a = make_pair(4,6)
修改数对
1
2
a.first = 1
a.second = 2
比较大小逻辑
1
a < b ? a.first < b.first || (a.first == b.first && a.second < b.second)

array

C++11

定义数组
1
2
3
array<int,5> a;
//等同于 
int a[5];

stack

栈

定义
1
stack<int> s
基本用法
1
2
3
4
5
6
7
8
9
10
stack<int> s;
s.push(1);
s.push(3);
printf("%d\n",s.top());
printf("%d\n",(int)s.size());
s.pop();
printf("%d\n",s.top());
printf("%d\n",(int)s.size());
s.empty(); //空的时候返回true
//只能手动pop 没有clear()函数

queue

队列（先进先出）

定义
1
queue<int> q;
用法
1
2
3
4
5
6
7
8
9
10
11
queue<int> q;
q.push(1);
q.push(2);
q.push(3);
printf("%d %d\n",q.front(),q.back())//输出第一个和最后一个数
q.pop();
printf("%d %d\n",q.front(),q.back())
/*
1 3
2 3
*/
bfs写法
1
2
3
4
5
6
7
8
9
queue<int> q;
q.push(s);
while(!q.empty()){
    int x = q.front();
    q.pop();
    for(int y : adj[x]){
        q.push(y);
    }
}

同样也q.empty()和q.size的写法

priority_queue

优先队列（大根堆）

时间复杂度：O(logn)

用法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
priority_queue<int> v;
v.push(3);
v.push(1);
v.push(2);
while(!v.empty()){
	int x = v.top();
    printf("%d\n",x);
    v.pop();
}
/*
3
2
1
*/

//小根堆
priority_queue<int> v;
v.push(-3);
v.push(-1);
v.push(-2);
while(!v.empty()){
	int x = v.top();
    printf("%d\n",-x);
    v.pop();
}
/*
1
2
3
*/

小根堆做法：对push进去的元素取反

或者

1
priority_queue<int, vector<int>,greater<int>> v;

deque

双端队列

定义
1
deque<int> v
用法
1
2
3
4
5
6
7
8
deque<int> v
//头部插入和尾部插入
v.push_front(1);
v.push_back(2);
//允许通过下标访问某个元素 printf("%d\n",v[1]);
//栈和队列不行
v.pop_front();
v.pop_back();

其中

1
push_front(),pop_front(),push_back(),pop_back()

时间复杂度均为O(1)

vector

容器

(可以不设置大小)

定义
1
2
3
4
vector<int> v
vector<int> v(3,100); //大小为3，每个为100
vector<int> v(3); // 构造一个长度为3的容器
vector<int> v{3,100} //大括号表示放这几个元素进去 C++11后的语法
改变容器大小
1
v.resize(100);//将大小设置成100

其中 v.size() 是无符号型，当 v.size() 为空的时候 写循环 v.size() - 1会死循环，建议写成 (int)v.size() - 1

末尾存入数与删除数

时间复杂度均为O(1)

1
2
3
vector<int> v;
v.push_back(1);
v.pop_back();

迭代器

1
2
3
4
5
6
7
8
9
10
vector<int>::iterator it = v.begin() //用指针指向容器开头
printf("%d\n",*it);
//v.end()表示最后一个元素的下一个下标
//遍历
for(auto it = v.begin();it != v.end();it++){
    *it = *it + 1;
    printf("%d\n",*it);
}
//C++11 auto 遍历
//C98 int i : X
插入/删除元素
1
2
3
v.insert(v.begin() + 1, 2) //在这个迭代器前插入一个元素
v.erase(v.begin() + 2); //就是删除掉对应元素
//时间复杂度：O(n)
遍历
1
2
3
4
5
6
7
8
9
10
11
12
13
for(int x : v){
	x += 1;
    /*
    等同于{
    int x = v[i];
    x += 1;
    }
    */
}
//修改容器内的每个数:
for(int &x : v){
    x += 1;
}
排序
1
sort(v.begin(),v.end());
二分查找
1
2
auto it = lower_bound(v.begin(),v.end(),2)//返回 >= 100 的第一个位置
auto it = upper_bound(v.begin(),v.end(),2); //返回 > 100 的第一个位置
存图
1
2
3
4
5
6
7
vector<int> g;
for(int i = 1;i<=m;i++){
	int u,v;
	scanf("%d%d", &u, &v);
	g[u].push_back(v);
	g[v].push_back(u);
}

set

集合

有序且从小到大

插入与删除
1
2
3
4
5
6
vector<int> v;
s.insert(x);//插入x
s.erase(x);//删除x
s.erase(s.begin());//删除首个，不支持s.begin() + k
//插入与删除时间复杂度 : O(logn) , 底层：红黑树
set<int> s(v.begin(),v.end());//可以直接把vector容器中所有元素直接丢进set里面
遍历
1
2
3
for(auto it = s.begin(); it != s.end(); it++) {
	printf("%d\n",*it)
}
查询是否存在
1
2
3
s.count(x);//查询有几个==》等价于查询存在不存在
//存在返回1 不存在返回0
s.find(x); //找不到返回s.end()
二分查找
1
2
3
4
s.lower_bound(x);
s.upper_bound(x);//同vector
auto it = s.lower_bound(x);
auto it2 = prev(it);//C++11 表示输出it的前一个数

map

哈希表

定义
1
2
map<int,int> v;
v[x] = y;//赋值，如果不存在就是新建了

其他用法基本和set一样

multiset

可重复的哈希表，与map用法大部分一样

定义与用法
1
2
3
4
5
multiset<int> s;//定义
s.erase(x);//把所有x删除
//如果要单独删除一个位置的话，那么需要使用迭代器
s.erase(s.find(x));
s.count(x);//时间复杂度与x的个数有关，建议不要用

unordered_set与unordered_map

不支持lower_bound查询

内部实现是hash表的set和map

会被卡，常数不是很好，慎用。（期望复杂度：O(1)）

string

定义
1
2
3
4
5
string s;//可理解成vector<char>上新加一些操作
int a = stoi(s);//字符串转成int型
int a = stoll(s);//字符串转成long long型
string s = to_string(a);//转成字符串
s += t; //时间复杂度：O(t)
用法
1
2
3
4
5
s.replace(start,length,str2);
s.c_str();//字符串类型转成char*
//puts(s.c_str());
s.find(t,pos);//从pos位置开始找t这个子串,找不到返回string::npos,时间复杂度：s.size() * t.size();
s.substr(start,length);//子串，没有length表示到结尾

algorithm

算法库

翻转
1
reverse(a,a + k);
旋转
1
rotate(a,a + 3,a + 5);
随机打乱(C++11及之前都有)
1
random_shuffle(a,a + 5);
排序
1
sort(a.begin(),a.end());
最大最小值
1
2
auto it = min_element(a, a + 5);//返回的是迭代器
auto it2 = max_element(a, a + 5);//返回的是迭代器
归并
1
2
3
merge(a.begin(),a.end(),b.begin(),b.end(),c.begin());
//都要求有序
inplace_merge(a.begin(),a.begin() + k,a.end());//不会用到额外的空间去做归并,很慢(慎用)
找到第k小
1
nth_element(a.begin(),a.begin() + k,a.end()); //时间复杂度：O(n),同时会把数组划分成>=a.begin()+k和a.begin()+k（乱序）
生成全排列
1
2
3
4
5
6
7
8
9
next_permutation(a,a + n);
//写法
while(true){
	for(int i = 0; i < n; i++){
        printf("%d ",a[i]);
    }
    puts("");
    if(!next_permutation(a, a + n)) break;
}