C++/STL/Iterator
iterator 是w:C++標準程式庫中的一個w:头文件,定义了C++ STL标准中的一些w:迭代器模板类 ,这些类都是以std::iterator为基类派生出来的。
迭代器模拟了C++中的指针,可以有++
运算,用*
(解引用算符,deference)或->
算符来访问容器中的元素。容器中元素如果改变了所用内存,也不影响绑定的迭代器指向正确的位置。因此,迭代器实际上更像是句柄(handler)。
STL的迭代器实现了设计模式中的“w:迭代器模式”。即顺序访问一个聚合中的元素,又不暴露聚合的实现细节。
迭代器支持以不同方法遍历聚合类型。例如,对一颗树数据类型,可以有前序、中序、后序遍历的迭代器。同一个聚合类型的对象上,可以同时有多个迭代器,各自保持不同的遍历状态。在不同的聚合类型上实现的迭代器具有标准的对外接口,这给STL中的算法使用迭代器提供了可能。熟练掌握这些迭代器的构造、用法,是基于STL的模板元编程的基础。
迭代器的分类与接口
[编辑]所有迭代器都应该实现自增算符:iter++
、++iter
- Input迭代器:
*iter
解引用后只能用作右值iter->member
解引用访问当前对象的成员数据iter=iter1
迭代器赋给另一个迭代器iter==iter1
迭代器相等比较iter!=iter1
迭代器不等比较
- Output迭代器:
*iter
解引用后只能用作左值iter=iter1
迭代器赋给另一个迭代器
- Forward迭代器:具有输入迭代器、输出迭代器的所有功能,且可以反复遍历操作。支持对同一个元素的多次读写。可复制前向迭代器来记录序列中的一个位置,以便将来返回此处。
- Bidirectional迭代器:是在前向迭代器的基础上,多了单步向后遍历的能力
--iter
iter--
- Random Access迭代器:在双向迭代器基础上,具有直接访问各数据元素的能力。随机迭代器增加了“迭代器算术运算”:
iter+=i
迭代器递增i位iter-=i
迭代器递减i位iter+i
加i位后的迭代器iter-i
减i位后的迭代器iter[i]
加i位后的迭代器的解引用iter<iter1
如果迭代器iter
的位置在iter1
前,返回true
,否则返回false
iter<=iter1
如果iter
的位置在iter1
的前面或同一位置时返回true
,否则返回false
iter>iter1
如果迭代器iter
的位置在iter1
后,返回true
,否则返回false
iter>=iter1
如果iter
的位置在iter1
的后面或同一位置时返回true
,否则返回false
在STL定义的容器中,string,vector与deque提供了随机访问迭代器,list、set、multiset、map、multimap提供了双向迭代器。
<iterator>中定义的类
[编辑]iterator_traits
[编辑]iterator_traits是一个类模板,用于定义一批成员数据类型,使得STL的算法可以用一致的界面来使用各种迭代器。下述类型定义中的Iterator是类模板参数:[1]
- difference_type Iterator::difference_type
- value_type Iterator::value_type
- pointer Iterator::pointer
- reference Iterator::reference
- iterator_category Iterator::iterator_category
5个作为iterator tag的空类
[编辑]input_iterator_tag, output_iterator_tag, forward_iterator_tag, bidirectional_iterator_tag, random_access_iterator_tag
均为空类。用于函数(模板)重载时的参数,以便STL算法据此判明迭代器所属类别做进一步优化。
iterator模板类
[编辑]在iterator模板类中,定义了5个成员类别:value_type,difference_type
pointer,reference, iterator_category
,用作所有其它迭代器的基类。
iterator adapters
[编辑]- reverse_iterator模板类,用来逆序遍历聚合,是STL各容器类的
rbegin、rend
成员函数返回的类型。其构造函数用正向迭代器作为参数,构造得到的迭代器指向参数迭代器所指位置的逆序的下一个元素。如果逆序迭代器r是用正序迭代器i构造得到,则&*r == &*(i-1)
为真。逆序迭代器的成员函数base(),返回指向当前定位的正序迭代器。 - move_iterator模板类,是一种输入迭代器。但与普通的迭代器不同,解引用(deference)操作得到的是右值,并按移动(move)赋值语义处理。
- make_move_iterator模板函数,用于方便地由一个容器构造出move_iterator。
- back_insert_iterator模板类,是一种输出迭代器,用于在容器对象的尾部追加新的元素。该迭代器被赋值时,调用了容器对象的push_back()成员函数。该迭代器的自增操作实际上为空操作。
- back_inserter模板函数,用于方便地由一个容器构造出back_insert_iterator
- front_insert_iterator模板类,是一种输出迭代器,用于在容器对象的头部插入新的元素。该迭代器被赋值时,调用了容器对象的push_front()成员函数。该迭代器的自增操作实际上为空操作。
- front_inserter模板函数,用于方便地由一个容器构造出front_insert_iterator
- insert_iterator模板类,是一种输出迭代器,用于在容器对象的指定位置插入新的元素。该迭代器被赋值时,调用了容器对象的insert()成员函数。该迭代器的自增操作实际上为空操作。
- insert_inserter模板函数,用于方便地由一个容器构造出insert_iterator
流迭代器
[编辑]任何已定义输入操作符(>>)的类型都可以定义istream_iterator。任何已定义输出操作符(<<)的类型也可定义ostream_iterator。在创建流迭代器时,必须指定迭代器所读写的对象类型。
- istream_iterator模板类,是一种单次遍历(single-pass)的输入迭代器。把一个std::basic_istream包装为一个输入流迭代器。从输入流迭代器通过自增操作来读取数据,实际上是调用了输入流的>>算符。输入流迭代器的默认构造函数返回一个指向流结束(end-of-stream)的迭代器。
- ostream_iterator模板类,是一种单次遍历(single-pass)的输出迭代器。把一个std::basic_ostream包装为一个输出流迭代器。对输出流迭代器赋值数据,实际上是调用了输出流的<<算符。对输出流迭代器自增,实际上是空操作。输出流迭代器的解引用操作返回该迭代器自身。
- istreambuf_iterator模板类,是一种单次遍历(single-pass)的输入迭代器。把一个std::basic_istreambuf包装为一个输入流迭代器。操作类似于istream_iterator,但效率更高。
- ostreambuf_iterator模板类,是一种单次遍历(single-pass)的输出迭代器。把一个std::basic_ostreambuf包装为一个输出流迭代器。操作类似于ostream_iterator,但效率更高。
迭代器操作函数
[编辑]- advance:把迭代器增量指定的步数。步数可以是负值。不检查迭代器是否超过序列尾部位置
end()
- distance:返回两个迭代器的距离值。两个迭代器必须指向同一个容器。如果不是随机迭代器,则第二个迭代器的位置必须与第一个迭代器的位置相同或在其后。
- iter_swap:交换两个迭代器所指的容器对象的元素值。迭代器类型可以不同,但其所指的值对象必须可以相互赋值。
- next:增量一个正向迭代器增量指定步数。此函数不适用reverse_iterator
- prev:把一个双向迭代器减量指定步数。
迭代器范围函数
[编辑]包括begin, cbegin, end, cend,rbegin,crbegin,rend, crend
等函数。返回聚合容器的开始位置、结束位置。
成员函数base()把逆向迭代器转化为对应的正向迭代器。
正向迭代器转化为逆向迭代器,只需要类型转化。
例子程序
[编辑]
#include <iostream>
#include <sstream>
#include <iterator>
#include <numeric>
int main()
{
std::istringstream str("0.1 0.2 0.3 0.4");
std::partial_sum(std::istream_iterator<double>(str),
std::istream_iterator<double>(),
std::ostream_iterator<double>(std::cout, " "));
}
运行后,输出结果:
0.1 0.3 0.6 1