一、头文件<algorithm>
①sort函数
- sort使用数组元素默认的大小比较运算符进行排序，只有在需要按照特殊依据进行排序时才需要传入额外的比较函数；
- sort可以给任意对象排序（不一定是内置类型，由此可见sort是模板函数），前提是类型需要定义“小于”运算符，或者在排序时传入一个“小于”函数；
- 排序对象若存在普通数组中，则用sort(a, a+n)的方式调用；
- 排序对象若存在vector中，则用sort(v.begin(), v.end())。
1 #include2 const int maxn = 10000; 3 int main() 4 { 5 int n, a[maxn]; 6 for(int i=0;i
②lower_bound函数
- 查找大于或者等于x的第一个位置
- 可以在用sort函数排好序后再使用lower_bound
1 #include2 const int maxn = 10000; 3 int main() 4 { 5 int n, a[maxn]; 6 for(int i=0;i
二、头文件<vector>
①特点：它把一些常用操作“封装”在了vector类型内部（例如：函数size()可以读取其大小）。
②区别于数组：无需另外用一个变量（maxn）指定元素个数。
③优点：可以直接赋值，还可以作为函数的参数或者返回值。
vector是一个模板类：
1 int main() 2 { 3 vector a; //声明一个不定长int型数组a 4 a.push_back(1); //在尾部添加元素1 5 a.pop_back(); //在尾部删除元素 6 cout<
三、头文件<set>
定义：set是数学上的集合——每个元素最多只能出现一次。
特点：和sort一样，自定义类型也可以构造set，但必须定义“小于”运算符。
性质：set中元素已从小到大排好序。
题目：输入一个文本，找出所有不同的单词（连续的字母序列），按字典序从小到大输出，单词不区分大小写。
1 #include2 #include 3 #include 4 #include 5 using namespace std; 6 7 set dict; //声明string集合 8 string s, buf; 9 10 int main() 11 {12 while(cin >> s) { //注意：string已经定义了"小于"运算符，可直接使用set保存单词集合 13 for(int i = 0; i < s.length(); i++) //利用了set的性质，一个for循环即可从小到大遍历所有元素 14 if(isalpha(s[i])) //判定s[i]是否为字母 15 s[i] = tolower(s[i]); //全都转为小写 16 else 17 s[i] = ' '; 18 stringstream ss(s);19 while(ss >> buf) 20 dict.insert(buf);21 }22 for(set ::iterator it = dict.begin(); it != dict.end(); ++it)//利用了set的性质，一个for循环即可从小到大遍历所有元素23 cout << *it << "\n"; //迭代器it的用法之一 24 return 0;25 }
四、头文件<map>
定义：map就是从键（key）到值（value）的映射。
特点：重载了[]运算符，map像是数组的“高级版”。
举例：用map<string,int> month_name来表示“月份名字到月份编号”的映射，然后用month_name["July"]=7这样的方式来赋值。
题目：输入一些单词，找出所有满足如下条件的单词：该单词不能通过字母重排而得到输入文本中的另外一个单词。字母不区分大小写。
1 #include2 #include 3 #include 4 #include 5 #include
小结：set和map都支持insert、find、count和remove操作，并且可以按照从小到大的顺序循环遍历其中的元素。此外，map还提供了“[]”运算符，使得map可以像数组一样使用。
五、头文件<stack>
- 定义：stack<int> s
- 入栈：push()
- 出栈：pop()
- 取栈顶元素：top()
题目：Uva12096
1 #include2 #include 3 #include 4 #include
六、头文件<queue>
- 定义：queue<int> s
- 入队：push()
- 出队：pop()
- 取队首元素：front()
【优先队列】
区别于队列：先出队列的元素是队列中优先级最高的元素。
声明：priority_queue<int> pq //pq是一个“越小的整数优先级越低的优先队列”
取队首元素：top()
注：自定义类型也可以组成优先队列，但必须为每个元素定义一个优先级。