圓形結構的迭代器

Question

下面的代碼顯示了我目前擁有的。它是一個適用於循環數據結構的適配器。主要功能顯示如何使用它。這 都很好，但我真的很想有 迭代器由circ定義的結構。到目前爲止所有的方法都涉及 或者一些計數方案（如果用循環器計數範圍， 構建一個計數增量和減量的迭代器）或布爾值 值來檢查迭代器是否已被移動以避免開始和結束 相等。

是否有一些常見的解決方案來修改循環結構到 迭代器？還有什麼其他的解決方法是可能的？

我想盡可能保持迭代速度，但 願意在這裏妥協。我會重視一個完全符合 迭代器在一個小的速度罰款。

#include <cstddef> // nullptr 
#include <iostream> 
#include <boost/noncopyable.hpp> 
#include <boost/operators.hpp> 

// circular structure that we want to iterate over 
struct circ : private boost::noncopyable { 
    unsigned int i; 
    circ* next; 
    circ* prev; 
}; 

// whacked up circulator, imagine some template cream here to make it 
// generic, omitted to preserve sanity 
struct circulator 
    : public boost::incrementable<circulator> 
    , public boost::decrementable<circulator> 
    , public boost::equality_comparable<circulator, circulator> 
    , public boost::dereferenceable<circulator, circ*> 
{ 
    circulator() 
    : c(nullptr) {} 
    circulator(circ& c) : c(&c) {} 

    bool operator==(const circulator& other) const { 
    return this->c == other.c; 
    } 

    circulator& operator++() { c = c->next; return *this; } 
    circulator& operator--() { c = c->prev; return *this; } 

    explicit operator bool() const { return c; } 

    circ& operator*() const { return *c; } 

    circ* c; 
}; 

int main() 
{ 
    circ a, b, c, d; 
    a.next = &b; a.prev = &a; a.i = 0; 
    b.next = &c; b.prev = &a; b.i = 1; 
    c.next = &d; c.prev = &b; c.i = 2; 
    d.next = &a; d.prev = &c; d.i = 3; 
    circulator begin{a}, end{a}; 
    if(begin) 
    do { 
     std::cout << begin->i << std::endl; 
     begin = ++begin; 
    } while(begin != end); 

    return 0; 
} 

如果有需要，我可以添加一些我以前的做法，但他們 相當冗長，並將不必要的膨脹增加的問題。

編輯：這將是很好，如果生成的迭代器是雙向的。雖然我可以放棄這個要求。

Answer 1

如果是我的話，我有operator++通知終止條件，並設置c一些前哨值：

circulator(circ& c) : c(&c), start(&c) {} 
circulator& operator++() { c = c->next; if(c==start) c=nullptr; return *this; } 

用法：

circulator begin{a}, end; 
while(begin != end) { 
    begin++; 
} 

注意，這種用法定義結束迭代器持有nullptr，這意味着你不能這樣做：

circulator end; 
--end; 

Answer 2

通常，「循環器」是指線性結構的循環迭代適配器。你所期望的實際上是一個逆適配器：它需要一個循環結構，並呈現一個具有開始和結束的線性迭代器 - 這樣的概念不適用於循環迭代器或循環結構。

所以，爲了避免混淆，我將該迭代器稱爲circ_iterator。圓形結構的真實circulator是微不足道的，不能關心任何目標或開始。

所期望的功能可以通過標記所述迭代器可得：

1. 得到start/end迭代器T類型的慣用方法是通過在命名空間begin和end其中T生活，或經由成員函數同名。實例化circ_iterator end{a}將是非慣用的。相反，在circ&上過載begin和end。兩者都返回一個指向參數的迭代器。 begin標記迭代器Default和end標記迭代器End。有關詳細信息，請參閱this question。

2. 只有結束迭代器是特殊的，並且所有典型的迭代器語義都可以通過向迭代器添加一個小的三值標記來實現。它的值是：

   • 結束：迭代器起源於end的結果;
   • Inc：迭代器不是從end發起的並且最近已經遞增;
   • 默認：否則。

   從end獲得的迭代器將永久保留其End標記。否則，迭代器以Default標記開始，並以遞增方式切換到Inc，並在遞減時返回到Default。

注意begin和end永遠是相同的，因爲沒有辦法爲圓形容器具有零大小：一個circ項目始終保持至少一個數據項。當然，您可以使用空迭代器來代表circ實例的缺失，該迭代器將與任何其他空迭代器進行比較。

遞增操作是特殊的，因爲接近結束迭代器的唯一合法方法是遞增。當這樣做時，必須滿足以下條件：

1. 您不是從頭開始遞增，因爲這是違法的。
2. 只有在增量之後，您可能會在結束之前或結束。

因此，迭代器是相同的，當它們的指針是相同的，並且：

• 另一迭代未標記的結束，或
• 此迭代未標記默認（它必須是本身完或公司 - 最近增加）。

由於標籤是小（2個比特寬），可以假定，或靜態地斷言，即特定於平臺的uintptr_t <的circ類型被對準以4個字節和 - >*circ轉換是「理智「，並使用標記的指針技巧將標記保留在指針的最低有效位中。我提供了使用標記指針技巧的版本和不支持的版本。

最後，通過派生自boost::iterator_facade來實現迭代器要容易得多。我將const_circ_iterator的實施作爲練習離開讀者。 It is well documented。

代碼編譯的MSVC2012還取決於LLVM 6

首先，讓我們處理標記指針 - 這是一個非常基本的實現，但我們的目的就行。

// https://github.com/KubaO/stackoverflown/tree/master/questions/circ- 

iterator-9993713 
#include <boost/iterator/iterator_facade.hpp> 
#include <boost/noncopyable.hpp> 
#include <boost/operators.hpp> 
#include <limits> 
#include <iostream> 
#include <cassert> 
#include <cstdint> 
#include <algorithm> 

template <typename T, bool merge_tag = false, typename tag_type = uint8_t> class tagged_ptr; 

template <typename T, typename tag_type> class tagged_ptr<T, true, tag_type> { 
    uintptr_t ptr; 
    typedef std::numeric_limits<uintptr_t> lim; 
    inline static uintptr_t ptr_of(T* p) { 
     assert(tag_of(p) == 0); 
     return uintptr_t(p); 
    } 
    inline static uintptr_t tag_mask() { return 3; } 
    inline uintptr_t ptr_only() const { return ptr & (lim::max() - tag_mask()); } 
    inline static tag_type tag_of(T* p) { return ((tag_type)(uintptr_t)p) & tag_mask(); } 
    inline tag_type tag_only() const { return ptr & tag_mask(); } 
public: 
    tagged_ptr(T* p, tag_type t) : ptr(ptr_of(p) | t) { assert(t <= tag_mask()); } 
    tagged_ptr(const tagged_ptr & other) : ptr(other.ptr) {} 
    operator T*() const { return reinterpret_cast<T*>(ptr_only()); } 
    T* operator->() const { return reinterpret_cast<T*>(ptr_only()); } 
    tagged_ptr & operator=(T* p) { ptr = tag_only() | ptr_of(p); return *this; } 
    tag_type tag() const { return tag_only(); } 
    void set_tag(tag_type tag) { assert(tag <= tag_mask()); ptr = tag | ptr_only(); } 
}; 

template <typename T, typename tag_type> class tagged_ptr<T, false, tag_type> { 
    T* ptr; 
    tag_type m_tag; 
public: 
    tagged_ptr(T* p, tag_type t) : ptr(p), m_tag(t) {} 
    tagged_ptr(const tagged_ptr & other) : ptr(other.ptr), m_tag(other.m_tag) {} 
    operator T*() const { return ptr; } 
    T* operator->() const { return ptr; } 
    tagged_ptr & operator=(T* p) { ptr = p; return *this; } 
    tag_type tag() const { return m_tag; } 
    void set_tag(tag_type tag) { m_tag = tag; } 
}; 

的circ類可以有一些方便的構造，使構建循環列表更容易，並避免你在你的問題做出的錯誤（a.prev = &a是錯誤的）。

struct circ : private boost::noncopyable { 
    unsigned int i; 
    circ* next; 
    circ* prev; 
    explicit circ(int i) : i(i), next(nullptr), prev(nullptr) {} 
    circ(int i, circ& prev) : i(i), next(nullptr), prev(&prev) { 
     prev.next = this; 
    } 
    circ(int i, circ& prev, circ& next) : i(i), next(&next), prev(&prev) { 
     prev.next = this; 
     next.prev = this; 
    } 
}; 

的circ_iterator則是：

class circ_iterator; 
circ_iterator end(circ& c); 

class circ_iterator 
     : public boost::iterator_facade< 
     circ_iterator, circ, boost::bidirectional_traversal_tag 
     > 
{ 
    tagged_ptr<circ> c; 
    enum { Default, Inc, End }; 
    friend class boost::iterator_core_access; 
    friend circ_iterator end(circ&); 
    struct end {}; 
    circ_iterator(circ& c_, end) : c(&c_, End) {} 

    circ& dereference() const { return *c; } 
    void increment() { 
     c = c->next; 
     if (c.tag() != End) c.set_tag(Inc); 
    } 
    void decrement() { 
     c = c->prev; 
     if (c.tag() != End) c.set_tag(Default); 
    } 
    bool equal(const circ_iterator & other) const { 
     return this->c == other.c && 
       (other.c.tag() != End || this->c.tag() != Default); 
    } 
public: 
    circ_iterator() : c(nullptr, Default) {} 
    circ_iterator(circ& c_) : c(&c_, Default) {} 
    circ_iterator(const circ_iterator& other) : c(other.c) {} 
}; 

circ_iterator begin(circ& c) { return circ_iterator(c); } 
circ_iterator end(circ& c) { return circ_iterator(c, circ_iterator::end()); } 

最後，一個簡單的例子：

int main() 
{ 
    circ a(0), b(1, a), c(2, b), d(3, c, a); 
    assert(end(a) == end(a)); 
    assert(++--end(a) == end(a)); 
    for (auto it = begin(a); it != end(a); ++it) { 
     std::cout << it->i << std::endl; 
    } 
    std::cout << "*" << std::endl; 
    for (auto it = ++begin(a); it != --end(a); ++it) { 
     std::cout << it->i << std::endl; 
    } 
    std::cout << "*" << std::endl; 
    for (auto & c : a) 
     std::cout << c.i << std::endl; 
} 

輸出：

0 
1 
2 
3 
* 
1 
2 
* 
0 
1 
2 
3