標準庫里的 list 實現是通過雙向鏈表實現的。這里沒有使用雙向鏈表，自然功能也就不能像標準庫里的 list 那樣完備。不支持逆向。
這里在單向鏈表的基礎上，加入了泛型，迭代器，盡可能多地添加一些接口，已盡量像標準庫里的 list 那樣操作。另外，這里沒有過多里涉及內存分配的問題。每次插入的時候是直接分配一個元素的空間，而不是采用 2 倍法則。
總體上，還沒有看過 STL 里 list 具體是怎么實現的，只是按照自己的想法隨意寫了一下。
1 #include <iostream>
2 using namespace std;
3
4 template <typename Type>
5 class mylist
6 {
7 public:
8 typedef Type value_type;
9 typedef unsigned int size_type;
10 struct node_
11 {
12 value_type data;
13 node_* next;
14 };
15 typedef node_ Node;
16 typedef node_* PNode;
17 struct iterator
18 {
19 private:
20 PNode iter_;
21 public:
22 iterator(PNode p) : iter_(p) {}
23 iterator() {}
24 iterator(const iterator& i) : iter_(i) {}
25 iterator& operator =(const iterator& i)
26 {
27 iter_ = i.iter_;
28 }
29 value_type operator *()
30 {
31 return iter_->data;
32 }
33 PNode operator ->()
34 {
35 return iter_;
36 }
37 PNode getPNode()
38 {
39 return iter_;
40 }
41 iterator& operator ++()
42 {
43 iter_ = iter_->next;
44 return *this;
45 }
46 const iterator operator ++(int)
47 {
48 iterator t(iter_);
49 ++iter_;
50 return t;
51 }
52 friend bool operator ==(const iterator& lhs, const iterator& rhs)
53 {
54 return lhs.iter_ == rhs.iter_;
55 }
56 friend bool operator !=(const iterator& lhs, const iterator& rhs)
57 {
58 return !(lhs == rhs);
59 }
60 };
61 typedef const iterator const_iterator;
62 private:
63 // public:
64 PNode head;
65 size_type size_;
66 PNode tail;
67 public:
68 mylist()
69 {
70 head = new Node;
71 if (head == 0)
72 {
73 exit(1);
74 }
75 head->next = 0;
76 size_ = 0;
77 tail = head;
78 }
79 mylist(const mylist<Type>& m)
80 {
81 head = new Node;
82 if (head == 0)
83 {
84 exit(1);
85 }
86 head->next = 0;
87 size_ = 0;
88 tail = head;
89 PNode p, q = head;
90 for (mylist<Type>::iterator iter = m.begin(); iter != m.end(); ++iter)
91 {
92 p = new Node;
93 if (p == 0)
94 {
95 exit(1);
96 }
97 // p->data = iter.getPNode()->data;
98 p->data = iter->data;
99 p->next = 0;
100 q->next = p;
101 q = p;
102 tail = p;
103 ++size_;
104 }
105 }
106 mylist<Type>& operator =(const mylist<Type>& rhs)
107 {
108 if (this != &rhs)
109 {
110 clear();
111 head = new Node;
112 if (head == 0)
113 {
114 exit(1);
115 }
116 head->next = 0;
117 size_ = 0;
118 tail = head;
119 PNode p, q = head;
120 for (mylist<Type>::iterator iter = rhs.begin(); iter != rhs.end(); ++iter)
121 {
122 p = new Node;
123 if (p == 0)
124 {
125 exit(1);
126 }
127 p->data = iter->data;
128 p->next = 0;
129 q->next = p;
130 q = p;
131 tail = p;
132 ++size_;
133 }
134 }
135 return *this;
136 }
137 ~mylist()
138 {
139 clear();
140 }
141 //// 重載 operator&
142 //unsigned int operator &()
143 //{
144 // return static_cast<unsigned int>(head);
145 //}
146 size_type size()
147 {
148 return size_;
149 }
150 bool empty()
151 {
152 return size_ == 0;
153 }
154 value_type front()
155 {
156 return head->next->data;
157 }
158 value_type back()
159 {
160 return tail->next;
161 }
162 iterator begin()
163 {
164 return head->next;
165 }
166 iterator end()
167 {
168 return tail->next;
169 }
170 const_iterator begin() const
171 {
172 return head->next;
173 }
174 const_iterator end() const
175 {
176 return tail->next;
177 }
178 void push_back(value_type v)
179 {
180 PNode p = new Node;
181 if (p == 0)
182 {
183 exit(1);
184 }
185 p->data = v;
186 p->next = 0;
187 tail->next = p;
188 tail = p;
189 ++size_;
190 }
191 void push_front(value_type v)
192 {
193 PNode p = new Node;
194 if (p == 0)
195 {
196 exit(1);
197 }
198 p->data = v;
199 p->next = head->next;
200 head->next = p;
201 ++size_;
202 }
203 void pop_front()
204 {
205 PNode p = head->next;
206 head->next = head->next->next;
207 delete p;
208 --size_;
209 }
210 iterator insert(const iterator& iter, value_type v)
211 {
212 Pnode p = new PNode;
213 if (p == 0)
214 {
215 exit(1);
216 }
217 p->data = v;
218 PNode q = iter.getPNode();
219 p->next = q->next;
220 q->next = p;
221 return p;
222 }
223 void clear()
224 {
225 PNode p = head->next, q;
226 while (p)
227 {
228 q = p->next;
229 delete p;
230 p = q;
231 }
232 head->next = 0;
233 delete head;
234 size_ = 0;
235 }
236 };
237
238 int main()
239 {
240 mylist<int> t;
241 for (int i = 0; i < 10; ++i)
242 {
243 t.push_back(i);
244 }
245 cout << t.size() << endl;
246 for (mylist<int>::iterator iter = t.begin(); iter != t.end(); ++iter)
247 {
248 cout << *iter << ' ';
249 }
250 cout << endl;
251
252 mylist<int> t2(t);
253 cout << t2.size() << endl;
254 for (mylist<int>::iterator iter = t2.begin(); iter != t2.end(); ++iter)
255 {
256 cout << *iter << ' ';
257 }
258 cout << endl;
259
260 mylist<int> t3;
261 cout << t3.size() << endl;
262 for (mylist<int>::iterator iter = t3.begin(); iter != t3.end(); ++iter)
263 {
264 cout << *iter << ' ';
265 }
266 cout << endl;
267 t3 = t2;
268 cout << t3.size() << endl;
269 for (mylist<int>::iterator iter = t3.begin(); iter != t3.end(); ++iter)
270 {
271 cout << *iter << ' ';
272 }
273 cout << endl;
274 //cout << &t << endl;
275 //cout << &t2 << endl;
276 //cout << t.head << endl;
277 //cout << t2.head << endl;
278 }
posted on 2011-04-24 01:04
unixfy 閱讀(343)
評論(0) 編輯 收藏 引用