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语言课上作为指针讲解的典例。

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

---

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

//数组排序：
int a[10]={1,3,5,7,9,2,4,6,8,0};
sort(a,a+10);

//如果用的是vector，这样写
vector<int> 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是一个越用越活的过程，你要喜欢，还能用：

sort(a,a+10,greater<int>());
sort(a.begin(),a.end(),less<int>());

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

---

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

//常用在字符串上
int a[5]={1,2,3,4,5};
reverse(a,a+5);
//序列现在是 5 4 3 2 1

char s[]="ericxie";
reverse(s,s+strlen(s));
//序列现在是 "eixcire"

同样适用于string//这个待会儿说
string s="qwer";
reverse(s.begin(),s.end());

---

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

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

---

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

手写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）：

//数组
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应该放入的位置。

//vector
vector<int> a;
若a中目前的元素也是{1,2,4,4,9,12,12,15};
那么
这里用lower_bound得到的应该也是一个类似于指针的东西，为什么不叫它指针呢？因为他有了一个名字，叫做迭代器。

vector<int>::iterator it;
it = lower_bound(a.begin(),a.end(),4);
//这里的it就是迭代器，那么*it就是该下标对应的value了。


//set(集合，放到后面讲)
set<int> a;
这里只介绍它的使用方法：
set<int>::iterator it;
it = a.lower_bound(value);

7.next_permutation （排列）

通常用于生成序列的全排列。
int a[]={1,2,3};
do{
/***********这里写你要对当前排列进行的操作**************/
}while(next_permutation(a,a+3));

如果我要输出全排列
结果为：
1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1

8.unique （去重）

如何把序列 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<len;i++)cout<<a[i]<<" ";
输出结果为：1 2 3 5 7 9 
/**/

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

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

下面就以邻接表为例展开介绍。

struct edge{//定义边
	int from,to,value;
}
const int maxn = 1e5+5;
//声明：
vector<edge> map[maxn];//一维向量相当于二维数组，便于理解。
在这里，如果我们使用二维数组存邻接表，需要开销一个1e10的空间，如果图中实际边数只有1e6，用数组无疑会造成极大浪费。

1.3.1 //初始化：
for(int i=0;i<maxn;i++)
{
	map[i].clear();
	//clear函数能清空向量，不是变成0，是清空。
}

下面还是用vector<int> a作为样例
a：{1，2，3，4，5，6，7，8，9}

1.3.2 //求向量中元素个数
int n = a.size();//此时n等于9

1.3.3 //取向量首个元素的迭代器
vector<int>::iterator it = a.begin();
注意这里得到的是迭代器，如果要直接得到值：

1.3.4 //取向量首个元素值
int value = a.front();//此时value等于1

1.3.5 //和begin对应的是end
vector<int>::iterator it = a.end();
注意，这里的it指向向量a末尾的下一个位置，注意是下一个位置，下一个位置。

1.3.6 //和front对应的是back，取向量尾部的元素值
int value = a.back();//此时value等于9

1.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，否则等于false

1.3.12 //常用的如上，一些不常用的可以在这里找到，这里贴个网址

传送门

---

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

2.4 主要函数的使用方法

2.4.1 声明一个set容器
set<int> s;

//下面用set<int> s作为例子 初始s:{1,2,3,4,5};
2.4.2 清空集合
s.clear();
//清空后的 s:{};

2.4.3 插入一个元素x
s.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 查询集合里有无元素x
int hav = s.count(x);
同样，平均时间复杂度是O(logn)
因为set的特性，集合里要么有x（表示为1），要么没有（为0）。

2.4.5 在集合里找到x的位置，返回迭代器
set<int>::iterator it = s.find(x);
如果找到了x，那么it指向x所在的位置

2.4.6 遍历集合所有元素
for(set<int>::iterator it = s.begin();it!=s.end();it++)
{
int x = *it;cout<<x<<",";
}
或者
for(auto x:s)
{
cout<<x<<" ";//这里的x就是元素值
}
//两种方法输出的结果都是1,2,3,4,5,

2.4.7 判断是否为空集
bool isempty = s.empty();
2.4.8 求集合元素个数
int n = s.size();
2.4.9 删除元素x
s.erase(x);
//如果x等于4，那么删除后的集合 s:{1,2,3,5};

待更

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

3.map（映射）

赏

谢谢打赏

支付宝

微信