如何實現一個'方形列表'迭代器

我正在使用C++來實現一個正方形列表，這是一個雙向鏈接列表的雙向鏈接列表。該列表是排序的，並且這個想法是該結構在元素被插入和擦除時保持正方形的形狀。如果列表總共有四個元素，那麼這個正方形將以2x2形狀。如何實現一個'方形列表'迭代器

它看起來是這樣的：

enter image description here

我已經做了鏈表一些研究和了解，一般的想法是創建一個保存每個數據元素的節點，以及指針和從周圍的元素，但有一件事是扔我離開我是如何（或可能）實現迭代器遍歷方形列表。

這是我第一次嘗試構建一個數據結構，所以這個過程對我來說是非常新的。任何提示讚賞！

來源

2014-02-12 mcraen

爲什麼「雙鏈表」有頭尾連接？這應該表述爲「循環雙向鏈表」。如果是這樣，那麼節點10和40的連接就很奇怪，因爲如果只有1路連接。 – Krypton

您不能爲頂級列表構建迭代器類型，爲二級列表構建迭代器類型，然後使用另一個迭代器類型來迭代這兩個維度？ – user3286380

@Krypton大概是這樣，你可以反向迭代它，而不必首先迭代它。 – user3286380

有你需要做，比如是否重要反過來如果整體迭代尾氣每個「內部」名單，還是應該返回所有內列出的第一要素，則第二等幾個設計決策..

至於如何實現這個味道：

#include <iostream> 
#include <list> 

template <typename T> 
struct Iterator 
{ 
    typedef typename std::list<std::list<T> >::iterator outer_iterator; 
    typedef typename std::list<T>::iterator inner_iterator; 

    outer_iterator outer_; 
    bool inner_initialised_; 
    inner_iterator inner_; 

    Iterator(outer_iterator begin) 
     : outer_(begin), inner_initialised_(false) 
    { } 

    T& operator*() 
    { 
     if (!inner_initialised_) 
     { 
      inner_ = outer_->begin(); 
      inner_initialised_ = true; 
     } 
     return *inner_; 
    } 

    T& operator->() { return operator*(); } 

    Iterator& operator++() 
    { 
     if (++inner_ == outer_->end()) 
     { 
      ++outer_; 
      inner_initialised_ = false; 
     } 
     return *this; 
    } 

    bool operator!=(outer_iterator i) const { return outer_ != i; } 
}; 

int main() 
{ 
    std::list<std::list<int>> lli; 
    std::list<int> li; 
    li.push_back(42); 
    li.push_back(13); 
    lli.push_back(li); 
    li.push_back(999); 
    lli.push_back(li); 
    for (Iterator<int> i = lli.begin(); i != lli.end(); ++i) 
     std::cout << *i << ' '; 
    std::cout << '\n'; 
}

輸出：

42 13 42 13 999

通知的bool inner_initialised_變量 - 它保證沒有嘗試在等於end()的外部迭代器值上調用->begin()。

你可能會想血肉出一點與operator==，++(int)，--，一個const版本const_iterator小號等更普遍的使用。我通常會讓自定義迭代器類成爲自定義容器類的成員，提供產生自定義迭代器對象的begin()和end()，但我不確定您是計劃實際使用「方形列表」類還是僅使用無處不在。

來源

2014-02-12 03:27:29

如何實現一個'方形列表'迭代器

回答

相關問題