list模拟实现（部分）

1.没有实现const迭代器。 

#include<iostream>
using namespace std;
namespace test {template<class T>struct list_node {T _val;list_node<T> * _prev;list_node<T> * _next;list_node(const T& val = T()) :_val(val), _prev(nullptr), _next(nullptr) {}};template<class T>struct __list_iterator {typedef list_node<T> Node;Node* _node;__list_iterator(Node* node) :_node(node) {}//T& operator*() {return this->_node->_val;}__list_iterator<T>& operator++() {this->_node = this->_node->_next;return *this;}__list_iterator<T> operator++(int) {__list_iterator<T> tmp(*this);_node = _node->_next;return tmp;}bool operator!=(const __list_iterator<T>& it) {return this->_node != it._node;}bool operator==(const __list_iterator<T>& it) {return this->_node == it._node;}};template<class T>class list {public:typedef __list_iterator<T> iterator;list() {//Node* p = new Node;//new Node()?//p->_next = _head;//p->_prev = _head;_head = new Node;_head->_next = _head;_head->_prev = _head;}iterator begin() {return _head->_next;}iterator end() {return _head;}~list() {}void push_back(const T& val) {Node* p = new Node(val);Node* tail = _head->_prev;tail->_next = p;p->_prev = tail;p->_next = _head;_head->_prev = p;}void pop_back() {Node* p = this->_head->_prev;p->_prev->_next = _head;_head->_prev = p->_prev;delete p;}void insert(iterator pos, const T& val) {Node* newnode = new Node(val);Node* p = pos._node;//只能使用点而不能用->，原因如下p->_prev->_next = newnode;newnode->_prev = p->_prev;p->_prev = newnode;newnode->_next = p;}void erase(iterator pos) {Node* p = pos._node;//. not -> 因为iterator没有重载后者p->_prev->_next = p->_next;p->_next->_prev = p->_prev;delete p;}private: typedef list_node<T> Node;//先写这个Node* _head;//再写这个，否则_head类型不明确};void test() {list<int> lt;lt.push_back(2);lt.push_back(5);lt.push_back(72);lt.push_back(585);lt.push_back(575);for (auto& e : lt) {cout << e << " ";}cout << endl;auto it = lt.begin();lt.insert(++it,8989);lt.erase(lt.begin());lt.erase(++lt.begin());list<int>::iterator itt = lt.begin();while (itt != lt.end()) {std::cout << *itt << " ";++itt;}std::cout << std::endl;}
}int main() {test::test();
}

2.已经实现const迭代器但没有使用双模板参数来减少代码冗余。并附加详细注释。

#include<iostream>
using namespace std;
namespace test
{template<class T>struct list_node//list中的node，一个node包含一个值和两个指针。{list_node<T>* _next;list_node<T>* _prev;T _val;list_node(const T& val = T())//你提供了val我们就用你的，你没提供我就调用T();:_next(nullptr), _prev(nullptr), _val(val){}};template<class T>struct __list_iterator//我们对于迭代器做了封装（这就是容器，只暴露迭代器，你使用它来访问），因为他已经不再像vector<内置类型>那样（typedef T* iterator;list存储不连续且一个node包含三个部分）{typedef list_node<T> Node;//为了这个struct内好写，我们将节点类型typedef以下，方便下面实现类内成员函数Node* _node;//迭代器内部只有一个成员即指向list的节点的指针_node;__list_iterator(Node* node)//对于迭代器的初始化就是对于这个指针的初始化:_node(node){}T& operator*()//*it就是it.operator*()，拿到val，返回类型的引用，因为走出这个函数这个_node指向的_val还在{return _node->_val;}__list_iterator<T>& operator++()//前置++,++it的时候就是it.operator++(){_node = _node->_next;return *this;}__list_iterator<T> operator++(int)//后置++，it++就是it.operator(int){__list_iterator<T> tmp(*this);_node = _node->_next;return tmp;}//注意后置和前置++返回类型不同，返回的都还是迭代器，但是一个是引用。//前置++： 为了实现链式操作，例如 ++it = 10;，需要返回一个左值，以便赋值。//后置++： 为了返回自增前的值，需要创建一个临时对象来保存原来的值，然后返回这个临时对象的副本。//前置++返回引用，可以支持链式操作，例如 ++it = 10;// 如果后置++也返回引用，那么 it++ = 10; 的含义就会变得模糊，到底是给自增前的迭代器赋值，还是给自增后的迭代器赋值？//所以前置++返回引用，方便我们修改，后置++返回一个副本，这个副本是自增前的值，方便我们再用以下，其实真实的已经改变了bool operator!=(const __list_iterator<T>& it)//while(it!=lt.end())就是it.!=(lt.end()）{return _node != it._node;}bool operator==(const __list_iterator<T>& it){return _node == it._node;}};template<class T>//const的迭代器，指向的迭代器不能修改struct __list_const_iterator{typedef list_node<T> Node;Node* _node;__list_const_iterator(Node* node):_node(node){}const T& operator*()//const迭代器返回const引用即可：(*it)+=10;这种就不能用了，//注意const不能加在最后边，因为那样就表明迭代器不能被修改了，即*this也就是调用这个函数的对象（迭代器）//但是我们知道迭代器是要修改的，只是迭代器的指向不能修改，所以我们在返回类型这里添加const！！！{return _node->_val;}__list_const_iterator<T>& operator++(){_node = _node->_next;return *this;}__list_const_iterator<T> operator++(int){__list_const_iterator<T> tmp(*this);_node = _node->_next;return tmp;}bool operator!=(const __list_const_iterator<T>& it){return _node != it._node;}bool operator==(const __list_const_iterator<T>& it){return _node == it._node;}};template<class T>class list{typedef list_node<T> Node;//list的节点我不希望任何人动.所以我private//typedef的作用1：迭代器各个容器之间都用iterator这个名字，但因为我们都在命名空间std中，所以会冲突，//所以使用了typedef来将__list_iterator<T>来重命名为iterator，这样我们自己可以使用这个名字，//而且也防止我们直接定义一个名字叫做iterator的类造成的冲突问题public:typedef __list_iterator<T> iterator;//iterator是暴露给外部的接口，其他人可以使用它操作这个list，我public，并typedef方便使用typedef __list_const_iterator<T> const_iterator;//注意const迭代器不是typedef const __list_iterator<T> iterator;后者迭代器不得修改了//这样设计有点冗余，库中使用了多个模板参数iterator begin()//这些下面都是list的对象也就是一个一个链表可以调用的函数，比如lt.begin() lt.end(){//return _head->_next;return iterator(_head->_next);//因为单参数的构造函数具有隐式类型转换功能，所以也可以像上面写//也可以写全，return this->_head->_next;}iterator end(){return _head;//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->_prev = _head;_head->_next = _head;}~list(){//...}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 pop_back() {Node* p = this->_head->_prev;p->_prev->_next = _head;_head->_prev = p->_prev;delete p;}void insert(iterator pos, const T& val) {Node* newnode = new Node(val);Node* p = pos._node;//只能使用点而不能用->，原因如下p->_prev->_next = newnode;newnode->_prev = p->_prev;p->_prev = newnode;newnode->_next = p;}void erase(iterator pos) {Node* p = pos._node;//. not -> 因为iterator没有重载后者p->_prev->_next = p->_next;p->_next->_prev = p->_prev;delete p;}private:Node* _head;//一个list，最重要的成员就是头指针（一个指向node的指针）};void Print(const list<int>& lt) {list<int>::const_iterator it = lt.begin();//这里你再使用list<int>::iterator it = lt.begin();就不行了，因为我们const引用了lt，它调用了const的begin方法，//const begin方法返回const的引用，你却将它赋给了非const的iterator，这是权限的放大while (it != lt.end()) {//同上，这里不能再对(*it)++;因为*it返回const引用，你不得对他自增cout << *it << " ";it++;}cout << endl;}void test_list1(){list<int> lt;lt.push_back(1);lt.push_back(2);lt.push_back(3);lt.push_back(4);list<int>::iterator it = lt.begin();//等号右侧是一个临时的迭代器对象，左侧是一个迭代器对象，所以底层调用了默认的拷贝构造（浅拷贝）//迭代器对象不能有析构函数，不能迭代器析构时把list的node给析构了//所以这两个对象都指向begin，但是析构两次没事（我们的析构是空的while (it != lt.end()){(*it) += 1;cout << *it << " ";++it;}cout << endl;lt.erase(lt.begin()++);lt.insert(++lt.begin(), 852);lt.insert(++lt.begin(), 852);lt.insert(++lt.begin(), 852);for (auto e : lt){cout << e << " ";}cout << endl << endl;Print(lt);}
}int main() {test::test_list1();
}
//由于上述代码存在冗余：const的迭代器和普通迭代器只是operator*这个函数的返回值不同，其他一样。所以我们可以考虑使用两个模板参数；

3.两个模板参数来缩减代码：

#include<iostream>
using namespace std;
namespace test
{template<class T>struct list_node{list_node<T>* _next;list_node<T>* _prev;T _val;list_node(const T& val = T()):_next(nullptr), _prev(nullptr), _val(val){}};template<class T,class Ref>struct __list_iterator{typedef list_node<T> Node;typedef __list_iterator<T, Ref> self;Node* _node;__list_iterator(Node* node):_node(node){}Ref operator*(){return _node->_val;}self& operator++(){_node = _node->_next;return *this;}self operator++(int){self tmp(*this);_node = _node->_next;return tmp;}bool operator!=(const self& it){return _node != it._node;}bool operator==(const self& it){return _node == it._node;}};template<class T>class list{typedef list_node<T> Node;public:typedef __list_iterator<T,T&> iterator;typedef __list_iterator<T,const T&> const_iterator;iterator begin(){//return _head->_next;return iterator(_head->_next);}iterator end(){return _head;}const_iterator begin()const {return const_iterator(_head->_next);}const_iterator end()const {return (const_iterator)_head;}list(){_head = new Node;_head->_prev = _head;_head->_next = _head;}~list(){//...}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 pop_back() {Node* p = this->_head->_prev;p->_prev->_next = _head;_head->_prev = p->_prev;delete p;}void insert(iterator pos, const T& val) {Node* newnode = new Node(val);Node* p = pos._node;p->_prev->_next = newnode;newnode->_prev = p->_prev;p->_prev = newnode;newnode->_next = p;}void erase(iterator pos) {Node* p = pos._node;p->_prev->_next = p->_next;p->_next->_prev = p->_prev;delete p;}private:Node* _head;};void Print(const list<int>& lt) {list<int>::const_iterator it = lt.begin();while (it != lt.end()) {cout << *it << " ";it++;}cout << endl;}void test_list1(){list<int> lt;lt.push_back(1);lt.push_back(2);lt.push_back(3);lt.push_back(4);list<int>::iterator it = lt.begin();while (it != lt.end()){(*it) += 1;cout << *it << " ";++it;}cout << endl;lt.erase(lt.begin()++);lt.insert(++lt.begin(), 852);lt.insert(++lt.begin(), 852);lt.insert(++lt.begin(), 852);for (auto e : lt){cout << e << " ";}cout << endl << endl;Print(lt);}
}int main() {test::test_list1();
}

4.我们重载了->运算符，使得list更好支持自定义类型。此时我们使用了三个模板参数：
 

#include<iostream>
using namespace std;
namespace test
{template<class T>struct list_node{list_node<T>* _next;list_node<T>* _prev;T _val;list_node(const T& val = T()):_next(nullptr), _prev(nullptr), _val(val){}};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->_val;}self& operator++(){_node = _node->_next;return *this;}Ptr operator->() {return &(this->_node)->_val;}self operator++(int){self tmp(*this);_node = _node->_next;return tmp;}bool operator!=(const self& it){return _node != it._node;}bool operator==(const self& it){return _node == it._node;}};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;iterator begin(){//return _head->_next;return iterator(_head->_next);}iterator end(){return _head;}const_iterator begin()const {return const_iterator(_head->_next);}const_iterator end()const {return (const_iterator)_head;}list(){_head = new Node;_head->_prev = _head;_head->_next = _head;}~list(){//...}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 pop_back() {Node* p = this->_head->_prev;p->_prev->_next = _head;_head->_prev = p->_prev;delete p;}void insert(iterator pos, const T& val) {Node* newnode = new Node(val);Node* p = pos._node;p->_prev->_next = newnode;newnode->_prev = p->_prev;p->_prev = newnode;newnode->_next = p;}void erase(iterator pos) {Node* p = pos._node;p->_prev->_next = p->_next;p->_next->_prev = p->_prev;delete p;}private:Node* _head;};struct A {A(int a=0, int b=0) :_a(a), _b(b) {}//这样写先当于没有默认构造函数了：A(int a, int b) :_a(a), _b(b) {}，但是list_node的构造函数中会用，所以我们给缺省值int _a, _b;};void test() {list<A> lt;lt.push_back(A(1, 1));lt.push_back(A(2, 2));lt.push_back(A(3, 3));lt.push_back(A(4, 4));auto it = lt.begin();while (it != lt.end()) {cout << it->_a << " " << it->_b << endl;//本质是cout<<it->->_a<<" "<<it->->_b<<endl;但为了重载函数的可读性，编译器做了优化//it->返回对象的地址（const或非const），得到地址后再去利用“地址->内容”的方式访问_a和_b++it;}}
}int main() {test::test();
}