C+中STL用法详解一_内容介绍

STL即标准模板库，其内封装了诸多的基本数据结构和算法。

1. 什么是STL

STL是C++标准程序库的核心，其中包含了很多常用的基本数据结构和算法，提供了一个可扩展的应用框架；

STL的一个重要特点是数据结构和算法的分离
这使得STL变得很通用，比如sort()方法是完全通用的，可以用它来操作任何数据集合，包括链表、容器、数组

STL是基于template模板实现的，而不是面向对象

2. STL内容介绍

STL中主要有六大组件：
1. 容器(Container)
用来存储并管理某类对象的集合，以模板类的方法提供。每一种容器都有其优缺点，为了访问容器中的数据，可以使用由容器类输出的迭代器。
2. 迭代器(Iterator)
提供访问容器中对象的方法。例如可以使用一对迭代器指定list或vector中一定范围的对象。迭代器可划分为 5 种类属，这 5 种类属归属两种类型：双向迭代器和随机存取迭代器
3. 算法(Algorithm)
用来操作容器中数据结构的模板函数。例如STL用sort()来对容器中数据排序，用find()在容器中查找元素。函数本身与它们操作的数据结构和类型无关，因此可以在简单数组和任何高复杂容器中使用
4. 仿函数(Functor)
5. 适配器(Adaptor)
6. 分配器(Allocator)

2.1 容器

STL中容器有序列式容器和关联容器，容器适配器(stack、queue、priority_queue)，位集(bit_set)，串包(string_package)等。
（1）序列式容器每个元素都有固定位置——取决于插入时机和下标，和元素值无关
（vector、deque、list）
（2）关联式容器，元素位置取决于特定的排序准则，和插入顺序无关
（set/multiset、map/mutlimap）
目前STL中已经提供的主要容器如下：

vector <T>：一种向量
list <T>：一个双向链表容器，完成了标准C++数据结构中链表的所有功能
deque <T>：双端队列容器
set <T>：一种集合容器，元素不能重复
multiset <T>：一种允许出现重复元素的集合容器
map <key,value>：关键值对的容器，key唯一
multimap <key,value>：一种允许出现重复key值的关联式容器
stack <T>：一种栈容器
queue <T> ：一种队列容器
prority_queue <T>：优先队列容器

2.2 STL迭代器

作用:

Iterator(迭代器)模式又称Cursor模式，可以使得我们在不知道对象内部表示情况下，按一定顺序访问聚合对象中的元素；

能让容器与算法不干扰的相互发展，最后又能无间隙的粘合起来，容器提供迭代器，算法使用迭代器访问容器中的数据；

重载了*、++、==、!=、=运算符。

2.3 算法

STL提供了大约100个实现算法的模板函数，只需要调用一下就可以很大程度上简化代码。
算法部分主要由头文件<algorithm>,<numeric>,<fuctional>组成，STL中的算法大致分为四类：

非可变序列算法：不直接修改所操作容器内容的算法
可变序列算法：可以修改所操作容器内容的算法
排序算法：对序列进行排序、合并、搜索、集合操作等
数值算法：对容器内容进行数值计算
常见的部分算法如下：
for_each()：用指定函数依次对指定范围内所有元素进行迭代访问，返回所指定的函数类型。
find()：利用底层元素的等于操作符，对指定范围内的元素与输入值进行比较。当匹配时，结束搜索，返回该元素的一个InputIterator。
find_if()：使用输入的函数代替等于操作符执行find。
count()：利用等于操作符，把标志范围内的元素与输入值比较，返回相等元素个数。
count_if()：利用输入的操作符，对标志范围内的元素进行操作，返回结果为true的个数。
replace()：将指定范围内所有等于vold的元素都用vnew代替。
replace_if()：将指定范围内所有操作结果为true的元素用新值代替。
sort()：以升序重新排列指定范围内的元素。重载版本使用自定义的比较操作。
merge()：合并两个有序序列，存放到另一个序列。重载版本使用自定义的比较。
reverse()：将指定范围内元素重新反序排序。
unique()：清除序列中重复元素。
remove()：删除指定范围内所有等于指定元素的元素。
equal()：如果两个序列在标志范围内元素都相等，返回true。
set_union()：返回两个序列的并集。
set_intersection()：返回两个序列的交集。
set_difference()：返回两个序列的差集。
set_symmetric_difference()：返回两个序列的对称差集。

2.4 仿函数

C++中通过一个类或结构体中重载括号运算符的方法使用一个函数对象而不是一个普通函数，要使
使用仿函数比一般函数优点参考以下链接link

struct cmp{
  bool operator()(ListNode* node1, ListNode* node2){
    return node1->val > node2->val;
  }
};

sort(a, a+n, cmp); //按照cmp的规则迭代排序

用STL内建的仿函数，必须包含头文件。该头文件包含的仿函数分类包括：

算术类仿函数
加： plus
减： minus
乘： multiplies
除： dividex
模取： modulus
否定： negate
关系运算类仿函数
等于： equal_to
不等于： not_equal_to
大于： greater
大于等于：greater_equal
小于： less
小于等于：less_equal
逻辑运算仿函数
逻辑与： logical_and
逻辑或： logical_or
逻辑否： logical_no

除了使用STL内建的仿函数，还可以使用自定义的仿函数。

2.5 容器适配器

容器适配器(配接器)对容器进行包装使其表现出另外一种行为。例如stack<int, vector>实现了栈的功能，但其内部使用顺序容器vector来存储数据（相当于是vector表现出了栈的行为）

种类	默认顺序容器	可用顺序容器	说明
stack	deque	vector、list、deque	#include “stack”
queue	deque	list、deque	#include “queue”；基础容器必须提供push_front()运算
priority_queue	vector	vector、deque	#include “queue”；基础容器必须提供随机访问功能