找回密码
 立即注册
  • QQ空间
  • 回复
  • 收藏

掌握C++标准库-第5讲

admin 2019-9-10 05:41 108人围观 C++相关

前面谈了STL容器,接下来谈谈STL迭代器。

STL迭代器

迭代器(iterators)一种抽象的设计概念,在23种设计模式中对迭代器模式的定义是:提供一种方法,使外界能够依次访问某个聚合物(容器)中的所有元素,并且不需要了解聚合物的实现方式。这正是STL所需要的。

STL的核心思想是:将容器和算法分开,彼此间独立,最后通过迭代器将它们撮合起来。也就是说,迭代器在STL中起着桥梁的作用。

弄懂STL迭代器的实现原理,有助于我们对泛型编程有更深的理解。首先看一段迭代器的应用场景:

    int main(){  int array[7] = {0, 1, 2, 3, 4, 5, 6};  vector<int> iv(array, array+7); //利用数组构建vector<int>容器对象  list<int> il(array, array+7);    //利用数组构建list<int>容器对象  //查找vector<int>中是否存在指定元素  vector<int>::iterator iter1 = find(iv.begin(), iv.end(), 4);if(iter1 != iv.end())  {    cout << *iter1 << “found.”<<endl;  }    //查找list<int>中是否存在指定元素list<int>::iterator iter2 = find(il.begin(), il.end(), 6);if(iter2 != il.end())  {   cout << *iter2 << “found.”<<endl; }}

    从上面这个例子看,迭代器都是由容器提供的。迭代器是否能够泛化呢?答案是不行的。这是因为不同类型的容器的内存布局是不一样的,所以其访问方法也会存在差异,因此不同类型的容器的迭代器是不同的。每一种容器都需要提供自己的迭代器。

    迭代器的实现

    迭代器是一种类似于指针的对象。它用来访问容器成员,因此具备内容提领(dereference)和成员访问(member access)功能,因此,迭代器必须实现operator*和operator->操作符。

    下面我们实现一个简单的List容器和其迭代器。list的实现如下:
      //list实现template<typename T>classList{public:voidinsert_front(T value);voidinsert_end(T value);private: ListNode<T>* begin; ListNode<T>* end;};
      //list节点实现template<typename T>classListNode{public:T value();ListNode* next();private: T value; ListNode* next; ListNode* front;};
      //List的迭代器实现template<typename T>classListIter{public: ListIter(T* p);  T& operator*(){return *pNode;}  T* operator->(){return pNode;}  ListIter& operator++(){pNode = pNode->next(); return *this;}private:  T* pNode;//指向list节点};

      从这个list容器的迭代器实现可以看到,迭代器需要知道容器的实现细节,因此,每一种STL容器都有专属的迭代器实现。庆幸的是,作为用户,我们不需要知道其实现方法。

      迭代器型别

      通过迭代器,我们能够获取容器数据成员,但有时我们需要获得迭代器的更多信息,比如某个函数需要返回迭代器所指的对象,这个函数如何设计呢?伪代码如下:
        template<typename Iterator>Type getVal(Iterator* iter){…}

        但template参数推导机制不能参与返回值的推导,因此我们需要一种可行的解法。这就需要迭代器的型别。在谈型别之前,我们先看什么是萃取机制。萃取机制是利用模板推导,来获取泛型的各种信息。例如:

          template<typename T>classtrait{  // 萃取类型型别typedef typename T::value_type value_type;};
          template<typename T>classIterator{public:typedef T value_type;//通过内嵌类型表达元素类型};
          //返回迭代器所指的对象类型template<typename Iter>tarit<Iter>::value_type func(){}

          这样就可以获取迭代器所指向的返回值类型,这就是萃取机制。要保证萃取机制有效运行,每种迭代器都要按照规定提供内嵌类型。如果不遵守规定,就不能融入到STL这个大家庭。那这个规定包括哪些呢?

          STL规定,迭代器必须提供5种相应型别:所指型别(value type),迭代器距离型别(difference type),引用型别(reference type),指针型别(pointer type),迭代器类型(iterator_category)。

          所指型别:指迭代器所指的对象的类型。迭代器距离型别:指两个迭代器之间的距离的类型。引用型别:指迭代器所指的对象能否被修改,分为常量迭代器和非常量迭代器两种。指针型别:迭代器所指的对象的指针类型。

          迭代器类型型别:迭代器分类分为五种,只写迭代器,只读迭代器,前向迭代器,双向迭代器,随机迭代器。

          • 只读迭代器:所指对象不能被外界修改,只读,支持operator++。

          • 只写迭代器:只写,支持operator++。

          • 前向迭代器:可读可写,只能前向移动,支持operator++。

          • 双向迭代器:可读可写,可双向移动,支持operator--。

          • 随机迭代器:可读可写,可随机移动,支持算术运算,iter+n,iter1<iter2等。



          这些迭代器的从属关系如图所示。受制于内存布局,不同的容器所提供的迭代器型别不同,vector、deque提供随机迭代器,list和关联容器提供双向迭代器,forward_list提供前向迭代器。

          之所以有这么多型别,就是为了提高算法的效率,STL追求极致的效率。以advanced为例,该函数接受两个参数,迭代器iter和正数n,其功能是将iter前进n个距离。对于不同的迭代器类型,有三种实现方式,伪代码如下:

            //只读迭代器版本voidadvance_II(InputIterator& p, Dist n){while(n-- > 0) ++p;}
            //双向迭代器版本voidadvance_BI(BidirectionalIterator& p, Dist n){  if(n>=0)   while(n--) ++p;  else   while(n++) –p;}
            //随机迭代器版本voidadvance_RI(RandomIterator& p, Dist n){ p += n;}

            显而易见,随机迭代器版本效率最高。当迭代器类型是随机访问迭代器时,就应该调用随机迭代器版本。如何实现呢?通过函数重载,在编译期就可选定最优的函数。实现如下:

              //只读迭代器类型重载版本void_advance(InputIterator& p, Dist n, input_iterator){ advance_II(p, n);}
              //双向迭代器类型重载版本void_advance(BidirectionalIterator& p, Dist n, bidirectional_iterator){ advance_BI(p, n);}
              //随机迭代器类型重载版本void_advance(RandomIterator& p, Dist n, random_iterator){ advance_RI(p, n);}
              //提供给用户的接口voidadvanced(Iterator& p, Dist n){  //通过萃取机制获取迭代器型别,从而实现重载抉择  _advance(p, n, iterator_trait<Iterator>::iterator_category());}

              综上,迭代器需要设计合适的型别。而设计合适的迭代器,是容器的责任,因为只有容器的设计者才知道如何遍历自己,并且其迭代器应该具备何种型别。而算法完全独立于容器和迭代器之外,这就是典型的面向接口编程。

              迭代器失效

              使用迭代器时,需要注意迭代器失效问题,否则程序会出现异常。迭代器失效发生在容器元素插入,删除等结构发生变化时的情况。

              vector迭代器失效情况有:插入或删除元素,插入和删除位置之后的所有迭代器都失效;插入元素导致vector容量发生重新分配,所有迭代器都失效。

              deque迭代器失效情况有:在首部或者尾部插入元素不会使得任何迭代器失效;在首部或尾部删除元素只会导致被删除元素的迭代器失效,其他位置的插入和删除操作将使所有迭代器失效。

              list、set、map迭代器失效情况有:插入元素不会导致任何迭代器失效;删除元素只会导致被删除元素的迭代器失效。



              ----------------------------------------------------------------------------------------------------------------------
              我们尊重原创,也注重分享,文章来源于微信公众号:程序猿Cpp,建议关注公众号查看原文。如若侵权请联系qter@qter.org。
              ----------------------------------------------------------------------------------------------------------------------

              鲜花

              握手

              雷人

              路过

              鸡蛋

              yafeilinux和他的朋友们微信公众号二维码

              微信公众号

              专注于Qt嵌入式Linux开发等。扫一扫立即关注。

              Qt开源社区官方QQ群二维码

              QQ交流群

              欢迎加入QQ群大家庭,一起讨论学习!

              我有话说......