笔记内容来源：《算法竞赛经典入门》(第二版) 刘汝佳著 第5章
一、基本概念
STL是指C++的标准模板库(Standard Template Library)。
二、排序与检索
sort函数，可以对任意对象进行排序，不一定是内置类型。
如果希望用sort函数排序，这个类型需要定义“小于”运算符，或者在排序时传入一个“小于”函数。排序对象可以存在普通数组或vector里。普通数组用sort(a, a+n)调用，后者用sort(v.begin(), v.end())方式调用。
sort是模板函数，在algorithm头文件里。
三、不定长数组vector
若a是一个vector：
a.size()是数组大小
a.resize()是改变大小
a.push_back()是向尾部添加元素
a.pop_back()是删除最后一个元素
声明方法：vector<int> a;
四、集合set
每个元素最多出现一次
可以用自定义类型构造set，需要定义“小于”运算符。
set具有其中元素会从小排到大的性质。
声明：set<string> dict;
dict.begin(), dict.end()
set迭代器的概念（和for循环类似）
<pre style="margin: 0px; padding: 0px; white-space: pre-wrap; overflow-wrap: break-word; font-family: "Courier New" !important; font-size: 12px !important;">for(set<string>::iterator it = dict.begin(); it!=dict.end();++it)
cout<<*it<<"\n";</pre>
五、映射map
map就是从key到value的映射，[]运算符被重载。
声明：map<string, int> month_name;
month_name["July"] = 7;
set和map都支持insert, find, count, remove等操作，并且可以按照从小到大的顺序循环遍历其中的元素。
六、栈、队列与优先队列
1. 栈
栈定义在头文件<stack>中
声明方式：stack<int> s;
push(), pop()。
2. 队列
队列定义在头文件<queue>中
声明方式：queue<int> q;
push(), pop(), front()取队首元素但不删除。
3. 优先队列
优先队列是一种抽象数据类型，行为有点像队列。
但先出队列的不是先进队列的元素，而是队列中优先级最高的元素。
优先队列也定义在头文件<queue>中
声明方式：priority_queue<int> pq; ===>这个pq是一个“越小的整数优先级越低的优先队列”。
自定义类型也可以组成优先队列，但必须为每个元素定义一个优先级。这个优先级并不需要一个确定的数字，只需要能比较大小就行。
可以定义一个结构体cmp，重载“（）”运算符，使其看上去像一个函数，然后用如下方式声明优先队列：
priority_queue<int, vector<int>, cmp> pq;
cmp可以定义为如下形式：
[
复制代码
](javascript:void(0); "复制代码")
<pre style="margin: 0px; padding: 0px; white-space: pre-wrap; overflow-wrap: break-word; font-family: "Courier New" !important; font-size: 12px !important;">struct cmp{ bool operator() (const int a, const int b) const { //a的优先级比b小时返回true
return a % 10 > b % 10;
}
} </pre>
复制代码
](javascript:void(0); "复制代码")
其他常见的优先队列：
“越小整数优先级越大”的优先队列：priority_queue<int, vector<int>, greater<int> > pq;
push(), pop(), top()取队首元素（但不删除）。
网友评论