循环结构的迭代器

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;
}

如果需要的话，我可以添加一些以前的方法，但它们有点冗长，会给问题增加不必要的负担。

编辑：如果生成的迭代器是双向的那就太好了。虽然我可以放弃这个需求。

- pmr

---

你有没有考虑使用（或者至少借鉴）boost::circular_buffer的设计？ - Robᵩ

据我所知，循环缓冲区并不是真正的循环迭代器。例如，越过结尾并不一定会使您到达开头。无论如何，我还是会检查一下。也许我的想法有点模糊。 - pmr

请查看这里更好的答案（令人惊讶的是，它比现在的回答早了3年）：https://dev59.com/KHI-5IYBdhLWcg3wlpYM#1782262 - Sergey Shevchenko

CGAL库定义并实现了环形迭代器的概念。https://doc.cgal.org/latest/Circulator/classCirculator.html - alfC

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;

- Robᵩ

---

这也需要一些技巧来使 operator-- 在迭代器中的 end 上工作，这是必需的。否则，思路不错。 - pmr

“operator--” 对于 ForwardIterator 不是必需的，只对 BidirectionalIterator 必需。您需要哪一个？ - Robᵩ

我将在问题中添加“双向”要求。我认为这很明显，因为circ有一个prev和next指针，而我的原始循环器也是如此。 - pmr

Answer 2

通常，“循环器”是线性结构的循环迭代适配器。您想要的实际上是一个反向适配器：它接受循环结构，并呈现具有开始和结束的线性迭代器——这些概念根本不适用于循环迭代器或循环结构。

因此，为避免混淆，我将把迭代器称为“circ_iterator”。对于您的循环结构来说，真正的“circulator”是微不足道的，不必考虑任何结束或开始。

通过标记迭代器，可以获得所需的功能：

1. 获取类型 T 的 start/end 迭代器的惯用方式是通过 T 所在的命名空间中的 begin 和 end，或者通过同名的成员函数。实例化 circ_iterator end{a} 是不惯用的。相反，在 circ& 上重载 begin 和 end。两者都返回指向参数的迭代器。 begin 标记迭代器为 Default，而 end 标记迭代器为 End。详情请参见 this question。

2. 只有结束迭代器是特殊的，所有典型的迭代器语义都可以通过向迭代器添加一个小的三值标记来实现。它的值为：

   • End：迭代器源自 end；
   • Inc：迭代器不是源自 end，并且最近已经增加；
   • Default：否则。

   从 end 获取的迭代器将永远保留其 End 标记。否则，迭代器从 Default 标记开始，增加时切换到 Inc，并在减少时切换回 Default。

注意，由于循环容器无法具有零大小，因此begin和end永远不能相同：一个circ项始终至少包含一个数据项。当然，您可以使用与任何其他空迭代器相等的空迭代器表示circ实例的缺失。

增量操作是特殊的，因为接近结束迭代器的唯一合法方式是通过增加。这样做时，必须满足以下条件：

1. 您不是从结束开始增加的，因为那是非法的。
2. 仅在增加后，您可能会在结束之前或结束。

因此，当它们的指针相同时，迭代器是相同的，并且：

• 另一个迭代器未标记为End，或
• 此迭代器未标记为Default（它必须是自身的End或Inc-最近增加的）。

由于标签很小（2位宽），您可以假设或静态断言circ类型对齐到4个字节并且特定于平台的uintptr_t<->*circ转换是“合理的”，并使用标记指针技巧将标记保留在指针的最低有效位中。我提供了使用标记指针技巧和不使用标记指针技巧的版本。

最后，通过从boost::iterator_facade派生实现迭代器要容易得多。我将const_circ_iterator的实现留给读者作为练习。文档记录良好。

该代码可在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

- Kuba hasn't forgotten Monica