1. 使用迭代器的原因
下面用两个遍历函数引出使用迭代器的原因。实现细节上来看,两个 find 函数算法不同,但广义上来看,他们的目的都是匹配值相同的一项。
1 | // 给定一个double数组, 返回值相同的一项 |
- 迭代器要求:为不同的类设计迭代器,并为迭代器定义p++、++p、p=q
- 容器要求:让数组和链表拥有超尾元素,迭代器到达超尾元素后结束搜索
1 | typedef double* iterator; |
2. 迭代器类型
不同算法对迭代器的要求不同。查找算法只需要读取数据;而排序算法需要读写数据和随机访问,例如 iter 是一个迭代器,需要重新定义 + 运算符来实现 iter + 10 访问元素
- 输入迭代器:输入是从程序的角度来说的,迭代器向程序输入,因此需要迭代器可以解引用使程序能读取迭代器中的值,但不需要修改迭代器中的值。注意迭代器是单项迭代器,只能递增不能递减,迭代器递增后也不能保证先前的值仍可以被解引用。
- 输出迭代器:输出是从程序输出到迭代器,因此需要迭代器可以被写入。注意输出迭代器只能写入却不能读取,这就类似于 cout 可以向屏幕输出但不能读取屏幕内容。
- 正向迭代器:正向迭代器与输入和输出迭代器相同,只能使用++运算符遍历容器。但正向迭代器递增后,仍然可以对前面迭代器的值解引用,并且支持输入和输出
- 双向迭代器:同时支持++和–
- 随机访问迭代器:允许从一个元素直接跳到另一个元素称为随机访问,它具有双向迭代器的所有特性
3. 迭代器层次结构
3.1 将指针用作迭代器
迭代器是广义指针,而指针满足迭代器的所有要求。迭代器是STL算法的接口,而指针就是迭代器,因此STL算法可以直接使用最普通的指针来进行一些操作,下面给出一个例子
1 | const int SIZE = 100; |
STL sort() 函数接收容器第一个指针和超尾指针作为参数,即&Receipts[0] 和 &Receipts[SIZE],也可以是下面的写法。因为c++将超尾概念用于数组,所以我们可以将STL算法用于常规数组
1 | sort(Receipts, Receipts + SIZE); |
4. 容器类型
4.1 序列容器
4.1.1 vector
vector 是数组的一种类表示,它提供了自动内存管理功能,容量随着元素添加和删除而增大和缩小。vector 是可翻转容器(reversible container),rbegin() 和 rend() 返回的是反转后的第一个元素的迭代器和反转后的超尾迭代器
1 | for_each(dice.begin(), dice.end(), Show); // 顺序显示 |
4.1.2 deque
deque 是双端队列,实现类似于 vector 容器,支持随机访问。与 vector 的主要区别是它在队列开始位置的插入和删除时间是固定的,而非线性
4.1.3 list和forward_list(C++11)
list 是双向链表,C++11 中实现了单链表 forward_list
4.1.4 queue和priority_queue
queue 是一个适配器类,实现了队列的功能(先进先出),底层实现默认为 deque
priority_queue是另一个适配器类,支持的操作与queue相同,但它自动将最大的元素移动到队首,默认底层类为 vector
4.1.5 stack
stack 是一个适配器类,默认底层类为vector,实现了栈的功能(后进先出)
4.1.6 array(C++11)
array不是STL容器,因为它的长度是固定的,但它定义了 operator[] () 和 at(),许多STL算法适用于array
4.2 关联容器
4.2.1 set和multiset
set 是关联集合,可以反转和自动排序,且键是唯一的,默认情况下使用模板less<>来对键进行排序
1 | set<string> A; |
排序方法决定了插入的位置,所以只需要提供插入的信息即可
1 | int main(){ |
4.2.2 map和mutimap
map和set最大的区别是,map的键和值类型不同,默认情况下也使用less进行排序
1 | map<int, string> code; |
下面是一个mutimap的例子,codes.equal_range(213) 返回一个键值对,包含两个迭代器,包含了键为213的所有值的信息,可以通过遍历这个迭代器得到
1 | int main(){ |
4.3 无序关联容器
无序关联容器与关联容器相同,将值和键关联起来,但关联容器底层通过树实现,无序关联容器通过哈希表实现,目的是提高添加和删除元素的速度以及查找算法的效率,它们是unordered_set、unordered_multiset、unordered_map、unordered_multimap