C++:Iterator
Iterator是序列概念的体现，Iterator指向值而不是值本身，因而也就具有两方面的特性，一方面Iterator可以指代值，另一方面具有序列指示特性，可以在序列中移动，指针和数组序号都具有这样的特性。Iterator(迭代器)可以说是std的灵魂所在，也可以这样说，Iterator为std的成功提供了保证。
Iterator为什么会如此重要，因为大部分程序都是图灵完备的，所以可以分析一下图灵机，我们把图灵机分成三个部件：条带、接口部件(包括移动和数据捡取部分）、处理部件。这三个部件中，接口部件对应就是Iterator，它是条带与处理部件的纽带，从中可以看出Iterator的重要性。
看std代码，觉得Iterator带点神奇也比较复杂，其实这也是std整体带给我们的印象。从上面图灵机的分析可以看出，Iterator要体现的意图还是比较明确的，而且拨开各种迷雾，std的实现还是非常简洁的。
这篇文章，先来学学迭代器的写法，然后在后续文章中试着编写树、图形等特殊迭代器。
以下的代码摘录自std vector的 iterator ，为了看起来清楚，做了一些简化。不是很长，就整个列在上面了。
template< class _Ty> class vector;
template < class _Ty>
class _Vector_iterator
{
public :
typedef vector <_Ty> _Myvec;
typedef _Ty * _Tptr;
typedef _Ty value_type;
typedef _Vector_iterator <_Ty> _Myt;
// typedef _Vector_iterator<_Ty> _Mybase; // 原来指向const_iterator,简化了。
typedef _Ty value_type;
typedef int difference_type;
typedef _Ty * pointer;
typedef _Ty & reference;
_Vector_iterator()
{ // construct with null vector pointer
}
_Vector_iterator(pointer _Ptr):_Myptr(_Ptr)
{ // construct with pointer _Ptr
}
reference operator *() const
{ // return designated object
return ((reference)* _Myptr);
}
pointer operator ->() const
{ // return pointer to class object
return (&** this );
}
_Myt & operator ++ ()
{ // preincrement
++ _Myptr;
return (* this );
}
_Myt operator ++( int )
{ // postincrement
_Myt _Tmp = * this ;
++* this ;
return (_Tmp);
}
_Myt & operator -- ()
{ // predecrement
--_Myptr ;
return (* this );
}
_Myt operator --( int )
{ // postdecrement
_Myt _Tmp = * this ;
--* this ;
return (_Tmp);
}
_Myt & operator += (difference_type _Off)
{ // increment by integer
_Myptr += _Off;
return (* this );
}
_Myt operator +(difference_type _Off) const
{ // return this + integer
_Myt _Tmp = * this ;
return (_Tmp += _Off);
}
_Myt & operator -= (difference_type _Off)
{ // decrement by integer
return (* this += - _Off);
}
_Myt operator -(difference_type _Off) const
{ // return this - integer
_Myt _Tmp = * this ;
return (_Tmp -= _Off);
}
difference_type operator -( const _Mybase& _Right) const
{ // return difference of iterators
return _Myptr - _Right._Myptr;
}
reference operator [](difference_type _Off) const
{ // subscript
return (*(* this + _Off));
}
bool operator ==( const _Myt& _Right) const
{ // test for iterator equality
return (_Myptr == _Right._Myptr);
}
bool operator !=( const _Myt& _Right) const
{ // test for iterator inequality
return (!(* this == _Right));
}
bool operator <( const _Myt& _Right) const
{ // test if this < _Right
return (_Myptr < _Right._Myptr);
}
bool operator >( const _Myt& _Right) const
{ // test if this > _Right
return (_Right < * this );
}
bool operator <=( const _Myt& _Right) const
{ // test if this <= _Right
return (!(_Right < * this ));
}
bool operator >=( const _Myt& _Right) const
{ // test if this >= _Right
return (!(* this < _Right));
}
_Tptr _Myptr;
};
template < class _Ty>
_Vector_iterator <_Ty> operator +(typename _Vector_iterator<_Ty> ::difference_type _Off,
_Vector_iterator <_Ty> _Next)
{ // add offset to iterator
return (_Next += _Off);
}
从代码可以看出，其实std还是写得比较简洁。在布局、取名、注释、代码行文等方面着比较鲜明的std风格，取名的简洁以及 difference_type 这样的名字，可以看得出作者的一些偏好，至少是偏重数学。熟悉这些风格，代码看起来还是比较容易。
从上面的代码可以看出，在这里 iterator 只是对指针作了包装，当然复杂的迭代器不会这么简单，对于 iterator 来说，主要是移动和取值操作，也就是 *、 ++、 --这三个操作，另外 -> 操作为复合数据提供方便。
operator * 取值代码如下，可以看出只是对指针直接求值。
reference operator *() const
{ // return designated object
return ((reference)* _Myptr);
}
operator ++、 -- 操作有两组，分别对应于前置和后置操作。
operator ++、 -- 的前置操作代码如下，比较简单，只是把对应操作作用到指针。
_Myt& operator ++ ()
{ // preincrement
++ _Myptr;
return (* this );
}
_Myt & operator -- ()
{ // predecrement
--_Myptr ;
return (* this );
}
operator ++、 -- 的后置操作稍微复杂一些，也有点意思，代码如下。与前项操作不一样，多了一个int的参数，至于依据是什么，说实在我也没搞清楚。后缀操作 复制了一个对象，然后本身做前置操作，然后返回拷贝的对象。从这里可以看出实现后缀操作的一些特性，在这里不是等句子结束，而是在这个操作的后续操作中，如继续引用这个对象，则对这个对象并不是指向原来位置，而已经指向新的位置。
_Myt operator ++( int )
{ // postincrement
_Myt _Tmp = * this ;
++* this ;
return (_Tmp);
}
_Myt operator --( int )
{ // postdecrement
_Myt _Tmp = * this ;
--* this ;
return (_Tmp);
}
下面再来看看vector的代码，与 iterator 一样，摘录的代码已经对原来代码做了简化。vector的代码如下，因为较长，就不展开了。
vector Code
vector的主体函数都比较简单，有几个辅助代码稍多一些，为简单起见，把allocator整个简化了，去掉的还有反向 iterator 。
为了保证vector可以独立运行，把几个allocator和内存移动相关的函数，简化后并进到vector中，具体的实现方式只能説是有用，但不严谨，也不高效。而这方面std其实是着墨很多，并使用了许多技巧。但通过上面的结构，对于了解std的设计还是有帮助的。
现在我们还是把注意力回到 iterator， 从代码可以看出，vector有三个字段，_Myfirst指向数组的起点，_Mylast指向数组数据的后一位置，vector会根据需要多申请一些空间，_Myend指向整个空间的末尾。_Mylast是数据越界的开始，_Myend是内存越界的开始。
protected :
pointer _Myfirst; // pointer to beginning of array
pointer _Mylast; // pointer to current end of sequence
pointer _Myend; // pointer to end of array
从下面的代码可以看出， iterator 构建在_Myfirst和_Mylast上，begin()以_Myfirst构建 iterator ，end()以_Mylast构建 iterator，所以可以分别作为迭代的开始和终止条件。
iterator begin()
{ // return iterator for beginning of mutable sequence
return (iterator(_Myfirst));
}
iterator end()
{ // return iterator for end of mutable sequence
return (iterator(_Mylast));
}
关于vector其他的就不多説，只是顺带説一下关于vector的内存扩充。从下面摘录自_Insert_n函数的语句可以看出，每一次按50%的容量内存扩充。
else if (_Capacity < size() + _Count)
{ // not enough room, reallocate
_Capacity = max_size() - _Capacity / 2 < _Capacity
? 0 : _Capacity + _Capacity / 2 ; // try to grow by 50%
if (_Capacity < size() + _Count)
_Capacity = size() + _Count;
pointer _Newvec = allocate(_Capacity);
下面是整个完整的代码，并加了一小段测试。
View Code
分类: 词汇演算 , 语言 , 语言编译 , 杂谈 http://www.cnblogs.com/qianxj/archive/2012/12/24/2821510.html
作者： Leo_wl
出处： http://www.cnblogs.com/Leo_wl/
本文版权归作者和博客园共有，欢迎转载，但未经作者同意必须保留此段声明，且在文章页面明显位置给出原文连接，否则保留追究法律责任的权利。
版权信息