STL定义了强大的、基于模板的、可复用的组件,实现了许多通用的数据结构及处理这些数据结构的算法。其中包含三个关键组件——容器(container,流行的模板数据结构)、迭代器(iterator)和算法(algorithm)。

组件描述
容器容器是用来管理某一类对象的集合。C++ 提供了各种不同类型的容器,比如 deque、list、vector、map 等。
迭代器迭代器用于遍历对象集合的元素。这些集合可能是容器,也可能是容器的子集。
算法算法作用于容器。它们提供了执行各种操作的方式,包括对容器内容执行初始化、排序、搜索和转换等操作。
一、容器简介

STL容器,可将其分为四类:序列容器、有序关联容器

序列容器:

标准库容器类描述
array固定大小,直接访问任意元素
deque从前部或后部进行快速插入和删除操作,直接访问任何元素
forward_list单链表,在任意位置快速插入和删除
list双向链表,在任意位置进行快速插入和删除操作
vector从后部进行快速插入和删除操作,直接访问任意元素

有序关联容器(键按顺序保存):

标准库容器类描述
set快速查找,无重复元素
multiset快速查找,可有重复元素
map一对一映射,无重复元素,基于键快速查找
multimap一对一映射,可有重复元素,基于键快速查找

无序关联容器:

标准库容器类描述
unordered_set快速查找,无重复元素
unordered_multiset快速查找,可有重复元素
unordered_map一对一映射,无重复元素,基于键快速查找
unordered_multimap一对一映射,可有重复元素,基于键快速查找

容器适配器:

标准库容器类描述
stack后进先出(LIFO)
queue先进先出(FIFO)
priority_queue优先级最高的元素先出

序列容器描述了线性的数据结构(也就是说,其中的元素在概念上” 排成一行"), 例如数组、向量和 链表。关联容器描述非线性的容器,它们通常可以快速锁定其中的元素。这种容器可以存储值的集合或 者键-值对。C++11中,关联容器中的键是不可变的(不能被修改)。序列容器和关联容器一起称为首类 容器。栈和队列都是在序列容器的基础上加以约束条件得到的,因此STL把stack和queue作为容器适配 器来实现,这样就可以使程序以一种约束方式来处理线性容器。类型string支持的功能跟线性容器一样, 但是它只能存储字符数据。

除此之外,有一些其他的容器种类被称为“ 近容器" (near con即ner): C类型的基于指针的数组用于维护标志位的 bitset, 以及用千进行高速向量运算的 valarray( 这个类对运算进行了优化,也不像首类容器那么复杂)。 这些类型称为“近容器”,是因为它们展现出来的功能与首类容器类似,但是不支持所有的首类容器的功能。

二、迭代器简介

迭代器在很多方面与指针类似,也是用于指向首类容器中的元素(还有一些其他用途,后面将会提到)。 迭代器存有它们所指的特定容器的状态信息,即迭代器对每种类型的容器都有一个实现。 有些迭代器的操作在不同容器间是统一的。 例如,*运算符间接引用一个迭代器,这样就可以使用它所指向的元素。++运算符使得迭代器指向容器中的下一个元素(和数组中指针递增后指向数组的下一个元素类似)。

STL 首类容器提供了成员函数 begin 和 end。函数 begin 返回一个指向容器中第一个元素的迭代器,函数 end 返回一个指向容器中最后一个元素的下一个元素(这个元素并不存在,常用于判断是否到达了容器的结束位仅)的迭代器。 如果迭代器 i 指向一个特定的元素,那么 ++i 指向这个元素的下一个元素。* i 指代的是i指向的元素。 从函数 end 中返回的迭代器只在相等或不等的比较中使用,来判断这个“移动的迭代器” (在这里指i)是否到达了容器的末端。

使用一个 iterator 对象来指向一个可以修改的容器元素,使用一个 const_iterator 对象来指向一个不能修改 的容器元素。

类型描述
随机访问迭代器(random access)在双向迭代湍基础上增加了直接访问容器中任意元素的功能, 即可以向前或 向后跳转任意个元素
双向迭代器(bidirectional)在前向迭代器基础上增加了向后移动的功能。支持多遍扫描算法
前向迭代器(forword)综合输入和输出迭代器的功能,并能保持它们在容器中的位置(作为状态信息),可以使用同一个迭代器两次遍历一个容器(称为多遍扫描算法)
输出迭代器(output)用于将元素写入容器。 输出迭代楛每次只能向前移动一个元索。 输出迭代器只支持一遍扫描算法,不能使用相同的输出迭代器两次遍历一个序列容器
输入迭代器(input)用于从容器读取元素。 输入迭代器每次只能向前移动一个元素。 输入迭代器只支持一遍扫描算法,不能使用相同的输入迭代器两次遍历一个序列容器

每种容器所支持的迭代器类型决定了这种容器是否可以在指定的 STL 算 法中使用。 支持随机访问迭代器的容器可用千所有的 STL 算法(除了那些需要改变容器大小的算法,这样的算法不能在数组和 array 对象中使用)。 指向 数组的指针可以代替迭代器用于几乎所有的 STL 算法中,包括那些要求随机访问迭代器的算法。 下表显示了每种 STL 容器所支持的迭代器类型。 注意, vector 、 deque 、 list 、 set 、 multiset 、 map 、 multimap( 首类容器)以及 string 和数组都可以使用迭代韶遍历。

容器支持的迭代器类型容器支持的迭代器类型
vector随机访问迭代器set双向迭代器
array随机访问迭代器multiset双向迭代器
deque随机访问迭代器map双向迭代器
list双向迭代器multimap双向迭代器
forword_list前向迭代器unordered_set双向迭代器
stack不支持迭代器unordered_multiset双向迭代器
queue不支持迭代器unordered_map双向迭代器
priority_queue不支持迭代器unordered_multimap双向迭代器

下表显示了在 STL容器的类定义中出现的儿种预定义的迭代器 typedef。不是每种 typedef 都出现在每个容器中。 我们使用常量版本的迭代器来访问只读容器或不应该被更改的非只读容器,使用反向迭 代器来以相反的方向访问容器。

为迭代器预先定义的typedef++的方向读写能力
iterator向前读/写
const_iterator向前
reverse_iterator向后读/写
const_reverse_iterator向后

下表显示了可作用在每种迭代器上的操作。 除了给出的对于所有迭代器都有的运算符,迭代器还必须提供默认构造函数、拷贝构造函数和拷贝赋值操作符。 前向迭代器支持++ 和所有的输入和输出迭 代器的功能。 双向迭代器支持–操作和前向迭代器的功能。 随机访问迭代器支持所有在表中给出的操作。 另外, 对于输入迭代器和输出迭代器,不能在保存迭代器之后再使用保存的值。

迭代器操作描述
适用所有迭代器的操作
++p前置自增迭代器
p++后置自增迭代器
p=p1将一个迭代器赋值给另一个迭代器
输入迭代器
*p间接引用一个迭代器
p->m使用迭代器读取元素m
p==p1比较两个迭代器是否相等
p!=p1比较两个迭代器是否不相等
输出迭代器
*p间接引用一个迭代器
p=p1把一个迭代器赋值给另一个
前向迭代器前向迭代器提供了输入和输出迭代器的所有功能
双向迭代器
–pq
p–后置自减迭代器
随机访问迭代器
p+=i迭代器p前进i个位置
p-=i迭代器p后退i个位置
p+i在迭代器p 的位置上前进i个位置
p-i在迭代器p的位置上后退i个位置
p-p1表达式的值是一个整数,它代表同一个容器中两个元素间的距离
p[i]返回与迭代器p的位置相距i的元素
p<p1若迭代器p小于p1(即容器中p在p1前)则返回 true, 否则返回 false
p<=p1若迭代器p小千或等于p1 (即容器中p 在p1前或位咒相同)则返回 true, 否则返回 false
p>p1若迭代器p 大于p1(即容器中p在p1后)则返回true, 否则返回false
p>=p1若迭代器p大于或等于p1(即容楛中p在p1后或位置相同)则返回 true, 否则返回 false
三、算法简介

STL提供了可以用于多种容器的算法,其中很多算法都是常用的。插入、删除、搜索、排序及其他一些对部分或全部序列容器和关联容器适用的算法。

STL包含了大约70个标准算法,表格中提供了这些算法的实例及概述。作用在容器元素上的算法只是间接地通过迭代器来实现。很多作用在序列元素上的算法通过一对迭代器定义:第一个迭代器指向这列元素的第一个,第二个迭代器指向最后一个元素之后的位置。 另外,还可以使用相似的方法创建自己的算法,这样它们就能和STL容器及迭代器一起使用了。

四、常用头文件

C++标准库分为很多部分,每个部分都有自己的头文件。头文件包含了形成标准库哥哥部分的相关函数的原型。头文件中还包含了各种各样的类类型和函数类型的定义,以及这些函数所需的常量。头文件可以“指示”编译器怎么处理标准库和用户编写的组件的接口问题。

C++标准库头文件说明
< iostream >包含C++标准输入和输出函数的原型。
< iomanip >包含格式化数据流的流操纵符的函数原型。
< cmath >包含数学库函数原型。
< cstdlib >包含数转换为文本、文本转换为数、内存分配、随机数及其他各种工具函数的函数原型。
< ctime >包含处理时间和日期的函数原型和类型。
< array >,< vector >,< list >,< forword_list >,< deque >,< queue >,< stack >,< map >,< unordered_map >,< unordered_set >,< set >,< bitset >这些头文件包含了实现C++标准库容器的类。 在程序执行期间 , 容器保存数据。
< ctype >包含测试字符特定属性(例如字符是否是数字字符或者标点符号)的函数原型和 用于将小写字母转换成大写字母 、 将大写字母转换成小写字母的函数原型。
< cstring >包含C风格字符串处理函数的函数原型。
< typeinfo >包含运行时类型识别(在执行时确定数据类型)的类。
< exception >,< stdexcept >这两个头文件包含用于异常处理的类。
< memory >包含被C++标准库用来向C++标准库容器分配内存的类和函数。
< fstream >包含执行由磁盘文件输入和向磁盘文件输出的函数的函数原型。
< string >包含来自C++标准库的 string类的定义。
< sstream >包含执行由内存字符串输人和向内存字符串输出的函数的函数原型。
< functional >包含C++标准库算法所用的类和函数。
< iterator >包含访问C++标准库容器中数据的类。
< algorithm >包含操作C++标准库容器中数据的函数。
< cassert >包含为辅助程序调试而添加诊断的宏。
< cfloat >包含系统的浮点数长度限制。
< climits >包含系统的整数长度限制。
< cstdio >包含C风格标准输入和输出库函数的函数原型。
< locale >包含流处理通常所用的类和函数,用来处理不同语言自然形式的数据(例如货币格式 、 排序字符串、字符表示 , 等等)。
< limits >包含为各计算机平台定义数字数据类型限制的类。
< utility >包含被许多C++标准库头文件所用的类和函数。
Logo

权威|前沿|技术|干货|国内首个API全生命周期开发者社区

更多推荐