跳转到内容

C++/STL/Iterator

维基教科书,自由的教学读本
< C++

iteratorw: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

参考文献

[编辑]
  1. Iterator library