Mit boost :: Iterator

Question

Ich schrieb einen spärlichen Vektor Klasse (siehe #1, #2.)

Ich möchte zwei Arten von Iteratoren bieten:

Der erste Satz, die regulären Iteratoren kann jeder Punkt Element, ob gesetzt oder nicht gesetzt. Wenn sie gelesen werden, geben sie entweder den gesetzten Wert oder value_type() zurück, wenn sie geschrieben werden, erzeugen sie das Element und geben die lvalue-Referenz zurück. So sind sie:

Random Access Traversal Iterator und Lesbare und Beschreibbare Iterator

Der zweite Satz, die spärlich Iteratoren iterieren nur die Set-Elemente. Da sie träge keine Elemente erstellen müssen, die geschrieben werden, sind sie:

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

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

Ich kann die Lücken ausfüllen, aber nicht sicher, wie boost :: iterator_adaptor zu starten.

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 iterator_adaptor in Ihrem Fall verwenden möchten - Sie möchten vielleicht iterator_facade stattdessen verwenden.

Ausführlichere Erläuterung: iterator_adaptors werden verwendet, wenn Sie einen vorhandenen Iterator haben (z. B. std::list<int>::iterator) und sein Verhalten für Ihren Iterator wiederverwenden möchten, z. Ihr Iterator gibt den doppelten Wert des Inhalts der Liste zurück, verwendet aber den Traversalcode des ursprünglichen Iterators erneut. Oder umgekehrt: Sie möchten vielleicht einen Iterator, der einige der Elemente in der ursprünglichen Liste überspringt, aber die Werte unverändert zurückgibt. Ich bin mir nicht sicher, ob Sie Ihren Iterator (wie im Wiederholungscode von) auf Iteratoren Ihrer zugrundeliegenden Strukturen basieren wollen, aber für mich sprechen würde ich nicht besonders im Fall von nichtparser Iterator, wie Sie wahrscheinlich einige erstellen möchten Proxy für die Referenz, was bedeutet, dass Sie keine zugrunde liegenden Iterator dereference() Code verwenden können, und Traversal ist wahrscheinlich einfach. Sie können jedoch Ihre sparse_iterator auf einen Iterator aufbauen, der bei Bedarf über tatsächlich vorhandene Elemente des Arrays iteriert.

Es gibt Probleme mit dem Proxy-Ansatz, also erwarte nicht, dass es fehlerfrei funktioniert, ohne viele Grenzen zu durchlaufen. Zum einen sollte die const-Version des Nicht-Parser-Iterators immer noch value_type() zurückgeben, was bedeutet, dass Ausdrücke wie iter->foo() in value_type().foo() übersetzt werden sollten, wenn der entsprechende Eintrag nicht existiert. Aber das wirft eine Schwierigkeit auf, die pointer_proxy::operator->() sollte etwas mit operator->, vorzugsweise ein Zeiger (definitiv nicht value_type()) zurückgeben. Was zur entscheidenden Frage führt: Ein Zeiger auf was?Es gibt Möglichkeiten, dies zu lösen (zum Beispiel, wenn Sie Ihre Objekte von boost::shared_pointer verwaltet haben, können Sie einfach shared_pointer an eine new 'd Instanz zurückgeben).

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

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

• reference_proxy::foo() für jede foo() Mitgliedsfunktion von Wert E_TYPE (sonst Ausdrücke wie (*it).foo() AFAIK nicht funktionieren)

• class pointer_proxy mit

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

Die Parameter Die Iterator-Fassadenvorlage sollte wie folgt lauten:

• Reference: die reference_proxy
• Pointer: die pointer_proxy

Die spärliche Version ist einfacher: Wenn die zugrunde liegende Iterator sinnvoll ist (dh. entspricht dem gewünschten Verhalten) und korrekt implementiert, Sie können einfach die Parameter iterator_adaptor (außer den ersten beiden) weglassen, und nehmen Sie die gesamte Implementierung.

Das Problem "Kompiliert nicht": Einfügen typename.