Итераторы для круговых структур

Question

Следующий код показывает, что у меня есть. Это адаптер для кольцевых структур данных . Основная функция показывает, как она используется. Это все хорошо и быстро, но я действительно хотел бы иметь итераторы над структурой, определенной circ. Все подходы до сих пор включали либо какую-либо схему подсчета (подсчитайте диапазон, если с циркулятором, построить итератор, который подсчитывает приращения и декременты) или boolean значений, чтобы проверить, был ли итератор перемещен, чтобы избежать начала и конца равным ,

Есть ли общие решения для адаптации круговой структуры к итераторам? Какие еще возможности для работы?

Я хотел бы сохранить скорость итерации как можно больше, но готов пойти на компромиссы здесь. Я бы оценил полностью соответствующий итератор за небольшую штрафную скорость.

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

Если нужно буду, я могу добавить некоторые из моих предыдущих подходов, но они довольно многословные и добавлю ненужные навороты к этому вопросу.

EDIT: Было бы неплохо, если бы полученный итератор был двунаправленным. Хотя я могу отказаться от этого требования.

Answer 1

Если бы это было, я бы operator++ уведомления терминал условия, и установить c в какое-то Sentinal значения:

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} был бы неидиоматическим. Вместо этого перегрузка begin и end на circ&. Оба возвращают итератор, указывающий на аргумент. begin теги итератор Default и end теги итератор End. См. this question.

2. Только конечный итератор является особым, и вся типичная семантика итератора может быть выполнена путем добавления к итератору небольшого трехзначного тега. Его значения:

   • Конец: Итератор возник из-за end;
   • Inc: итератор не происходил от end и был самым последним приращением;
   • По умолчанию: в противном случае.

   Итератор, полученный от end, сохранит свой знак End навсегда. В противном случае итератор начинает с тега Default и переключается на Inc с шагом и обратно до Default по декременту.

Обратите внимание, что begin и end никогда не могут быть одинаковыми, так как нет никакого способа для круговой контейнер, чтобы иметь нулевой размер: а circ элемент всегда имеет место по крайней мере один элемент данных. Конечно, вы можете представить отсутствие экземпляра circ с использованием нулевого итератора, который сравнивается с любым другим нулевым итератором.

Операция приращения является специальной, так как единственным законным способом приближения к итератору конца является увеличение. При этом должны быть соблюдены следующие условия:

1. Вы не увеличиваете число начиная с конца, так как это незаконно.
2. Только после инкремента вы можете быть до конца или в конце.

Таким образом, итераторы идентичны, когда их указатели идентичны, а также:

• другой итератор не помечен End, или
• этот итератор не помечен по умолчанию (она должна быть сам по себе End или Inc - недавно увеличен).

Поскольку тег мал (2 бита), то можно предположить, или статически утверждать, что circ тип выравнивается по 4 байта и на конкретной платформе uintptr_t < ->*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