目錄

一.list的介紹

二.list的接口實現

1.結點

2.list結構

3.迭代器?

（1）begin

（2）end

?4.修改

（1）insert

（2）push_back

（3）push_front

（4）erase

（5）pop_back

（6）pop_front

（7）swap

（8）clear?

5.默認成員函數

（1）構造函數

（2）拷貝構造函數

（3）賦值重載

（4）析構函數

三.代碼總覽

list.h

test.cpp

---

?

一.list的介紹

源文檔

二.list的接口實現

1.結點

template<class T>
struct list_node
{list_node* _prev;list_node* _next;T _data;// 由于數據類型由模板參數決定，所以缺省值給匿名對象list_node(const T& x = T()):_prev(nullptr),_next(nullptr),_data(x){}
};

? ? ? ? 用一個結構體來封裝結點，我們手動寫默認構造函數以便在申請結點時調用。

2.list結構

template<class T>
class list
{// 結點typedef list_node<T> Node;
public:// 在類域外訪問// 迭代器typedef list_iterator<T, T&, T*> iterator;typedef list_iterator<T, const T&, const T*> const_iterator;
private:// 哨兵位Node* _head;// 有效數據個數size_t _size = 0;
};

3.迭代器?

? ? ? ? list的迭代器與之前的string和vector不同，由于list的數據存儲空間并不是連續的，所以我們無法再繼續用原生指針來實現迭代器類型，++，解引用等操作并不能實現想要達到的目的，所以我們需要重載這些操作符，并將迭代器封裝成一個新的類。

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){}// 比較指向的結點是否相同bool operator!=(const Self& s){return _node != s._node;}bool operator==(const Self& s){return _node == s._node;}// Ref來控制iterator與const_iterator// Ref->T& -- iterator;// Ref->const T& -- const_iterator;// 獲取結點存儲的數據Ref operator*(){return _node->_data;}// 使迭代器指向下一個結點Self& operator++(){_node = _node->_next;return *this;}// 后置++Self operator++(int){Self tmp(*this);_node = _node->_next;return tmp;}// 使迭代器指向前一個結點Self& operator--(){_node = _node->_prev;return *this;}// 前置--Self operator--(int){Self tmp(*this);_node = _node->_prev;return tmp;}// 為了可讀性進行特殊處理 it->->_a1 被優化為 it->_a1// Ptr來控制iterator與const_iterator// Ptr->T* -- iterator// Ptr->const T* -- const_iteratorPtr operator->(){return &_node->_data;}
};

（1）begin

iterator begin()
{return iterator(_head->_next);
}

const_iterator begin() const
{return const_iterator(_head->_next);
}

（2）end

iterator end()
{// 返回尾結點的下一個結點，也就是哨兵位return iterator(_head);
}

const_iterator begin() const
{return const_iterator(_head->_next);
}

?4.修改

（1）insert

void insert(iterator pos, const T& x)
{// 申請新結點的空間，調用構造Node* newnode = new Node(x);// 斷開舊連接，連接新結點Node* cur = pos._node;Node* prev = cur->_prev;// prev newnode curnewnode->_prev = prev;newnode->_next = cur;prev->_next = newnode;cur->_prev = newnode;++_size;
}

（2）push_back

void push_back(const T& x)
{//Node* newnode = new Node(x);//Node* tail = _head->_prev;tail newnode _head//newnode->_prev = tail;//newnode->_next = _head;//tail->_next = newnode;//_head->_prev = newnode;insert(end(), x);
}

（3）push_front

void push_front(const T& x)
{insert(begin(), x);
}

（4）erase

iterator erase(iterator pos)
{Node* cur = pos._node;Node* prev = cur->_prev;Node* next = cur->_next;prev->_next = next;next->_prev = prev;delete cur;--_size;//return iterator(next);// 為防止迭代器失效，返回刪除后的下一個結點的迭代器// 單參數構造函數支持隱式轉換return next;
}

? ? ? ? 為防止erase后，pos依然指向被delete的結點從而導致迭代器失效，erase返回指向下一個結點的迭代器。?

（5）pop_back

void pop_back()
{erase(--end());
}

（6）pop_front

void pop_front()
{erase(begin());
}

（7）swap

void swap(list<T>& lt)
{std::swap(_head, lt._head);std::swap(_size, lt._size);
}

? ? ? ? 交換哨兵位即可交換兩個list。

（8）clear?

void clear()
{auto it = begin();while (it != end()){it = erase(it);}
}

? ? ? ? 除了哨兵位，其他結點逐個erase。?

5.默認成員函數

（1）構造函數

空list申請哨兵位：empty_init

// 空list申請哨兵位
void empty_init()
{_head = new Node;_head->_prev = _head;_head->_next = _head;
}// 無參數構造
list()
{//_head = new Node;//_head->_prev = _head;//_head->_next = _head;empty_init();
}// initializer_list構造
list(std::initializer_list<T> il)
{empty_init();for (auto& e : il){push_back(e);}
}

（2）拷貝構造函數

list(const list<T>& lt)
{empty_init();for (auto& e : lt){push_back(e);}
}

? ? ? ? 先申請哨兵位，再逐個尾插即可。

（3）賦值重載

list<T>& operator=(list<T> lt)
{swap(lt);return *this;
}

（4）析構函數

~list()
{clear();delete _head;_head = nullptr;
}

三.代碼總覽

list.h

#include<iostream>
#include<initializer_list>namespace my_list
{template<class T>struct list_node{list_node* _prev;list_node* _next;T _data;// 由于數據類型由模板參數決定，所以缺省值給匿名對象list_node(const T& x = T()):_prev(nullptr),_next(nullptr),_data(x){}};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){}// 比較指向的結點是否相同bool operator!=(const Self& s){return _node != s._node;}bool operator==(const Self& s){return _node == s._node;}// Ref來控制iterator與const_iterator// Ref->T& -- iterator;// Ref->const T& -- const_iterator;// 獲取結點存儲的數據Ref operator*(){return _node->_data;}// 使迭代器指向下一個結點Self& operator++(){_node = _node->_next;return *this;}// 后置++Self operator++(int){Self tmp(*this);_node = _node->_next;return tmp;}// 使迭代器指向前一個結點Self& operator--(){_node = _node->_prev;return *this;}// 前置--Self operator--(int){Self tmp(*this);_node = _node->_prev;return tmp;}// 為了可讀性進行特殊處理 it->->_a1 被優化為 it->_a1// Ptr來控制iterator與const_iterator// Ptr->T* -- iterator// Ptr->const T* -- const_iteratorPtr operator->(){return &_node->_data;}};template<class T>class list{// 結點typedef list_node<T> Node;public:// 迭代器typedef list_iterator<T, T&, T*> iterator;typedef list_iterator<T, const T&, const T*> const_iterator;// 空list申請哨兵位void empty_init(){_head = new Node;_head->_prev = _head;_head->_next = _head;}// 無參數構造list(){//_head = new Node;//_head->_prev = _head;//_head->_next = _head;empty_init();}// initializer_list構造list(std::initializer_list<T> il){empty_init();for (auto& e : il){push_back(e);}}list(const list<T>& lt){empty_init();for (auto& e : lt){push_back(e);}}// lt2 = lt1list<T>& operator=(list<T> lt){swap(lt);return *this;}~list(){clear();delete _head;_head = nullptr;}void clear(){auto it = begin();while (it != end()){it = erase(it);}}void swap(list<T>& lt){std::swap(_head, lt._head);std::swap(_size, lt._size);}size_t size(){return _size;}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);}void push_back(const T& x){//Node* newnode = new Node(x);//Node* tail = _head->_prev;tail newnode _head//newnode->_prev = tail;//newnode->_next = _head;//tail->_next = newnode;//_head->_prev = newnode;insert(end(), x);}void push_front(const T& x){insert(begin(), x);}void pop_back(){erase(--end());}void pop_front(){erase(begin());}void insert(iterator pos, const T& x){// 申請新結點的空間，調用構造Node* newnode = new Node(x);// 斷開舊連接，連接新結點Node* cur = pos._node;Node* prev = cur->_prev;// prev newnode curnewnode->_prev = prev;newnode->_next = cur;prev->_next = newnode;cur->_prev = newnode;++_size;}iterator erase(iterator pos){Node* cur = pos._node;Node* prev = cur->_prev;Node* next = cur->_next;prev->_next = next;next->_prev = prev;delete cur;--_size;//return iterator(next);// 為防止迭代器失效，返回刪除后的下一個結點的迭代器// 單參數構造函數支持隱式轉換return next;}private:// 哨兵位Node* _head;// 有效數據個數size_t _size = 0;};
}

test.cpp

#include"list.h"
using namespace std;namespace my_list
{void test_list1(){list<int> lt1;lt1.push_back(1);lt1.push_back(2);lt1.push_back(3);lt1.push_back(4);list<int>::iterator it = lt1.begin();while (it != lt1.end()){*it += 10;cout << *it << " ";++it;}cout << endl;lt1.push_back(1);lt1.push_back(2);lt1.push_front(3);lt1.push_front(4);for (auto& e : lt1){cout << e << " ";}cout << endl;lt1.pop_back();lt1.pop_front();for (auto& e : lt1){cout << e << " ";}cout << endl;cout << lt1.size() << endl;}void test_list2(){list<int> lt1;lt1.push_back(1);lt1.push_back(2);lt1.push_front(3);lt1.push_front(4);for (auto& e : lt1){cout << e << " ";}cout << endl;list<int> lt2(lt1);for (auto& e : lt1){cout << e << " ";}cout << endl;list<int> lt3;lt3 = lt1;for (auto& e : lt1){cout << e << " ";}}struct AA{int _a1;int _a2;AA(int a1 = 1, int a2 = 1):_a1(a1), _a2(a2){}};void test_list3(){list<int> lt1 = { 1,2,3,4 };for (auto& e : lt1){cout << e << " ";}cout << endl;list<AA> lt2 = { {1,1},{2,2},{3,3},{4,4} };list<AA>::iterator it = lt2.begin();while (it != lt2.end()){//cout << (*it)._a1 << ":" << (*it)._a2 << endl;//cout << it->->_a1 << ":" << it->->_a2 << endl;cout << it->_a1 << ":" << it->_a2 << endl;++it;}list<AA>::iterator lit = lt2.begin();while (lit != lt2.end()){cout << lit.operator->()->_a1 << ":" << lit.operator->()->_a2 << endl;++lit;}}
}int main()
{my_list::test_list3();return 0;
}