Yanyg - Software Engineer
Archives | Index | TAGS | Github | About Me

STL源码分析之一：迭代器详解

2007-09-26发布于CSDN： http://blog.csdn.net/cppgp/article/details/1802227

本系列文章将会尽可能的剖析STL实现细节。本文假定读者对象是热爱GP编程、希望探究STL实现的程序员。本系列不适合STL初学者。

[本篇分析STL迭代器,在文章最后给出一个拥有迭代器和常用操作的仿STL实现的单链表源码]

1.概述 《Design Patterns》中iterator模式的定义如下：提供一种方法，使之能够依序寻访某个 聚合物(容器)所含的各个元素。

在STL中，迭代器是一种行为类似指针的对象，可透过与一般指针一致的接口来完成自己的 工作(事实上除了随机迭代器以外，其他迭代器只有比指针更少的操作，但是所有迭代器都有 提领操作(*iterator)、成员访问操作(iterator->member)、前置递增操作(\+\+iterator)、 后置 递增操作(iterator++)，是容器和算法的粘合剂。同时透过迭代器，向操作者隐藏了具体数据结构 和实现细节。例如，我们要遍历某个容器，可以不必关心其采用的数据结构是数组、链表或者某种 图结构，只需要定义一个迭代器，然后按照如下操作： 

for( iterator iter = container.begin() ;  container.end() != iter ; ++iter )
 <process>(*iter);

其中container是任意容器。<process>是准备遍历施加的操作。 按照迭代器可以施行的操作将其分为5种，分别是

  1. 输入迭代器(input iterator);
  2. 输出迭代器(output iterator);
  3. 前向迭代器(forward iterator);
  4. 双向迭代器(bidirectional iterator);
  5. 随机迭代器(random access iterator)。

当不同的迭代器作为参数传递给对应算法时，算法会根据迭代器特性提供最大优化。例如，STL中的distance()对于不同的迭代器，算法不同，分别如下： 

template <class _InputIterator, class _Distance>
inline void __distance
(_InputIterator __first,
 _InputIterator __last,
 _Distance& __n,
 input_iterator_tag)
{
  while (__first != __last) { ++__first; ++__n; }
}

template <class _RandomAccessIterator, class _Distance>
inline void __distance
(_RandomAccessIterator __first,
 _RandomAccessIterator __last,
 _Distance& __n,
 random_access_iterator_tag)
{
  __n += __last - __first;
}
template <class _InputIterator, class _Distance>
inline void distance
(_InputIterator __first,
 _InputIterator __last,
 _Distance& __n)
{
  __distance(__first, __last, __n, iterator_category(__first));
}

2.STL中迭代器层次关系 

struct output_iterator_tag{}
struct input_iterator_tag{}
struct forward_iterator_tag : public input_iterator_tag {};
struct bidirectional_iterator_tag : public forward_iterator_tag{}
struct random_accessl_iterator_tag : public bidirectional_iterator_tag{}

3.使用 OutIt：只能通过存储来间接地拥有一个值V。在输出迭代器中存储一个值后必须将其递增。例如： *X++ = V; *X = V,++X; *X = V,X++; InIt：如果其值不为end-of-sequence，可以间接的存取它所拥有的值。例如： V = *X; V = *X++; 一旦对其递增，其所有其他拷贝不保证能完成比较、取值、递增等操作。 FwdIt：假设X是FwdIt，如果*X可变，就可替换InIt。可以同时拥有一个前向迭代器的多份拷贝，它们中的每一份都可以各自间接取值，或者各自进行递增。 BidIt：可以用它来替换FwdIt，同时可以进行诸如–X和X–相关的递减操作。 RanIt：除了有BidIt相关操作之外，可以进行任何指针算术运算。

* 五类迭代器的详述 * 1.输出迭代器(output iterator) 1).struct output_iterator_tag{} 用来读取有序序列中的元素。既可用来表示将值存储到对象中，也可表示从一个对象中获得它所保存的值。如果需要创建一个新的值序列并且以有序的方式来产生值，可用如下循环语句： for( ; <not done> ; ++next ) *next = <whatever>; 或者： while( <not done> ) { *next++ = <whatever>; } 其中，next表示一个迭代器类型为X的对象；<not done>是一个检测循环是否应该终止的谓词(predicate)；<whatever>是一个表达式，类型为序列中元素的类型T或者可以转化为T的类型。

2).所拥有的操作： a).提领操作 (*a，作为左值才有效) b).前置递增操作 (a) c).后置递增操作 (a) d).复制构造函数(copy constructor) e).析构函数(destructor) f).赋值操作符(assignment operator)

3).限制条件 必须保证输出迭代器在存储每一个元素后得以增加； 必须保证输出迭代器在两次存储的间隔内增加的次数不得超过一次； 输入迭代器只在类似 1) 中给出的循环语句中使用。

4).操作说明： 对于输出迭代器，只可以向目的序列一个一个的写入，只能一个一个地赋新值，而且不能对同一序列进行两次遍历。如果在相同位置上进行第二次写入，不能确保这次写入的值会3覆盖前一次写入的值。operator*只有作为左值才有效。Output Iterator无须比较(comparison)操作，无法判断迭代器是否有效，或写入是否成功。使用者唯一可做的就是写入写入再写入。纯粹Output Iterator的一个典型例子就是“将元素写至标准输出装置”，另一个就是Inserters，以后详述。其所有操作如下： *iter = value; //将数值写入迭代器所指位置 iter; //向前步进（传回新位置） iter; //向前步进（传回旧位置） TYPE(iter) //复制迭代器（copy构造函数）

5).特性说明 [参数说明]X:迭代器类型，a的类型为X&，T是元素类型，t的类型是T

表达式 结果的类型 含义 注释

X(a) X 产生a的一个拷贝 析构函数是可见的 *X(a)=t与*a=t的作用相同 X u(a) X& u是a的一个拷贝 X u=a

r=a X& a赋值给r 结果*r=t和*a=t作用相同

*a=t void 在序列中存储新元素

++r X& 指向下一个元素 &r = &++r，r不是end-of-sequence

r++ const X& 指向下一个元素 &r = &r++ {X temp = *r; ++r; return temp;} *r++=t void

2.输入迭代器(input interator)

1).struct input_iterator_tag{} 用来产生新的序列，可顺序存取已有值或对已有序列进行排序。可用于如下循环语句： for( p = first ; p != last ; ++p ) { <process>(*)p } 其中p、first、last都是迭代器类型X的对象，<process>是一个能接受T类型为参数的函数 2).所拥有的操作： a).提领操作 (*a) b).成员访问操作 (a->member) c).前置递增操作 (a) d).后置递增操作 (a) e).复制构造函数(copy constructor) f).析构函数(destructor) g).赋值操作符(assignment operator)

3).限制条件 两个迭代器中只有一个具有end-of-sequence值时输入迭代器之间的比较才一定有意义 输入迭代器只在类似 1) 中给出的循环语句中使用。

4).操作说明： 对于输入迭代器，只能一次一个向前读元素，按此顺序一个个传回元素值，而且只能读一次。如果复制Input Iterator，并使原Input Iterator和新产生的Input Iterator都向前读取，可能会遍历到不同值。纯粹Input Iterator的一个典型例子就是从“标准输入装置读取数据”的迭代器（比如从键盘）。两个Input Iterator占用同一个位置则其相等，但是其传回值不一定相等。其所有操作如下： *iter; //读取实际元素，提领操作 iter->member; //读取实际元素的成员（果T是结构化类型），成员访问操作 iter; //向前步进（传回新位置），前置递增操作 iter; //向前步进（传回旧位置），后置递增操作 iter1 = iter2; //赋值操作 iter1 = iter2; //判断两个迭代器是否相等，a和b在同一值域内 iter1 ! iter2; //判断两个迭代器是否不等，a和b在同一值域内 TYPE(iter) //复制迭代器（copy构造函数）

说明：应该尽量使用前置式递增

5).特性说明 [参数说明]X:迭代器类型，a的类型为X&，T是元素类型，t的类型是T，m是T的成员，m的类型是M

表达式 结果的类型 含义 注释

X(a) X 产生a的一个拷贝 析构函数是可见的 *X(a)与*a的作用相同 X u(a) X& u是a的一个拷贝 创建完成后u等于a X u=a

r=a X& a赋值给r 结果r=a

a == b bool 相等比较 a和b在同一值域内

a != b bool !(a==b) 同上

*a T 从序列中取元素 a不是end-of-sequence

a->m M (*a).m T的成员m

++r X& 指向下一个元素 &r = &++r

r++ void 指向下一个元素 &r = &r++ {X temp = *r; ++r; return temp;}

3.前向迭代器(forward iterator) 1).struct forward_iterator_tag{} 可以比较两个前向迭代器是否相等，同时他们可以都为或都不为end-of-sequence，但是如前，这两个迭代器必须处于同一个值域。同时可以用一个前向迭代器的多个有效拷贝值来指向当前序列中的任意位置。前向迭代器不能回退，不能直接(随机)存取任意元素。可以简单想象它为一个单向链表中元素的指针。

2).所拥有的操作： a).提领操作 b).成员操作 c).前置递增操作 (a) d).后置递增操作 (a) e).默认构造函数 d).复制构造函数(copy constructor) e).析构函数(destructor) f).赋值操作符(assignment operator)

3).操作说明： Forward Iterator 是 Output Iterator 和 Input Iterator的结合，具有 Input Iterator 的全部功能和 Output Iterator的大部分功能，事实上在STL中，forward iterator 派生自 input iterator。其所有操作如下： *iter; //存取实际元素 iter->member; //存取实际元素的成员，如果有的话 iter; //向前步进（传回新位置） iter; //向前步进（传回旧位置） iter1 = iter2; //判断两个迭代器是否相等 iter1 ! iter2; //判断两个迭代器是否不等 TYPE(); //产生迭代器(default构造函数) TYPE(iter); //复制迭代器（copy构造函数） iter1 = iter2; //赋值

Forward Iterator有Output Iterator的大部分功能而非全部功能的原因是某些对Output Iterator有效的程序对Forward Iterator可能无效。有以下两点： (1)面对Output Iterator无须检查其是否抵达序列尾端，便可直接写入数据。事实上由于Output Iterator不提供比较操作，因此无法将Output Iterator与end-of-sequence相比较。以下循环是正确的： while(true) { *pos = foo(); ++pos; }

(2)对于Forward Iterator，必须在提领数据之前确保其有效，因此上述循环对Forward Iterator是错误的。对于Forward Iterator上述循环应改为： while( pos != coll.end() ) { *pos = foo(); ++pos; } 而同时，该循环不适用于Output Iterator，因为Output Iterator没有operator!=

4).特性说明 [参数说明]注释：X是迭代器类型，a和b的类型为X；r和s的类型为X&；T是元素类型，t的类型为T，m是T的成员，m的类型是M。

表达式 结果的类型 含义 注释 X() X 产生一个默认值 析构函数是可见的，值可以是end-of-sequence

X u X& u具有默认值 创建完成后 u == a X u =a

X(a) X 产生a的一个拷贝 析构函数是可见的，*X(a)与*a的作用相同

X u(a) X& u是a的一个拷贝 创建完成后 u == a X u =a

r = a X& a赋值给r 结果 r == a

a = b bool 相等比较 a和b在同一值域内 a ! b bool !( a == b ) 　

*a T& 从序列中存取元素 a不是end-of-sequence，a = b <==> *a = *b

*a = t T& 在元素中存储 a不是end-of-sequence，a是可变的

a -> m M (*a).m T有成员m

++r X& 指向下一个元素 &r = &++r，r不是end-of-sequence，r = s <==> ++r = ++s

r++ const X& {X tmp(r);++r;return tmp;} 　 *r++ void {T tmp = *r;++r;return tmp;}

4.双向迭代器(bidirectional iterator) 1).struct bidirectional_iterator_tag{} 具有前向迭代器的所有特性，另外还具有逆向移动特性。可以简单想象它为一个双向链表中元素的指针。

2).所拥有的操作： a).前向迭代器的所有操作 b).前置递减操作 (–a) c).后置递减操作 (a–)

3).操作说明： Forward Iterator的所有操作均可用，新增加的操作如下： –iter; //只向前一个元素，传回新位置 iter–; //只向前一个元素，传回旧位置

4).特性说明 [参数说明]注释：X是迭代器类型，a和b的类型为X；r和s的类型为X&；T是元素类型，t的类型为T，m是T的成员，m的类型是M。 有Forward Iterator的所有特性，新加特性如下：

表达式 结果的类型 含义 注释 –r X& 指向前一个元素 &r = &–r，r不是end-of-sequence，r = s <==> --r = –s r– const X& {X tmp(r);++r;return tmp;} 　 *r++ void {T tmp = *r;++r;return tmp;}

5.随机迭代器(random access iterator) 1).struct random_access_iterator_tag{} 具有双向迭代器的所有特性，另外还具有支持加减、大小判断、迭代器在序列中的顺序、下标操作迭代器特性。可以简单想象它为一个数组中元素的指针。

2).所拥有的操作： a).双向迭代器的所有操作 b).加减操作(a+=n;a-=n;a+n;a-n;a-b;b-a) c).大小判断(a>b;a<b;a>=b;a<=b) d).下标操作(a[n])

3).操作说明： Bidirectional Iterator的所有操作均可用，新增加的操作如下： iter1 < iter2; iter1 <= iter2; iter += n; iter -= n; iter + n; n + iter; iter - n; n - iter; iter1 - iter2; iter[n]

4).特性说明 [参数说明]注释：X是迭代器类型，a和b的类型为X；r和s的类型为X&；T是元素类型，t的类型为T；Dist是X的差距类型 有Forward Iterator的所有特性，新加特性如下：

表达式 结果的类型 含义 注释 a < b bool 从a可以到达b a和b在同一值域中 a > b bool b < a 　 a <= b bool !(b < a) 　 a >= b bool !(a < b) 　 r += n X& {Dist m = n;while(0<m)–m,++r;while(m<0)++m,–r;return r;}

a + n X {X tmp(a);tmp += n;return tmp;} n + a

r -= n X& r += -n; 　 a - n X a + (-n) 　 b - a Dist {Dist m = 0;while(a<b)++a,++m;while(b<a)++b;–m;return m;} 　 a[n] T的任意类型 *(a+n) 

#include <new>
//这个是链表基本结构,里面不存储任何东西,纯粹为了实现算法
struct SListBaseNode
{
  SListBaseNode* s_Next;
};

//这个函数在prevNode节点后面插入新节点 newNode
inline SListBaseNode* InsertAfterNode( SListBaseNode* prevNode , SListBaseNode* newNode )
{
  newNode->s_Next = prevNode->s_Next;    //newNode的下一节点为prevNode的下一节点
  prevNode->s_Next = newNode;        //prevNode的下一节点为newNode
  return newNode;                //返回newNode,实现串接算法,详细见下面的[注释1]
}

/*
  [注释1] : 这类算法返回的原因是为了实现链接调用,例如:
  InsertAfterNode( InsertAfterNode(front,newNode1) , newNode2 );
  再比如c库函数strcpy等都是这个原因,例如:
  char buff[128];
  int len = strlen( strcpy(buff,"yanyg") );
*/

//这个函数得到节点node的前一节点
inline SListBaseNode* GetPrevious( SListBaseNode* front , const SListBaseNode* node )
{
  for ( ; front && front->s_Next != node ; front = front->s_Next );
  return front;
}

//这个函数是前一个函数的const版本
inline const SListBaseNode* GetPrevious( const SListBaseNode* front , const SListBaseNode* node )
{
  for ( ; front && front->s_Next != node ; front = front->s_Next );
  return front;
}

//这个函数逆序链表,并返回最后一个节点
inline SListBaseNode* Reverse( SListBaseNode* node )
{
  SListBaseNode* result = node;

  node = node->s_Next;
  result->s_Next = 0;

  while ( node )
    {
      SListBaseNode* next = node->s_Next;
      node->s_Next = result;
      result = node;
      node = next;
    }

  return result;
}

//计算node之后的节点个数
inline size_t ListSize( SListBaseNode* node )
{
  size_t result = 0;

  for ( ; 0 != node ; node = node->s_Next , ++result );

  return result;
}

//这个派生是链表具体存储的对象
template<typename T>
struct SListNode : public SListBaseNode
{
  SListNode():s_Next(0){}
  SListNode( const T& t ):s_Data(t){ s_Next = 0; }
  T s_Data;
};

/************************************************************************
 *    这里实现一个简单的迭代器
 *    如果想和stl完美融合
 *    那么需要从stl迭代器萃取某些特征型别信息
 *    型别萃取不是本篇重点,不再详细论述
 *    单链表是一个forward_iterator
 *    因此只实现 iter++/++iter/*iter/iter->member/==/!=六种操作
 ************************************************************************/
template<class T , class Ref , class Ptr >
struct SList_Iterator
{
  typedef SList_Iterator<T,T&,T*> iterator;
  typedef SList_Iterator<T,const T&,const T*> const_iterator;
  typedef SList_Iterator<T,Ref,Ptr> self;

  typedef T value_type;
  typedef Ptr pointer;
  typedef Ref reference;
  typedef SListNode<T> list_node;

  SList_Iterator( list_node* x ):s_Node(x){}
  SList_Iterator():s_Node(0){}
  SList_Iterator( const_iterator& x ):s_Node(x.s_Node){}

  reference operator*() const { return ((list_node*)s_Node)->s_Data; }
  pointer operator->() const { return &(operator*()); }

  self& operator++()
  {
    s_Node = s_Node->s_Next;
    return *this;
  }

  const self operator++(int)
  {
    self tmp(*this);
    s_Node = s_Node->s_Next;

    return tmp;
  }

  bool operator==( const SList_Iterator& x ){ return s_Node == x.s_Node; }
  bool operator!=( const SList_Iterator& x ){ return s_Node != x.s_Node; }

  SListBaseNode* s_Node;
};

//单链表类实现
template < class T >
class SList
{
public:
  typedef T value_type;
  typedef value_type* pointer;
  typedef const value_type* const_pointer;
  typedef value_type& reference;
  typedef const value_type& const_reference;
  typedef size_t size_type;
  typedef ptrdiff_t difference_type;

  typedef SList_Iterator< T , T& , T* > iterator;
  typedef SList_Iterator< T, const T&, const T* > const_iterator;


private:
  typedef SListNode<T> list_node;
  typedef SListBaseNode list_node_base;

  list_node_base m_Head;

public:
  SList() { m_Head.s_Next = 0; }    //初始化
  ~SList(){ clear(); }        //删除内存

  iterator begin() { return iterator( (list_node*)m_Head.s_Next ); }
  iterator end() { return iterator(0); }
  const_iterator begin() const { return const_iterator( (list_node*)m_Head.s_Next ); }
  const_iterator end() const { return const_iterator(0); }
  size_t size() const { return ListSize(m_Head.s_Next); }
  size_t max_size() const { return size_t(-1); }
  bool empty() const { return 0 == m_Head.s_Next; }

  reference front() { return ((list_node*)m_Head.s_Next)->s_Data; }
  const_reference front() const { return ((list_node*)m_Head.s_Next)->s_Data; }

  void push_front( const value_type& t ) { InsertAfterNode(&m_Head,new list_node(t)); }
  void pop_front() { list_node* node = (list_node*)(m_Head.s_Next); m_Head.s_Next = node->s_Next; delete (list_node*)node; }

  iterator previous( const_iterator pos ) { return iterator(GetPrevious(m_Head.s_Next,pos)); }
  const_iterator previous( const_iterator pos ) const { return const_iterator(GetPrevious(m_Head.s_Next,pos)); }

  iterator insert( iterator pos, const value_type& x ){ return iterator((list_node*)InsertAfterNode( GetPrevious(&m_Head,pos.s_Node),new list_node(x))); }
  iterator insert_after( iterator pos, const value_type& x ){ return iterator( (list_node*)InsertAfterNode(pos.s_Node,new list_node(x) ) ); }
  void erase( iterator pos ){ SListBaseNode* temp = GetPrevious(&m_Head,pos.s_Node); temp->s_Next = pos.s_Node->s_Next; delete (list_node*)pos.s_Node; }
  void erase_after( iterator pos ) { iterator tmp(pos); ++pos; tmp.s_Node->s_Next = pos.s_Node->s_Next; delete (list_node*)pos.s_Node; }

  void reverse(){ m_Head.s_Next = Reverse(m_Head.s_Next); }

  void clear(){ list_node_base* node=m_Head.s_Next; for(;0!=node;node=m_Head.s_Next)m_Head.s_Next=node->s_Next,delete (list_node*)node; }
};
2012-2020 Copyright© YANYG
Powered by Emacs Orgmode