C++ Primer 學習筆記_48_STL剖析（三）：迭代器、迭代器的類型、常用的容器成員、迭代器失效的問題

一、迭代器

1、迭代器是泛型指針

通過重載*，->，++，--等運算符

（1）普通指針可以指向內存中的一個地址

（2）迭代器可以指向容器中的一個位置

2、STL的每一個容器類模版中，都定義了一組對應的迭代器類。使用迭代器，算法函數可以訪問容器中指定位置的元素，而無需關心元素的具體類型。

二、迭代器的類型iterator_category

1、輸入迭代器（*p ， ++）

可以用來從序列中讀取數據

2、輸出迭代器（*p = 0 ， ++）

允許向序列中寫入數據

3、前向迭代器（++，但不支持--）

既是輸入迭代器又是輸出迭代器，並且可以對序列進行單向的遍歷

4、雙向迭代器（++，支持--）

與前向迭代器相似，但是在兩個方向上都可以對數據遍歷

5、隨機訪問迭代器（++，--， 支持+=5， +3）

也是雙向迭代器，但能夠在序列中的任意兩個位置之間進行跳轉

三、常用的容器成員

下面列舉的成員中，有一些是所有容器共有的，有些是特有的，注意區別：

簡單的測試程序跟蹤調試如下：

#include 
#include 
#include 

using namespace std;

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

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

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


    list l;
    l.push_back(1);
    l.push_back(2);
    l.push_back(3);

    list::iterator it2;

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

    return 0;
}

稍微看一下vector::iterator 和vector::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 reverse_iterator;
    typedef std::reverse_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 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
struct _Allocator_base
{
    // base class for generic allocators
    typedef _Ty value_type;
};

template
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
};

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

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

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

iter = vec.insert(iter);
iter = vec.erase(iter);