C++STL大全----容器篇（上）

（一）概念

STL，英文全称 standard template library，中文可译为标准模板库或者泛型库，其包含有大量的模板类和模板函数，是 C++ 提供的一个基础模板的集合，用于完成诸如输入/输出、数学计算等功能。

STL 最初由惠普实验室开发，于 1998 年被定为国际标准，正式成为 C++ 程序库的重要组成部分。

STL的从广义上讲分为三类：algorithm（算法）、container（容器）和iteraotr（迭代器），容器和算法通过迭代器可以进行无缝地连接。几乎所有的代码都采用了模板类和模板函数的方式，这相比于传统的由函数和类组成的库来说提供了更好的代码重用机会。

在C++标准中，STL被组织为下面的13个头文件：<algorithm>、<deque>、<functional>、<iter>、<vector>、<list>、<map>、<memory>、<numeric>、<queue>、<set>、<stack> 和<utility>。

（二）STL的意义、作用

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

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

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

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

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

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

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

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

5）了解到STL的这些好处，每一个C＋＋程序员都应该好好学习STL。只有能够熟练使用STL的程序员，才是好的C++程序员。

6）竞赛中，它是很好用的东西，几乎每场竞赛都能用到；就好比你可以有蘑菇弹，可以不用它，也比你没有蘑菇弹强。

（三） STL六大块

Ⅰ 容器

容器，顾名思义，置物之器也。

研究数据的特定排列方式，以利于搜索或排序或其他特殊目的，这一门学科我们称为数据结构。几乎可以说，任何特定的数据结构都是为了实现某种特定的算法。STL容器就是将运用最广泛的一些数据结构实现出来。

常用的数据结构：数组(array),链表(list),树(tree)，栈(stack),队列(queue),集合(set),映射表(map),根据数据在容器中的排列特性，这些数据分为序列式容器和关联式容器两种。

序列式容器：即以线性排列（类似普通数组的存储方式）来存储某一指定类型（例如 int、double 等）的数据，需要特殊说明的是，该类容器并不会自动对存储的元素按照值的大小进行排序。。

关联式容器：非线性排列(二叉树)，在存储元素时会为每个元素在配备一个键，整体以键值对的方式存储到容器中，可以通过键值直接找到对应的元素，而无需遍历整个容器。另外，关联式容器在存储元素，默认会根据各元素键值的大小做升序排序。

Ⅱ 算法

算法，简言之，即问题之解法也。

以有限的步骤，解决逻辑或数学上的问题，我们叫做算法(Algorithms).

广义而言，我们所编写的每个程序都是一个算法，其中的每个函数也都是一个算法，毕竟它们都是用来解决或大或小的逻辑问题或数学问题。STL收录的算法经过了数学上的效能分析与证明，是极具复用价值的，包括常用的排序，查找等等。特定的算法往往搭配特定的数据结构，算法与数据结构相辅相成。

算法分为:质变算法和非质变算法。

质变算法：是指运算过程中会更改区间内的元素的内容。例如拷贝，替换，删除等等

非质变算法：是指运算过程中不会更改区间内的元素内容，例如查找、计数、遍历、寻找极值等等

Ⅲ 迭代器

迭代器(iterator)是一种抽象的设计概念，现实程序语言中并没有直接对应于这个概念的实物。

iterator模式定义如下：提供一种方法，使之能够依序寻访某个容器所含的各个元素，而又无需暴露该容器的内部表示方式。(实际上是封装了指针的类中类)

迭代器的设计思维-STL的关键所在，STL的中心思想在于将容器(container)和算法(algorithms)分开，彼此独立设计，最后再一贴胶着剂将他们撮合在一起。从技术角度来看，容器和算法的泛型化并不困难，c++的class template和function template可分别达到目标，如果设计出两这个之间的良好的胶着剂，才是大难题。

简言之，迭代器的作用是用来访问容器（用来保存元素的数据结构）中的元素的。这和访问数组这个序列的指针一样，因为数组范围内的指针就是迭代器的一种

迭代器的种类
种类	功能	操作
输入迭代器	提供对数据的只读访问	只读，支持++、==、!=
输出迭代器	提供对数据的读写访问	读写，支持++
前向迭代器	提供读写操作，并能向前推进迭代器	读写，支持++、==、!=
双向迭代器	提供读写操作，并能向前和向后操作	读写，支持++、--，
随机访问迭代器	提供读写操作，并能以跳跃的方式访问容器的任意数据，是功能最强的迭代器	读写，支持++、--、[n]、-n、<、<=、>、>=

Ⅳ 仿函数

仿函数定义

仿函数（Functor）又称为函数对象（Function Object）是一个能行使函数功能的类，仿函数是定义了一个含有operator()成员函数的对象，可以视为一个一般的函数，只不过这个函数功能是在一个类中的运算符operator()中实现，是一个函数对象，它将函数作为参数传递的方式来使用。

写一个简单类，除了维护类的基本成员函数外，只需要重载 operator() 运算符。这样既可以免去对一些公共变量的维护，也可以使重复使用的代码独立出来，以便下次复用。

仿函数优点

如果可以用仿函数实现，那么你应该用仿函数，而不要用CallBack。原因在于：

仿函数可以不带痕迹地传递上下文参数。而CallBack技术通常使用一个额外的void*参数传递。这也是多数人认为CallBack技术丑陋的原因。
仿函数技术可以获得更好的性能，这点直观来讲比较难以理解。

仿函数作用

仿函数通常有下面四个作用：

作为排序规则，在一些特殊情况下排序是不能直接使用运算符<或者>时，可以使用仿函数。
作为判别式使用，即返回值为bool类型。
同时拥有多种内部状态，比如返回一个值得同时并累加。
作为算法for_each的返回值使用。

标准仿函数

STL 中也大量涉及到仿函数，有时仿函数的使用是为了函数拥有类的性质，以达到安全传递函数指针、依据函数生成对象、甚至是让函数之间有继承关系、对函数进行运算和操作的效果。比如 STL 中的容器 set 就使用了仿函数 less ，而 less 继承的 binary_function，就可以看作是对于一类函数的总体声明，这是函数做不到的。