STL与STL容器

一、标准模板库STL

STL 是“Standard Template Library”的缩写，中文译为“标准模板库”。STL 是 C++ 标准库的一部分，不用单独安装。2011年4月14日，CCF公布了《关于NOI系列赛编程语言使用限制的规定》，明确指出C++选手允许使用STL。

C++ 对模板（Template）支持很好，STL 借助模板把常用的数据结构及其算法都实现了，并且做到了数据结构和算法的分离。例如，vector 的底层为顺序表（数组），list 的底层为双向链表，deque 的底层为循环队列，set 的底层为红黑树，hash_set 的底层为哈希表。

STL 位于诸多 C++ 的头文件中，以源代码的形式提供。从根本上说，STL 由容器、算法和其他一些组件（例如迭代器）三大部分组成，所有容器和算法都是总结了几十年来算法和数据结构的研究成果，汇集了许多计算机专家学者经验的基础上实现的，可以说，STL 基本上达到了各种存储方法和相关算法的高度优化。

STL 在适用性和兼容性方面考虑全面，这样也导致其体量比较臃肿，在一些时候可能没有自己原生写的处理速度快。例如我们用数组模拟的元素是 int 的简单栈（线性表——栈），可能比 STL 中的 stack 容器快，但是需要自己实现细节，没有使用STL中的栈stack方便。使用 STL 开启 O2 优化一般可以有效提高程序运行效率。

为了让大家简单认识使用 STL 编程的优势，这里以“对输入的若干数据去重并排序”为例来比较说明，先来看原始的程序：

#include<iostream>
#include<algorithm>
using namespace std;
int a[10010],len = 0;  
int main()
{   
	int n,m;
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>m;
		//查找m是否出现过 
		int j;
		for(j=0;j<len;j++){
			if(a[j]==m) break;
		}
		//没有出现过，追加到数组“末尾” 
		if(j==len) a[len++] = m; 
	}
	sort(a,a+len);  //sort函数也是STL的内容
	for(int i=0;i<len;i++) cout<<a[i]<<" "; 
	return 0; 
}

其实上面的这个原始的程序已经使用了STL，程序中使用的sort函数就是STL中提供的一种高效排序算法。

可以使用STL中的集合容器set来简化编程并提高程序运行效率，由于set容器已经在内部实现了去重和排序，所以只需要使用set容器的成员函数insert将数据依次插入的集合中（每次插入后，set容器会自动高效地实现内部元素的去重并排序），最后使用STL的迭代器遍历集合输出所有元素即可：

#include<iostream>
#include<set>
using namespace std;  
int main()
{   
	set<int> se;	//元素为int的集合（定义模板类变量） 
	int n,m;
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>m;
		//使用set的成员函数insert向集合se中插入新元素m 
		se.insert(m);
	}
	
	//使用迭代器遍历输出集合中的所有元素（现在要读懂有点难度） 
	set<int>::iterator it = se.begin();
	for(;it!=se.end();it++) cout<<*it<<" ";
	return 0; 
}

从上面两段程序的对比可以看出，使用 STL 可以更加方便高效地处理数据。使用STL，可以集中精力去实现程序的功能，而无需再纠结某些细节如何用代码实现。STL是一个实用高效的工具，我们首先做到会用，现阶段并不需要深入地去研究其实现细节，例如我们能使用set集合实现自动去重排序就行，不用过于纠结set集合内部究竟是如何实现去重和排序的这些细节（其实比较复杂）。

二、STL中的容器与数据结构

首先，我们了解什么是容器。在C++中容器被定义为：在数据存储时，有一种对象类型，它可以持有其它对象或指向其它对象的指针，这种对象类型就叫做容器。可见，容器就是保存其它对象的对象，当然容器还包含了一系列处理其存储的“对象”的方法。其实容器可以简单理解为“装”其它对象的器具（模板类），并且还提供了一系列操作这些对象的方法（成员函数）。

容器还有另一个特点是容器可以自行扩展。在解决问题时我们常常不知道需要存储多少个对象，也就是说不知道应该创建多大的内存空间来保存要处理的对象。显然，数组在这一方面也力不从心（竞赛时往往开一个能满足最大数据规模的大数组）。容器的优势就在这里，它不需要你预先告诉它你要存储多少对象，只要你创建一个容器对象，并合理的调用它所提供的方法（成员函数），所有的处理细节将由容器来自身完成。它可以为你申请内存或释放内存，并且用高效的算法来执行你的命令。现阶段我们会用容器就行，不必关注其内部是如何实现的。

C++中的容器是基于模板类实现的。标准C++库中的容器提供了多种数据结构，这些数据结构可以与标准算法一起很好的工作。STL的通用容器可以分为三类：顺序性容器、关联式容器和容器适配器。

顺序性容器是一种各元素之间有顺序关系的线性表，顺序性容器中的每个元素均有固定的位置，除非用删除或插入的操作改变这个位置。常用的顺序性容器包括vector、deque和list。

关联式容器和顺序性容器不一样，关联式容器是非线性的树结构，更准确的说是二叉树结构。各元素之间没有严格的物理上的顺序关系，也就是说元素在容器中并没有保存元素置入容器时的逻辑顺序。但是关联式容器提供了另一种根据元素特点排序的功能，这样迭代器就能根据元素的特点“顺序地”获取元素。常用的关联式容器有set和map。

容器适配器是一个比较抽象的概念，C++的解释是：适配器是使一事物的行为类似于另一事物的行为的一种机制。容器适配器是让一种已存在的容器类型采用另一种不同的工作方式来实现的一种机制。例如栈就是一种基于顺序性容器实现的容器适配器，但是与顺序性容器工作原理不同，栈的所有操作依据LIFO（后进先出）的特殊规则。常用的容器适配器有stack和queue。

前面介绍基本数据结构的时候提到过栈、队列和链表，STL容器与之对应的分别是stack、queue和list，当然STL中的容器还可以实现更复杂的数据结构。