1.C++STL库的简单介绍

STL全称：Standard Template Library 标准模板库
（具体的枯燥无味的概念可以自行百度百科）

模板库内容主要包含了一些常用的算法如快速排序、简单查找等，当然还包括了一些常用的数据结构，如可变长数组、链表、字典等。

（可能中文不太好记忆。可对于学过数据结构的同学，vector（可变长数组）、Map/multimap（映射表）、List（链表）、set/multiset（平衡二叉树）…这些英文单词应该还是熟悉的）

STL库因其使用方便，效率较高，受到广大爱好者的青睐。
（其实就是懒…因为有了它不用当场编写一些常用且有些复杂的结构，而且STL库里的模板时间也是比较快的）

包含头文件

#include<algorithm>
//当然使用万能头文件的请忽略这句话#include<bits/stdc++.h>
using namespace std; 
//当然不能忘了这句话

2. 快速排序 sort

时间复杂度 O(nlogn)

2.1 对基本类型数组（int、double、char）进行排序

用法
sort(a+n, a+m);

解释： n , m都必须是 int 类型的表达式，可以包含变量，因为实质上这里的n,m是数组a的下标，若n = 0，则 + n 可以省略不写。
这里是将数组 a 下标 为 [n , m) 的元素 从小到大 进行排序。
注意是左闭右开，所以说下标为 m 的元素不在排序区间内。

int a[] = {15,4,3,9,7,2,6};
sort(a,a+7);
// 对整个数组从小到大排序；int a[] = {15,4,3,9,7,2,6};
sort(a,a+3);
// 对前三个数(下标从0到)从小到大排序；
// 结果：{3,4,15,9,7,2,6}int a[] = {15,4,3,9,7,2,6};
sort(a+2,a+5);
// 对第三个数到第五个数（下标为2，到下标为4）从小到大排序；
// 结果：{15,4,3,7,9,2,6}

2.2 对基本类型数组从大到小排序

使用方法

sort(a+n,a+m,greater<T>()
不要忘记最后的圆括号。

用法解释：对于元素类型为 T 的数组a将其下标从n到m-1的元素进行从大到小排序。
用法中的T可以更改为int 、double、char等，取决于数组a的类型。

当然这个用法比较鸡肋，因为可以直接进行运算符重载，或者进行接下来的自定义运算法则。

int a[] = {15,4,3,9,7,2,6};
sort(a+2,a+5,greater<int>());

2.3 用自定义的排序规则，对任何类型T的数组排序

用法
sort (a+n,a+m,Sort_Rule())

用法解释：将任意元素类型 T 的数组a中的下标从n到m-1的元素按照Sort_Rule的排序规则进行排序

Sort_Rule 如何定义

struct Rule  // 这里的Rule即为排序规则名，可以任取。
{bool operator()(const T & a1 , const T & a2) const{// T 代表的是数组元素的类型，需要更改。//若a1 应该排在 a2 的前面 则返回true//否则返回false}
}

这里的operator 其实类似于运算符的重载。

#include<bits/stdc++.h>
using namespace std;
struct Rule1   //从大到小排序
{bool operator()(const int & a1 , const int & a2) const{return a1 > a2;// 从大到小，即大应该排在前面，所以如果a1大，则就返回true。}
}
struct Rule2   // 按个位数从小到大排序
{bool operator()(const int & a1 , const int & a2) const{return a1%10 < a2%10;}
}
int main()
{int a[] = {15,4,3,9,7,2,6};sort(a,a+sizeof(a)/sizeof(int)，Rule1); // 从大到小sort(a,a+sizeof(a)/sizeof(int)，Rule2); //  按个位数从小到大
}

当然 对于结构体数组也是可以自定义进行排序的，只需要将数组类型T 改成 相对应自定义结构体时的类型足矣。

3.二分查找算法

STL 库中提供了三种二分查找算法模板
顾名思义，时间复杂度为O(logn)
binary_search
lower_bound
upper_bound

3.1 binary_search

用法一：binary_search(a+n,a+m,k)

解释：在从小到大排好序的基本类型数组a在下标范围为 [n,m) （即从下标为n到m-1的数组元素）上进行二分查找，寻找 “值” “等于” k的元素，返回值为true（找到）或false（未找到）。
当 n = 0时，+n 可以省略。

这里的类型包括了int char double 等基本数据类型。

这里的“等于” 的 含义：k 等于 a[i] 等价于 k < a[i] 和 k > a[i] 都不成立
（对于基本数据类型，目前可以将这里的“等于”暂时理解为 “==” 号）

用法二：binary_search(a+n,a+m,k,Sort_Rule)
在用自定义排序规则Sort_Rule排好序的、元素为任意的T类型的数组a中进行二分查找,查找“值”为k的元素。
解释与用法一相同。

这里的“等于” 的 含义：k 等于 a[i] 等价于 （在该排序规则下）k必须在a[i]前面 和 a[i]必须在k前面 都不成立
强调：查找时的排序规则必须和排序时的规则一致

3.2 lower_bound

二分查找下界

在对元素类型为 T 的 从小到大排好序的基本类型的数组中查找

用法一
T * lower_bound(a+n,a+m,k)

返回值 是一个指针 T * p

*p 是查找区间 [n,m) 里下标最小的，大于等于 k 的元素。如果找不到，p 指向下标为m 的元素。(下标为m的元素是不在查找区间里的）

用法二
T * lower_bound(a+n,a+m,k,Sort_Rule)

返回值 是一个指针 T * p

*p 是查找区间 [n,m) 里下标最小的，按照自定义排序规则可以排在 k 后面的元素。如果找不到，p 指向下标为m 的元素。(下标为m的元素是不在查找区间里的）

3.3 upper_bound

二分查找上界

在对元素类型为 T 的 从小到大排好序的基本类型的数组中查找

用法一
T * upper_bound(a+n,a+m,k)

返回值 是一个指针 T * p

*p 是查找区间 [n,m) 里下标最小的，大于 k 的元素。如果找不到，p 指向下标为m 的元素。(下标为m的元素是不在查找区间里的）

用法二
T * upper_bound(a+n,a+m,k,Sort_Rule)

返回值 是一个指针 T * p

*p 是查找区间 [n,m) 里下标最小的，按照自定义排序规则必须排在 k 后面的元素。如果找不到，p 指向下标为m 的元素。(下标为m的元素是不在查找区间里的）

4. STL中的平衡二叉树数据结构

• 在需要大量增加、删除数据的同时，还要进行大量的数据的查找
• 并且希望算法效率要高，增加、删除、查找数据都能在log(n)的时间复杂度下完成
• 排序+二分查找显然不可以，因为加入新数据就要重新排序
• 可以使用“平衡二叉树”数据结构存放数据，体现在STL中的四种“排序容器”（有着始终维持的排好序的特性）
• multiset \ set \ multimap \ map

4.1 multiset

用法
multiset<T> st

解释：定义了一个multiset变量st，st里面可以存放T类型的数据，并且存放后自动排序。开始，st容器为空。

排序规则：表达式a < b 为 true，则a排在b前面

基本操作（时间复杂度均为log(n)）

• 添加元素k：st.insert(k)
• 查找元素k：st.find(k)
• 删除元素k：st.erase(k)

4.1.1multiset的迭代器

定义
multiset<T>::iterator p;

p就是迭代器，类似于指针，可以指向multiset中的元素，当需要访问multiset中的元素要通过迭代器。

但是其与指针不同之处：multiset的迭代器可++，–，可用!=，==进行比较，但不可以比大小，不可以加减整数，不可以相减。

基本操作：
先定义一个容器:multiset st;

• **st.begin() **返回值类型为 multiset::iterator，是指向st中的头一个元素的迭代器。
• **st.end() ** 返回值类型为 multiset::iterator，是指向st中的最后一个元素后面的迭代器（实际上此时得带器指向的容器中是没有元素的）。
• 对迭代器++，就是指向容器中下一个元素，–就是指向上一个元素

用法展示

#include<bits/stdc++.h>
//如果不使用万能头文件的话，则需要加#include<set>使用multiset和set都需要此头文件
using namespace std;
int main()
{multiset<int> st;int a[10] = {1,14,12,13,7,13,21,19,8,8};for(int i = 0 ; i < 10; i++)st.insert(a[i])//插入的是a[i]的复制品multiset<int>::iterator i;//迭代器，近似于指针//可以理解为这里的i作为迭代器的类型就是multiset<int>for(i = st.begin(); i != st.end();++i)cout<<*i<<',';//输出：1 7 8 8 12 13 13 14 19 21（从小到大输出）//排序容器自动保持有序状态i = st.find(22)//查找22，返回值是一个迭代器。if(i == st.end())    //找到的话就返回位置迭代器，找不到就是返回end()cout<<"not found";st.insert(22); //插入22i = st.find(22);if( i == st.end())cout<<"not found"<<endl;elsecout<<"found"<<*i<<endl;i = st.lower_bound(13);// 这里的lower_bound是容器st中成员函数//  返回最靠后的迭代器it，使得[ begin(),it)的元素都在13前面i = st.upper_bound(8);//  返回最靠前的迭代器it，使得[ it ,end())的元素都在8后面cout<<*i;st.earse(i); // 删除迭代器i 指向的元素，即12；
}

4.1.2 自定义排序规则的multiset

用法**multiset<T,Sort_Rule> st**
解释：定义一个按照Sort_Rule排序的multiset容器，里面存储的数据类型为T

特殊：multiset<int,greater<int>> st 排序规则为从大到小。（不要忘记还有一个Int）

Sort_Rule 使 用 样 例

struct Rule1
{bool operater()(const int & a,const int & b) const{if(a%10==b%10){return a > b;}return a%10>b%10;}// 排序规则：个位大的排在前面，个位相等的值大的排在前面。
}
multiset<int,Rule> st;

在排序容器中查找一个值：即 st.find(x)，就是在排序容器中，x必须排在y前面 和 y 必须排在x 前面都不成立。

那么之前有说过 迭代器的功能类似于指针，那么指针的用法可否类似地用在迭代器上呢？

#include<bits/stdc++.h>
using namespace std;
struct student
{char name[20];int id;int score;
}stu[]={{"jack",112,78},{"mary",102,85},{"ala",333,92}};
//自定义了一个数据类型student
struct rule
{bool operator() (const student & a, const student & b) const{if(a.score!=b.score)   return a.score > b.score;else return (strcmp(a.name,b.name) < 0);}// 自定义排序规则：第一关键字是分数从大到小，第二关键字是名字按字典序排。
}
int main()
{multiset<student,rule> st;for(int i = 0 ; i < 3; i++)st.insert(stu[i]);multiset<student,rule>::iterator p;for(p = st.begin(); p != st.end(); p++)cout<<p->score<<" "<<p->name<<" "<<p->id<<endl;// 这里的用法可以类似于指针的用法student s = {"mary",1000,85};p = st.find(s);// 容器虽然没有与s 完全相同的元素，但是还是可以找到的，返回的迭代器 it 指向的是  {"mary",102,85},// 因为在排序的规则中，没有关于id的排序，所以id的不同并不会影响谁排前谁排后,// 也就符合了上文中提到的，s和*it在当前的排序规则下，满足了s 可以 排在 *it的前面，也可以排在*it的后面，所以认为他们“相等”。return 0;     
}

4.2 set

• 用法： set与multiset用法类似，但是两者的区别在于，set容器里面不能有重复元素。
• 在容器当中，什么叫重复元素？也就是上文提到的，在当前排序规则下，a必须排在b的前面 和 b 必须排在a的前面都不成立，那么a,b就是重复的，即在上文代码的中的 s 与 *it， 虽然一个结构体内部元素有一个不同，但是并不影响排序，所以他们认为是相同的，即是重复的。
• 因为set中不允许出现重复元素，所以set插入元素可能不成功。

4.2.1 pair 模板的用法

pair<T1,T2>
这里的pair等价于

struct{T1 first;T2 second;
};

例如

pair<int,double> a;
a.first = 1;
a.second = 10.88;
// 必须是first和second

4.2.2 set 的用法

set<int> st;
int a[10] = {1,2,3,8,7,7,5,6,8,12};
for(int i = 0; i < 10; i++)st.insert(a[i]);
cout<<st.size()<<endl;
//  输出是8，说明st中只有八个数，因为7,8重复出现了两次。
set<int>::iterator i;
for(i = st.begin(); i != st.end(); i++)cout<<*i<<',';//输出：1,2,3,5,6,7,8,12
pair<set<int>::iterator,bool> result = st.insert(2);
// 定义这样的pair，first代表的是插入的值，second代表的是是否插入成功
if(!result.second)   //条件成立说明插入不成功cout<<*result.first<<"already exists."<<endl;
elsecout<<*result.first<<"inserted"<<endl;

4.3 multimap

multimap 容器里的元素都是pair 形式的
multimap<T1,T2>mp
则 mp中的元素都是如下类型

struct {T1 first;//关键字T2 second;//值
}

初始定义下，multimap中的元素都是按照 first 排序，并可以按 first 进行查找，时间复杂度都在log(n)
排序规则是a.first < b.first为true,则 a 排在 b 前面
使用时需包括
# include<map>

#include<bits/stdc++.h>
using namespace std;
struct studentinfo
{int id;char name[20];
};
struct student
{int score;studentinfo info;
};
// 每个student都对应着一个score 和 一个 info ，一个info 中又包括了id 和 name
// 目标是将每个student的信息放入multimap的容器中
typedef multimap<int,studentinfo> map_std;
//  这里的typedef 类似于#define 只不过这里定义的数据类型，即此后map_std就等价于multimap<int,studentinfo> ,
//  这样可以使程序更加简洁易懂。
//  并且这里的 multimap中可放入的元素和student类型的元素是相同。
//  这里是按照 score 从小到大排序
int main()
{map_std mp;student st;char cmd[20];while(cin>>cmd){if(cmd[0] == 'A'){cin >> st.info.name >> st.info.id >> st.score;mp.insert(make_pair(st.score,st.info));//能够插入Multimap类型中必须类型和multimap类型相同的pair//所以make_pair就可以将几个合并成一起，以达到可以插入容器中的类型//first = st.score, second = st.info}else if ( cmd[0] == 'Q'){int grade;cin >> grade;map_std::iterator p = mp.lower_bound(grade);// 定义一个迭代器叫 p , 利用下界函数寻找低于grade的最高分的学生// 这里的lower_bound 和 之前stl库中提供的二分查找的lower_bound不一样// 之前的lower_bound是在排好序的数组的一段区间上寻找大于等于某个值的最小下标。// 这里的lower_bound类似于是在容器中寻找小于该关键字的最大关键字的元素// 如果找到，则 [ mp.begin(), p ) 这样一个左闭右开区间中的所有元素的关键字都是小于该关键字的// 注意不包括p所指向的元素，所以找到p后，要自减。if(p != mp.begin()){--p;grade = p->first;map_std::iterator maxp = p;int maxid = p->second.id;// 强调一下，这里的p是multimap容器中的迭代器所以说只可以用first和second和所等价的结构体是不一样的。for(; p != mp.begin() && p->first == grade;--p)   // 遍历所有成绩和grade相同的学生，即可能存在小于要查询分数的最高分有多个学生。{if( p->second.id > maxid){maxp = p;maxid = p->second.id;}}// 这个循环的终止条件有两个，所以可能会出现，p走到mp.begin()，// 可是p->first == grade，所以这里还需有一个判断。if(p->first == grade){if(p->second,id > maxid){maxp = p;maxid = p->second.id;}}cout<<maxp->second.name<<' '<<maxp->second.id<<' '<<maxp->first<<endl;}elsecout<<"Nobody"<<endl;// 说明在lower_bound查找过程中就没有找到，说明没人分数比查询分数要低}}return 0;
}

4.4 map

map 和 multimap 的区别（类似于set和multiset的区别）

• 不能有关键字重复的元素
• 可以使用 [ ] , （可以理解为数组中的下标，所以一般称作为映射表），下标为关键字，返回值为first 和关键字相同的元素的 second，这个将成为map用途广泛的重要原因，可以用来压缩空间，比爆开数组具有空间优势。
• 插入元素可能失败

使用示例：

#include<bits/stdc++.h>
using namespace std;
struct student
{char [100] name;int score;
};
student st[5]={{"Jack",89},{"Tom",74},{"Cindy",87},{"Alysa",87},{"Micheal",98}};
typedef map<string,int> MP;
// 定义MP类型
int main()
{MP mp;for(int i = 0 ;i < 5; i++)mp,insert(make_pair(st[i].name,st[i].score));cout << mp["Jack"] <<endl;// 输出与 [ ]中相同first对应的元素的second的值// 所以这里应该输出 89for(MP::iterator i = mp.begin(); i != mp.end(); ++i)cout<<'('<<i->first<<','<<i->second<<')';//输出：(Alysa,87) (Cindy,87) (Jack,60) (Micheal,98) (Tom,74)//按照的是关键字的字典序进行排序，并且查找仍然是log(n)的时间复杂度。cout<<endl;student stu;stu.name = "Jack";stu.score = 99;pair<MP::iterator,bool> p = mp.insert(make_pair(stu.name,stu.score));// p.first 代表的是插入的值， p.second 代表的是插入是否成功， 且p 就指向的是插入的值得位置if( p.second )cout << '(' << p.first->first <<','<<p.first->second <<")inserted"<<endl;elsecout<< "insertion failed"<<endl;// 同样更简洁的插入可以这么写mp["Harry"] = 78;// 这里就代表的插入了一个pair，first为Harry， second 为 78// 所以简单来记忆，map可以用作映射的功能，即将两个或者更多的不同类型或者相同类型的数据进行相关联// 而搜索时，只需要搜索关键字即可。MP::iterator q = mp.find("Harry");cout<<'('<<q->first<<','<<q->second<<')'<<endl;       return 0;
}

解题示例

• 简单来记忆，map可以用作映射的功能，即将两个或者更多的不同类型或者相同类型的数据进行相关联，而搜索时，只需要搜索关键字即可。

如果这道题没有学习map的话，这道题是不是很麻烦，需要构建一个结构体存储两个变量，一个来存储字符串，一个来存储出现次数，而且每次读入都需要遍历结构体数组进行判断，并且最后还要排序非常麻烦。

不过对于map就简单多了，首先他是单词出现个数，必然单词作为关键字，当然，排序还是躲不掉的。

#include<bits/stdc++.h>
using namespace std;
struct word
{int times;string wd;
};
struct rule
{bool operator() (const word & w1, const word $w2) const {if(w1.times == w2.times)return w1.wd < w2.wd;return w1.times > w2.times;}
}
int main()
{string s;set<word,rule> st;map<string,int> mp;while(cin>>s)mp[s]++;for(map<string,int>::iterator i = mp.begin();i != mp.end(); i++){word tmp;tmp.wd = i->first;tmp,times = i->second;st,insert(tmp);// 注意这里，因为i的类型是map<string,int>::iterator，所指向的元素是不可以直接放入st容器中的// 所以必须转换成与st中元素的类型相同的元素才可以放进去。}for( set <word,rule>::iterator i = st.begin(); i != st.end(); i++)cout<<i->wd<<' '<<i->times<<endl;return 0;
}

x 写在最后

文章会持续更新，我会不断搜集有关C++STL库的使用教程，并及时分享给大家。

---------------------------笔记分割线------------------------------
码字不易，喜欢这篇文章的话，关注我的CSDN吧，
我的高中数理化学习干货
Noip竞赛经验
自招笔试小窍门、面试小套路
大学理工科学习规划
均在我的公众号中
扫码关注吧！

结语

感谢你的耐心阅读，码字不易，阅读不易。

愿你的努力加上我的，能完美解决你的问题。