LIST类结构
1 template <typename Object>
2 class List
3 {
4 private:
5 struct Node//所有都是公有的
6 {
7 Object data;
8 Node *prev;
9 Node *next;
10
11 Node(const Object & d = Object(),Node *p = NUll,Node *n = Null):
12 data(d) , prev(p) , next(n)
13 {
14 }
15 };
16 public:
17 class const_iterator
18 {
19 public:
20 const_iterator() : current(NULL){}
21 const Object & operator* () const
22 {
23 return retrieve();
24 }
25 const_iterator & operator++ ( ) const
26 {
27 current = current->next;
28 return *this;
29 }
30 const_iterator & operator++( int )
31 {
32 const_iterator old = *this;
33 ++(*this);
34 return old;
35 }
36 bool operator == (const const_iterator * rhs) const
37 {
38 return current == rhs.current;
39 }
40 bool operator != (const const_iterator & rhs) const
41 {
42 return !(*this == rhs);
43 }
44
45 protected:
46 Node *current;
47
48 Object & retrieve() cosnt
49 {
50 return current->data;
51 }
52 const_iterator(Node *p) : current(p)
53 {
54 }
55 friend class List<Object>;
56 };
57 class iterator : public const_iterator
58 {
59 public:
60 iterator()
61 {
62 }
63 Object & operator* ()
64 {
65 return retrieve();
66 }
67 const Object & operator* () const
68 {
69 return const_iterator::operator*();
70 }
71 iterator & operator++()
72 {
73 iterator old = *this;
74 ++(*this);
75 return old;
76 }
77
78 protected:
79 iterator(Node *p) : const_iterator(p)
80 {
81 }
82
83 friend class List<object>;
84 };
85 public:
86 List()
87 {
88 init();
89 }
90 List(const List & rhs)
91 {
92 init();
93 *this = rhs;
94 }
95 ~List()
96 {
97 clear();
98 delete head;
99 delete tail;
100 }
101 const List & operator =(const List & rhs)
102 {
103 if(this == &rhs)
104 return *this;
105 clear();
106 for(const_iterator itr = rhs.begin();itr!=rhs.end();++itr)
107 push_back(*itr);
108 return *this;
109 }
110 void init()
111 {
112 theSize = 0;
113 head = new Node;
114 tail = new Node;
115 head->next = tail;
116 tail->prev = head;
117 }
118
119 iterator begin()
120 {
121 return iterator(head->next);
122 }
123 const_iterator begin() const
124 {
125 return const_iterator(head->next);
126 }
127 iterator end()
128 {
129 return iterator(tail);
130 }
131 const_iterator end() const
132 {
133 return const_iterator(tail);
134 }
135
136 int size() const
137 {
138 return theSize;
139 }
140 bool empty() const
141 {
142 return size() == 0;
143 }
144 void clear()
145 {
146 while(!empty())
147 pop_front();
148 }
149 Object & front()
150 {
151 return *begin();
152 }
153 const Object & front() const
154 {
155 return *begin();
156 }
157 Object & back()
158 {
159 return *--end();
160 }
161 const Object & back() const
162 {
163 return *--end();
164 }
165 void push_front(const Object & x)
166 {
167 insert(begin(),x);
168 }
169 void push_back(const Object & x)
170 {
171 insert(end(),x);
172 }
173 void pop_front()
174 {
175 erase(begin());
176 }
177 viod pop_back()
178 {
179 erase(end());
180 }
181
182 iterator insert(iterator itr,const Object & x)
183 {
184 }
185 iteratro erase(iterator itr )
186 {
187 }
188 iterator erase(iterator start,iterator end)
189 {
190 }
191
192 private:
193 int theSize;
194 Node *head;
195 Node *tail;
196
197 void init()
198 {
199 }
200 }