一、STL是什么?
STL
英文全称为Standard Template Library
,常被称为标准模板库或者泛型库。
里面包含有大量的模板类和模板函数,是C++提供的一个基础模板的集合,用于完成诸如输入/输出、数学计算等功能。
从根本上来说,STL
是一些容器、算法和一些其他组件的集合,比如我们最常见的vector
, map
等等,就属于STL
。
它其中最重要的概念就是模板,以达到泛型编程的目的,不清楚的请先阅读另外一篇文章:模板。
二、STL组成
STL共有6大组件,包含了13个头文件。
首先是6大组件:
组件 | 功能 |
---|---|
容器 | 一些封装好的数据结构模板类,比如vector ,list 等等 |
算法 | STL提供了100个左右的数据结构算法, 它们也都被设计成了一个个模板函数,大部分包含在头文件algorithm 中,少部分包含在numeric 中 |
迭代器 | 我们对STL中容器的读写操作,都是通过这个迭代器完成的,使用起来和指针很像,相当于指针的一种抽象 |
函数对象 | 类将() 运算符重载位成员函数,这个类就称为函数对象类, 这个类的实例对象就是函数对象,又称为仿函数 |
适配器 | 让一个类的接口适配成用户的指定形式,让原本不能一起工作的两个类在一起工作 |
内存分配器 | 为上面的容器模板类提供自定义的内存申请和释放功能, 除非有特殊需求,否则我们一般用不着,默认即可 |
所在的头文件有以下这些:
iterator | function | vector |
---|---|---|
list | queue | stack |
deque | set | map |
algorithm | numeric | memory |
utility |
需要注意的是,所有的STL
内容, 均在std
这个命名空间之内。
这是很常见的错误, 一旦你前面没写using namespace std;
, 那么就会给你一直报错,特别是一些stl
的算法函数, 大家很容易忘记这些函数还需要一个std
命名空间才能使用。
三、STL容器
所谓容器, 就是帮助我们管理内存, 存储数据的结构。
这样我们就不用自己去亲自new
与delete
内存,可以极大提高我们的程序开发效率。
比如vector
,我们只需要通过函数调用,来达到存储或访问或删除数据等功能,而完全无需自己操心内存的管理
STL
容器也有三个类别,分别是序列容器、排序容器与哈希容器
- 序列容器
主要包括 vector
向量容器、list
列表容器以及 deque
双端队列容器。
之所以被称为序列容器,是因为元素在容器中的位置同元素的值无关,即容器内的值没有经过排序。将元素插入容器时,指定在什么位置,元素就会在什么位置。
- 排序容器
包括 set
集合容器、multiset
多重集合容器、map
映射容器以及 multimap
多重映射容器。
排序容器中的元素默认是由小到大排序好的,即便是插入元素,元素也会插入到适当位置。所以关联容器在查找时具有非常好的性能。
- 哈希容器
C++ 11 新加入 4 种关联式容器,分别是 unordered_set
哈希集合、unordered_multiset
哈希多重集合、unordered_map
哈希映射以及 unordered_multimap
哈希多重映射。
和排序容器不同,哈希容器中的元素是未排序的,元素的位置由哈希函数确定。
注意:以上 3 类容器的存储方式完全不同,因此使用不同容器完成相同操作的效率也大不相同。所以在实际使用时,要善于根据实现的功能去选择合适的容器。
四、STL迭代器
为了理解迭代器的作用, 我们还是需要知道为什么需要它。
首先我们要考虑一件事, 无论是序列容器还是关联容器,最常做的操作无疑是遍历容器中存储的元素。
但各个容器的内部结构并不完全相同, 比如vector
我们可以使用下标访问,,而list
我们只能从头遍历。
这就是因为其内部的实现机制不同导致的,,vector
是一块连续的内存,你才可以按下标直接访问,而list
内存并不连续,只能通过各个节点的指针按顺序从头访问。
但这些操作对于我们程序员来说,是没有必要的, 我们根本不需要知道内部原理,我们只想要遍历这个容器里面的数据。
所以为了统一遍历方法,就出现了迭代器
这个玩意, 无论标准库里面各个容器底层实现的机制是什么,我们访问的方法都一样:获取这个容器的开始迭代器,与结束迭代器,然后通过这个迭代器, 就能遍历完这个容器中的数据。
迭代器的使用方法和指针基本一样,也可以++
、 --
与*
或->
来取值。
但由于各个容器的底层实现机制不同,所以迭代器也分了类别。
比如单向列表,底层机制就决定了它只能前进,不能后退,所以就不存在--
这个操作。