stl

STL(标准模板库)基本概念

一、什么是STL

STL（Standard Template Library，标准模板库)的从广义上讲分为三类：algorithm（算法）、container（容器）和iterator（迭代器），容器和算法通过迭代器可以进行无缝地连接。几乎所有的代码都采 用了模板类和模板函数的方式，这相比于传统的由函数和类组成的库来说提供了更好的代码重用机会。在C++标准中，STL被组织为下面的13个头文 件：<algorithm>、<deque>、<functional>、<iterator>、<vector>、<list>、<map>、<memory>、<numeric>、<queue>、<set>、<stack> 和<utility>。

STL详细的说六大组件

–  容器（Container）

–  算法（Algorithm）

–  迭代器（Iterator）

–  仿函数（Function object）

–  适配器（Adaptor）

–  空间配制器（allocator）

使用STL的好处

1）STL是C++的一部分，因此不用额外安装什么，它被内建在你的编译器之内。

2）STL的一个重要特点是数据结构和算法的分离。尽管这是个简单的概念，但是这种分离确实使得STL变得非常通用。

例如，在STL的vector容器中，可以放入元素、基础数据类型变量、元素的地址；STL的sort()函数可以用来操作vector,list等容器。

1）  程序员可以不用思考STL具体的实现过程，只要能够熟练使用STL就OK了。这样他们就可以把精力放在程序开发的别的方面。

2）  STL具有高可重用性，高性能，高移植性，跨平台的优点。

高可重用性：STL中几乎所有的代码都采用了模板类和模版函数的方式实现，这相比于传统的由函数和类组成的库来说提供了更好的代码重用机会。关于模板的知识，已经给大家介绍了。

高性能：如map可以高效地从十万条记录里面查找出指定的记录，因为map是采用红黑树的变体实现的。(红黑树是平横二叉树的一种)

高移植性：如在项目A上用STL编写的模块，可以直接移植到项目B上。

                跨平台：如用windows的Visual Studio编写的代码可以在Mac OS的XCode上直接编译。

二、容器的概念

容器：用来管理一组元素

容器的分类

1.序列式容器（Sequence containers）

每个元素都有固定位置－－取决于插入时机和地点，和元素值无关。如：vector、deque、list

2.关联式容器（Associated containers）

元素位置取决于特定的排序准则，和插入顺序无关。如：set、multiset、map、multimap

数据结构

描述

实现头文件

向量(vector)

连续存储的元素

<vector>

列表(list)

由节点组成的双向链表，每个结点包含着一个元素

<list>

双队列(deque)

连续存储的指向不同元素的指针所组成的数组

<deque>

集合(set)

由节点组成的红黑树，每个节点都包含着一个元素，节点之间以某种作用于元素对的谓词排列，没有两个不同的元素能够拥有相同的次序

<set>

多重集合(multiset)

允许存在两个次序相等的元素的集合

<set>

栈(stack)

后进先出的值的排列

<stack>

队列(queue)

先进先出的执的排列

<queue>

优先队列(priority_queue)

元素的次序是由作用于所存储的值对上的某种谓词决定的的一种队列

<queue>

映射(map)

由{键，值}对组成的集合，以某种作用于键对上的谓词排列

<map>

多重映射(multimap)

允许键对有相等的次序的映射

<map>

三、迭代器

　　迭代器在STL中用来将算法和容器联系起来，起着一种黏和剂的作用。几乎STL提供的所有算法都是通过迭代器存取元素序列进行工作的，每一个容器都定义了其本身所专有的迭代器，用以存取容器中的元素。

　　迭代器部分主要由头文件<utility>,<iterator>和<memory>组 成。<utility>是一个很小的头文件，它包括了贯穿使用在STL中的几个模板的声明，<iterator>中提供了迭代器 使用的许多方法，而对于<memory>的描述则十分的困难，它以不同寻常的方式为容器中的元素分配存储空间，同时也为某些算法执行期间产生 的临时对象提供机制,<memory>中的主要部分是模板类allocator，它负责产生所有容器中的默认分配器。

四、算法

STL提供了大约100个实现算法的模版函数，比如算法for_each将为指定序列中的每一个元素调用指定的函数，stable_sort以 你所指定的规则对序列进行稳定性排序等等。这样一来，只要熟悉了STL之后，许多代码可以被大大的化简，只需要通过调用一两个算法模板，就可以完成所需要 的功能并大大地提升效率。

算法部分主要由头文件<algorithm>，<numeric>和<functional>组 成。<algorithm>是所有STL头文件中最大的一个（尽管它很好理解），它是由一大堆模版函数组成的，可以认为每个函数在很大程度上 都是独立的，其中常用到的功能范围涉及到比较、交换、查找、遍历操作、复制、修改、移除、反转、排序、合并等等。<numeric>体积很 小，只包括几个在序列上面进行简单数学运算的模板函数，包括加法和乘法在序列上的一些操作。<functional>中则定义了一些模板类， 用以声明函数对象。

五、C++标准库

C++强大的功能来源于其丰富的类库及库函数资源。C++标准库的内容总共在50个标准头文件中定义。在C++开发中，要尽可能地利用标准库完 成。

C++标准库的内容分为10类，分别是：

C1. 标准库中与语言支持功能相关的头文件

头文件

描        述

<cstddef>

定义宏NULL和offsetof，以及其他标准类型size_t和ptrdiff_t。与对应的标准C头文件的区别是，NULL是C++空指针常量的补充定义，宏offsetof接受结构或者联合类型参数，只要他们没有成员指针类型的非静态成员即可。

<limits>

提供与基本数据类型相关的定义。例如，对于每个数值数据类型，它定义了可以表示出来的最大值和最小值以及二进制数字的位数。

<climits>

提供与基本整数数据类型相关的C样式定义。这些信息的C++样式定义在<limits>中

<cfloat>

提供与基本浮点型数据类型相关的C样式定义。这些信息的C++样式定义在<limits>中

<cstdlib>

提供支持程序启动和终止的宏和函数。这个头文件还声明了许多其他杂项函数，例如搜索和排序函数，从字符串转换为数值等函数。它与对应的标准C头文件 stdlib.h不同，定义了abort(void)。abort()函数还有额外的功能，它不为静态或自动对象调用析构函数，也不调用传给 atexit()函数的函数。它还定义了exit()函数的额外功能，可以释放静态对象，以注册的逆序调用用atexit()注册的函数。清除并关闭所有 打开的C流，把控制权返回给主机环境。

<new>

支持动态内存分配

<typeinfo>

支持变量在运行期间的类型标识

<exception>

支持异常处理，这是处理程序中可能发生的错误的一种方式

<cstdarg>

支持接受数量可变的参数的函数。即在调用函数时，可以给函数传送数量不等的数据项。它定义了宏va_arg、va_end、va_start以及va_list类型

<csetjmp>

为C样式的非本地跳跃提供函数。这些函数在C++中不常用

<csignal>

为中断处理提供C样式支持

C2. 支持流输入/输出的头文件

头文件

描        述

<iostream>

支持标准流cin、cout、cerr和clog的输入和输出，它还支持多字节字符标准流wcin、wcout、wcerr和wclog。

<iomanip>

提供操纵程序，允许改变流的状态，从而改变输出的格式。

<ios>

定义iostream的基类

<istream>

为管理输出流缓存区的输入定义模板类

<ostream>

为管理输出流缓存区的输出定义模板类

<sstream>

支持字符串的流输入输出

<fstream>

支持文件的流输入输出

<iosfwd>

为输入输出对象提供向前的声明

<streambuf>

支持流输入和输出的缓存

<cstdio>

为标准流提供C样式的输入和输出

<cwchar>

支持多字节字符的C样式输入输出

C3. 与诊断功能相关的头文件

头文件

描        述

<stdexcept>

定义标准异常。异常是处理错误的方式

<cassert>

定义断言宏，用于检查运行期间的情形

<cerrno>

支持C样式的错误信息

C4. 定义工具函数的头文件

头文件

描        述

<utility>

定义重载的关系运算符，简化关系运算符的写入，它还定义了pair类型，该类型是一种模板类型，可以存储一对值。这些功能在库的其他地方使用

<func