日本免费高清视频-国产福利视频导航-黄色在线播放国产-天天操天天操天天操天天操|www.shdianci.com

學無先后，達者為師

網站首頁 編程語言 正文

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

作者：m0_52012656 ? 更新時間： 2022-06-15 編程語言

概念

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

迭代器是一種行為類似智能指針的對象， 而指針最常見的行為就是內 容提領和成員 訪問。 因此迭代器最重要的行為就是對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;
    };

原文鏈接：https://blog.csdn.net/m0_52012656/article/details/123478610

欄目分類
最近更新