程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> C++ Primer 學習筆記_48_STL剖析(三):迭代器、迭代器的類型、常用的容器成員、迭代器失效的問題

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

編輯:C++入門知識

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


一、迭代器

1、迭代器是泛型指針

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

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

(2)迭代器可以指向容器中的一個位置

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

\

二、迭代器的類型iterator_category

1、輸入迭代器(*p , ++)

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

2、輸出迭代器(*p = 0 , ++)

允許向序列中寫入數據

3、前向迭代器(++,但不支持--)

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

4、雙向迭代器(++,支持--)

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

5、隨機訪問迭代器(++,--, 支持+=5, +3)

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

6、下圖是不同類型的迭代器能夠實現的操作:

\

三、常用的容器成員

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

\

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

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

typedef_Vector_iterator<_Ty,_Alloc>iterator; 可知iterator 只是類型定義,而_Vector_iterator 又繼承自_Vector_const_iterator,這個類有個成員_Tptr_Myptr; 進一步看_Tptr 可以知道類型是value_type*,假設現在使用的容器是vector,那麼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 ,那麼返回的也就是const int& ,即不能將其作為左值進行賦值,但能作為右值,如 cout<<*it;同樣地, iterator 的 operator++ 也調用了 const_iterator 的 operator++, 在函數裡面也是執行 ++_Myptr; 的操作,返回的是const_iterator& ,而從iterator 的 operator++ 返回的是iterator& 。

 

typedef std::reverse_iterator reverse_iterator;再來看reverse_iterator,繼承自_Revranit, 這個類有個成員_RanItcurrent;也就是說有個 iterator 類成員,即包裝了一個iterator 類成員,從這個角度看,reverse_iterator 也可以算是一個適配器,利用 iterator類的一些操作完成自身的功能。

××××××××××××××××××××××××××××××××××××××××××××××××××××××××××××××××××××××××××××××××××××××××××××××××××××

上面介紹的是vector::iterator ,比如 list::iterator 實現是類似的,內部成員也是一個指針,不過是指向Node 結點的指針,如:_Nodeptr _Ptr;// pointer to node

×××××××××××××××××××××××××××××××××××××××××××××××××××××××××××××××××××××××××××××××××××××××××××××××××××

\

\

\

\

\

四、迭代器失效的問題(摘自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返回的迭代器,以便用重新獲取新的有效的迭代器進行正確的操作:
代碼如下:

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

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved