C++模板实战6：迭代器

1 迭代器的类型：

输入迭代器 、前向迭代器、双向迭代器、跳转迭代器以及输出迭代器。这五种迭代器的限制条件从左至右越来越强。

2 输入迭代器需满足的条件：

3 前向迭代器满足的条件：

#include 
  
   
#include 
   
     template
    
      class stack_iterator { public: typedef typename Stack::value_type value_type; typedef typename Stack::reference reference; private: Stack &s; value_type *pos; public: stack_iterator(Stack &_s) : s(_s), pos(_s.size()   &_s.top() : 0) {} reference operator * () const {return *pos;} stack_iterator& operator ++ () { s.pop(); pos = s.size()   &s.top() : 0; return *this; } bool operator == (stack_iterator const &rh) const {return pos == rh.pos;} bool operator != (stack_iterator const &rh) const {return pos != rh.pos;} }; int main() { using namespace std; int numbers[] = {0, 1, 2, 3, 4}; typedef stack
     
       int_stack; int_stack s; for (int i = 0; i < 5; ++i) s.push(numbers[i]); stack_iterator
      
        a(s); stack_iterator
       
         b(s); cout<<*a<<" "<<*b<
        
         程序输出： 
         
 
         
4 4
 a == b
 3 4
 3 2
 ++a != ++b
 3 //虽然有输出，但是这是危险操作
 
         
 前向迭代器支持算法多次遍历数据，而输入迭代器在自增操作时可能会使其它迭代器失效。
 
         

 
 
         
4 双向迭代器，在前向迭代器基础上增加了后退操作如下：
 
         
 
         
 
          
           
          
 
           
 
            
--u;
 
            
将迭代器后退一位，只要存在迭代器s满足++s==u,则一定有―u==s
 
           
 
           
 
            
u--;
 
            
等价于{X tmp=u; --u; return tmp;}
 
           
 
          
 
         
 
         
 
         
 
         
 
         
5 跳转迭代器(随机迭代器)：在双向迭代器基础上增加了跳转指定位操作：
 
         
 
         
 
          
           
          
 
           
 
            
u+=n;
 
            
当n>0时相当于进行n次++u操作，当n<0时等价于进行n次―u操作
 
           
 
           
 
            
u-=n;
 
            
等价于u+=-n;
 
           
 
           
 
            
u+n; n+u;
 
            
等价于{X tmp=u; return tmp+=n;}
 
           
 
           
 
            
u-n;
 
            
等价于{X tmp=u; return tmp-=n;}
 
           
 
           
 
            
v-u;
 
            
得到两代器v和u间的距离，结果为一整数满足：v=u+n;
 
           
 
           
 
            
u[n];
 
            
等价于*(u+n)
 
           
 
           
 
            
u
              
             
            
等价于u-n<0
 
           
 
           
 
            
u>v;
 
            
等价于v
              
             
           
 
           
 
            
u<=v;
 
            
等价于!(u>v)
 
           
 
           
 
            
u>=v
 
            
等价于!(u
              
             
           
 
          
 
         
 
         
 
         
 
         
6 输出迭代器：与输入迭代器类似，输出迭代器移至下一位置后不能保证和之前相等的迭代器还有效，作用于输出迭代器的算法也只能遍历一次。例如：将一个缓冲区写入文件，当迭代器向前移动时，其它迭代器可能失效，因为数据已经改变了。
 
         
 
         
 
          
           
          
 
           
 
            
X(a); X u(a); X u=a;
 
            
可复制构造
 
           
 
           
 
            
*u=o;
 
            
去引用所得必须是一个对所指数据的左值引用
 
           
 
           
 
            
++u;
 
            
迭代器移至下一个位置
 
           
 
           
 
            
u++;
 
            
等价于{X tmp=u; ++u; return tmp;}
 
           
 
          
 
         
 
         
 
         
 
         
7 如果迭代器能满足输出迭代器的要求，则可称为是可写迭代器，即通过迭代器可以改变其所指数据的值*u=o;否则称为只读迭代器。vector、deque、array提供可写跳转迭代器，list提供可写双向迭代器，forward_list提供可写前向迭代器，set和multiset提供只读双向迭代器(key值不能改变),而map和multimap能修改value但是不能修改key所以迭代器类型不易分类，hash和二叉搜索树也如此。
 
         

 
 
         
8 迭代器属性类模板：迭代器出了提供必要的操作外，还需要包含足够的信息描述其本身的属性。标准模板类std::iterator_traits
          
           为算法提取迭代器的属性。标准规定了迭代器的五种属性：
          
 
         
1） difference_type迭代器差值类型
 
         
2） valule_type迭代器所指数据类型
 
         
3） pointer数据指针类型
 
         
4） reference数据引用类型
 
         
5） iterator_category迭代器所属类型
 
         
 利用iterator_category算法作者可以根据迭代器类型采取不同的策略，实例如下:模仿std::advance(i,n)
 
         





 
         
// 适用于前向迭代器的advance函数实现，n次加1操作
template
          
           
void advance_impl(I &i,
                  typename std::iterator_traits
           ::difference_type n, std::forward_iterator_tag) {for (; n > 0; --n) ++i;} // 适用于跳转迭代器的advance函数实现，直接用i += n template
            
              void advance_impl(I &i, typename std::iterator_traits
             ::difference_type n, std::random_access_iterator_tag) {i += n;} template
              
                void advance(I &i, typename I::difference_type n) { // 以iterator_category()为哑参数指导编译器选择适当的重载实现，不参与任何实现工作，只用于重载识别，不需要参数名 advance_impl(i, n, typename std::iterator_traits
               ::iterator_category()); }
              
            
          
          同理可以实现std::distance. 
 

 
 
9 标准定义的迭代器基类模板，实例如下：
 
 
namespace std{
    template
             
              
    struct iterator{
        using iterator_category=Category;
        using value_type=Value;
        using difference_type=Distance;
        using pointer=Pointer;
        using reference=Reference;
    };
}

template
              
                struct myIterator: public std::iterator
               
                //继承标准的迭代器类可以实现简化自己的迭代器代码，并且无需再为指针之类实现自定义迭代器模板特例 { //... };
               
              
             
 
 

 
 10 反向迭代器模板类reverse_iterator
            
             可以构造一个前进方向与原迭代器完全相反的迭代器，其自增操作是实际为后退操作，这在一些反向访问序列算法中非常有用，例如通过向find(i,j,v)传入反向迭代器从而可以找到元素v在序列[i,j)中最后一次出现的位置。值得注意的是：反向迭代器的解引用是其所指位置后退一位的数据引用，这是为了保证左开右闭区间的使用习惯。实例如下： 
             
 
             
#include 
              
               
#include 
               
                 #include 
                
                  #include 
                 
                   void print(char c) {std::cout << c;} int main() { char array[] = "Madam I'm Adam"; typedef std::reverse_iterator
                  
                    backward_iterator; using namespace std; for_each(backward_iterator(array + strlen(array)),backward_iterator(array),print);//第一个迭代器指向的是'\0'但是其解引用是'm'。第二个迭代器指向'a'但是其解引用是'M' cout << endl; return 0; }
                  
                 
                
               
              
             
 11 插入迭代器：在指定位置前插入元素。三种插入模板类迭代器以容器为模板参数： 
             
 
             
1） back_insert_iterator
              
                在容器末端插入数据，容器支持push_back操作
              
 
             
2） front_insert_iterator
              
                在容器前端插入数据，容器支持push_front操作
              
 
             
3） insert_iterator
              
                在容器指定位置插入数据，容器支持insert(i,v)操作
              
 
             
 标准实现了三个模板函数用于插入：
 
             
1) back_inserter(c)
 
             
2) front_inserter(c)
 
             
3) inserter(c,i)
 
             
 实例如下：
 
             
 
             
void foo() {
    using namespace std;
    int array[] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
    list
              
                il;
    // 将array[5]到array[9]插入到il末尾
    copy(array + 5, array + 10, back_inserter(il));
    
    // 将array[4]到array[0]插入到il前端，为保证数据顺序不变，需要用到
    // reverse_iterator
    typedef reverse_iterator
               
                 array_reverse_iterator; copy(array_reverse_iterator(array + 5),array_reverse_iterator(array),front_inserter(il)); }
               
              
             
 11 流迭代器：可以直接作用于内存外的数据，如文件/标准输入输出。迭代器器只符合输入迭代器或输出迭代器的要求，因此只能为算法提供单次遍历。 
             
 
             
 标准定义的流迭代器类模板：
 
             
1） istream_iterator 输入流迭代器
 
             
2） ostream_iterator输出流迭代器
 
             
3） istreambuf_iterator 输出缓冲区迭代器
 
             
4） ostreambuf_iterator 输出缓冲区迭代器
 
             
 istream_iterator和ostream_iterator基于">>"操作符提取/输出数据，而istreambuf_iterator和ostreambuf_iterator基于底层面向字节的函数实现数据提取/输出。
 
             
 实例如下：
 
             
 
             
#include
              
               
#include
               
                 #include
                
                  #include
                 
                   using namespace std; int main(){ using namespace std; istringstream s("The quick brown fox jumps over the lazy dog."); using char_istream_iterator=istream_iterator
                  
                   ; //typedef istreambuf_iterator
                   
                     char_istream_iterator; cout << count(char_istream_iterator(s),char_istream_iterator(),'o')<
                    
                      统计'o'在字符串中出现的次数，由于istream_buf基于">>"操作符实现，所以不能统计空格出现的次数。注释的istreambuf_iterator基于sgetc()面向字符处理函数能统计空格出现的次数。 
                     
 
                     
 输出流迭代器不支持比较相等，ostream_iterator利用"<<"操作符实现，其输出流在构造时指定，还需接收一个分隔符作为参数，而ostreambuf_iterator基于sputc()面向字符输出，不支持分隔符。当为标准库容器或其它自定义类重载">>"或"<<"用于流迭代器时，一定要把该重载操作符写在std命名空间内，因为流迭代器在std内，重载操作符也应该在std内。实例如下：
 
                     
 
                     
#include 
                      
                       
#include 
                       
                         #include 
                        
                       
                      
程序输出： 
                     
 
                     
(0, a)
 (1, b)
 (2, c)