C++模擬實現List迭代器詳解

2022-04-15 16:00:19

概念

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

迭代器是一種行為類似智慧指標的物件，而指標最常見的行為就是內容提領和成員存取。因此迭代器最重要的行為就是對operator*和operator->進行過載。

STL的中心思想在於：將資料容器和演演算法分開，彼此獨立設計，最後再以一貼膠合劑（ iterator）將它們撮合在一起。STL的迭代器是一個可遍歷STL容器全部或者部分資料

迭代器使用

我們可以使用迭代器存取修改連結串列元素

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

2.我們有些函數介面需要傳迭代器，例如：

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);

迭代器模擬實現

迭代器的大體結構

//連結串列節點
template<class T>
struct ListNode {
    ListNode<T>* _next;
    ListNode<T>* _prev;
    T _data;
    //構造節點值
    ListNode(const T& data = T())
        :_next(nullptr)
        ,_prev(nullptr)
        ,_data(data)
    {}
};

///迭代器
//T為list資料型別，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;//節點指標
    
    //接下來實現的函數都是在這個位置
};

建構函式

一般都會傳過來一個節點地址

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

注意迭代器的拷貝構造、賦值過載以及解構函式不需要我們自己實現，編譯器實現的完全夠用。

拷貝構造與賦值過載：因為list迭代器本身就是一個自定義型別的指標，都是地址的拷貝與賦予。所以淺拷貝就滿足使用。
解構函式：因為list迭代器是藉助節點指標存取修改連結串列，節點是連結串列的，不需要迭代器釋放。

解除參照過載

解除參照過載（*）

解除參照本質是根據地址拿到在這個地址的有效資料

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

過載

->過載

->本質是拿到所求資料的地址

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

自增實現

前置++

++後迭代器指向當前位置的下一個位置，返回指向下一個位置的迭代器

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

後置++

++後迭代器指向當前位置的下一個位置，返回指向之前位置的迭代器,要使用一個臨時變數儲存++之前的this指標，然後後移_node,返回臨時變數。

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

自減實現

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

前置--

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

後置--

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

運運算元過載

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

迭代器失效

以vector為例，當我們插入一個元素時它的預分配空間不夠時，它會重新申請一段新空間，將原空間上的元素複製到新的空間上去，然後再把新加入的元素放到新空間的尾部，以滿足vector元素要求連續儲存的目的。而後原空間會被系統復原或徵做他用，於是指向原空間的迭代器就成了類似於“野指標”一樣的東西，指向了一片非法區域。如果使用了這樣的迭代器會導致嚴重的執行時錯誤就變得很自然了。這也是許多書上敘述vector在insert操作後“可能導致所有迭代器實效”的原因。

但是想到這裡我不禁想到vector的erase操作的敘述是“會導致指向刪除元素和刪除元素之後的迭代器失效” ，這裡的刪除元素不一定不成功，但一定存在迭代器失效。例：

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

所以要避免這種情況，改程序式碼

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

改程序式碼

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

歸納迭代器失效的型別

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

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

模擬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;
    };

到此這篇關於C++模擬實現List迭代器詳解的文章就介紹到這了,更多相關C++ List迭代器內容請搜尋it145.com以前的文章或繼續瀏覽下面的相關文章希望大家以後多多支援it145.com！