迭代器實現問題

我試圖用一個類似於內部STL的迭代器創建一個雙向鏈表時寫了下面的代碼。我現在只提供頭文件和非相關的部分。迭代器實現問題

我的問題是...

的STL使用迭代器以一定的方式 - 具體來說，您STL容器從.begin瀏覽超過（）迭代直到但不包括.END（）迭代器。爲此，.end（）迭代器必須超過容器的末尾。我將如何實現這種語義給予我開始（這是主要問題）？
接口中是否存在任何缺失（關於迭代器類和應該存在的東西）？

下面的代碼：

template <typename T> 
class Node 
{ 
    T data; 
    Node<T>* next; 
    Node<T>* prev; 
}; 

template <typename T> 
class LinkedList 
{ 
    public: 

     class Iterator 
     { 
      public: 

       Iterator() {} 
       explicit Iterator(const Node<T>& init) { current = init; } 

       //Dereference operator - return the current node's data. 
       inline T& operator*() { return current->data; } 

       //Prefix returns by reference. 
       inline Iterator& operator++() { current = current->next; return *this; } 
       inline Iterator& operator--() { current = current->prev; return *this; } 

       //Postfix returns non-reference and has int parameter to differentiate function signature. 
       inline Iterator operator++(int) { Iterator res = *this; current = current->next; return res; } 
       inline Iterator operator--(int) { Iterator res = *this; current = current->prev; return res; } 

      private: 

       Node<T>* current; 
     }; 

     Iterator begin() { return Iterator(m_start); } 
     Iterator end() { return Iterator(m_end); } 

    private: 
     Node<T>* m_start; 
     Node<T>* m_end; 
};

我知道，我可能會或可能不會有與++ /問題 - 運營商，但是，這並不特別煩我，因爲我」當我有足夠的代碼對此進行一些測試時，我會解決這些問題。隨意丟棄提示但如果你傾向於:)

來源

2011-12-17 John Humphreys - w00te

第一個節點的上一個指針爲NULL，所以是最後一個節點的下一個指針。一個過去的指針current應該是NULL。
operator->

來源

2011-12-17 22:48:27 Pubby

我該如何實現該操作符 - >爲了這個類的需要？（我沒有具體詢問運算符是如何被重載的，更像是我做了什麼，我不知道如何轉發它來調用基礎列表數據類型的函數）。並感謝你的答案到目前爲止:) +1 – 2011-12-17 22:52:28

@ w00te它只是返回一個指向數據'＆current-> data'的指針，奇怪的是它的工作方式。儘管答案中的一些信息會很好。 – 2011-12-17 22:54:09

@ w00te'T * operator - >（）{return＆（current-> data）; }' – Pubby 2011-12-17 22:54:33

我認爲NULL將適合在這裏好了。
你可能想寫一些像for (iterator it = list.begin(); it != list.end(); it++)，所以你也需要比較運算符來定義。

來源

2011-12-17 22:59:30 prazuber

謝謝，+1 :) – 2011-12-17 23:02:58

當然比較運算符，完全忘了那些。但是對於'+'之類的，雙鏈表實際上只有雙向迭代器。雖然你可以通過在'+ ='中實現一個循環來隱藏它，但它會隱藏這個操作的線性複雜性，因此我會保留雙向迭代器，不包含'+ ='和co。這就是明確的'std :: advance'的意思。 – 2011-12-17 23:05:20

@ChristianRau是的，也許像'+'這樣的運營商在這裏是不必要的。我真的沒有想到這一點。 – prazuber 2011-12-17 23:10:06

通過end()返回必須decrementable迭代器，否則你無法通過反向對列表進行迭代。你能做到這一點，通過具有迭代店兩個指針：當前節點（這將是空的結束）和前一個節點（它允許你找到它的數據的最後一個節點，即使current == NULL

class Iterator 
{ 
    public: 

     Iterator() {} 
     explicit Iterator(Node<T>* curr, Node<T>* prev): 
      current(curr), previous(prev) {} 

     //Dereference operator - return the current node's data. 
     inline T& operator*() { return current->data; } 

     //Prefix returns by reference. 
     inline Iterator& operator++() 
     { 
      previous = current; 
      current = current->next; 
      return *this; 
     } 
     inline Iterator& operator--() 
     { 
      current = previous; 
      previous = current->previous; 
      return *this; 
     } 

     //Postfix should be implemented in terms of prefix operators 
     inline Iterator operator++(int) { Iterator res = *this; ++*this; return res; } 
     inline Iterator operator--(int) { Iterator res = *this; --*this; return res; } 

    private: 

     Node<T>* current; 
     Node<T>* previous; 
}; 

Iterator begin() { return Iterator(m_start, 0); } 
Iterator end() { return Iterator(0, m_end); }

。

或者你可以讓你的列表包含一個指定列表的「one-past-end」的sentinel節點，這個節點不應該有數據成員，這可以通過將Node類拆分成一個non-只有指向下一個和前一個節點的指針的模板庫

例如，看起來GCC的列表實現存儲指向標記的指針，所以它的next指向列表中的第一個項目，其prev指向列表中的最後一個項目（或者兩者均指向自身，如果列表爲空）。

你缺少operator->，operator==和operator!=，這可以從std::iterator繼承分級的typedef，一個常量性實現（迭代器應該是隱式轉換爲常量性）。

來源

2011-12-18 10:29:55 UncleBens

迭代器實現問題

回答

相關問題