Mit boost::iterator
Schrieb ich eine sparse-Vektor-Klasse (siehe #1, #2.)
Möchte ich zwei Arten von Iteratoren:
Den ersten Satz, den regelmäßigen Iteratoren, können Punkt-jedes element, ob gesetzt oder nicht gesetzt. Wenn Sie Lesen, Sie kehren entweder der Sollwert oder value_type()
, wenn Sie geschrieben werden, erstellen Sie das element und die Rückgabe der lvalue-Referenz. So sind Sie:
Random-Access-Traversal Iterator und Lesbar und Beschreibbar Iterator
Den zweiten Satz, das sparse-Iteratoren, Durchlaufen nur die set-Elemente. Da brauchen Sie nicht zu träge zu erstellen, die Elemente, die geschrieben werden, sind Sie:
Random-Access-Traversal Iterator und Lesbar und Beschreibbar und Lvalue Iterator
Brauche ich auch, const Versionen der beiden, die sind nicht beschreibbar.
Kann ich in die Leerstellen zu füllen, aber nicht sicher, wie die Verwendung von boost::iterator_adaptor zu beginnen.
Hier ist, was ich habe, so weit:
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
> {
};
};
außerdem ist das illegal?
typedef boost::reverse_iterator<sparse_iterator> reverse_sparse_iterator;
Du musst angemeldet sein, um einen Kommentar abzugeben.
Ich bin mir nicht sicher, dass Sie wirklich wollen, zu verwenden
iterator_adaptor
in Ihrem Fall - Sie möchten möglicherweise verwenden Sieiterator_facade
statt.Ausführliche Erklärung:
iterator_adaptors
werden verwendet, wenn Sie eine bestehende iterator (sagen wir malstd::list<int>::iterator
) und wiederverwenden möchten, Ihr Verhalten für Ihre iterator, zB. Ihre iterator zurückgeben wird, den doppelten Wert von dem, was in der Liste, aber die Wiederverwendung traversal-code von der original-iterator. Oder anders herum: vielleicht möchten Sie einen iterator, überspringen einige der Elemente in der ursprünglichen Liste, aber wieder die Werte unverändert. Ich bin mir nicht sicher, ob Sie Basis-iterator (wie in der Wiederverwendung von code) mit Iteratoren der Ihr zugrunde liegenden Strukturen, sondern spricht für mich, ich würde nicht vor allem im Fall von nonsparse iterator als würden Sie wahrscheinlich wollen, um einige proxy für die Referenz, das heißt, Sie können nicht alle zugrunde liegenden iteratordereference()
code, und traversal ist wahrscheinlich einfach. Sie können jedoch als Basis für Ihrsparse_iterator
auf einige iterator, iteriert über die tatsächlich vorhandenen Elemente des Arrays, wenn Sie wollen.Gibt es Probleme mit dem proxy-Ansatz, also nicht erwarten, dass es einwandfrei funktioniert, ohne durch viele Reifen. Für eine Sache, die const-version des nonsparse iterator sollte noch zurück
value_type()
, was bedeutet, dass Ausdrücke wieiter->foo()
übersetzen sollten, umvalue_type().foo()
wenn der entsprechende Eintrag nicht vorhanden ist. Aber dies birgt die Schwierigkeit, dasspointer_proxy::operator->()
etwas zurückgeben sollte mitoperator->
, vorzugsweise einen Zeiger (definitiv nichtvalue_type()
). Das führt zu der entscheidenden Frage: Einen Zeiger auf was? Es gibt Möglichkeiten, um dieses Problem zu lösen (für einen, wenn Sie Ihre Objekte verwaltetboost::shared_pointer
haben, können Sie einfach schicken Sie eineshared_pointer
zu einemnew
'd. B.).Für die nonsparse iterator, die Sie implementieren müssen:
class reference_proxy
mitreference_proxy::operator&
(das wird wohl wieder ein Zeiger proxy)reference_proxy::operator value_type&()
für const verwendetreference_proxy::operator const value_type&()
für non-const verwendetreference_proxy::foo()
für allefoo()
member-Funktion von value_type (sonst Ausdrücke wie(*it).foo()
AFAIK nicht funktionieren)class pointer_proxy
mitpointer_proxy::operator*
(Rückkehr eine reference_proxy)pointer_proxy::operator->
(tun Sie etwas vernünftiges, siehe oben)Die Parameter für die iterator-Fassade Vorlage:
Reference
: diereference_proxy
Pointer
: diepointer_proxy
Sparse-version ist einfacher: Wenn die zugrunde liegende iterator sinnvoll ist (ie. entspricht das Verhalten, die Sie wollen) - und richtig umgesetzt, können Sie nur die Parameter weglassen, um die
iterator_adaptor
(mit Ausnahme der ersten beiden), und nehmen Sie alle die Umsetzung.Das "nicht kompiliert" problem: einfügen
typename
.