迭代器

  1 #pragma once
  2 #include <assert.h>
  3 template<typename T>
  4 class CList
  5 {
  6 private:
  7     //链表的结点
  8     typedef struct tagNode
  9     {
 10         tagNode() :m_pPre(nullptr), m_pNext(nullptr) {}
 11         tagNode(T val) :m_val(val), m_pPre(nullptr), m_pNext(nullptr) {}
 12         T m_val;  //结点保存的数据
 13         tagNode* m_pPre;  //前驱结点的指针
 14         tagNode* m_pNext;  //后继结点的指针
 15     }NODE, * PNODE;
 16 
 17 public:
 18     class CIterator
 19     {
 20     public:
 21         friend class CList;
 22         CIterator(PNODE pPos) :m_pPos(pPos) {}
 23         CIterator& operator++()
 24         {
 25             //尾哨兵不能后移
 26             assert(m_pPos->m_pNext != nullptr);
 27             m_pPos = m_pPos->m_pNext; //位置后移，指向自己的后继
 28             return *this;
 29         }
 30         CIterator operator++(int)
 31         {
 32             assert(m_pPos->m_pNext != nullptr);
 33             CIterator itrTmp(m_pPos);  //保存原来的位置
 34             ++(*this);  //m_pPos = m_pPos->pNext;
 35             return itrTmp;  //返回原来的位置
 36         }
 37 
 38         CIterator& operator--()
 39         {
 40             //头结点不能前移
 41             assert(m_pPos->m_pPre->m_pPre != nullptr);
 42 
 43             m_pPos = m_pPos->m_pPre; //位置前移，指向自己的前驱
 44             return *this;
 45         }
 46         CIterator operator--(int)
 47         {
 48             assert(m_pPos->m_pPre->m_pPre != nullptr);
 49 
 50             CIterator itrTmp(m_pPos);  //保存原来的位置
 51             --(*this);  //m_pPos = m_pPos->pPre;
 52             return itrTmp;  //返回原来的位置
 53         }
 54 
 55         T& operator*()
 56         {
 57             //尾哨兵不能取内容
 58             assert(m_pPos->m_pNext != nullptr);
 59 
 60             return m_pPos->m_val;
 61         }
 62 
 63         T* operator->()
 64         {
 65             return &m_pPos->m_val;
 66         }
 67 
 68         bool operator==(const CIterator& obj)
 69         {
 70             return m_pPos == obj.m_pPos;
 71         }
 72         bool operator!=(const CIterator& obj)
 73         {
 74             return !(*this == obj);
 75         }
 76 
 77     private:
 78         PNODE m_pPos;  //结点的指针，用来指示位置
 79     };
 80 
 81     class CReverseIterator
 82     {
 83     public:
 84         friend class CList;
 85         CReverseIterator(PNODE pPos) :m_pPos(pPos) {}
 86         CReverseIterator& operator++()
 87         {
 88             //头哨兵不能前移
 89             assert(m_pPos->m_pPre != nullptr);
 90 
 91             m_pPos = m_pPos->m_pPre; //位置前移，指向自己的前驱
 92             return *this;
 93         }
 94         CReverseIterator operator++(int)
 95         {
 96             assert(m_pPos->m_pPre != nullptr);
 97 
 98             CReverseIterator itrTmp(m_pPos);  //保存原来的位置
 99             ++(*this);  //m_pPos = m_pPos->pNext;
100             return itrTmp;  //返回原来的位置
101         }
102 
103         CReverseIterator& operator--()
104         {
105             //尾结点不能后移
106             assert(m_pPos->m_pNext->m_pNext != nullptr);
107 
108             m_pPos = m_pPos->m_pNext; //位置后移，指向自己的后继
109             return *this;
110         }
111         CReverseIterator operator--(int)
112         {
113             assert(m_pPos->m_pNext->m_pNext != nullptr);
114 
115             CReverseIterator itrTmp(m_pPos);  //保存原来的位置
116             --(*this);  //m_pPos = m_pPos->pPre;
117             return itrTmp;  //返回原来的位置
118         }
119 
120         T& operator*()
121         {
122             //头哨兵不能取内容
123             assert(m_pPos->m_pPre != nullptr);
124 
125             return m_pPos->m_val;
126         }
127 
128         bool operator==(const CReverseIterator& obj)
129         {
130             return m_pPos == obj.m_pPos;
131         }
132         bool operator!=(const CReverseIterator& obj)
133         {
134             return !(*this == obj);
135         }
136 
137     private:
138         PNODE m_pPos;  //结点的指针，用来指示位置
139     };
140 
141     CList();
142     CList(const CList& obj);
143     CList& operator=(const CList& obj);
144     CList(std::initializer_list<T>);
145     ~CList();
146 
147     CIterator begin();  //小写begin支持范围循环，大写Begin不支持范围循环
148     CIterator end();  //小写end支持范围循环，大写End不支持范围循环
149 
150     CReverseIterator rbegin();  //小写begin支持范围循环，大写Begin不支持范围循环
151     CReverseIterator rend();  //小写end支持范围循环，大写End不支持范围循环
152 
153     CIterator Insert(CIterator itr, T val);  //如果pNode为空，则不允许插入
154     CIterator InsertHead(T val);
155     CIterator InsertTail(T val);
156 
157     void Delete(CIterator itr);
158     void DeleteHead();
159     void DeleteTail();
160 
161     CIterator Find(T val)const;  //失败返回nullptr
162 
163     T& operator[](size_t nIdx);
164 
165     void Clear();
166     size_t GetLen()const;
167     bool IsEmpty()const;
168 
169     T GetHead();  //获取头部元素
170     T GetTail();  //获取尾部元素
171 
172 private:
173     void Init();
174     void UnInit();
175 
176 private:
177     PNODE m_pHeadSentinel;  //指向头部哨兵的指针
178     PNODE m_pTailSentinel;  //指向尾部哨兵的指针
179     size_t m_nLen;  //链表中元素的个数
180 };
181 
182 
183 template<typename T>
184 CList<T>::CList()
185 {
186     Init();
187 }
188 
189 template<typename T>
190 CList<T>::CList(const CList& obj)
191 {
192     Init();
193 
194     *this = obj;
195 }
196 
197 template<typename T>
198 CList<T>& CList<T>::operator=(const CList& obj)
199 {
200     if (this == &obj) //防止自己=自己
201     {
202         return *this;
203     }
204 
205     Clear();
206 
207     PNODE pNode = obj.m_pHeadSentinel->m_pNext; //取obj的头结点
208 
209     while (pNode != obj.m_pTailSentinel)//判断是否到obj的链表的尾
210     {
211         InsertTail(pNode->m_val);
212         pNode = pNode->m_pNext;  //取obj的下一个结点
213     }
214 
215     return *this;
216 }
217 
218 template<typename T>
219 inline CList<T>::CList(std::initializer_list<T>list)
220 {
221     Init();
222     for (auto it = list.begin();it!=list.end();it++)
223     {
224         this->InsertTail(*it);
225     }
226 }
227 
228 template<typename T>
229 CList<T>::~CList()
230 {
231     Clear();
232     UnInit();
233 }
234 
235 template<typename T>
236 typename CList<T>::CIterator CList<T>::begin()
237 {
238     return CIterator(m_pHeadSentinel->m_pNext);
239 }
240 
241 template<typename T>
242 typename CList<T>::CIterator CList<T>::end()
243 {
244     return CIterator(m_pTailSentinel);
245 }
246 
247 template<typename T>
248 typename CList<T>::CReverseIterator CList<T>::rbegin()
249 {
250     return CReverseIterator(m_pTailSentinel->m_pPre);
251 }
252 
253 template<typename T>
254 typename CList<T>::CReverseIterator CList<T>::rend()
255 {
256     return CReverseIterator(m_pHeadSentinel);
257 }
258 
259 template<typename T>
260 typename CList<T>::CIterator CList<T>::Insert(CIterator itr, T val)
261 {
262     if (itr == nullptr)
263     {
264         return nullptr;
265     }
266 
267     //链表非空
268     PNODE pNewNode = new NODE(val);
269     PNODE pNext = itr.m_pPos;
270     PNODE pPre = pNext->m_pPre;
271     if (pNewNode == nullptr)
272     {
273         return nullptr;
274     }
275     pPre->m_pNext = pNewNode;
276     pNext->m_pPre = pNewNode;
277 
278     pNewNode->m_pPre = pPre;
279     pNewNode->m_pNext = pNext;
280 
281     ++m_nLen;
282 
283     return CIterator(pNewNode);
284 }
285 
286 template<typename T>
287 typename CList<T>::CIterator CList<T>::InsertHead(T val)
288 {
289     return Insert(CIterator(m_pHeadSentinel->m_pNext), val);
290 }
291 
292 template<typename T>
293 typename CList<T>::CIterator CList<T>::InsertTail(T val)
294 {
295     return Insert(CIterator(m_pTailSentinel), val);
296 }
297 
298 template<typename T>
299 void CList<T>::Delete(CIterator itr)
300 {
301     if (itr == nullptr)
302     {
303         return;
304     }
305 
306     //取结点前驱后继
307     PNODE pNext = itr.m_pPos->m_pNext;
308     PNODE pPre = itr.m_pPos->m_pPre;
309 
310     //后继为前驱新后继，前驱为后继新前驱
311     pPre->m_pNext = pNext;
312     pNext->m_pPre = pPre;
313 
314     delete itr.m_pPos;
315 
316     --m_nLen;
317 }
318 
319 template<typename T>
320 void CList<T>::DeleteHead()
321 {
322     Delete(CIterator(m_pHeadSentinel->m_pNext));
323 }
324 
325 template<typename T>
326 void CList<T>::DeleteTail()
327 {
328     Delete(CIterator(m_pTailSentinel->m_pPre));
329 }
330 
331 template<typename T>
332 typename CList<T>::CIterator CList<T>::Find(T val) const
333 {
334     PNODE pNode = m_pHeadSentinel->m_pNext;
335 
336     while (pNode != m_pTailSentinel)
337     {
338         if (pNode->m_val == val)
339         {
340             return CIterator(pNode);
341         }
342 
343         pNode = pNode->m_pNext;
344     }
345 
346     return nullptr;
347 }
348 
349 template<typename T>
350 T& CList<T>::operator[](size_t nIdx)
351 {
352     //边界检查
353     assert(nIdx < m_nLen);
354 
355     auto pNode = m_pHeadSentinel->m_pNext;
356     for (size_t i = 0; i < nIdx; i++)
357     {
358         pNode = pNode->m_pNext;
359     }
360 
361     return pNode->m_val;
362 }
363 
364 template<typename T>
365 void CList<T>::Clear()
366 {
367     while (!IsEmpty())
368     {
369         DeleteHead();
370     }
371 }
372 
373 template<typename T>
374 size_t CList<T>::GetLen() const
375 {
376     return m_nLen;
377 }
378 
379 template<typename T>
380 bool CList<T>::IsEmpty() const
381 {
382     return m_nLen == 0;
383 }
384 
385 template<typename T>
386 inline T CList<T>::GetHead()
387 {
388     return m_pHeadSentinel->m_pNext->m_val;
389 }
390 
391 template<typename T>
392 inline T CList<T>::GetTail()
393 {
394     return m_pTailSentinel->m_pPre->m_val;
395 }
396 
397 template<typename T>
398 void CList<T>::Init()
399 {
400     m_pHeadSentinel = new NODE;
401     m_pTailSentinel = new NODE;
402 
403     if (m_pHeadSentinel == nullptr || m_pTailSentinel == nullptr)
404     {
405         return;
406     }
407 
408     //没有存储数据前，头哨兵的后继是尾哨兵，尾哨兵的前驱是头哨兵
409     m_pHeadSentinel->m_pNext = m_pTailSentinel;
410     m_pTailSentinel->m_pPre = m_pHeadSentinel;
411 
412     m_nLen = 0;
413 }
414 
415 template<typename T>
416 void CList<T>::UnInit()
417 {
418     if (m_pHeadSentinel != nullptr)
419     {
420         delete m_pHeadSentinel;
421         m_pHeadSentinel = nullptr;
422     }
423 
424     if (m_pTailSentinel != nullptr)
425     {
426         delete m_pTailSentinel;
427         m_pTailSentinel = nullptr;
428     }
429 
430     m_nLen = 0;
431 }