Mit boost :: Iterator

Question

Ich schrieb eine spärliche Vektor Klasse (siehe # 1 , # 2 .)

Ich möchte zwei Arten von Iteratoren bieten:

Der erste Satz, die regelmäßigen Iteratoren kann jedes Element zeigen, ob Satz oder nicht gesetzt. Wenn sie aus gelesen werden, kehren sie entweder den eingestellten Wert oder value_type(), wenn sie geschrieben sind, schaffen sie das Element und gibt den L-Wert-Referenz. So sind sie:

Random Access Traversal Iterator und Lesbare und Beschreibbare Iterator

Der zweite Satz, die spärlich Iteratoren Iterierte nur über die Set-Elemente. Da sie nicht brauchen Elemente zu träge erstellen, die geschrieben werden, sind sie:

Random Access Traversal Iterator und Lesbare und Beschreibbare und L-Wert Iterator

Ich brauche auch const Versionen der beiden, die nicht beschreibbar sind.

Ich kann in den Lücken füllen, aber nicht sicher, wie Boost verwenden :: iterator_adaptor zu beginnen.

Hier ist, was ich bisher:

template<typename T>
class sparse_vector {
public:
    typedef size_t size_type;
    typedef T value_type;

private:
    typedef T& true_reference;
    typedef const T* const_pointer;
    typedef sparse_vector<T> self_type;
    struct ElementType {
        ElementType(size_type i, T const& t): index(i), value(t) {}
        ElementType(size_type i, T&& t): index(i), value(t) {}
        ElementType(size_type i): index(i) {}
        ElementType(ElementType const&) = default;
        size_type index;
        value_type value;
    };
    typedef vector<ElementType> array_type;

public:
    typedef T* pointer;
    typedef T& reference;
    typedef const T& const_reference;

private:
    size_type                                   size_;
    mutable typename array_type::size_type      sorted_filled_; 
    mutable array_type                          data_;

// lots of code for various algorithms...

public:    
    class sparse_iterator
        : public boost::iterator_adaptor<
          sparse_iterator                   // Derived
          , typename array_type::iterator            // Base (the internal array)
          , value_type              // Value
          , boost::random_access_traversal_tag    // CategoryOrTraversal
          > {...}

    class iterator_proxy {
          ???
    };

    class iterator
        : public boost::iterator_facade<
          iterator                          // Derived
          , ?????                           // Base
          , ?????              // Value
          , boost::??????    // CategoryOrTraversal
          > {
    };
};

Auch ist dies illegal?

typedef boost::reverse_iterator<sparse_iterator> reverse_sparse_iterator;

Answer 1

Ich bin nicht sicher, dass Sie wirklich Gebrauch iterator_adaptor in Ihrem Fall wollen -. Sie verwenden iterator_facade stattdessen wollen könnte

Weitere ausführliche Erklärung: iterator_adaptors verwendet werden, wenn Sie eine bestehende Iterator haben (sagen wir mal std::list<int>::iterator) und wollen ihr Verhalten für Ihre Iterator wieder zu verwenden, z. B. Ihr Iterator zweimal den Wert zurückzugeben, was in der Liste enthalten ist, aber die Wiederverwendung Traversal-Code aus dem ursprünglichen Iterator. Oder umgekehrt: Sie könnten einen Iterator wollen, dass einige der Elemente in der ursprünglichen Liste überspringen, aber kehren die Werte unverändert. Ich bin nicht sicher, ob Sie Ihren Iterator basieren sollen (wie in Wiederverwendung Code) auf Iteratoren Ihrer zugrunde liegenden Strukturen, aber für mich sprechen, würde ich nicht besonders im Fall von nonsparse Iterator als würden Sie wollen wahrscheinlich etwas schaffen Proxy für die Referenz, die bedeutet, dass Sie nicht zugrunde liegenden Iterator dereference() Code verwenden können, und Traversal ist wahrscheinlich einfach. Sie können jedoch die Basis Ihre sparse_iterator auf einige Iterator, dass iteriert tatsächlich Elemente des Arrays bestehenden wenn Sie möchten.

Es gibt Probleme mit dem Proxy-Ansatz, also nicht erwarten, es ohne durch viele Reifen einwandfrei zu arbeiten. Für eine Sache, die const-Version des nonsparse sollte Iterator noch zurückkehren value_type(), die Mittel Ausdrücke wie iter->foo() zu value_type().foo() übersetzen sollten, wenn der entsprechende Eintrag nicht existiert. Aber dies stellt eine Schwierigkeit, sollte dieser pointer_proxy::operator->() zurückkehrt etwas mit operator->, vorzugsweise einen Zeiger (definitiv nicht value_type()). Das führt zu der entscheidenden Frage: Ein Zeiger auf was? Es gibt Möglichkeiten, dies zu lösen (für ein, wenn Sie Ihre Objekte von boost::shared_pointer verwaltet, kann man einfach ein shared_pointer zu einer new'd Instanz zurück).

Für die nonsparse Iterator, müssen Sie implementieren:

• class reference_proxy mit
• reference_proxy::operator& (die wahrscheinlich einen Zeiger Proxy zurück)
• reference_proxy::operator value_type&() für const Anwendungen
• reference_proxy::operator const value_type&() für Nicht-const Anwendungen

• reference_proxy::foo() für jede foo() Memberfunktion von value_type (sonst Ausdrücke wie (*it).foo() AFAIK nicht funktionieren wird)

• class pointer_proxy mit

• pointer_proxy::operator* (zurückgeben reference_proxy)
• pointer_proxy::operator-> (tun etwas Vernünftiges, siehe oben)

Die Parameter an die Iterator Fassade Vorlage sollte sein:

• Reference: die reference_proxy
• Pointer: die pointer_proxy

Die spärliche Version ist einfacher: Wenn der Iterator zugrunde liegenden sinnvoll ist (. Dh Spiele das gewünschte Verhalten) und ordnungsgemäß durchgeführt, können Sie weglassen nur die Parameter an die iterator_adaptor (mit Ausnahme der ersten beiden), und nehmen Sie alle die Umsetzung .

Die "lässt sich nicht kompilieren" Problem:. Einsatz typename