huaxiazhihuo

 

迭代器的抽象

      迭代器是好东西,也是猿猴工具箱里面的七种武器之一。代码中必然要操作一堆数据,因此就要有容器,有了容器,自然就不可缺少迭代器,没有迭代器,容器使用上就会非常不方便,并且还必须暴露其内部实现方式。比如,在可怜的C语言里面,操作数组容器就要通过整数索引来访问其元素,操作链表容器,就要通过while(node->next!=null)这样的方式来访问其元素。某种意义上讲,整数索引,node->next这些都是迭代器,只是它们的使用方式没有统一起来而已。既然如此,全世界的迭代器的使用方式都统一起来,那么这就是迭代器了。
      基本上,现代化的语言,都会在语言层面上提供foreach之类的语法糖,其形式不外乎是,foreach(e:c){}。就是这样,只要提供元素的名字和容器对象。后面跟着循环体。其思想就是从容器里面取出一个元素,用循环体对这个元素进行操作。循环完毕,就完成了对容器里面数据的操作。这种语法形式,简洁得不能再简洁了。很好很方便,什么额外重复的代码都不劳费心了,甚至连类型推导不用做。真的,类型可以推导的时候,就让编译器推导好了。代码里面必须大规模的使用auto,var这样的关键字。不要担心看不出来变量的类型。变量类型应该从变量的名字中体现出来其抽象意义,当然,不要搞什么匈牙利命名法,那个太丑陋了。
      既然语法糖提供了这种对迭代器的支持操作语法,自然而然,只要涉及到一堆数据这样的概念,不必局限于具体的容器(数组,链表,哈希表),文件夹也是一堆数据,Composition模式也是一堆数据,数列,……,等等所有这些,全部都是概念上的一堆数据,只要提供了迭代器,猿猴就可以很优雅的用foreach这样的语法糖来统一操作数据,多么方便,多么的多态。不管这一堆数据的内部实现方式是什么,后期怎么修改,在foreach这里代码全部都不会受影响。更何况,对于迭代器,语法上不仅仅提供foreach的便利得无以复加的甜糖,还有一大堆的标准库函数来让猿猴操作迭代器,什么排序,查找,映射……。更令人发指的是,C#把迭代器捣鼓得好用得让人伤心难过悲愤欲绝,而linq语法上还可以把IEnumbale整成monad,可以用来作什么cps的变换。迭代器在手,天下我有。
      迭代器这个概念的抽象似乎很理所当然,但是不然,比如,刘未鹏举过Extended STL的例子,操作文件夹。C和C++代码对比。
// in C
DIR*  dir = opendir(".");
if(NULL != dir)
{
  
struct dirent*  de;
  
for(; NULL != (de = readdir(dir)); )
  {
    
struct stat st;
    
if0 == stat(de->d_name, &st) &&
        S_IFREG 
== (st.st_mode & S_IFMT))
    {
      remove(de
->d_name);
    }
  }
  closedir(dir);
}
 
// in C++
readdir_sequence entries(".", readdir_sequence::files); 
std::for_each(entries.begin(), entries.end(), ::remove);
显然,前者是没有迭代器的抽象,后者是有迭代器抽象的简洁异常的代码。第一次看到,惊为天人,其实本就该如此,只是C将这一切搞复杂了。当然,还有一批C 粉反对,说什么代码不透明了,隐藏了代码背后可能的复杂实现。对于这一簇人的坚持不懈反对抽象的态度,真不知该说什么好呢?代码的能力里面,最最重要的事情就是抽 象,通过抽象,猿猴才可以避开细节,将精力集中于更加重要更加复杂的事情。通过抽象,可以减少重复的代码,可以提高类型安全。C++是唯一能在玩抽象概念的同时,又可以兼顾到底层细节的处理,从而不仅能写出高效代码,还能玩出更炫的技巧。很多时候,必须底层玩得越深,抽象的触角才能伸得越高。
      其实,迭代器不必依存于容器。而是,先有了迭代器,才会有容器。请谨记,迭代器可以独立存在。begin和end就代表了一堆数据的概念。至于这一堆数据是如何存放的,这一切都无关紧要。基于此,有必要用class来表达一堆数据这么一个通用性极高的概念。其实,boost里面好像也有这么一个东西。就叫做DataRange吧。为何不叫Range,因为Range另有更重要用途,这么好的名字就是用来生成DataRange,代码不会直接看到DataRange,都是通过Range来生成DataRange。
template<typename Iterator>
struct DataRange
{
    typedef Iterator IteratorType;

    DataRange(IteratorType beginIter, IteratorType endIter) : mBegin(beginIter), mEnd(endIter)
    {
    }

    IteratorType begin()
const { return mBegin; }
    IteratorType end()
const { return mEnd; }
    IteratorType mBegin;
    IteratorType mEnd;
};
      然后,随便搞两行代码试试
   vector<int> vvv = { 1, 2, 3 };
    for (auto i : Range(vvv))
    {
        cout << i << endl;
    }
      其实,C++11概念上就支持一堆数据的操作,只要一个类型struct或者class里面有begin()和end()这一对活宝,并且这一对活宝的返回类型是迭代器,那么就可以尽情的享用foreach的甜糖。那么,何谓迭代器。就是支持三种操作的数据类型:!=(判断相等,用来结束迭代操作),前++(用来到迭代到下一个元素),*(取值)。那么,这就是迭代器了,显然,指针就是原生的迭代器。虽然,整形int也可以++,!=,但是不支持取值操作,所以int不是迭代器。下面就要把int变成迭代器。
template<typename Ty, typename Step>
struct ValueIncrementIterator
{
    typedef ValueIncrementIterator ThisType;
    typedef Ty ValueType;
    typedef Step StepType;

    ThisType(ValueType val, StepType step)
        :mValue(val), mStep(step){}

    
bool operator != (const ThisType& other) const
    {
        
return mValue < other.mValue;
    }

    ValueType 
operator* () const
    {
        
return mValue;
    }

    ThisType
& operator++ ()
    {
        mValue 
+= mStep;
        
return *this;
    }

    ValueType mValue;
    StepType mStep;
};
然后,再用一个函数FromTo(也不知叫什么名字更好),用来生成DataRange。请注意,我们的迭代器怎么实现,那都是细节。最后展示在用户层代码都是干干净净的function生成的DataRange,甚至连尖括号都不见了。也不用写具体是什么类型的DataRange,只须用auto让编译器自动推导类型就好了。
// step = 1是偷懒做法,万一Step的构造函数不能以1为参数就弱鸡了。比如DateTime和TimeSpan
template<typename Ty, typename Step>
auto FromTo(Ty from, Ty to, Step step 
= 1-> DataRange<ValueIncrementIterator<Ty, Step>>
{
    typedef ValueIncrementIterator
<Ty, Step> ValueType;
    
return DataRange<ValueType>(ValueType(from, step), ValueType(to, step));
}
于是,FromTo(1, 10, 2)就表示10以内的所有奇数,可以用for range的语法糖打印出来。
      这里的FromTo是按照上升状态产生一系列数据,同样,也可以产生下降的一堆数据FromDownTo,如果愿意的话,同学们也可以用迭代器形式生成斐波那契数列。不知注意到了,请用抽象的角度理解++和*这两个操作符。++就是为新的数据做准备进入到下一个状态,根据情况,可以有不同方式,进入到下一个状态,比如上面的ValueIncrementIterator根据步长递增到新的数值,ValueDecrementIterator的++却是在做减法,甚至还可以做Filter操作;*就是取到数据,我们可以在*的时候,才生成一个新的数据,这里从某种意义上来讲,其实就是延迟求值;而!=判断结束条件的方式又多种多样。总之,凭着这三个抽象操作,花样百出,基本上已经能够覆盖所有的需求了。
      为了体现这种抽象的威力,让我们给DataRange增加一个函数Concate,用于将两堆数据串联成一堆数据。首先,定义一个游走于两堆数据的迭代器,当它走完第一堆数据,就进入第二堆数据。
//不知道有什么语法能推导迭代器的值类型,所以搞这个辅助函数。可能写成type_trait形式更好,就算偷懒吧
template<typename Iter>
auto GetIteratorValueType(Iter
* ptr) -> decltype(**ptr)
{
    
return **ptr;
}

template
<typename Iter1, typename Iter2>
struct ConcateIterator
{
    typedef ConcateIterator ThisType;
    typedef Iter1 Iter1Type;
    typedef Iter2 Iter2Type;
    
//typedef decltype(*mBegin1) ValueType;
    typedef decltype(GetIteratorValueType((Iter1Type*)nullptr)) ValueType;

    ThisType(Iter1Type begin1, Iter1Type end1, Iter2Type begin2)
        :mBegin1(begin1), mEnd1(end1), mBegin2(begin2), mInBegin2(
false){}

    ThisType(Iter1Type end1, Iter2Type begin2)    
//这里有些蹊跷,不过也没什么
        :mBegin1(end1), mEnd1(end1), mBegin2(begin2), mInBegin2(true){}

    
bool operator != (const ThisType& other) const
    {
        
if (!mInBegin2 && other.mInBegin2)
            
return true;
        
if (!mInBegin2 && !other.mInBegin2 && mBegin1 != other.mBegin1)
            
return true;
        
if (mInBegin2 && other.mInBegin2 && mBegin2 != other.mBegin2)
            
return true;
        
return false;
    }

    ValueType 
operator* () const
    {
        
return mInBegin2 ? (*mBegin2) : (*mBegin1);
    }

    ThisType
& operator++ ()
    {
        
if (mInBegin2)
        {
            
++mBegin2;
        }
        
else
        {
            
if (mBegin1 != mEnd1)
                
++mBegin1;
            
if (!(mBegin1 != mEnd1))
                mInBegin2 
= true;
        }
        
return *this;
    }

    Iter1Type mBegin1;
    Iter2Type mBegin2;
    Iter1Type mEnd1;
    
bool mInBegin2;
};

有了ConcateIterator,DataRange的Concate函数就很好办了。
    template<typename OtherRange>
    auto Concate(
const OtherRange& otherRange)
        
->DataRange<ConcateIterator<IteratorType, decltype(otherRange.begin())>>
    {
        typedef ConcateIterator 
< IteratorType, decltype(otherRange.begin())> ResultIter;
        
return DataRange<ResultIter>(
            ResultIter(mBegin, mEnd, otherRange.begin()), ResultIter(mEnd, otherRange.end()));
    }
然后,试试
    list<int> numList = { 10, 11, 12 };
    for (auto i : Range(vvv).Concate(FromTo(4, 10, 2)).Concate(numList))   //后面随便接容器
    {
        cout << i << endl;
    }
     这样,就把两堆数据串联在一块了,是不是很酷呢?用C++11写代码,很有行云流水的快感,又有函数式编程的风格。下期节目继续发挥,给DataRange加入Filter,Map,Replace等操作,都是将一个DataRange变换成另一个DataRange的操作,显然,这是一种组合子的设计方式,也是吸收了haskell和linq的设计思路。某种意义上讲,就是给迭代器设计一套dsl,通过.操作符自由组合其成员函数,达到用起来很爽的效果,目标就是仅仅通过几个正交成员函数的随意组合,可以在大多数情况下代替stl算法的鬼麻烦的写法。这种dsl的最大好处类似于linq,先处理的步骤写在最前面,避开了函数调用的层次毛病,最外层的函数反而写在顶层。其实迭代器这个话题要展开来说的话,很有不少内容,比如用stackless协程来伪装成迭代器,Foldl,Foldl1,Scan等。当然,真要用得爽,还要配合boost中lambda的语法,好比什么_1+30,_1%2,当然,那个也可以自己写,因为C++现在已经支持lambda了,所以,自己写boost lambda的时候,可以剪裁,取其精华,去其糟粕。如果,再弄一个支持arena内存批量释放又或者是Stack风格的allocator(线程相关),那么就更不会有任何心智负担了,内存的分配和释放飞快,这样的动多态的allocator写起来也很有意思,它可以根据不同情况表现不同行为,比如说多线程下,就会用到线程同步,单线程就无须同步,每个线程单独拥有一个allocator,根据用户需要,还能用栈式内存分配,也就是分配内存时只是修改指针而已,释放时就什么都不做了,最后通过析构函数,将此allocator的内存一次性释放。当拥有一个表现如此多样的allocator,stl用起来真是爽。

posted on 2016-05-14 02:10 华夏之火 阅读(1301) 评论(2)  编辑 收藏 引用 所属分类: c++技术探讨

评论

# re: 迭代器的抽象 2016-05-25 10:38 linda

迭代器的确是个好东西  回复  更多评论   

# re: 迭代器的抽象 2016-05-25 11:21 华夏之火

@linda
迭代器不仅仅是好东西,而是必须物,不可或缺。没有迭代器的抽象,要么就是延迟求值,要么代码就会写起来很痛苦  回复  更多评论   


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理


导航

统计

常用链接

留言簿(6)

随笔分类

随笔档案

搜索

积分与排名

最新评论

阅读排行榜

评论排行榜