目錄

迭代器

介紹

種類?

本質

介紹

模擬實現

注意點

代碼?

---

迭代器

介紹

在C++中，迭代器（Iterators）是一種用于遍歷容器（如數組、vector、list等）中元素的工具

無論容器的具體實現細節如何,訪問容器中的元素的方法都是統一的,使用者不需要知道具體實現的細節

• 迭代器的概念類似于指針，但迭代器更為通用，可以適用于各種不同類型的容器(且不同對象的迭代器,種類也不同)
• 迭代器在算法函數中也可以使用,這樣可以兼容不同的容器(比如sort,find),就可以使用通用的算法模板

種類?

迭代器分為幾種不同類型，每種類型對應不同的容器特性和訪問方式：

1. 輸入迭代器（Input Iterator）：僅支持從容器中讀取數據，類似于只讀操作。它們一次只能移動一個位置，不允許修改容器的元素。

2. 輸出迭代器（Output Iterator）：僅支持向容器中寫入數據，類似于只寫操作。與輸入迭代器類似，一次只能移動一個位置。

3. 前向迭代器（Forward Iterator）：支持讀取和寫入操作，并且可以多次遍歷容器。每次移動一個位置。

4. 雙向迭代器（Bidirectional Iterator）：與前向迭代器類似，但可以向前和向后移動，每次一個位置。

5. 隨機訪問迭代器（Random Access Iterator）：具有最強大的功能，可以在常量時間內跳轉到容器中的任何位置，支持讀取、寫入和算術操作

• 這幾種迭代器互相有包含關系,比如可以使用雙向迭代器的,也可以使用隨機迭代器

• 

• 不同的迭代器用以支持遍歷不同類型的容器,以及限制了算法函數兼容的容器類型(比如sort就不支持list類型)
• 
• 每個容器都有自己對應的迭代器類型
• 

本質

實際上都是指針,有些容器的迭代器可以直接使用指針(eg:vector),但有些不行(eg: list)

• list的物理空間并不連續,直接使用無法實現++的效果,其他功能也不行
• 因此就需要創建一個類,來規定迭代器的操作

介紹

list是標準模板庫（STL）提供的一個雙向帶頭鏈表容器類

上面有說,list并不支持sort,但list內部有自己的sort

• 雖然是這樣沒錯,但既然不支持,自然有它的道理
• 內部的sort在遇到大數據時,遠不如 "將數據拷貝到vector中,由vector使用sort排序,再將排序后的數據恢復成list"?的效率高
• 當然,小數據的時候就不需要這些麻煩的操作了,這時候內部的sort還是很方便嘟

模擬實現

注意點

• 迭代器封裝+結點封裝(以及進行了重命名,會有各種嵌套)
• 結點類中有前后指針+數據,list類中有頭結點指針+結點個數,迭代器是結點指針包裝后的產物

• const迭代器的實現 (模板參數)
• 兩種迭代器 在list類中傳參+重命名 實例化,可以傳指針構造,也有拷貝構造

• ' -> '符號的重載?(->重載函數返回指針,因此訪問迭代器的實際語法應為 it -> ->begin(),是編譯器簡化成了只有一個->)
• list的多種拷貝構造

代碼?

#include <iostream>
#include <assert.h>
#include <string>using namespace std;namespace bit
{// List的節點類template <class T>struct ListNode // struct默認公有(因為不會有人去訪問結點成員的){typedef ListNode<T> *PNode;ListNode(const T &val = T()): _ppre(nullptr), _pnext(nullptr), _val(val){};PNode _ppre;PNode _pnext;T _val;};// List的迭代器類 -- 因為無法直接使用指針作為迭代器,需要手動添加功能template <class T, class Ref, class Ptr> // ref用于標記*時對象的const屬性,ptr用于標記->時返回對象的const屬性class ListIterator{public:typedef ListNode<T> *PNode;             // 指針重命名typedef ListIterator<T, Ref, Ptr> Self; // 迭代器重命名PNode _pNode; // 將指針作為迭代器的底層public:ListIterator(PNode pnode = nullptr): _pNode(pnode){};ListIterator(const Self &l): _pNode(l._pNode){};T &operator*(){return _pNode->_val;}T *operator->(){return &(_pNode->_val);}Self &operator++(){_pNode = _pNode->_pnext;return (*this);}Self operator++(int){Self tmp(*this);_pNode = _pNode->_pnext;return tmp;}Self &operator--(){_pNode = _pNode->_ppre;return (*this);}Self operator--(int){Self tmp(*this);_pNode = _pNode->_ppre;return tmp;}bool operator!=(const Self &l){return _pNode != l._pNode;}bool operator==(const Self &l){return _pNode == l._pNode;}};// list類template <class T>class mylist{typedef ListNode<T> Node;typedef Node *PNode;public: // 兩種迭代器typedef ListIterator<T, T &, T *> iterator;typedef ListIterator<T, const T &, const T &> const_iterator;public:// List的構造mylist(){CreateHead();}mylist(int n, const T &value = T()){CreateHead();PNode p = _pHead;for (size_t i = 0; i < n; ++i){push_back(value);}_size += n;}template <class Iterator>mylist(Iterator first, Iterator last){CreateHead();while (first != last){push_back(*first);++first;}}mylist(const mylist<T> &l){CreateHead();for (auto c : l){push_back(c);}}mylist<T> &operator=(const mylist<T> l){swap(l);return (*this);}~mylist(){// clear();// delete[] _pHead;while (!empty()){erase(begin());}}// List Iteratoriterator begin(){return iterator(_pHead->_pnext);}iterator end(){return iterator(_pHead);}const_iterator begin() const{return const_iterator(_pHead->_pnext);}const_iterator end() const{return const_iterator(_pHead);}// List Capacitysize_t size() const{return _size;}bool empty() const{return _size == 0;}// List AccessT &front(){return *begin();}const T &front() const{return *begin();}T &back(){return *(--end());}const T &back() const{return *(--end());}// List Modifyvoid push_back(const T &val){insert(end(), val);}void pop_back(){erase(--end());}void push_front(const T &val){insert(begin(), val);}void pop_front(){erase(begin());}// 在pos位置前插入值為val的節點iterator insert(iterator pos, const T &val){PNode cur = pos._pNode;PNode pre = cur->_ppre;PNode newnode = new Node(val);newnode->_pnext = cur;pre->_pnext = newnode;cur->_ppre = newnode;newnode->_ppre = pre;_size++;return newnode;}// 刪除pos位置的節點，返回該節點的下一個位置iterator erase(iterator pos){PNode cur = pos._pNode;PNode pre = cur->_ppre, next = cur->_pnext;pre->_pnext = cur->_pnext;cur->_pnext->_ppre = pre;delete cur;--_size;return next;}void clear(){PNode cur = _pHead->_pnext;while (cur != _pHead){PNode tmp = cur;cur = cur->_pnext;delete tmp;}_size = 0;// iterator it = begin();// while (it != end())// {//     it = erase(it);// }}void swap(mylist<T> &l){std::swap(_pHead, l._pHead);std::swap(_size, l._size);}private:void CreateHead(){_pHead = new Node;_pHead->_pnext = _pHead;_pHead->_ppre = _pHead;_size = 0;}PNode _pHead;size_t _size;};
};