通常,“循环器”是线性结构的循环迭代适配器。您想要的实际上是一个反向适配器:它接受循环结构,并呈现具有开始和结束的线性迭代器——这些概念根本不适用于循环迭代器或循环结构。
因此,为避免混淆,我将把迭代器称为“circ_iterator”。对于您的循环结构来说,真正的“circulator”是微不足道的,不必考虑任何结束或开始。
通过标记迭代器,可以获得所需的功能:
获取类型 T
的 start
/end
迭代器的惯用方式是通过 T
所在的命名空间中的 begin
和 end
,或者通过同名的成员函数。实例化 circ_iterator end{a}
是不惯用的。相反,在 circ&
上重载 begin
和 end
。两者都返回指向参数的迭代器。 begin
标记迭代器为 Default
,而 end
标记迭代器为 End
。详情请参见 this question。
只有结束迭代器是特殊的,所有典型的迭代器语义都可以通过向迭代器添加一个小的三值标记来实现。它的值为:
- End:迭代器源自
end
;
- Inc:迭代器不是源自
end
,并且最近已经增加;
- Default:否则。
从 end
获取的迭代器将永远保留其 End
标记。否则,迭代器从 Default
标记开始,增加时切换到 Inc
,并在减少时切换回 Default
。
注意,由于循环容器无法具有零大小,因此
begin
和
end
永远不能相同:一个
circ
项始终至少包含一个数据项。当然,您可以使用与任何其他空迭代器相等的空迭代器表示
circ
实例的缺失。
增量操作是特殊的,因为接近结束迭代器的唯一合法方式是通过增加。这样做时,必须满足以下条件:
- 您不是从结束开始增加的,因为那是非法的。
- 仅在增加后,您可能会在结束之前或结束。
因此,当它们的指针相同时,迭代器是相同的,并且:
- 另一个迭代器未标记为End,或
- 此迭代器未标记为Default(它必须是自身的End或Inc-最近增加的)。
由于标签很小(2位宽),您可以假设或静态断言circ
类型对齐到4个字节并且特定于平台的uintptr_t
<->*circ
转换是“合理的”,并使用标记指针技巧将标记保留在指针的最低有效位中。我提供了使用标记指针技巧和不使用标记指针技巧的版本。
最后,通过从boost::iterator_facade
派生实现迭代器要容易得多。我将const_circ_iterator
的实现留给读者作为练习。文档记录良好。
该代码可在MSVC2012和LLVM 6上编译。
首先,让我们处理标记指针——这是一个非常基本的实现,但对我们的目的足够了。
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