引言

在STL容器中，list作為經典的雙向鏈表容器，其迭代器設計體現了C++模板編程的精髓。本文將深入探討如何從零開始設計一個符合STL規范的list迭代器，揭示其背后的設計哲學和技術細節。

1、鏈表基礎結構

template <class T>
struct list_node {T data_;list_node<T>* next_;list_node<T>* prev_;list_node(const T& data = T()) : data_(data), next_(nullptr), prev_(nullptr) { }
};

每一個節點包含前驅指針、后繼指針和數據元素，構成雙向鏈表的基礎單元。

2、鏈表迭代器的封裝

list不像vector那樣是一段連續的空間，方便通過直接通過+、-來計算地址位置，因此不能采用原生指針進行typedef，需要將節點類型進行封裝，通過運算符重載來達到移動“迭代器指針”。

2.1 初步封裝迭代器類

template <class T>
struct __list_iterator {typedef list_node<T> node;typedef __list_iterator<T> self;node* node_; // 成員變量，為一個節點的指針__list_iterator(node* node): node_(node) { }// 解引用操作符重載T& operator*() {return node_->data_;}// 后置++操作符重載，完成迭代器的移動self& operator++() {node_ = node_->next_; // 移動到下一個節點return *this;}// !=操作符重載bool operator!=(const self& other) {return node_ != other.node_;}
};

2.2 引入const迭代器

如上述代碼，若實現const迭代器，本能的反映是再封裝一個迭代器類，但這個類與普通迭代器實現是沒有區別的，只是在返回參數上有所改變。而再封裝一個類導致了代碼的冗余，我們是否可以只封裝一個迭代器類，實現const和非const功能呢？

2.2.1 參考STL源代碼

template<class T, class Ref, class Ptr>
struct __list_iterator {typedef __list_iterator<T, T&, T*>             iterator;typedef __list_iterator<T, const T&, const T*> const_iterator;typedef __list_iterator<T, Ref, Ptr>           self;
}

• 從STL源代碼中我們可以看到，list迭代器在設計中，使用了三個模板參數，分別是：
  • 數據類型T
  • 引用數據類型Ref
  • 指針數據類型Ptr

2.2.2 完善迭代器

template <class T, class Ref, class Ptr>
struct __list_iterator {typedef list_node<T> node;typedef __list_iterator<T, Ref, Ptr> self;node* node_; // 成員變量，為一個節點的指針__list_iterator(node* node): node_(node) { }// 解引用操作符重載Ref operator*() {return node_->data_;}// 后置++操作符重載，完成迭代器的移動self& operator++() {node_ = node_->next_; // 移動到下一個節點return *this;}// !=操作符重載bool operator!=(const self& other) {return node_ != other.node_;}// ->操作符重載Ptr operator->() {return &(node_->data_);}
};// typedef迭代器類
typedef __list_iterator<T, T&, T*> iterator;
typedef __list_iterator<T, const T&, const T*> const_iterator;

3、迭代器實現機制

操作類型	失效情況
插入操作	不影響現有迭代器
刪除操作	被刪除元素的迭代器立即失效
合并/轉移操作	被轉移元素的迭代器失效

結語

list迭代器設計體現了C++模板元編程的強大能力，通過精巧的類型系統設計和操作符重載，使得鏈表容器能夠無縫接入STL算法體系。理解其實現原理不僅有助于深入掌握STL工作機制，更能提升我們對迭代器設計模式的認識。