C with STL入门详解（适合初学者）

如何学好STL：正确的学习姿势，以及，熟能生巧。

1.STL是什么？

STL是Standard Template Library的简称，中文名标准模板库。简单来说就是封装好的一些组件。主要有容器(containers)和算法(algorithms)两部分。

2.C with STL是什么？字面意思，一般来说程设竞赛或程设考试用得上的C++部分其实就是C+STL，有了《C语言程序设计》和《数据结构》这两门课程的基础，学习C+STL并非难事。

3.为什么要学STL呢？方便。比如你要实现一个链式队列，以及它的一系列功能，你需要敲几十乃至上百行代码，还要投入精力debug，可在STL里，给你做好现成的queue你用不用？现成的快排你用不用？平均复杂度O(nlogn)的排序只要几句话，手写一个冒泡也得好几行吧？还卡时。

4.我有兴趣了，怎么学呢？正确的学习姿势，以及，熟能生巧。

下面步入主题。

1.swap（交换两元素值，在algorithm下，用法：swap(a,b);）交换两元素的值在C语言课上作为指针讲解的典例。

123int a=1,b=2;swap(a,b);//此时a=2,b=1

2.sort（对序列进行排序，在algorithm下）

123456789101112131415161718//数组排序：int a[10]={1,3,5,7,9,2,4,6,8,0};sort(a,a+10);//如果用的是vector，这样写vector a;sort(a.begin(),a.end());//之后会提到vector，这里不做解释//默认由小到大排序，当然我们可以重载排序的顺序bool cmp(int a,int b)//从大到小排序{ return a>b;}//然后sort(a,a+10,cmp);sort(a.begin(),a.end(),cmp);

使用sort是一个越用越活的过程，你要喜欢，还能用：

12sort(a,a+10,greater());sort(a.begin(),a.end(),less());

sort的平均时间复杂度是O(nlogn) 。

3.reverse（翻转序列，在algorithm下）

12345678910111213//常用在字符串上int a[5]={1,2,3,4,5};reverse(a,a+5);//序列现在是 5 4 3 2 1char s[]="ericxie";reverse(s,s+strlen(s));//序列现在是 "eixcire"同样适用于string//这个待会儿说string s="qwer";reverse(s.begin(),s.end());

4.min，max（取大，取小）

12345int a=1,b=2,c;c=min(a,b);//此时c等于1c=max(a,b);//此时c等于2

5.__gcd（这东西想必大家都不陌生了）

12345手写gcd函数也行，这里介绍一下用法。int a=4,b=6;int c=__gcd(a,b);//注意下划线，此时c等于2

6.lower_bound和upper_bound（二分查找）功能：我们来看看百度百科的解释 lower_bound()返回一个 iterator 它指向在[first,last)标记的有序序列中可以插入value，而不会破坏容器顺序的第一个位置，而这个位置标记了一个不小于value 的值。意思就是：找到第一个位置，使得：在这个位置插入value后，原有序序列依旧有序。

这是lower_bound，那upperbound的效果呢？找到最后一个位置，使得：在这个位置插入value后，原有序序列依旧有序。

用法如下（上面讲了upper的不同，下面只拿lower做样例，不赘述upper）：

12345678910111213141516171819202122232425//数组int a[100]={1,2,4,4,9,12,12,15};int pos1 = lower_bound(a,a+8,4)-a;int pos2 = upper_bound(a,a+8,4)-a;//在这个样例下，pos1!=pos2根据我的理解，这里lower_bound(a,a+8,value)得到的是一个地址，拿这个地址减去数组首地址a[0]，那么刚好就是value应该放入的位置。//vectorvector a;若a中目前的元素也是{1,2,4,4,9,12,12,15};那么这里用lower_bound得到的应该也是一个类似于指针的东西，为什么不叫它指针呢？因为他有了一个名字，叫做迭代器。vector::iterator it;it = lower_bound(a.begin(),a.end(),4);//这里的it就是迭代器，那么*it就是该下标对应的value了。//set(集合，放到后面讲)set a;这里只介绍它的使用方法：set::iterator it;it = a.lower_bound(value);

7.next_permutation （排列）

123456789101112131415通常用于生成序列的全排列。int a[]={1,2,3};do{/***********这里写你要对当前排列进行的操作**************/}while(next_permutation(a,a+3));如果我要输出全排列结果为：1 2 31 3 22 1 32 3 13 1 23 2 1

8.unique （去重）

1234567891011121314如何把序列 a 中的重复元素去除呢？首先需要对原序列 a 进行排序，保证有序后，调用`unique(a.head , a.tail )`就可以了。unique会返回一个新长度，表示去重之后序列的长度。下面是实例。/**/int a[]={1,3,5,7,9,2,2,2,1,1,1};sort(a,a+11);int len = unique(a,a+11)-a;for(int i=0;i

9.random_shuffle（随机打乱序列，2018.6.25添加）

1234567891011对于一个数组a，我想打乱它原有的顺序，那么可以用该函数。注意，如果要真正的随机，需要srand(time(NULL))操作，因为random_shuffle用的是随机数发生器，还记得rand()吗，如果不srand随机数种子，得到的随机数是固定的。int a[1024];for(int i=0;i<1024;i++)a[i]=i;srand(time(NULL));random_shuffle(a,a+1024);//以上代码能得到一个permutation。//应用：codeforces round 492 div-2 E，用随机生成序列的方法能够ac此题。

上面这些提到的函数都是些基础吧，不定期更新。2018.5.8更新了一部分函数。

下面开始介绍一些好用的容器。

1.vector1.1 vector（不定长数组，向量）。1.2 我们有数组，为什么还要用vector呢？ 菜刀可以削皮，削皮刀也可以削皮；菜刀可以切丝，切丝器也可以切丝。菜刀这么多用处，那我们为什么还要用削皮刀和切丝器呢？每种不同的数据结构在不同场合下能发挥出不同的作用。（致敬eric）1.3实例：邻接表

12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758下面就以邻接表为例展开介绍。struct edge{//定义边 int from,to,value;}const int maxn = 1e5+5;//声明：vector map[maxn];//一维向量相当于二维数组，便于理解。在这里，如果我们使用二维数组存邻接表，需要开销一个1e10的空间，如果图中实际边数只有1e6，用数组无疑会造成极大浪费。1.3.1 //初始化：for(int i=0;i a作为样例a：{1，2，3，4，5，6，7，8，9}1.3.2 //求向量中元素个数int n = a.size();//此时n等于91.3.3 //取向量首个元素的迭代器vector::iterator it = a.begin();注意这里得到的是迭代器，如果要直接得到值：1.3.4 //取向量首个元素值int value = a.front();//此时value等于11.3.5 //和begin对应的是endvector::iterator it = a.end();注意，这里的it指向向量a末尾的下一个位置，注意是下一个位置，下一个位置。1.3.6 //和front对应的是back，取向量尾部的元素值int value = a.back();//此时value等于91.3.7 //直接下标访问(这个地方和数组很像)int value0 = a[0];//下标从0开始的，所以下标是不超过a.size()-1的int value1 = a[1];1.3.8 //往尾部添加一个元素（重要，重要，重要）由于我们不知道再添加元素是放在哪里，所以搞了个push_back函数，往尾部添加一个元素。a.push_back(value);//若value为1，则 a：{1，2，3，4，5，6，7，8，9，1}1.3.9 //与之对应，我们还有pop_back()，用于删除尾部第一个元素。a.pop_back();//pop后，序列为 a：{1，2，3，4，5，6，7，8}1.3.10 //前面提到了reverse函数，翻转向量。a.reverse(a.begin() , a.end());//翻转后的序列 a：{9，8，7，6，5，4，3，2，1}1.3.11 //判断向量是否为空bool isempty = a.empty();向量为空 isempty等于true，否则等于false1.3.12 //常用的如上，一些不常用的可以在这里找到，这里贴个网址

传送门

2.set（集合）2.1 集合中的元素有三个特征： 1.确定性（集合中的元素必须是确定的）。 2.互异性（集合中的元素互不相同）。 3.无序性（集合中的元素没有先后之分）。2.2 set容器是由红黑树实现的。在这里我们尽量把STL容器当作黑箱子使用，不需要知道原理，会用就行。2.3 由于set的一些特性，我们可以用来做一些特定的工作。十分方便。

1234567891011121314151617181920212223242526272829303132333435363738394041424344452.4 主要函数的使用方法2.4.1 声明一个set容器set s;//下面用set s作为例子 初始s:{1,2,3,4,5};2.4.2 清空集合s.clear();//清空后的 s:{};2.4.3 插入一个元素xs.insert(x);//如果x等于1，那么插入后的 s:{1,2,3,4,5};（互异性）//如果x等于6，那么插入后的 s:{1,2,3,4,5,6};前面我们提到set由树实现，那么插入一个元素的平均时间复杂度应该是O(logn)的，并且在用迭代器遍历set时，得到的元素应该是有序的。2.4.4 查询集合里有无元素xint hav = s.count(x);同样，平均时间复杂度是O(logn)因为set的特性，集合里要么有x（表示为1），要么没有（为0）。2.4.5 在集合里找到x的位置，返回迭代器set::iterator it = s.find(x);如果找到了x，那么it指向x所在的位置2.4.6 遍历集合所有元素for(set::iterator it = s.begin();it!=s.end();it++){int x = *it;cout<

待更

前几天更新过，由于浏览器故障没能保存，今天再更新一次吧。–2018.5.8删改了部分非书面或者有错误的描述。

3.map（映射）

赏

谢谢打赏

支付宝

微信