从零开始学C++之STL(三):迭代器类vector::iterator 和 vector::reverse_iterator 的实现、迭代器类型、常用的容器成员

一、迭代器

迭代器是泛型指针

普通指针可以指向内存中的一个地址 迭代器可以指向容器中的一个位置

STL的每一个容器类模版中,都定义了一组对应的迭代器类。使用迭代器,算法函数可以访问容器中指定位置的元素,而无需关心元素的具体类型。

下面来稍微看一下vector<class>::iterator 和 vector<class>::reverse_iterator 的源码:

template < class _Ty,
         class _Alloc >
class _Vector_val
    : public _CONTAINER_BASE_AUX_ALLOC<_Alloc>
{
    // base class for vector to hold allocator _Alval
protected:
    _Vector_val(_Alloc _Al = _Alloc())
        : _CONTAINER_BASE_AUX_ALLOC<_Alloc>(_Al), _Alval(_Al)
    {
        // construct allocator from _Al
    }

    typedef typename _Alloc::template
    rebind<_Ty>::other _Alty;

    _Alty _Alval;   // allocator object for values
};

template < class _Ty,
         class _Ax >
class vector
    : public _Vector_val<_Ty, _Ax>
{
    // varying size array of values
public:
    .....
   typedef _Vector_val<_Ty, _Ax> _Mybase;
    typedef typename _Mybase::_Alty _Alloc;  //_Alloc 的定义所在
    typedef _Vector_iterator<_Ty, _Alloc> iterator;
    typedef _Vector_const_iterator<_Ty, _Alloc> const_iterator;

    //  friend class _Vector_iterator<_Ty, _Alloc>;
    friend class _Vector_const_iterator<_Ty, _Alloc>;

    typedef std::reverse_iterator<iterator> reverse_iterator;
    typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
    .......
};

template < class _Ty,
         class _Alloc >
class _Vector_iterator
    : public _Vector_const_iterator<_Ty, _Alloc>
{
    // iterator for mutable vector
public:
    typedef _Vector_iterator<_Ty, _Alloc> _Myt;
    typedef _Vector_const_iterator<_Ty, _Alloc> _Mybase;
    .......
};

template < class _Ty,
         class _Alloc >
class _Vector_const_iterator
    : public _Ranit < _Ty, typename _Alloc::difference_type,
      typename _Alloc::const_pointer, typename _Alloc::const_reference >
{
    // iterator for nonmutable vector
public:
    .....
    typedef typename _Alloc::pointer _Tptr;
   typedef random_access_iterator_tag iterator_category;
   typedef _Ty value_type;
   typedef typename _Alloc::difference_type difference_type;
   typedef typename _Alloc::const_pointer pointer;
  typedef typename _Alloc::const_reference reference;
 typedef const value_type _FARQ *const_pointer;
 typedef const value_type _FARQ& const_reference;
    ....
    _Tptr _Myptr;   // offset of element in vector
};

template<class _Ty>
class allocator
    : public _Allocator_base<_Ty>
{
    // generic allocator for objects of class _Ty
public:
    ......
    typedef _Allocator_base<_Ty> _Mybase;
    typedef typename _Mybase::value_type value_type;
    typedef value_type _FARQ *pointer;
   typedef value_type _FARQ& reference;
    ...
};

// TEMPLATE CLASS _Allocator_base
template<class _Ty>
struct _Allocator_base
{
    // base class for generic allocators
    typedef _Ty value_type;
};

template<class _RanIt>
class reverse_iterator
    : public _Revranit<_RanIt, iterator<...> >
{
    // wrap iterator to run it backwards
    ........
    typedef reverse_iterator<_RanIt> _Myt;
    typedef _RanIt iterator_type;
    ..............

};

// TEMPLATE CLASS _Revranit
template < class _RanIt,
         class _Base >
class _Revranit
    : public _Base
{
    // wrap iterator to run it backwards
    ....
protected:
    _RanIt current; // the wrapped iterator
};

typedef _Vector_iterator<_Ty, _Alloc> iterator; 可知iterator 只是类型定义,而_Vector_iterator 又继承自 _Vector_const_iterator,这个类有个成员_Tptr _Myptr;  进一步看_Tptr 可以知道类型是value_type*, 假设现在使用的容器是vector<int>,那么value_type 也就是int, 那么实际上iterator 内部就只有一个int* _Myptr; 成员而已。即包装了一般的指针。很明显地,iterator 类里面一定重载了operator*, ->, ++, -- 等操作符,而这些操作符实际上还是对一般的指针_Myptr 进行操作。举operator* 来说:

// iterator
reference operator*() const
{
    // return designated object
    return ((reference) **(_Mybase *)this);
}

// const_iterator
reference operator*() const
{
    // return designated object

    .....
    return (*_Myptr);
}

this 在这里是iterator*, (_Mybase *)this就是const_iterator*,*(_Mybase *)this就是const_iterator 对象,**(_Mybase *)this就是调用const_iterator的 operator*(), 即 返回*_Myptr,即指向的元素,iterator 的 operator* 返回的是引用 reference ,这其实是在allocator 类中定义的const_reference,即 const value_type&, 假设现在的容器是vector<int> ,那么返回的也就是const int& ,即不能将其作为左值进行赋值,但能作为右值,如 cout<<*it;

同样地, iterator 的 operator++ 也调用了 const_iterator 的 operator++, 在函数里面也是执行  ++_Myptr; 的操作,返回的是const_iterator& ,而从iterator 的 operator++ 返回的是iterator& 。

typedef std::reverse_iterator<iterator> reverse_iterator; 再来看 reverse_iterator,继承自_Revranit, 这个类有个成员 _RanIt current; 

也就是说有个 iterator 类成员,即包装了一个iterator 类成员,从这个角度看,reverse_iterator 也可以算是一个适配器,利用 iterator 类的一些操作完成自身的功能。

上面介绍的是vector::iterator ,比如 list::iterator 实现是类似的,内部成员也是一个指针,不过是指向Node 结点的指针,如:

_Nodeptr _Ptr;// pointer to node

简单的测试程序如下:

#include <vector>
#include <list>
#include <iostream>

using namespace std;

int main(void)
{
    vector<int> v;
    v.push_back(1);
    v.push_back(2);
    v.push_back(3);

    vector<int>::iterator it;
    for (it = v.begin(); it != v.end(); ++it)
    {
        cout << *it << ' ';
    }
    cout << endl;

    vector<int>::reverse_iterator ri;
    for (ri = v.rbegin(); ri != v.rend(); ++ri)
    {
        cout << *ri << ' ';
    }
    cout << endl;


    list<int> l;
    l.push_back(1);
    l.push_back(2);
    l.push_back(3);

    list<int>::iterator it2;

    for (it2 = l.begin(); it2 != l.end(); ++it2)
    {
        cout << *it2 << ' ';
    }
    cout << endl;

    return 0;
}

二、迭代器的类型 iterator_category

输入迭代器 可以用来从序列中读取数据

输出迭代器 允许向序列中写入数据

前向迭代器 既是输入迭代器又是输出迭代器,并且可以对序列进行单向的遍历

双向迭代器 与前向迭代器相似,但是在两个方向上都可以对数据遍历

随机访问迭代器 也是双向迭代器,但能够在序列中的任意两个位置之间进行跳转 下图是不同类型的迭代器能够实现的操作:

1、The standard-library container classes all support bidirectional iterators.

of curse the const iterator only meets the requirements for input iterators.

2、The vector and deque iterators are random-access iterators. however, the list iterator is not; it supports only bidirectional iterators.etc,it does not support [] operation.

3、If c is a container that supports push_back, then back_inserter(c)  is an output iterator that meets no other iterator requirements.

4、The stream iterators are defined in the <iterator> header,  the istream_iterator<class name> meets the requirements for input iterators; the ostream_iterator<class name>  meets the requirements for output iterators.

 we can use it like this:

vector<int> v;
// read ints from the standard input and append them to v
// istream_iterator<int>() indicate "EOF"
copy(istream_iterator<int>(cin), istream_iterator<int>(), back_inserter(v));


// write the elements of v each seperated from other by a space
copy(v.begin(), v.end(), ostream_iterator<int>(cout, " ");

     // no seperation between elements!
     copy(v.begin(), v.end(), ostream_iterator<int>(cout);

不同的迭代器支持不同的操作集,而各种算法也要求相应的迭代器具有最小的操作集。因此,可以将算法的迭代器分为下面五类:

除了输出迭代器,其他类别的迭代器形成了一个层次结构:需要低级类别迭代器的地方,可使用任意一种更高级的迭代器。例如,对于需要输入迭代器的算法,可传递前向、双向或随机访问迭代器调用该算法。而反之则不行。注意:向算法传递无效的迭代器类别所引起的错误,无法保证会在编译时被捕获到。

map, set, list类型提供双向迭代器,而string, vector和deque容器上定义的迭代器都是随机访问迭代器,用作访问内置数组元素的指针也是随机访问迭代器。istream_iterator是输入迭代器,ostream_iterator是输出迭代器。

另外,虽然map和set类型提供双向迭代器,但关联容器只能使用这部分算法的一个子集。因为关联容器的键是const对象。因此,关联容器不能使用任何写序列元素的算法。只能使用与关联容器绑在一起的迭代器来提供用于读操作的实参。因此,在处理算法时,最好将关联容器上的迭代器视为支持自减运算的输入迭代器,而不是完整的双向迭代器。

最后需要注意的是,stack、queue、priority_queue 都不支持任一种迭代器,它们都是容器适配器类型,stack是用vector/deque/list对象创建了一个先进后出容器,queue是用deque或list对象创建了一个先进先出容器,priority_queue是用vector/deque创建了一个排序队列。

三、常用的容器成员

下面列举的成员中,有一些是所有容器共有的,有些是特有的,注意区别:

四、迭代器失效的问题(摘自 http://blog.csdn.net/hackbuteer1/article/details/7734382)

vector迭代器的几种失效的情况:  1、当插入(push_back)一个元素后,end操作返回的迭代器肯定失效。 2、当插入(push_back)一个元素后,capacity返回值与没有插入元素之前相比有改变,则需要重新分配整个容器,此时first和end操作返回的迭代器都会失效。 3、当进行删除操作(erase,pop_back)后,指向删除点的迭代器全部失效;指向删除点后面的元素的迭代器也将全部失效。

 deque迭代器的失效情况: 在C++Primer一书中是这样限定的:  1、在deque容器首部或者尾部插入元素不会使得任何迭代器失效。  2、在其首部或尾部删除元素则只会使指向被删除元素的迭代器失效。 3、在deque容器的任何其他位置的插入和删除操作将使指向该容器元素的所有迭代器失效。

 list的迭代器好像很少情况下会失效,也许就只是在删除的时候,指向被删除节点的迭代器会失效吧,其他的还没有发现。 先看两条规制: 1、对于节点式容器(map, list, set)元素的删除、插入操作会导致指向该元素的迭代器失效,其他元素迭代器不受影响。 2、对于顺序式容器(vector)元素的删除、插入操作会导致指向该元素以及后面的元素的迭代器失效。

众所周之当使用一个容器的insert或者erase函数通过迭代器插入或删除元素"可能"会导致迭代器失效,因此建议我们获取insert或者erase返回的迭代器,以便用重新获取新的有效的迭代器进行正确的操作:

代码如下:

参考:

C++ primer 第四版 Effective C++ 3rd C++编程规范

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏小白客

每天学习一点儿算法--散列表

在之前我们已经学过了二分查找和简单查找,我们知道二分查找的运行时间为O(㏒ n), 简单查找的运行时间为O(n)。除此之外,还有没有更快的查找算法呢? 可能有人...

2546
来自专栏web前端教室

javascript 红皮高程(17)

按位操作符真是有头大的感觉,其实我也不太清楚哪里可以用到它。但即使不懂,也要先学会再说。 今天继续,按位或(OR), 它由一个竖线符号(|) 表示,同样也是操作...

17210
来自专栏还债之路

redis管理

Redis发布消息通常有两种模式: • 队列模式(queuing) • 发布-订阅模式(publish-subscribe) 任务队列:顾名思义,就是“...

1073
来自专栏决胜机器学习

《Redis设计与实现》读书笔记(五) ——Redis中的整数集合

《Redis设计与实现》读书笔记(五) ——Redis中的整数集合 (原创内容,转载请注明来源,谢谢) 一、概述 整数集合(intset)是redis数据结构集...

3004
来自专栏小樱的经验随笔

51 Nod 1005 大数加法【Java大数乱搞,python大数乱搞】

1005 大数加法 基准时间限制:1 秒 空间限制:131072 KB 分值: 0 难度:基础题 给出2个大整数A,B,计算A+B的结果。 Input 第1行:...

3289
来自专栏JavaQ

Guava之Objects

Guava中Objects类提供了很多和Object类作用相同、效率更高的方法可供使用: 1.equal方法 使用Obejct的equals方法进行相等判断,...

3117
来自专栏aCloudDeveloper

大神洗礼第四讲——函数相关及编程技巧

Author:bakari       Date:2012.11.2 1、参数传递问题: < 1 >、堆栈传参 < 2 >、寄存器传参(利用通用寄存器进行函数参...

18310
来自专栏Spark学习技巧

Flink DataStream编程指南

Flink程序是执行分布式集合转换(例如,filtering, mapping, updating state, joining, grouping, defi...

4547
来自专栏desperate633

深入理解SortSet类型的使用及应用Redis 有序集合(sorted set)SortSet的应用场景SortSet的常用命令

Redis 有序集合和集合一样也是string类型元素的集合,且不允许重复的成员。

842
来自专栏Java3y

八大基础排序总结

前言 大概花了一周的时间把八大基础排序过了一遍,这篇博文主要是用来回顾一下八大基础排序的要点和一些总结~ 回顾: 冒泡排序就这么简单 选择排序就这么简单 插入排...

3725

扫码关注云+社区