Iteratoren für kreisförmige Strukturen

Question

Der folgende Code zeigt, was ich derzeit habe. Es ist ein Adapter für zirkuläre Datenstrukturen. Die Hauptfunktion zeigt, wie sie verwendet wird. Diese ist alles schön und schnell, aber ich hätte gerne Iteratoren über die Struktur definiert durch circ. Alle bisherigen Ansätze beinhalten entweder ein Zählschema (zähle den Bereich wenn mit dem Zirkulator, baue einen Iterator, der Inkremente und Dekremente zählt) oder boolean Werte um zu überprüfen, ob der Iterator verschoben wurde um Anfang und Ende zu vermeiden .

Gibt es einige allgemeine Lösungen, um eine zirkuläre Struktur an Iteratoren anzupassen? Welche anderen Umgehungen sind möglich?

Ich möchte die Iterationsgeschwindigkeit so gut wie möglich beibehalten, aber bin bereit, hier Kompromisse zu machen. Ich würde einen vollständig übereinstimmenden Iterator über eine kleine Geschwindigkeitsstrafe schätzen.

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

Wenn Notwendigkeit ich einige meiner bisherigen Ansätze hinzufügen können, aber sie sind ziemlich ausführlich und würde unnötig aufblähen auf die Frage hinzuzufügen.

EDIT: Es wäre nett, wenn der resultierende Iterator bidirektional wäre. Obwohl ich diese Anforderung aufgeben kann.

Answer 1

Wenn es nach mir ginge, würde ich operator++ Mitteilung der Endbedingung, mitzuführen und c bis zu einem gewissen sentinal Wert:

circulator(circ& c) : c(&c), start(&c) {} 
circulator& operator++() { c = c->next; if(c==start) c=nullptr; return *this; } 

Verbrauch:

circulator begin{a}, end; 
while(begin != end) { 
    begin++; 
} 

Beachten Sie, dass diese Nutzung definiert das Ende Iterator als Halten einer Nullptr, was bedeutet, dass Sie dies nicht tun können:

Answer 2

Normalerweise bedeutet "Zirkulator" einen kreisförmigen Iterationsadapter für eine lineare Struktur. Was Sie wünschen, ist wirklich ein umgekehrter Adapter: Es braucht eine zirkuläre Struktur und präsentiert einen linearen Iterator, der einen Anfang und ein Ende hat - solche Konzepte gelten einfach nicht für zirkuläre Iteratoren oder zirkuläre Strukturen.

Also, um Verwirrung zu vermeiden, werde ich den Iterator als circ_iterator bezeichnen. Die wahre circulator für Ihre kreisförmige Struktur ist trivial und muss sich nicht um irgendwelche Enden oder Anfänge kümmern.

Die gewünschte Funktionalität kann durch Markieren des Iterator gehabt werden:

1. Der idiomatische Weg start/end Iteratoren des Erhaltens T für Typen ist über begin und end im Namensraum, wo T Leben oder über Mitgliederfunktionen mit dem gleichen Namen. Die Instanziierung circ_iterator end{a} wäre nicht idiomatisch. Überlasten Sie stattdessen begin und end auf circ&. Beide geben einen Iterator zurück, der auf das Argument zeigt. begin Tags der Iterator Default und end Tags der Iterator End. Einzelheiten finden Sie unter this question.

2. Nur der End-Iterator ist speziell und alle typischen Iteratorsemantiken können durch Hinzufügen eines kleinen, dreiwertigen Tags zum Iterator erstellt werden. Seine Werte sind:

   • Ende: der Iterator entstand als Ergebnis von end;
   • Inc: der Iterator stammt nicht von end und wurde zuletzt inkrementiert;
   • Vorgabe: Sonst.

   Ein Iterator von end erhalten wird für immer seine End Tag behalten. Andernfalls startet ein Iterator mit dem Tag Default und wechselt bei Inkrementierung auf Inc und bei Dekrement auf Default zurück.

Beachten Sie, dass begin und end können nie gleich sein, da es keine Möglichkeit für den kreisförmigen Behälter ist eine Null-Größe zu haben: ein circ Element hält immer mindestens ein Datenelement. Sie könnten natürlich eine Abwesenheit einer circ Instanz darstellen, die einen Null-Iterator verwendet, der den gleichen Wert wie jeder andere Null-Iterator hat.

Die Inkrement-Operation ist speziell, da der einzige legale Weg, sich dem End-Iterator zu nähern, durch Inkrementieren erfolgt. Dabei muss Folgendes gelten:

1. Sie erhöhen nicht beginnend am Ende, da dies illegal ist.
2. Nur nach einem Inkrement können Sie vor dem Ende oder am Ende sein.

Somit sind die Iteratoren identisch sind, wenn ihre Zeiger identisch sind, und:

• die andere Iterator Ende nicht markiert oder
• diese Iterator Standard nicht markiert (es muss sich Ende sein oder Inc - kürzlich inkrementiert).

Da der Tag ist klein (2 Bit breit), können Sie davon ausgehen, oder statisch behaupten, dass die circ Typ 4 Byte ausgerichtet ist und die plattformspezifischen uintptr_t < ->*circ Conversions „gesund sind und Verwenden des markierten Zeigertricks, um das Etikett in den niedrigstwertigen Bits des Zeigers zu halten. Ich stelle sowohl die Version bereit, die den getaggten Pointer-Trick verwendet, als auch die, die das nicht tut.

Schließlich ist es viel einfacher, Iteratoren durch Ableiten von boost::iterator_facade zu implementieren. Ich überlasse die Implementierung von const_circ_iterator als eine Übung für den Leser. It is well documented.

Der Code kompiliert auf MSVC2012 und auch auf LLVM 6.

Lassen Sie uns zunächst mit den etikettierten Zeiger umgehen - das ist eine sehr einfache Implementierung, aber für unsere Zwecke zu tun.

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

Die circ Klasse können einige Bequemlichkeit Konstrukteure müssen Kreislisten erleichtern die Konstruktion und den Fehler, den Sie in Ihrer Frage gestellt vermeiden (a.prev = &a ist falsch).

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

Die circ_iterator ist dann:

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

Schließlich ist eine einfache Demonstration:

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

Ausgang:

0 
1 
2 
3 
* 
1 
2 
* 
0 
1 
2 
3