标准模板库STL

STL定义了强大的、基于模版的、可重用的组件，它基于泛型编程实现了许多通用的数据结构及相关算法。它主要有三个组件：容器、迭代器和算法。

STL三种组件

容器

容器：序列容器、关联容器和容器适配器

序列容器：描述了线性的数据结构。

关联容器：描述了非线性的容器存放键值对

以上两种也成为首类容器。

容器适配器：栈和队列。

容器的通用函数：默认构造函数，拷贝构造函数，析构函数，empty，size，操作符=<等，swap交换。

首类容器的函数：max_size，begin，end，rbegin，rend，erase，clear。

迭代器

迭代器类似于指针。

STL首类容器中成员函数begin和end分别返回指向容器中第一个元素和最后一个元素的下一个元素的迭代器（可以理解为指针，只不过有更多的信息和功能）。

若i为指向一个特定元素的迭代器，则*i为i指向的元素，++i使迭代器指向这个元素的下一个元素。

迭代器的层次：

底层的迭代器可以实现上层迭代器的所有功能。

迭代器预先定义的typedef：

Iterator向前，读写

Const_iterator 向前，读

Reverse_iterator向后，读写

Constreverseiterator向后，读

算法

STL中提供了多种常用的操作容器的算法。

序列容器

序列容器有三种：vetor，deque和list。其中vetor和deque是基于数组的类模版，而list是基于链表的数据结构。

Vetor比较像数组，只不过有更多的功能，在vetor尾部插入操作是高效的，它可以变长来适应新添加的元素。但是由于他在内存中占用的是连续的空间，其插入和删除操作是低效的。

Deque适用于在两端插入和删除元素，其在前端插入删除操作要高于vetor。

List是一个基于链表的结构，所以他的插入和删除操作具有更高的效率。

关联容器

关联容器通过关键词直接存取元素，即字典，STL中存在四种关联容器：multiset、set、multimap和map。每种容器都按照已经排序好的方式保存所有关键字。Multiset和set类提供了控制数值集合的操作，其中元素的值就是关键字。Multimpa和map提供了处理关键字、值（键值对）的功能。Multi-的区别在于它允许重复的关键字。

适配器容器

适配器容器和首类容器的区别在于他们不提供真正用于存储数据的数据结构，而是在首类容器的基础上进行封装，来实现增强的数据结构。而且他们不支持迭代器。

适配器容器之所以叫适配器容器的原因在于他为首类容器加了一个封装，同时，我们可以选择适配器容器的底层数据结构。

适配器容器有三种：stack、queue和priority_queue适配器。

Stack适配器容器实现了堆栈的功能， 即后进先出的数据结构。他可以选择任意一种序列（vector,list或deque），但是deque（默认）和vector是stack最好的底层容器。

它主要的功能：push，pop，top，empty，size。

Queue适配器容器实现了一个队列的功能，先进先出。Queue容器可以使用list或deque实现，默认deque，效率也比较高的。

Priority_queue适配器实现了一个按顺序的数据结构，他和queue的区别在于他里面的元素一直是有序的，每次删除时都是删除最高优先级的元素。底层容器可以使用deque和vector。

STL算法

这里大体记录下，以后如果使用在查阅使用方法。

容器元素操作算法：

Fill,filln,generate,generaten填充或者是用函数生成元素添加到容器中。

Equal,mismatch,lexicographical_compare比较两个序列是否相同、不匹配的位置以及比较字符数组的内容。

Remove,removeif,removecopy,removecopyif删除或移动，if的话会有一个比较函数，true则删除或移动。

Replace,replaceif,replacecopy,replacecopyif替换或复制。

Swap,iterswap,swapranges交换元素

数学算法

Random_shuffle随即重排

Count和count_if统计元素个数

Minelement/maxelement锁定最小/最大元素位置

Accumulate:计算和

For_each每个元素执行一个函数，但不能修改元素。

Transform每个元素执行一个不改变元素的函数，并将结果输出到某个容器里。

搜索和排序算法：

Find查找元素位置

Find_if搜索判断函数返回true的元素。

Sort以递增的数序排列元素

Binary_search确定某值是否在序列之间。这个序列事先必须以递增的顺序排列。

其他略。。。

Bitset类

Bitset类主要是为了创建和操作位集合，有set，reset，flip等位集合的操作。

函数对象

函数对象是一个重载了（）运算符的类。与函数指针相比，一方面可以通过内联函数提高性能，其次可以拥有成员变量来协助工作。