Обычно «циркулятор» означает адаптер круговой итерации для линейной структуры. На самом деле вы хотите использовать обратный адаптер: он принимает круговую структуру и представляет линейный итератор, имеющий начало и конец - такие концепции просто не применимы к круговым итераторам или круговой структуре.
Итак, чтобы избежать путаницы, я буду ссылаться на итератор как circ_iterator. Истинная circulator для вашей круговой структуры тривиальна и не должна заботиться о каких-либо концах или начинаниях.
Желаемую функциональность можно получить, пометив итератор:
Идиоматический способ получения итераторов start / end для типа T - через begin и end в пространстве имен, где живет T, или через функции-члены с тем же именем , Инстанциация circ_iterator end{a} не будет идиоматической. Вместо этого перегрузите begin и end на circ&. Оба возвращают итератор, указывающий на аргумент. begin обозначает итератор Default, а end обозначает итератор End. Подробнее см. в этом вопросе .
Только конечный итератор является особенным, и всю типичную семантику итератора можно получить, добавив небольшой трехзначный тег к итератору. Его значения:
- Конец: итератор возник в результате
end;
- Inc: итератор не произошел от
end и был недавно увеличен;
- По умолчанию: в противном случае.
Итератор, полученный из 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.
Во-первых, давайте разберемся с теговыми указателями - это очень простая реализация, но она подойдет для наших целей.
// 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;
}
};
Тогда цирк-итератор:
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