STL实践与分析

--再谈迭代器【下】

三、反向迭代器【续：习题】

//P355 习题11.19
int main()
{
    vector
  
    iVec;
    for (vector
   
    ::size_type index = 0; index != 10; ++index) { iVec.push_back(index); } for (vector
    
     ::reverse_iterator r_iter = iVec.rbegin(); r_iter != iVec.rend(); ++r_iter) { cout << *r_iter << endl; } } 
    
   
  

//习题 11.20
int main()
{
    vector
  
    iVec;
    for (vector
   
    ::size_type index = 0; index != 10; ++index) { iVec.push_back(index); } for (vector
    
     ::iterator iter = iVec.end()-1;iter >= iVec.begin(); --iter) { cout << *iter << endl; } } 
    
   
  

//习题 11.21
int main()
{
    int ia[] = {0,1,2,3,4,5,6,0,7,8,9,0,10};
    vector
  
    iVec(ia,ia + sizeof(ia)/sizeof(*ia));

    vector
   
    ::reverse_iterator r_iter = find(iVec.rbegin(),iVec.rend(),0); if (r_iter != iVec.rend()) { cout << "element after the last 0 : " << *(-- r_iter) << endl; } else { cout << "Not found!" << endl; } } 
   
  

//习题11.22
int main()
{
    int ia[] = {0,1,2,3,4,5,6,0,7,8};
    vector
  
    iVec(ia,ia + sizeof(ia)/sizeof(*ia));

    list
   
     iList; vector
    
     ::reverse_iterator rbeg = iVec.rbegin(),rend; for (int i = 0; i != 3; ++i) ++ rbeg; rend = rbeg; for (int i = 0; i != 5; ++i) ++rend; copy(rbeg,rend,back_inserter(iList)); for (list
     
      ::iterator iter = iList.begin(); iter != iList.end(); ++iter) { cout << *iter << endl; } } 
     
    
   
  

四、const迭代器

算法要求用于指定范围的两个迭代器必须具有完全一样的类型。比如我们曾将使用的find_first_of算法：

    find_first_of(it, roster1.end(),roster2.begin(), roster2.end())

该函数调用的输入范围由it和调用roster1.end()返回的迭代器指定。算法要求用于指定范围的两个迭代器必须具有完全一样的类型。roster1.end()返回的迭代器依赖于roster1的类型。如果该容器是const对象,则返回的迭代器是const_iterator类型;否则,就是普通的iterator类型。在这个程序中,roster1不是 const对象,因而end返回的只是一个普通的迭代器。

如果我们将it定义为const_iterator,那么find_first_of的调用将无法编译。用来指定范围的两个迭代器的类型不相同。it是 const_iterator类型的对象,而rotser1.end()返回的则是一个iterator对象。

五、五种迭代器

可以根据算法要求它的迭代器的提供什么类型的操作，对算法分类：

1、输入迭代器

可用于读取容器中的元素，但是不保证能够支持容器的写入操作。输入迭代器必须至少提供下列操作：

1)相等和不等操作符(==,!=),比较两个迭代器。

2)前置和后置的自增运算(++),使迭代器向前递进指向下一个元素。

3)用于读取元素的解引用操作符(*),此操作符只能出现在赋值运算的右操作数上。

4)箭头操作符(->),这是(*it).member的同义语,也就是说,对迭代器进行解引用来获取其所关联的对象的成员。

输入迭代器只能顺序使用;一旦输入迭代器自增了,就无法再用它检查之前的元素。要求在这个层次上提供支持的泛型算法包括find和 accumulate。标准库istream_iterator类型输入迭代器。

2、输出迭代器

可以视为与输入迭代器功能互补的迭代器；输入迭代器可用于向容器写入元素，但不保证能支持读取容器的内容。输入迭代器要求：

1)前置和后置的自增运算(++),使迭代器向前递进指向下一个元素。

2)解引用操作符(*),引操作符只能出现在赋值运算的左操作数上。给解引用的输出迭代器赋值,将对该迭代器所指向的元素做写入操作。

输出迭代器可以要求每个迭代器的值必须正好写入一次。使用输出迭代器时,对于指定的迭代器值应该使用一次*运算,而且只能用一次。输出迭代器一般用作算法的第三个实参,标记起始写入的位置。例如,copy算法使用一个输出迭代器作为它的第三个实参,将输入范围内的元素复制到输出迭代器指定的目标位置。标准库ostream_iterator类型输出迭代器

3、前向迭代器

用于读写指定的容器。这类迭代器只会以一个方向遍历序列。前向迭代器支持输入迭代器和输出迭代器提供的所有操作,除此之外,还支持对同一个元素的多次读写。需要前向迭代器的泛型算法包括replace。

4、双向迭代器

从两个方向读写容器。出了提供前向迭代器的全部操作，还支持前置和后置的自减运算（--）。需要使用双向迭代器的泛型算法包括reverse。所有标准库容器提供的迭代器都至少达到双向迭代器的要求。

5、随机访问迭代器

提供在常量时间内访问容器任意位置的功能。不仅支持双向迭代器的所有功能,还支持下面的操作:

1)关系操作符<、<=、>和>=,比较两个迭代器的相对位置。

2)迭代器与整型数值n之间的加法和减法操作符+、+=、-和 -=,结果是迭代器在容器中向前(或退回)n个元素。

3)两个迭代器之间的减法操作符(--),得到两个迭代器间的距离。

4)下标操作符iter[n],这是*(iter+ n) 的同义词。

需要随机访问迭代器的泛型算法包括sort算法。vector、deque和string迭代器是随机访问迭代器,用作访问内置数组元素的指针也是随机访问迭代器。

除了输出迭代器,其他类别的迭代器形成了一个层次结构:需要低级类别迭代器的地方,可使用任意一种更高级的迭代器。

【总结】

map、set和 list类型提供双向迭代器,而string、vector和 deque容器上定义的迭代器都是随机访问迭代器都是随机访问迭代器,用作访问内置数组元素的指针也是随机访问迭代器。istream_iterator是输入迭代器,而ostream_iterator则是输出迭代器。

【关键概念：关联容器与算法】

尽管map和 set类型提供双