C++標准庫中的list設計

在C++中采用了大量的標志模板庫（STL）實現程序的設計，這種設計方式使得不同類型的對象都能通用，而不再是C語言中的通常對於不同的類型需要重新設計或者或者比較采用間接的指針操作。C++中的這種方式簡化了寫代碼的復雜度，但是增加了編譯器的復雜度和難度。

在數據結構中鏈表是比較基本的類型，在C++中鏈表是基於模板的類，因此在實際的使用過程中需要涉及到實際的類型。

1. #include<list>
2. list<int> lint;

在C++中關於list的接口比較豐富，主要是關於大小，數據的插入、刪除等。但是在C++中引入了迭代器的概念，這個迭代器是關於關於容器中比較重要的一部分，因為這種迭代器使得算法等問題與容器獨立開來，迭代器實質上還是指針，准確的將是一個封裝了指針的類。

迭代器類的創建應該包含下面的操作，首先應該支持的操作符至少包括如下（operator*()，operator++()，operator++(int)，operator==()， operator!=()）,當然也會存在const_iterator這樣的常迭代器，也就是只允許訪問，不能修改對象的迭代器，當然存在迭代器的構造函數、復制控制函數，這些函數都是必須要存在的，因為設計到了指針的操作問題，構造函數應該存在參數是鏈表節點指針的定義，只有存在這個定義才能間接的訪問節點對象。

當然在類中至少存在返回迭代器的begin()和end()函數，這兩個函數返回的迭代器分別指向鏈表的開始和鏈表結束的下一個地址，這是迭代器中經常容易理解錯誤的地方。

在C++中通常創建const_iterator類，然後iterator直接繼承const_iterator。

下面說說list類設計的基本思路：
首先、創建鏈表節點對象，實質上是完成對傳遞進來的類型的封裝操作，同時構成一個雙向鏈表的基本要素（prev、next指針）。節點肯定要存在構造函數，而且是直接初始化三個成員變量。
其次、創建迭代器類，實質上就是封裝一個節點指針，通過節點指針實現操作，至少要實現的操作符已說明。這兩個類都要設置List為友元類，因為這樣才能用List直接操作迭代器的相關操作。
最後、依靠上面的迭代器類和節點類，創建一個List類，該類中主要完成一些基本操作。其中需要注意的就是迭代器的操作，比如刪除元素和插入元素以後迭代器的變化問題等。

需要注意的是在List中采用了哨兵節點，這個哨兵節點並不算實際的操作對象，也就是為了保證肯定有目標所指向，存在一個head對象，這個對象的next就是實際的數據，而tail是迭代器所能到達的最後一個對象，但是這個對象並不是合理的區域，實際上end()實際上就是指向了tail節點，這兩個節點head和tail就是哨兵節點。具體的參看代碼。

實現的基本形式如下：

1. #ifndef __MYLIST_H_H_
   
2. #define __MYLIST_H_H_
   
3. 
   
4. #include<iostream>
   
5. 
   
6. namespace myspace
   
7. {
   
8. 
   
9. template<typename Object>
   
10. class List
    
11. {
    
12. private:
    
13. /*封裝對象，形成鏈表節點*/
    
14. struct Node
    
15. {
    
16. Object data;
    
17. struct Node *prev;
    
18. struct Node *next;
    
19. 
    
20. /*節點構造函數*/
    
21. Node(const Object &d = Object(), Node *p = NULL, Node *n = NULL)
    
22. :data(d), prev(p), next(n){}
    
23. };
    
24. 
    
25. public:
    
26. /*創建一個常量迭代器類，這是容器設計的關鍵*/
    
27. class const_iterator
    
28. {
    
29. public:
    
30. const_iterator():current(NULL)
    
31. {}
    
32. 
    
33. /*重載迭代器的值*/
    
34. const Object & operator*()const
    
35. {
    
36. return retrieve();
    
37. }
    
38. /*重載前向++操作符*/
    
39. const_iterator & operator++ ()
    
40. {
    
41. current = current->next;
    
42. 
    
43. return *this;
    
44. }
    
45. /*重載後向++操作符，因為是一個局部對象不能返回引用*/
    
46. const_iterator operator++(int)
    
47. {
    
48. const_iterator old = *this;
    
49. ++(*this);
    
50. 
    
51. return old;
    
52. }
    
53. /*判斷迭代器是否相同，實質上就是判斷指向的節點是否相同*/
    
54. bool operator==(const const_iterator &rhs) const
    
55. {
    
56. return current == rhs.current;
    
57. }
    
58. /*調用==操作符*/
    
59. bool operator!=(const const_iterator &rhs)const
    
60. {
    
61. return (!(*this == rhs));
    
62. }
    
63. protected:
    
64. /*迭代器實質就是一個節點指針*/
    
65. Node *current;
    
66. 
    
67. /*獲得鏈表中的內容*/
    
68. Object & retrieve() const
    
69. {
    
70. return current->data;
    
71. }
    
72. 
    
73. /*基於指針參數的迭代器構造函數，保證只有List使用*/
    
74. const_iterator(Node *p):current (p)
    
75. {}
    
76. 
    
77. /*友元類，可以調用迭代器的私有成員*/
    
78. friend class List<Object>;
    
79. };
    
80. /*一般迭代器，直接繼承const_iterator*/
    
81. class iterator : public const_iterator
    
82. {
    
83. public:
    
84. iterator():const_iterator()
    
85. {}
    
86. 
    
87. /*得到對象的值*/
    
88. Object &operator*()
    
89. {
    
90. return retrieve();
    
91. }
    
92. 
    
93. /*基於const的重載*/
    
94. const Object& operator*()const
    
95. {
    
96. return const_iterator::operator*();
    
97. }
    
98. /*前向++操作符*/
    
99. iterator &operator++()
    
100. {
     
101. current = current->next;
     
102. 
     
103. return *this;
     
104. }
     
105. /*後向++操作符*/
     
106. iterator operator++(int)
     
107. {
     
108. iterator *old = *this;
     
109. ++(*this);
     
110. return old;
     
111. }
     
112. 
     
113. protected:
     
114. /*基於節點的迭代器構造函數*/
     
115. iterator(Node *p):const_iterator(p)
     
116. {}
     
117. 
     
118. friend class List<Object>;
     
119. };
     
120. public:
     
121. List()
     
122. {
     
123. init();
     
124. }
     
125. ~List()
     
126. {
     
127. clear();
     
128. delete head;
     
129. delete tail;
     
130. }
     
131. 
     
132. List(const List &rhs)
     
133. {
     
134. /*創建哨兵節點*/
     
135. init();
     
136. /*復制數據*/
     
137. *this = rhs;
     
138. }
     
139. 
     
140. const List & operator=(const List &rhs)
     
141. {
     
142. if(this == &rhs)
     
143. return *this;
     
144. /*清除原有的信息*/
     
145. clear();
     
146. /*添加新的對象*/
     
147. for(const_iterator itr = rhs.begin(); itr != rhs.end(); ++ itr)
     
148. push_back(*itr);
     
149. 
     
150. return *this;
     
151. }
     
152. 
     
153. /*得到迭代器，實質上就是得到節點指針*/
     
154. iterator begin()
     
155. {
     
156. /*iterator()是構造函數*/
     
157. return iterator(head->next);
     
158. }
     
159. 
     
160. const_iterator begin()const
     
161. {
     
162. return const_iterator(head->next);
     
163. }
     
164. 
     
165. iterator end()
     
166. {
     
167. return iterator(tail);
     
168. }
     
169. 
     
170. const_iterator end()const
     
171. {
     
172. return const_iterator(tail);
     
173. }
     
174. 
     
175. int size()const
     
176. {
     
177. return theSize;
     
178. }
     
179. 
     
180. bool empty()const
     
181. {
     
182. return size() == 0;
     
183. }
     
184. 
     
185. void clear()
     
186. {
     
187. while( !empty())
     
188. pop_front();
     
189. }
     
190. 
     
191. /*得到第一個元素*/
     
192. Object & front()
     
193. {
     
194. /*采用了迭代器begin()*/
     
195. return *begin();
     
196. }
     
197. const Object &front()const
     
198. {
     
199. return *begin();
     
200. }
     
201. 
     
202. Object &back()
     
203. {
     
204. /*end()指向最後一個對象的下一個地址，因此需要--*/
     
205. return *--end();
     
206. }
     
207. const Object &back()const
     
208. {
     
209. return *--end();
     
210. }
     
211. /***********************************************
     
212. *從頭插入新的節點，這時候的begin已經不再是begin
     
213. *因此插入操作會導致迭代器出錯
     
214. ***********************************************/
     
215. void push_front(const Object &x)
     
216. {
     
217. insert(begin(), x);
     
218. }
     
219. /*從後插入新的節點，這時候會將end後移*/
     
220. void push_back(const Object &x)
     
221. {
     
222. insert(end(), x);
     
223. }
     
224. 
     
225. /*從頭彈出一個對象*/
     
226. void pop_front()
     
227. {
     
228. erase(begin());
     
229. }
     
230. void pop_back()
     
231. {
     
232. erase(--end());
     
233. }
     
234. 
     
235. /*插入對象，參數是迭代器和數據*/
     
236. iterator insert(iterator itr, const Object &x)
     
237. {
     
238. /*得到當前迭代器的指針*/
     
239. Node *p = itr.current;
     
240. theSize ++;
     
241. 
     
242. /*
     
243. *Node *np = Node(x,p->prev,p);
     
244. this means that np->prev = p->prev,
     
245. and np->next = p;
     
246. 
     
247. update the p->prev and p->prev->next;
     
248. *p->prev->next = np;
     
249. *p->prev = np;
     
250. */
     
251. return iterator(p->prev=p->prev->next= new Node(x,p->prev, p));
     
252. }
     
253. 
     
254. /*刪除迭代器處的對象,因此刪除也會導致迭代器破壞*/
     
255. iterator erase(iterator itr)
     
256. {
     
257. /*得到當前迭代器的指針*/
     
258. Node *p = itr.current;
     
259. /*得到新的迭代器，並初始化*/
     
260. iterator retVal(p->next);
     
261. /*更新鏈表的鏈接關系*/
     
262. p->prev->next = p->next;
     
263. p->next->prev = p->prev;
     
264. /*刪除對象*/
     
265. delete p;
     
266. /*使得對象數減少*/
     
267. theSize --;
     
268. /*返回新的迭代器*/
     
269. return retVal;
     
270. }
     
271. 
     
272. /*刪除迭代器指向的對象*/
     
273. iterator erase(iterator start, iterator end)
     
274. {
     
275. /*for中不使用++itr的原因是erase之後
     
276. *就是下一個迭代器，因此不需要++操作*/
     
277. for(iterator itr = start; itr != end; )
     
278. {
     
279. /*該操作會導致迭代器更新到下一個*/
     
280. itr = erase(itr);
     
281. }
     
282. return itr;
     
283. }
     
284. 
     
285. private:
     
286. /*鏈表中的數據成員*/
     
287. int theSize;
     
288. Node *head;
     
289. Node *tail;
     
290. /*初始化函數*/
     
291. void init()
     
292. {
     
293. theSize = 0;
     
294. /*create two sentinel node*/
     
295. /*構建兩個哨兵節點，也就是兩個並不算在結構體中的對象*/
     
296. head = new Node;
     
297. tail = new Node;
     
298. /*綁定起來*/
     
299. head->next = tail;
     
300. tail->prev = head;
     
301. }
     
302. };
     
303. }
     
304. 
     
305. #endif