STL容器内部实现

3.1. STL容器

（1）序列式容器（Sequence containers），每个元素都有固定位置－－取决于插入时机和地点，和元素值无关，vector、deque、list；

Vectors：将元素置于一个动态数组中加以管理，可以随机存取元素（用索引直接存取），数组尾部添加或移除元素非常快速。但是在中部或头部安插元素比较费时；

Deques：是“double-ended queue”的缩写，可以随机存取元素（用索引直接存取），数组头部和尾部添加或移除元素都非常快速。但是在中部或头部安插元素比较费时；

Lists：双向链表，不提供随机存取（按顺序走到需存取的元素，O(n)），在任何位置上执行插入或删除动作都非常迅速，内部只需调整一下指针；

（2）关联式容器（Associated containers），元素位置取决于特定的排序准则，和插入顺序无关，set、multiset、map、multimap；

Sets/Multisets：内部的元素依据其值自动排序，Set内的相同数值的元素只能出现一次，Multisets内可包含多个数值相同的元素，内部由二叉树实现，便于查找；

Maps/Multimaps：Map的元素是成对的键值/实值，内部的元素依据其值自动排序，Map内的相同数值的元素只能出现一次，Multimaps内可包含多个数值相同的元素，内部由二叉树实现，便于查找；

容器的比较：

	Vector	Deque	List	Set	MultiSet	Map	MultiMap
内部结构	dynamic array	array of arrays	double linked list	binary tree	binary tree	binary tree	binary tree
随机存取	Yes	Yes	No	No	No	Yes(key)	No
搜索速度	慢	慢	很慢	快	快	快	快
快速插入移除	尾部	首尾	任何位置	--	--	--	--

 

迭代器的作用：能够让迭代器与算法不干扰的相互发展，最后又能无间隙的粘合起来，重载了*，＋＋，＝＝，！＝，＝运算符。用以操作复杂的数据结构，容器提供迭代器，算法使用迭代器；

3.2 STL迭代器

迭代器作用：

（1）能够让迭代器与算法不干扰的相互发展，最后又能无间隙的粘合起来；

（2）重载了＊，＋＋，＝＝，！＝，＝运算符。用以操作复杂的数据结构；

（3）容器提供迭代器，算法使用迭代器；

简单例子：

迭代器的分类：

Input Iterator, Output Iterator, Forward Iterator, Bidirectional Iterator, Random access Iterator等；

不同容器提供自己的迭代器，所以不同迭代器具有不同的能力；

不同的算法需要不同的迭代器的能力；相同的算法需要根据迭代器的能力不同而做相应的优化；

3.3 STL算法

STL算法部分主要由头文件, , 组成；要使用STL中的算法函数必须包含头文件，对于数值算法须包含，中则定义了一些模板类，用来声明函数对象；

STL中算法大致分为四类：

非可变序列算法：指不直接修改其所操作的容器内容的算法。

可变序列算法：指可以修改它们所操作的容器内容的算法。

排序算法：包括对序列进行排序和合并的算法、搜索算法以及有序序列上的集合操作。

数值算法：对容器内容进行数值计算。

查找算法(13个)：判断容器中是否包含某个值；

adjacent_find：在iterator对标识元素范围内，查找一对相邻重复元素，找到则返回指向这对元素的第一个元素的Forward Iterator；否则返回last；

binary_search：在有序序列中查找value，找到返回true。重载的版本实用指定的比较函数对象或函数指针来判断相等；

count：利用等于操作符，把标志范围内的元素与输入值比较，返回相等元素个数；

count_if：利用输入的操作符，对标志范围内的元素进行操作，返回结果为true的个数；

equal_range：功能类似equal，返回一对iterator，第一个表示lower_bound，第二个表示upper_bound；

其他：find，find_end，find_first_of，find_if，lower_bound，upper_bound，search，search_n；

排序和通用算法(14个)：提供元素排序策略；

inplace_merge：合并两个有序序列，结果序列覆盖两端范围。重载版本使用输入的操作进行排序；

merge：合并两个有序序列，存放到另一个序列。重载版本使用自定义的比较；

nth_element：将范围内的序列重新排序，使所有小于第n个元素的元素都出现在它前面，而大于它的都出现在后面。重载版本使用自定义的比较操作；

partial_sort：对序列做部分排序，被排序元素个数正好可以被放到范围内。重载版本使用自定义的比较操作；

partial_sort_copy：与partial_sort类似，不过将经过排序的序列复制到另一个容器；

其他：partition，random_shuffle，reverse，reverse_copy，rotate， rotate_copy，sort，stable_sort，stable_partition；

删除和替换算法(15个)；

排列组合算法(2个)：提供计算给定集合按一定顺序的所有可能排列组合；

算术算法(4个)；

生成和异变算法(6个)；

关系算法(8个)；

集合算法(4个)；

堆算法(4个)；

4. STL使用示例

待续…

5. 参考文档

（1）C++ STL 快速入门 

（2）三十分钟掌握STL