快捷導(dǎo)航

C++模擬實(shí)現(xiàn)List迭代器詳解

更新時(shí)間：2022年04月15日 12:15:19 作者：m0_52012656

list不同于其他容器，他是一個(gè)鏈表，物理地址并不連續(xù)。所以在實(shí)現(xiàn)list類的迭代器的時(shí)候，需要將迭代器單獨(dú)封裝到一個(gè)類里，因?yàn)樾枰剌d很多操作符來(lái)跟其他容器的迭代器使用達(dá)成一致

概念

迭代器是一種抽象的設(shè)計(jì)概念，其定義為：提供一種方法，使他能夠按順序遍歷某個(gè)聚合體（容器）所包含的所有元素，但又不需要暴露該容器的內(nèi)部表現(xiàn)方式。

迭代器是一種行為類似智能指針的對(duì)象，而指針最常見的行為就是內(nèi) 容提領(lǐng)和成員訪問(wèn)。因此迭代器最重要的行為就是對(duì)operator*和operator->進(jìn)行重載。

STL的中心思想在于：將數(shù)據(jù)容器和算法分開，彼此獨(dú)立設(shè)計(jì)，最后再以一貼膠合劑（ iterator）將它們撮合在一起。STL的迭代器是一個(gè)可遍歷STL容器全部或者部分?jǐn)?shù)據(jù)

迭代器使用

我們可以使用迭代器訪問(wèn)修改鏈表元素

list<int>  lt;
list<int>::iterator it=lt.begin();
while(it!=lt.end())
{
    *it+=2;
    cout<<*it<<" ";
    it++;
}

2.我們有些函數(shù)接口需要傳迭代器，例如：

template <class InputIterator, class T>
   InputIterator find (InputIterator first, InputIterator last, const T& val);
?
template <class ForwardIterator, class T>
  void replace (ForwardIterator first, ForwardIterator last,
                const T& old_value, const T& new_value);

迭代器模擬實(shí)現(xiàn)

迭代器的大體結(jié)構(gòu)

//鏈表節(jié)點(diǎn)
template<class T>
struct ListNode {
    ListNode<T>* _next;
    ListNode<T>* _prev;
    T _data;
    //構(gòu)造節(jié)點(diǎn)值
    ListNode(const T& data = T())
        :_next(nullptr)
        ,_prev(nullptr)
        ,_data(data)
    {}
};
?
///迭代器
//T為list數(shù)據(jù)類型，Ref為T&,Ptr為T*
template<class T,class Ref,class Ptr>
struct __list_iterator
{
    typedef ListNode<T> Node;
    typedef __list_iterator<T,Ref,Ptr> self;
    Node* _node;//節(jié)點(diǎn)指針
    
    //接下來(lái)實(shí)現(xiàn)的函數(shù)都是在這個(gè)位置
};

構(gòu)造函數(shù)

一般都會(huì)傳過(guò)來(lái)一個(gè)節(jié)點(diǎn)地址

__list_iterator(Node* x)
:_node(x)
{ }

注意迭代器的拷貝構(gòu)造、賦值重載以及析構(gòu)函數(shù)不需要我們自己實(shí)現(xiàn)，編譯器實(shí)現(xiàn)的完全夠用。

拷貝構(gòu)造與賦值重載：因?yàn)閘ist迭代器本身就是一個(gè)自定義類型的指針，都是地址的拷貝與賦予。所以淺拷貝就滿足使用。
析構(gòu)函數(shù)：因?yàn)閘ist迭代器是借助節(jié)點(diǎn)指針訪問(wèn)修改鏈表，節(jié)點(diǎn)是鏈表的，不需要迭代器釋放。

解引用重載

解引用重載（*）

解引用本質(zhì)是根據(jù)地址拿到在這個(gè)地址的有效數(shù)據(jù)

Ref operator*()
{
    return _node->_data;
}

重載

->重載

->本質(zhì)是拿到所求數(shù)據(jù)的地址

Ptr operator->()
{
    return &_node->_data;
}

自增實(shí)現(xiàn)

前置++

++后迭代器指向當(dāng)前位置的下一個(gè)位置，返回指向下一個(gè)位置的迭代器

self& operator++()
{
    _node=_node->_next;
    return *this;
}

后置++

++后迭代器指向當(dāng)前位置的下一個(gè)位置，返回指向之前位置的迭代器,要使用一個(gè)臨時(shí)變量保存++之前的this指針，然后后移_node,返回臨時(shí)變量。

//這塊一定要使用占位符，防止與前置++重命名。
self& operator++(int)
{
    __list_iterator<T> tmp(*this);
    _node=_node->_next;
    return tmp;
}

自減實(shí)現(xiàn)

與++基本一樣，不做解釋。

前置--

self& operator--()
{
    _node=_node->_prev;
    return *this;
}

后置--

self& operator--（int）
{
    __list_iterator<T> tmp(*this);
    _node=_node->_prev;
    return tmp;
}

運(yùn)算符重載

bool operator!=(const self& it)const
{
    return _node!=it._node;
}
 
bool operator==(const self& it)const
{
    return _node==it._node;
}

迭代器失效

以vector為例，當(dāng)我們插入一個(gè)元素時(shí)它的預(yù)分配空間不夠時(shí)，它會(huì)重新申請(qǐng)一段新空間，將原空間上的元素復(fù)制到新的空間上去，然后再把新加入的元素放到新空間的尾部，以滿足vector元素要求連續(xù)存儲(chǔ)的目的。而后原空間會(huì)被系統(tǒng)撤銷或征做他用，于是指向原空間的迭代器就成了類似于“野指針”一樣的東西，指向了一片非法區(qū)域。如果使用了這樣的迭代器會(huì)導(dǎo)致嚴(yán)重的運(yùn)行時(shí)錯(cuò)誤就變得很自然了。這也是許多書上敘述vector在insert操作后“可能導(dǎo)致所有迭代器實(shí)效”的原因。

但是想到這里我不禁想到vector的erase操作的敘述是“會(huì)導(dǎo)致指向刪除元素和刪除元素之后的迭代器失效” ，這里的刪除元素不一定不成功，但一定存在迭代器失效。例：

vector<int> v;//{1,2,3,4,5}
vector<int>::iterator it=v.begin();
while(it!=v.end())
{
    if(*it%2==0)
    {
        v.erase(it);
    }
    it++;
}

所以要避免這種情況，改進(jìn)代碼

vector<int> v;//{1,2,3,4,5}
vector<int>::iterator it=v.begin();
while(it!=v.end())
{
    if(*it%2==0)
    {
        v.erase(it);
    }
    else
        it++;
}

list迭代器失效

list<int> l1;
list<int>::iterator it=l1.begin();
while(it!=l1.end())
{
    if(*it%2==0)
    {
        l1.erase(it);
    }
    else
        ++it;
}

改進(jìn)代碼

list<int> l1;
list<int>::iterator it=l1.begin();
while(it!=l1.end())
{
    if(*it%2==0)
    {
        it=l1.erase(it);
    }
    else
        ++it;
}

歸納迭代器失效的類型

（1）由于容器元素整體“遷移”導(dǎo)致存放原容器元素的空間不再有效，從而使得指向原空間的迭代器失效。

（2）由于刪除元素使得某些元素次序發(fā)生變化使得原本指向某元素的迭代器不再指向希望指向的元素

模擬List

具體下一章講

 template<class T>
    class list
    {
        typedef ListNode<T> Node;
    public:
        typedef __list_iterator<T, T&, T*> iterator;
        typedef __list_iterator<T, const T&, const T*> const_iterator;
        iterator begin()
        {
            return iterator(_head->_next);
        }
?
        iterator end()
        {
            return iterator(_head);
        }
?
        const_iterator begin()const
        {
            return const_iterator(_head->_next);
        }
?
        const_iterator end()const
        {
            return const_iterator(_head);
        }
?
        list()
        {
            _head = new Node();
            _head->_next = _head;
            _head->_prev = _head;
        }
        void push_back(const T& x)
        {
            Node* tail = _head->_prev;
            Node* newnode = new Node(x);
            tail->_next = newnode;
            newnode->_prev = tail;
            newnode->_next = _head;
            _head->_prev = newnode;
        }
?
        void insert(iterator pos, const T& x)
        {
?
        }
        void erase(iterator pos)
        {
?
        }
    private:
        Node* _head;
    };

到此這篇關(guān)于C++模擬實(shí)現(xiàn)List迭代器詳解的文章就介紹到這了,更多相關(guān)C++ List迭代器內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

您可能感興趣的文章: