[STL基础]STL概述

什么是STL

STL就是StandardTemplateLibrary，标准模板库。STL是泛型编程的实例，用到的技术就是类模板和函数模板。STL的一个重要特点是数据结构和算法的分离。

模板：所谓模板是一种使用无类型参数来产生一系列函数或类的机制。通过模板可以产生类或函数的集合，使它们操作不同的数据类型，从而避免需要为每一种数据类型产生一个独立的类或函数。

STL简介

STL的代码从广义上讲分为3类：algorithm(算法)、container(容器)和iterator(迭代器)。几乎所有的代码都采用了模板类和模板函数的方式，这相比于传统的由函数和类组成的库来说提供了更好的代码重用几乎。在C++标准中，STL由13个头文件组成，如<list>

STL的代码从广义上讲分为三类(共13个头文件)

算法(algorithm)3个头文件	algorithm,numeric,functional
容器(container)7个头文件	vector,list,deque,stack,set(set,multiset),map(map,multimap),queue(queue,priority_queue)共10个数据结构
迭代器(iterator)3个头文件	iterator,memory,utility

算法

算法是用来操作容器中的数据的模版函数。例如，STL用sort()来对一个vector中的数据进行排序，用find()来搜索一个list中的对象。函数本身与他们操作的数据的结构和类型无关，因此他们可以从简单的数组到高度复杂容器的任何数据结构上使用。

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

容器

容器是一种数据结构，如list，vector和deques，以模板类的方法提供。为了访问容器中的数据，可以使用容器类输出的迭代器。

数据结构	描述	头文件
vector向量	连续存储元素	<vector>
list列表	由节点组成的双向链表，每个节点包含一个元素	<list>
deque双列表	连续存储的指向不同元素的指针所组成数组	<deque>
set集合	由节点组成的红黑树，每个节点都包含着一个元素，节点之间以某种作用于元素对的谓词排列，没有两个不同的元素能够拥有相同的次序	<set>
multiset多重集合	允许存在两个次序相等的元素的集合	<set>
stack栈	后进先出的值的排列	<stack>
queue队列	先进先出的执的排列	<queue>
priority_queue优先队列	元素的次序是由作用于所存储的值对上的某种谓词决定的的一种队列	<queue>
map映射	由{键，值}对组成的集合，以某种作用于键对上的谓词排列	<map>
multimap多重映射	允许键对有相等的次序的映射	<map>

对应的数据结构：vector线性表，list双向链表，stack栈，queue队列，deque可以理解为vector和list的结合体，set红黑树，map平衡二叉树

容器分为三大类

顺序容器	vector：后部插入/删除，直接访问 deque：前/后部插入/删除，直接访问 list：双向链表，任意位置插入/删除
关联容器	set：快速查找，无重复元素 multiset：快速查找，可有重复元素 map：一对一映射，无重复元素，基于关键字查找 multimap：一对一映射，可有重复元素，基于关键之查找
容器适配器	stack：LIFO queue：FIFO priority_queue：优先级高的元素先出

迭代器

迭代器提供了访问容器中对象的方法。例如，可以使用一对迭代器指定list或vector中的一定范围的对象。迭代器就如同一个指针。事实上，C++的指针也是一种迭代器。但是，迭代器也可以是那些定义了operator*()以及其他类似于指针的操作符地方法的类对象。

软件设计有一个基本原则，所有的问题都可以通过引进一个间接层来简化，这种简化在STL中就是用迭代器来完成的。概括来说，迭代器在STL中用来将算法和容器联系起来，起着一种黏和剂的作用。几乎STL提供的所有算法都是通过迭代器存取元素序列进行工作的，每一个容器都定义了其本身所专有的迭代器，用以存取容器中的元素。

迭代器部分主要由头文件<utility>,<iterator>和<memory>组成。

<utility>是一个很小的头文件，它包括了贯穿使用在STL中的几个模板的声明，

<iterator>中提供了迭代器使用的许多方法，

而对于<memory>的描述则十分的困难，它以不同寻常的方式为容器中的元素分配存储空间，同时也为某些算法执行期间产生的临时对象提供机制,<memory>中的主要部分是模板类allocator，它负责产生所有容器中的默认分配器。