圆形结构的迭代器

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