1.    void clear()
2.    {
3.      iterator it = begin();
4.      while (it != end())
5.      {
6.        erase(it++);//erase需要传参迭代器，即位置
7.      }
8.    }

1. //头插   
2. void push_front(const T& x)
3.    {
4.      insert(begin(), x);
5.    }

1.    //尾插
2.    void push_back(const T& x)
3.    {
4.      insert(end()--, x); 
5.    }

1.    //头删
2.    void pop_front()
3.    {
4.      erase(begin());
5.    }

1.    //尾删
2.    void pop_back()
3.    {
4.      erase(--end());
5.    }

1.    //判空
2. bool empty()
3.    {
4.      return end() == begin();
5.    }

1.    //求节点个数
2. size_t size()
3.    {
4.      iterator it = begin();
5.      size_t sz = 0;
6.      while (it != end())//时间复杂度O(N)
7.      {
8.        it++;
9.        sz++;
10.       }
11. 
12.       return sz;
13.     }

1. #pragma once
2. #include<iostream>
3. #include<assert.h>
4. using namespace std;
5. 
6. namespace delia
7. {
8.  template<class T>
9.  struct _list_node
10.   {
11.     T _val;
12.     _list_node<T>* _prev;
13.     _list_node<T>* _next;
14. 
15.     _list_node(const T& val = T())
16.       :_val(val) 
17.       , _prev(nullptr)
18.       , _next(nullptr)
19.     {}; 
20.   };
21. 
22. 
23.   //节点的指针原生行为不满足迭代器定义，在这里，迭代器通过类来封装节点的指针重载运算符来控制
24. 
25.   //对于T&，类模板实例化出两个类，一个是T&类，一个是const T&类，同理，T*也一样。
26.   //使用template<class T,class Ref,class Ptr>类模板就会实例化出来两个类，一个是T,T&, T*的，一个是T,const T&, const T*的   
27.   //template _list_iterator<T, T&, T*> _iterator;
28.   //template _list_iterator<T, const T&, const T*> const_iterator;
29. 
30.   //这样就不需要再去定义一个如下const的迭代器类：
31.   //template<class T>
32.   //struct _list_const_iterartor
33.   //{
34.   //  typedef _list_node<T> node;
35.   //  typedef _list_const_iterartor<T> self;
36. 
37.   //  node* _pnode;
38.   //}
39.   // 
40. 
41.   template<class T,class Ref,class Ptr>
42.   struct _list_iterator//使用_list_iterator类来封装node*
43.   {
44.     typedef _list_node<T> node;
45.     typedef _list_iterator<T,Ref,Ptr> self;
46. 
47.     node* _pnode;
48. 
49.     //构造函数
50.     _list_iterator(node* pnode)
51.       :_pnode(pnode)
52.     {}
53. 
54.     //拷贝构造、赋值运算符重载、析构函数，编译器默认生成即可
55. 
56.     //解引用，返回左值，是拷贝，因此要用引用返回
57.     Ref operator*()
58.     {
59.       return _pnode->_val;
60.     }
61. 
62.     //结构体指针解引用，返回节点值的引用
63.     Ptr operator->()
64.     {
65.       return &_pnode->_val;
66.     }
67. 
68.     //!=重载
69.     bool operator!=(const self& s) const
70.     {
71.       return _pnode != s._pnode;
72.     }
73. 
74.     //==重载
75.     bool operator==(const self& s) const
76.     {
77.       return _pnode == s._pnode;
78.     }
79. 
80.     //前置++  it.operator(&it)
81.     self& operator++()
82.     {
83.       _pnode = _pnode->_next;
84.       return *this;
85.     }
86. 
87.     //后置++ 返回++之前的值  it.operator(&it,0)
88.     self operator++(int)
89.     {
90.       self tmp(*this);
91.       _pnode = _pnode->_next;
92.       return tmp;
93.     }
94. 
95.     //前置--  it.operator(&it)
96.     self& operator--()
97.     {
98.       _pnode = _pnode->prev;
99.       return *this;
100.    }
101. 
102.    //后置++ 返回++之前的值  it.operator(&it,0)
103.    self operator--(int)//临时对象不能用引用返回，所以self没有加&
104.    {
105.      self tmp(*this);
106.      _pnode = _pnode->_prev;
107.      return tmp;
108.    }
109.  };
110. 
111.  template<class T>
112.  class list
113.  {
114.    typedef _list_node<T> node;
115.  public:
116.    typedef _list_iterator<T,T&,T*> iterator;//重命名迭代器
117.    typedef _list_iterator<T, const T&, const T*> const_iterator;//重命名const迭代器
118. 
119.    //构造函数
120.    list()
121.    {
122.      _head = new node;//会调_list_node的构造函数
123.      _head->_next = _head;//整个链表只有头节点，先构造一个没有实际节点的链表
124.      _head->_prev = _head;//整个链表只有头节点，先构造一个没有实际节点的链表
125.    }
126. 
127.    //拷贝构造 lt1(lt)
128.    list(const list<T>& lt)
129.    {
130.      //1.先构造一个只有头节点的空list：创建头节点，头节点的前一个是自己，头节点的后一个是自己
131.      _head = new node;
132.      _head->_next = _head;
133.      _head->_prev = _head;
134. 
135.      //2.将lt的元素全部尾插到新链表
136.      for (const auto& e : lt)
137.      {
138.        push_back(e);
139.      }
140.    }
141. 
142.    赋值运算符重载  lt1 = lt  传统写法
143.    //list<T>& operator=(list<T>& lt)
144.    //{
145.    //  if(this != lt)
146.    //  {
147.    //    for (auto& e : lt)
148.    //    {
149.    //      push_back(e);
150.    //    }
151.    //  }
152.    //}
153. 
154.    //赋值运算符重载  lt1 = lt  现代写法
155.    list<T>& operator=(list<T>& lt)
156.    {
157.      swap(_head, lt._head);
158.      return *this;
159.    }
160. 
161.    //析构
162.    ~list()
163.    {
164.      clear();
165.      delete _head;
166.      _head = nullptr;
167.    }
168. 
169.    iterator begin()
170.    {
171.      return iterator(_head->_next);
172.    }
173. 
174.    iterator end()
175.    {
176.      return iterator(_head);//尾节点的下一个节点位置即头节点
177.    }
178. 
179.    const_iterator begin() const
180.    {
181.      return const_iterator(_head->_next);
182.    }
183. 
184.    const_iterator end() const
185.    {
186.      return const_iterator(_head);//尾节点的下一个节点位置即头节点
187.    }
188. 
189.    //插入节点
190.    void insert(iterator pos, const T& x)
191.    {
192.      assert(pos._pnode);
193.      node* newnode = new node(x);//构造节点
194. 
195.      node* prev = pos._pnode->_prev;//为方便后续操作，给插入位置的前一个节点起了个名字，pos是迭代器对象
196. 
197.      //插入节点
198.      newnode->_next = pos._pnode;
199.      pos._pnode->_prev = newnode;
200.      prev->_next = newnode;
201.      newnode->_prev = prev;
202. 
203.    }
204. 
205.    //删除节点
206.    iterator erase(iterator pos)
207.    {
208.      assert(pos._pnode);//判断该位置节点是否存在
209.      assert(pos != end());//end()是最后一个节点的下一个节点位置，也就是头节点，头节点不能删，需要断言
210. 
211.      node* prev = pos._pnode->_prev;//pos位置节点的前一个节点
212.      node* next = pos._pnode->_next;//pos位置节点的后一个节点
213. 
214.      //删除节点
215.      delete pos._pnode;
216.      prev->_next = next;
217.      next->_prev = prev;
218. 
219.      return iterator(next);//删除之后pos失效，把下一个位置的迭代器给它
220.    }
221. 
222.    void clear()
223.    {
224.      iterator it = begin();
225.      while (it != end())
226.      {
227.        erase(it++);
228.      }
229.    }
230. 
231.    //头插
232.    void push_front(const T& x)
233.    {
234.      insert(begin(), x);
235.    }
236. 
237.    //尾插
238.    void push_back(const T& x)
239.    {
240.      insert(end()--, x); 
241.    }
242. 
243.    //头删
244.    void pop_front()
245.    {
246.      erase(begin());
247.    }
248. 
249.    //尾删
250.    void pop_back()
251.    {
252.      erase(--end());
253.    }
254. 
255.    //判空
256.    bool empty()
257.    {
258.      return _head->_next == _head;
259.    }
260. 
261.    //求节点个数
262.    size_t size()
263.    {
264.      iterator it = begin();
265.      size_t sz = 0;
266.      while (it != end())//时间复杂度O(N)
267.      {
268.        it++;
269.        sz++;
270.      }
271. 
272.      return sz;
273.    }
274.  private:
275.    node* _head;
276.  };
277. 
278.  void PrintList(const list<int>& lt)
279.  {
280.    list<int>::const_iterator it = lt.begin();
281.    while (it != lt.end())
282.    {
283.      cout << it._pnode->_val << " ";
284.      it++;
285.    }
286.    cout << endl;
287.  }
288. 
289.  void test_list1()
290.  {
291.    list<int> l1;
292.    l1.push_back(5);
293.    l1.push_back(8);
294.    l1.push_back(20);
295.    l1.push_back(9);
296. 
297.    PrintList(l1);
298. 
299.    list<int> l2;
300.    l2 = l1;
301.    PrintList(l2);
302. 
303.    cout << endl;
304.  }
305. }

1. #include "016-list.h"
2. #include<list>
3. using namespace std;
4. 
5. int main()
6. {
7.  delia::test_list1();
8.  return 0;
9. }