list源碼剖析

建議先看c++STL-list的使用和迭代器-CSDN博客。

STL中某版本的list的結點原型：

template <class T>
struct __list_node{typedef void* void_pointer;void_pointer next;voie_pointer prev;T data;
}

void 后期還需要強轉。

定義結點用struct，可以換成class，但要另一個類將這個類封裝成友元，因為class默認私有。

__list_node：__表示內部的實現，算是項目上的約定。

之后list類的成員：

template <class T, class Alloc = alloc>
class list {
protected:typedef void* void_pointer;//結點類型typedef __list_node<T> list_node;//空間配置器typedef simple_alloc<list_node, Alloc> list_node_allocator;
public://類型typedef T value_type;//類型指針typedef value_type* pointer;typedef const value_type* const_pointer;//類型引用typedef value_type& reference;typedef const value_type& const_reference;typedef list_node* link_type;//結點數和引用數typedef size_t size_type;typedef ptrdiff_t difference_type;//迭代器typedef __list_iterator<T, T&, T*>             iterator;typedef __list_iterator<T, const T&, const T*> const_iterator;//...
protected:link_type node;
}

看代碼（容器）先看構造函數，初始化決定初始結構是什么樣的。

template<class T>
class list {list() { empty_initialize(); }//空結點初始化//證明鏈表在生成時會先//生成哨兵衛結點void empty_initialize() {node = get_node();node->next = node;node->prev = node;}link_type get_node() { return list_node_allocator::allocate(); }link_type create_node(const T& x) {link_type p = get_node();__STL_TRY{//調用定位newconstruct(&p->data, x);}__STL_UNWIND(put_node(p));return p;}void put_node(link_type p) { list_node_allocator::deallocate(p); }iterator begin() { return (link_type)((*node).next); }iterator end() { return node; }
};

allocate是空間配置器，也就是說get_node是獲取一個新的結點。

list的迭代器功能比string和vector復雜，因此庫里的list將迭代器封裝成了一個類，通過模板參數的不同來區分不同類型的迭代器。

//Ref,即reference，引用
//Ptr,即pointer，指針
//表示引用類型和指針類型也作為模板參數的一部分
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;typedef bidirectional_iterator_tag iterator_category;typedef T value_type;typedef Ptr pointer;typedef Ref reference;typedef __list_node<T>* link_type;typedef size_t size_type;typedef ptrdiff_t difference_type;link_type node;__list_iterator(link_type x) : node(x) {}__list_iterator() {}__list_iterator(const iterator& x) : node(x.node) {}bool operator==(const self& x) const { return node == x.node; }bool operator!=(const self& x) const { return node != x.node; }reference operator*() const { return (*node).data; }#ifndef __SGI_STL_NO_ARROW_OPERATORpointer operator->() const { return &(operator*()); }
#endif /* __SGI_STL_NO_ARROW_OPERATOR */self& operator++() {node = (link_type)((*node).next);return *this;}self operator++(int) {self tmp = *this;++* this;return tmp;}self& operator--() {node = (link_type)((*node).prev);return *this;}self operator--(int) {self tmp = *this;--* this;return tmp;}
};

end()是尾結點的迭代器，begin()是end()->next。

list模擬實現

list的本質是封裝加運算符重載。

因此list由三部分組成：

1. 結點類__list_node。
2. 迭代器類__list_iterator。
3. 鏈表本體list。

__list_node，考慮到庫中的結點給的前驅和后綴都是void*，正式使用時還要強制轉換，于是這里嘗試做改進：

template<class T>
struct __list_node {//指針域typedef __list_node* pointer;pointer next;pointer view;//數據域T data;
};

為了能做到迭代器重載const修飾和非const修飾的迭代器，參考庫中的__list_iterator，需要設計成三個模板參數的類模板，自己改進了看起來比較冗余的部分：

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;typedef __list_node<T>* link_node;link_node node;
};

最后是list本體：

class list {
public:typedef __list_iterator<T, T&, T*> iterator;typedef __list_iterator<T, const T&, const T*> const_iterator;typedef __list_node<T> Node;//...
private:Node* node;
};

list構造函數

構造函數選擇這幾個常用的實現：

list ();list (size_t n, const T& val = T());template <class InputIterator>list (InputIterator first, InputIterator last);list (const list& x);

默認構造函數用于生成哨兵衛結點。

要使用list (InputIterator first, InputIterator last);，則需要再加上一個
list (int n, const T& val = T());，防止整型被識別成迭代器。

拷貝構造函數

同樣可以創造新的頭結點，并遍歷鏈表（范圍for）進行尾插。

賦值重載

• 清理鏈表，保留頭結點，之后遍歷形參的鏈表即可。
• 同樣可以交換哨兵衛結點。

迭代器 iterator

迭代器用3個模板參數的模板類封裝。

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;typedef __list_node<T>* link_node;link_node node;
};

迭代器需要支持的操作：

1. 構造能指向指定結點的構造函數。
2. 拷貝構造函數。
3. 解引用操作*，返回迭代器指向的結點的數據域。要求數據域能讀、能寫。
4. 解引用操作->，返回迭代器指向的結點的數據域，當數據域也是自定義類型時，返回指針。
5. ==，用于判斷兩個迭代器指向的結點是否相等。
6. !=，用于判斷兩個迭代器指向的結點是否不等。
7. ++，當前迭代器指向后繼結點。
8. --，當前迭代器指向前驅結點。
9. begin()，返回哨兵衛結點的后一個結點。
10. end()，返回哨兵衛結點。

訪問結點數size和判空

返回除哨兵衛結點外的結點數_size。

判斷_size是否為0，或哨兵衛的兩個指針是否都指向自己。

尾插 push_back

void push_back(const T& val);

在end()前插入結點即可。可以另外實現，也可以復用insert。

頭插 push_front

void push_front(const T& val);

在begin()前插入結點即可。可以另外實現，也可以復用insert。

尾刪pop_back

刪除--end()結點即可。

頭刪pop_front

刪除begin()結點即可。

插入 insert

iterator insert(iterator pos, const T& val);

在迭代器pos前插入以val為數據的新結點。

這樣在end()前插入結點相當于是尾插，在begin()前插入結點相當于是頭插。

鏈表的迭代器不受擴容的影響，不會出現迭代器失效的問題，給不給返回值都可以。這里選擇給。

刪除 erase

iterator erase(iterator pos);

刪除pos迭代器指向的結點。

刪除后pos迭代器必定失效，因此需要返回下一個結點的迭代器。

清空clear和析構函數

void clear();

刪除除哨兵衛結點外的所有結點。

析構函數在clear的基礎上，進一步清理哨兵衛結點。

訪問結點

用一個隊首front和隊尾back訪問頭、尾結點即可。

需要注意end()在這里設定為哨兵衛結點，一般情況下不可訪問。

參考程序

某.h文件：

#pragma once
#include<cassert>namespace mystd {template<class Type>void swap(Type& a, Type& b) {Type tmp = a;a = b;b = tmp;}template<class T>struct __list_node {//指針域typedef __list_node* pointer;pointer next;pointer view;//數據域T data;__list_node(const T& x = T()):data(x), next(nullptr), view(nullptr) {}};//三個模板參數分別為：存儲的數據類型//存儲的數據的引用、存儲的數據空間的地址類型template<class T, class Ref, class Ptr>struct __list_iterator {typedef __list_iterator<T, Ref, Ptr> self;typedef __list_node<T>* link_node;link_node node;__list_iterator<T, Ref, Ptr>(link_node x = nullptr):node(x) {}__list_iterator<T, Ref, Ptr>(const self& x): node(x.node) {}Ref operator*() {return node->data;}//為了支持T為自定義類型的情況//返回迭代器指向的結點的數據域的地址Ptr operator->() {return &node->data;}bool operator==(const self& x) const{return node == x.node;}bool operator!=(const self& x) const {return node != x.node;}self& operator++() {node = node->next;return *this;}self& operator--() {node = node->view;return *this;}self operator++(int) {self tmp(*this);node = node->next;return tmp;}self operator--(int) {self tmp(*this);node = node->view;return tmp;}};template<class T>class list {public:typedef __list_iterator<T, T&, T*> iterator;typedef __list_iterator<T, const T&, const T*> const_iterator;typedef __list_node<T> Node;//默認構造函數list<T>() {node = get_node();node->next = node->view = node;_size = 0;}//構造函數list<T>(int n, const T& val = T()) {node = get_node();node->next = node->view = node;size_t tmp = n;for (size_t i = 0; i < tmp; i++)push_back(val);}list<T>(size_t n, const T& val = T()) {node = get_node();node->next = node->view = node;size_t tmp = n;for (size_t i = 0; i < tmp; i++)push_back(val);}template<class Inputiterator>list<T>(Inputiterator first, Inputiterator second) {node = get_node();node->next = node->view = node;while (first != second) {push_back(*first);first++;}}//拷貝構造函數list<T>(const list<T>& obj) {node = get_node();node->next = node->view = node;for (const auto& x : obj)this->push_back(x);}//賦值重載list<T>& operator=(list<T>obj) {mystd::swap(this->node, obj.node);mystd::swap(this->_size, obj._size);return *this;}//析構函數~list() {clear();delete node;}//迭代器iterator begin() {return iterator(node->next);}iterator end() {return iterator(node);}const_iterator begin() const {return const_iterator(node->next);}const_iterator end() const {return const_iterator(node);}//結點數size_t size()const {return _size;}//判斷是否為空bool empty()const {return this->node->next == this->node&& this->node->view == this->node;}//頭插void push_front(const T& val) {insert(begin(), val);}//尾插void push_back(const T& val) {insert(end(), val);}//尾刪void pop_back() {erase(--end());}//頭刪void pop_front() {erase(begin());}//插入iterator insert(iterator pos, const T& val) {Node* cur = pos.node->view;Node* newnode = get_node(val);newnode->next = cur->next;newnode->view = cur;cur->next = newnode;newnode->next->view = newnode;++_size;return iterator(newnode);}//刪除iterator erase(iterator pos) {assert(pos != end());Node* del = pos.node, * cur = pos.node->next;del->view->next = del->next;del->next->view = del->view;delete del;--_size;return iterator(cur);}//清空void clear() {auto it = begin();while (it != end()) {it = erase(it);}}//訪問T& front() {return node->next->data;}T& back() {return node->view->data;}private:Node* get_node(const T& x = T()) {Node* tmp = new Node(x);tmp->next = tmp->view = nullptr;//這里建議賦值tmpreturn tmp;}template<class Type>friend void mystd::swap(Type&, Type&);Node* node;//哨兵衛size_t _size;//結點數};
}