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
1 | struct 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
种类 | 默认顺序容器 | 可用顺序容器 | 说明 |
---|---|---|---|
stack | deque | vector、list、deque | #include “stack” |
queue | deque | list、deque | #include “queue”;基础容器必须提供push_front()运算 |
priority_queue | vector | vector、deque | #include “queue”;基础容器必须提供随机访问功能 |
定义适配器
初始化
1
stack<int>T;
覆盖默认容器类型
1
stack<int, vector<int> >T;
(需注意两个“<”之间要留一个空格,以免被编译器当作输出流符号)
3. 总结
STL作为C++通用库,主要由容器、迭代器、算法、仿函数、容器适配器、内存配置器六大部分组成。使用 STL 最重要的是掌握基本理论和编程方法,了解 STL 编程技术,必须深刻掌握 STL 容器技术和 STL 迭代器技术。
STL 提供了一组表示容器、迭代器、仿函数和算法的模板:
- 容器是类似数组的单元,可存储 若干个值,且STL容器是同质的,即存储的值类型相同;
- 算法是完成特定任务的处方;
- 迭代器能够用来遍历容器的对象,与能够遍历数组的指针类似,是广义指针;
- 仿函数是类似于函数的对象,可以是类对象或函数指针。