版本比较
标识
- 该行被添加。
- 该行被删除。
- 格式已经改变。
STL基本概念
- 容器:用于存放数据的类模板,比如vector, list, stack, queue等。
- 迭代器:用于存取容器中存放的元素,可以理解成指针,用于遍历和操作容器。使用迭代器可以实现以相同的风格访问和操作大部分的容器。
- 算法:用来操作容器中元素的函数模板,比如sort, unique等。
容器
用于存放元素,实例化时指定元素类型。如果存储的是一个对象,那么最好重载==
和<
运算,因为大部分算法都会用这两个运算符来进行相等判断和排序。
容器分为两大类:
顺序容器:可变长动态数组vector、双端队列deque、双向链表list。顺序容器的元素具有前后关系,可指定位置插入和删除。
关联容器:set、multiset、map、multimap。关联容器的元素是排序过的,不能指向插入位置。插入的元素会自动排序。默认情况下,关联容器中的元素按从小到大排序,使用运算符"<"进行比较。关联容器在查找时有很好的性能。
容器适配器:栈stack、队列queue、优先队列priority_queue。在上两类容器的基础上屏蔽一部分功能,突出或增加另一部分功能。
任何两个容器对象,只要类型相同,就可以用<、<=、>、>=、==、!=进行字典式的比较,它们的运行规则如下:
a == b: a和b中的元素个数相同,且对应元素相等,使用==运算符。
a < b: 类似于单词的字典序比较,使用<运算符。
a != b: 等价于!(a == b)。
a > b: 等价于 b < a。
a <= b:等价于 !(b < a)。
a >= b: 等价于!(a < b)。
所有的容器都有以下两个成员函数:
int size():返回容器对象中元素的个数。
bool empty():判断容器对象是否为空。
顺序容器和关联容器还有以下成员函数:
begin(): 返回指向容器第一个元素的迭代器。
end(): 返回指向容器最后一个元素后面的位置的迭代器。
rbegin(): 返回指向容器最后一个元素的反向迭代器。
rend(): 返回指向容器第一个元素前面的位置的迭代器。
erase(): 删除一个或几个元素。
clear(): 删除所有元素。
顺序容器还有以下常用成员函数:
front(): 返回容器中第一个元素的引用。
back(): 返回容器中最后一个元素的引用。
push_back(): 在容器末尾增加新的元素。
pop_back(): 删除容器末尾的元素。
insert(): 插入一个或多个元素。
迭代器
用于访问容器中的元素,有以下四种:
1. 正向迭代器,定义方法如下:
代码块 |
---|
容器类名::iterator 迭代器名; |
2. 常量正向迭代器,定义方法如下:
代码块 |
---|
容器类名::const_iterator 迭代器名; |
3. 反向迭代器,定义方法如下:
代码块 |
---|
容器类名::reverse_iterator 迭代器名; |
4. 常量反向迭代器,定义方法如下:
代码块 |
---|
容器类名::const_reverse_iterator 迭代器名; |
注意,容器适配器stack、queue和priority_queue没有迭代器,它们有自己的方法用于访问元素。
迭代器的功能分类
不同的容器的迭代器功能有强弱之分,这决定了容器是否支持某种STL算法,比如,排序算法sort需要通过迭代器支持随机访问功能,如果某种容器不支持随机访问,如list,那就不支持使用sort进行排序。
常用的迭代器按功能强弱分为输入、输出、正向、双向、随机访问5种:
正向迭代器:支持++p和p++、*p,两个迭代器可以赋值,可以用==和!=比较;
双向迭代器:支持正向迭代器的全部功能,还支持--p和p--;
随机访问迭代器:在双向迭代器的基础上,支持 p+i、p-i、p+=i、p-=i、p[i],还支持 <、>、<=、>=比较。
不同容器的迭代器功能:
容器 | 迭代器功能 |
---|---|
vector | 随机访问 |
deque | 随机访问 |
list | 双向 |
set/multiset | 双向 |
map/multimap | 双向 |
stack | 不支持 |
queue | 不支持 |
priority_queue | 不支持 |
迭代器的辅助函数
advance(p, n): 使迭代器向前或向后移动n个元素。
distance(p, q): 计算两个迭代器之间的距离,即p经过多少次++后和q相等,如果p本身就在q后面,则这个函数会陷入死循环。
iter_swap(p, q): 用于交换两个迭代器q、q指向的值,相当于通过指针交换元素内容。
算法
能在各种容器上通用的函数模板,通过迭代器来操作元素。
大部分算法需要通过迭代器提供一个操作区间,比如begin()~end()。
有的算法返回一个迭代器,比如find算法。
排序、查找等算法需要对元素进行比较,比较判断大小及是否相等。在STL中,比较大小通过"<"运算符来实现,和">"无关。而比较相等时,并不一定是使用"=="运行符,而是要根据情况来确定。如果是在未排序的区间上应用find进行查找,那么使用"=="运算符来判断相等。如果是在已经排序好的区间上进行查找、合并等操作(比如折半查找算法binary_search,关联容器自身的find成员函数),那么判断x=y的条件是x<y和y<x同时为假。如果一个类将"<"运算符重载为永远返回false,那么对于STL算法来说,这个类的所有对象都是相等的。
目录 |
---|