Standard Template Library(STL，标准模板库)

STL（标准模板库）是C++标准程序库的核心，它深刻影响了标准程序库的整体结构。

STL是一个泛型(generic)程序库，提供一系列软件方案，利用先进，高效的算法来管理数据。

STL的所有组件都由template（模板）构成，故其元素可以是任意型别。

通过C++开发者们精心设计的组件，共同构筑起了STL的基础。而在这些组件之中最为重要的要数迭代器，容器，算法

容器 Containers ，用来管理某类对象的合计。STL库的中每一个容器都会有其自身的优缺点，所以为了应付程序中的不同需求，STL准备了不同的容器类型，例如dynamic arrays,linked list,binary tree等迭代器 Iterators，用来在一个对象群集的元素上进行相关的遍历动作。而使用迭代器的主要好处则是，为所有的容器提供一组很小的且相对安全的公共接口。而利用这个接口，某项操作就可以在这个容器对象的集群运行，或者行进至群集内的下一个元素

（注：迭代器的接口和一般的指针差不多，以operator++累进，以operator* 指向所指的元素值。因而，我们可以将迭代器视为一种smart poiner，能够把“前进至下一个元素”的意图转换成合适的操作

算法 Algorithms，用来处理群集内的元素

STL的基本观念就是将数据和操作分离。（重中之重）

数据由容器类别加以管理，操作则由可定制的算法定义之。迭代器在二者之间从当粘合剂，使其任何算法都可以和任何容器交互运作

STL的一个根本特性：所有组件都可以针对任意性别运作。顾名思义，所谓的Standard template library表示其内的所有组件都是“可接受任意型别”的template,前提是这些型别能够执行必要的操作。故，STL成了泛型编程（generic programming）概念下的一个出色案例

STL当然也能够提供更加泛型化的组件。通过特定的配接器和仿函数，使用者可以补充，约束或者订制算法，满足特别的需求

容器类别（简称为容器）用来管理一组元素。为了适应不同的需求，STL提供了不同类型的容器

总的来说，STL的容器可分为两类：

序列式容器Sequence containers，此乃可序群集，其中的每个元素均有固定位置—取决于插入元素的时机和其地址，与元素值本身无关。STL提供三个定义好的序列式容器：vector,deque,list关联式容器Associative container，此乃已序群集，元素位置取决于特定的排序准则。如果你将六个元素置于这样的群集中，则它们的位置取决于元素本身的值，和元素的插入次序无关。STL提供了四个关联式容器：set,multiset,map,multimap

关联式容器也可被视为特殊的序列式容器，因为已序群集正是根据某个排序准则排列而成

**注意事项：**STL所提供的群集型别彼此独立，各自实现，毫无关联，即其间并无classes继承关系

关联式容器自动对其元素进行排序，这并不意味着它就是用来排序的。当然，STL的使用者可以对序列式容器的元素加以手动排序。而关联式自动对其元素进行排序的主要优点是，当你搜寻元素时，可获得更佳的效率，自动排序只不过是关联式容器的一个有用的副作用而已

注：客观来说，对关联式容器插入大量元素进行排序与一次性对Vector插入大量元素在进行排序所损耗的时间相比，vector所耗费的时间更少，效率更佳

STL内部预先定义好了以下三个序列式的容器：

vectordequelist

此外，你也可将string和array当作一种序列式容器

​ Vector将其元素置于一个dynamic array中加以管理。它允许随机存取，也就是你可以利用索引直接存取任何一个元素。在vector尾部附加元素或者移除元素均非常的快速，但在array中部或者头部安插元素就比较费时费力了

#include
#include
using namespace std;

int main()
{
    vector vi;
    for(int i=1;i<=6;++i)
        vi.push_back(i);
    for(int i=0;i 
程序输出结果：
 
1 2 3 4 5 6
 
知识点：
 
#include< vector >含入vectors的头文件push_back()函数可为容器的尾部安插元素size()成员函数返回容器中的元素的个数可通过subscript（下标）操作符[]，存取vector内的某个元素 
Deque 
​ 所谓deque，是“double-ended queue”的缩写。它是一个dynamic array，可以向两端发展，因此不论在尾部或者是头部安插元素都十分的迅速。在中间部分安插元素则比较费时费力，因为必须移动其他元素
 
#include
#include
using namespace std;

int main()
{
    deque dd;
    for(int i=1;i<=6;++i)
        dd.push_front(i*1.1);
    for(auto it=dd.begin();it!=dd.end();++it)
        cout<<*it< 
程序输出结果：
 
6.6 5.5 4.4 3.3 2.2 1.1
 
知识点：
 
#include< deque>含入deques的头文件push_front()函数可为容器的头部安插元素begin()成员函数返回容器中第一个元素的地址，end()成员函数返回容器中最后一个元素的地址 
push_front()函数会将元素安插于群集前端。需要注意的是，这种安插方式造成的结果就是，元素排放的次序与安插次序恰好相反，因为每个元素都安插于上一个元素的前面
 
当然，我们也可使用成员函数push_back()在deque尾端附加元素。vector并未提供push_front()函数，因为这样做的话，其时间性能很差，在vector的头端安插一个元素，需要移动全部的元素！
 
一般而言，STL容器只提供通常具备良好时间效能的成员函数（所谓“良好”的时间效能，通常意味着具有常数复杂度或者对数复杂度），以防止程序员调用性能很差的函数
 
List 
​ List由双向链表（double linked list）实作而成。这意味着list内的每个元素都以一部分内存指示其前趋元素和后继元素。List不提供随机存取
 
List的优势：在任何位置上执行安插或删除动作动作都非常迅速，因为只须改变链接（links）就行。这表示在list中间位置移动元素比在vector和deque快得多
 
#include
#include
using namespace std;

int main() 
{
    list lc;
    for(char c='a';c<='z';++c)
        lc.push_back(c);
    while(!lc.empty()) {
        cout< 
程序输出结果：
 
a b c d e f g h i j k l m n o p q r s t u v w x y z
 
知识点：
 
#include< list >含入list的头文件empty()成员函数的返回值告诉我们容器中是否还有元素front()成员函数会返回容器的第一个元素pop_front()成员函数会删除容器中的第一个元素，需要注意的是pop_front()并不会返回被删除的元素 
lists并没有提供以operator[]直接存取元素的能力，因为lists不支持随机存取，如果采用operator[]会导致不良效能。使用迭代器一样可以遍历并打印所有元素
 
Arrays 
​ 这种容器不是类别（class），而是C/C++语言核心所支持的一个型别(type)：具有静态大小或者动态大小的array
 
#include
#include
using namespace std;

int main()
{
    array ai = { 1,2,3,4,5,6 };
    for(auto it=ai.begin();it!=ai.end();++it)
        cout<<*it< 
程序输出结果：
 
1 2 3 4 5 6
 
关联式容器（Associative Containers） 
​ 关联式容器依据特定的排序准则，自动为其元素排序。排序准则以函数形式呈现，用来比较元素值（value）或元素键（key）。通常关联式容器由二叉树（binary tree）视作出来。在二叉树中，每个元素(节点)都有一个父节点和两个子节点；左子树的所有元素都比自己小，右子树的所有元素都比自己大
 
关联式容器的差别主要在于元素的类型以及处理重复元素时的方式（态度）
 
Sets 
Set的内部元素依据其值自动排序，每个元素值只能出现一次，不允许重复
 
Multisets 
Multisets和set相同，只不过它允许重复元素，也就是说multiset可包含多个数值相同的元素
 
Maps 
Map的元素都是“实值/键值”所形成的一个对组(key/value pairs)。每个元素有一个键，是排序准则的基础。每一个键只能出现一次，不允许重复。Map可被视为关联式数组，也就是具有任意索引型别的数组
 
Multimaps 
Multimap和map相同，但允许重复元素，也就是说multimap可包含多个键值(key)相同的元素。Multimap可被当作“字典”使用
 
我们可以将set视为一种特殊的map：其元素实值就是键值。实际产品中，所有这些关联式容器通常都由二叉树（binary tree）实作而成
 
Set和Muliset 
#include
#include
using namespace std;

int main()
{
	typedef set IntSet;
	
	IntSet I_set;
	
	I_set.insert(3);
	I_set.insert(5);
	I_set.insert(1);
	I_set.insert(2);
	I_set.insert(4);
	I_set.insert(1); // 重复插入，忽略该操作 
	
	IntSet::iterator it;
	for(it=I_set.begin();it!=I_set.end();++it)
		cout<<*it< 
程序输出结果：
 
1 2 3 4 5
 
知识点：
 
#include< set >含入set和muliset的头文件所有关联式容器都提供有一个insert()成员函数，用来安插新元素，新元素会根据排序准则自动安插到正确的位置需要注意的是，我们不能使用序列容器的push_back()和push_front()函数，它们在这里毫无意义，因为我们没有权力指定新元素的位置如果你想用multiset而不是set，唯一需要改变的就是容器的型别（set和multiset的设定被置于同一个头文件中） 
Maps和Multimaps 
​ Map的元素是成对的键值/实值(key/valule)。因此其声明，元素安插，元素存取皆和set有所不同，以下为multimap的使用案例：
 
#include
#include