Type-Erased Ranges
-
Nexus schrieb:
Dann gehören die
any<X>
-Objekte aber dem Container, bei Ranges handelt es sich nur um Verweise (View auf Container). Und ich brauche keinen vollständigen Container wiestd::vector
, eine Range bietet nur einen Teil der Operationen an.Das verstehe ich nicht. Irgendwo müssen die Objekte ja liegen. Und ein vector ist per Definition eine Range. Was meinst Du mit Range.
make_pair( vec.begin(),vec.end() )
liefert Dir auch eine View auf den vector.Du kannst natürlich die any Types in jede beliebte Struktur packen und Dir eine Range dafür definieren.
Nexus schrieb:
Ausserdem fürchte ich, dass die Type-Erasure-Library mit dem exzessiven Einsatz von Boost.MPL und impliziten Concepts für den 0815-Benutzer viel zu kompliziert ist. Aber danke trotzdem für den Hinweis auf die Bibliothek!
Das kann sein, man kann einen any Type aber auch relativ einfach selber implementieren.
-
Wozu brauch ich überhaupt
any
? Der Elementtyp selbst soll ja nicht type-erased sein, nur die Iteratoren bzw. die Range.
-
Nexus schrieb:
Wozu brauch ich überhaupt
any
? Der Elementtyp selbst soll ja nicht type-erased sein, nur die Iteratoren bzw. die Range.Weil wenn du type erasure betreibst du so oder so alle kosten zahlst, egal wieviel zu erased. also erased man einfach alles und hat wenigstens maximale flexibilitaet.
-
Die Flexibilität ist aber nicht gratis, man bezahlt sie teuer mit Typsicherheit (und Typinferenz). Das zeigt sich dann in
auto elem = any_cast<MyType>(*range); // Todo: Fehlerbehandlung
statt
auto elem = *range;
Ich sehe den Vorteil echt nicht, im Endeffekt ist man dauernd am casten. Wie will man überhaupt von der "Flexibilität" mehrerer Typen Gebrauch machen, ohne explizite If-Else-Fallunterscheidungen einzusetzen?
-
Naja...
Die
range<T>
könnte ja von einerany_range
ableiten.any_range
könnte dabei sämtliche Funktionen anbieten die nicht das aktuelle Element zurückgeben, also alles bis auf diefront/back
Funktionen. Bzw. man könnte sogarfront_ptr/back_ptr
Funktionen anbieten, die einfach void-Zeiger zurückgeben.Wenn man es schlau anstellt, sollte das mMn. auch möglich sein ohne dass man dabei zusätzliche Performance-Einbussen hat.
Die zusätzliche Type-Erasure liesse sich verwenden um dem Template-Bloat in diversen Algorithmen entgegenzuwirken.
Natürlich würde man an der Stelle dann erneut für die Type-Erasure im Algorithmus zahlen, mit einem virtual-call bzw. function-pointer-call überall wo man auf ein Element zugreifen muss.Ob das jetzt Sinn macht oder nicht sei mal dahingestellt, aber wenn man es gratis oder quasi-gratis anbieten kann, dann könnte das bei sowas allgemeinem wie einer Range-Implementierung schon Sinn machen.
----
Was mMn. gar keinen Sinn macht ist der Weg über any. Denn ich traue mich wetten, dass man mit any so überhaupt keine Chance hat es vergleichbar schnell wie ohne die 2. Type-Erasure hinzubekommen. Wenn überhaupt, dann über void-Zeiger. void-Zeiger sind nicht böse
-
Die Any-Range klingt interessant, allerdings kommt beim Elementzugriff (der in STL-Style-Algorithmen oft vorkommt, z.B. für
swap()
) wieder einany
ins Spiel.Bei meiner Range bin ich vor allem von Anwendungsfällen wie im
ControlUnits()
-Beispiel ausgegangen, wo es um konkrete Elementtypen geht. Wenn sich diese als Spezialfall der Any-Range performant implementieren liesse, wäre das durchaus eine Überlegung wert. Möglicherweise kann man durch die zusätzliche Typsicherheit in der konkreten Range schnell casten.Mal schauen, ich habe inzwischen mit der Implementierung begonnen.
-
BTW: willst du die Iteratoren-Variante bauen (also dass man von der Range wieder Iteratoren bekommen kann wenn man will), oder eine "reine" Range?
Und was ist das
ControlUnits()
-Beispiel? - kann ich grad nicht zuordnen...
-
Hab mal bisschen was gebastelt.
#include <cstddef> #include <memory> template <typename T> struct default_iterator_traits { typedef std::size_t size_type; typedef std::ptrdiff_t difference_type; typedef T value_type; typedef T& reference; typedef T const& const_reference; typedef T* pointer; typedef T const* const_pointer; }; template <typename T, typename Traits> struct forward_iterator; template <typename T, typename Traits> bool operator == (forward_iterator<T, Traits> const& first, forward_iterator<T, Traits> const& second); template <typename T, typename Traits = default_iterator_traits<T>> struct forward_iterator { typedef typename Traits::size_type size_type; typedef typename Traits::difference_type difference_type; typedef typename Traits::value_type value_type; typedef typename Traits::reference reference; typedef typename Traits::const_reference const_reference; typedef typename Traits::pointer pointer; typedef typename Traits::const_pointer const_pointer; forward_iterator(forward_iterator const& other) : wrapper_(other.wrapper_->clone()) {} template <typename ForwardIterator> forward_iterator(ForwardIterator const& iter) : wrapper_(new wrapper<ForwardIterator>(iter)) {} forward_iterator& operator = (forward_iterator const& other) { if(&other != this) wrapper_.reset(other.wrapper_->clone()); return *this; } forward_iterator& operator ++ () { ++*wrapper_; return *this; } forward_iterator operator ++ (int) { forward_iterator iter(*this); ++iter; return iter; } reference operator * () const { return **wrapper_; } pointer operator -> () const { return (*wrapper_).operator -> (); } friend bool operator == <>(forward_iterator const& first, forward_iterator const& second); private: struct wrapper_base { virtual void operator ++ () = 0; virtual reference operator * () const = 0; virtual pointer operator -> () const = 0; virtual bool operator == (wrapper_base& other) const = 0; virtual wrapper_base* clone() const = 0; virtual ~wrapper_base() {} }; template <typename ForwardIterator> struct wrapper : wrapper_base { wrapper(ForwardIterator const& iter) : iter_(iter) {} virtual void operator ++ () override { ++iter_; } virtual reference operator * () const override { return *iter_; } virtual pointer operator -> () const override { return iter_.operator -> (); } virtual bool operator == (wrapper_base& other) const override { wrapper* w = dynamic_cast<wrapper*>(&other); return w && iter_ == w->iter_; } virtual wrapper_base* clone() const override { return new wrapper(iter_); } private: ForwardIterator iter_; }; std::unique_ptr<wrapper_base> wrapper_; }; template <typename T, typename Traits> bool operator == (forward_iterator<T, Traits> const& first, forward_iterator<T, Traits> const& second) { #pragma GCC diagnostic ignored "-Wparentheses" // icanhaz no warning plox return !first.wrapper_ && !second.wrapper_ || *first.wrapper_ == *second.wrapper_; #pragma GCC diagnostic warning "-Wparentheses" } template <typename T, typename Traits> bool operator != (forward_iterator<T, Traits> const& first, forward_iterator<T, Traits> const& second) { return !(first == second); } template <typename T, typename IteratorTraits = default_iterator_traits<T>> struct forward_range { typedef typename IteratorTraits::size_type size_type; typedef typename IteratorTraits::difference_type difference_type; typedef typename IteratorTraits::value_type value_type; typedef typename IteratorTraits::reference reference; typedef typename IteratorTraits::const_reference const_reference; typedef typename IteratorTraits::pointer pointer; typedef typename IteratorTraits::const_pointer const_pointer; typedef forward_iterator<T, IteratorTraits> iterator; template <typename ForwardIterator> forward_range(ForwardIterator const& begin, ForwardIterator const& end) : begin_(begin), end_(end) {} iterator begin() { return begin_; } iterator end() { return end_; } private: iterator begin_, end_; }; ////////////////////////////////// #include <iostream> #include <vector> void foo(forward_range<int> r) { for(int i : r) std::cout << i << '\n'; } int main() { std::vector<int> v{ 1, 2, 3, 4, 5 }; foo({ v.begin(), v.end() }); }
So ungefaehr?
-
Ja, meine Implementierung sieht recht ähnlich aus. Nur ein paar Punkte:
- Ich habe in der Basisklasse benannte Funktionen statt Operatoren. Für die Dereferenzierung sollte eigentlich eine Funktion reichen, oder?
- Generalisierungen wie Traits implementiere ich normalerweise erst später (warum nicht
std::iterator_traits
?). Optimierungen und Debugging werden so einfacher. Auch verschiedene Iteratorkategorien und Const-Iteratoren wären ein Thema... - Auf diverse C++11-Features muss ich wegen Visual Studio verzichten.
- Bei
operator==
würde ich im Release-Modus wohlstatic_cast
stattdynamic_cast
nehmen. Verschiedenewrapper
-Instantiierungen deuten auf inkompatible Iteratoren hin, da sollte UB zugunsten der Geschwindigkeit vertretbar sein. - Die Range hat weitere Methoden, sodass man sie nicht nur über Iteratoren ansprechen kann.
-
Nexus schrieb:
Ich habe in der Basisklasse benannte Funktionen statt Operatoren. Für die Dereferenzierung sollte eigentlich eine Funktion reichen, oder?
Der Typ von &*iter muss ja nicht gleich dem von iter.operator->() sein, oder?
Nexus schrieb:
Generalisierungen wie Traits implementiere ich normalerweise erst später (warum nicht
std::iterator_traits
?). Optimierungen und Debugging werden so einfacher. Auch verschiedene Iteratorkategorien und Const-Iteratoren wären ein Thema...Auf die Kategorien und const Iteratoren hatte ich gerade keine lust :p
Nexus schrieb:
Bei
operator==
würde ich im Release-Modus wohlstatic_cast
stattdynamic_cast
nehmen. Verschiedenewrapper
-Instantiierungen deuten auf inkompatible Iteratoren hin, da sollte UB zugunsten der Geschwindigkeit vertretbar sein.Das ist eine Designfrage, ueber die ich sicherlich schon ein paar Stunden philosophiert habe. Momentan ist meine favorisierte Loesung hier, statisch Typ-IDs zu vergeben, um dem dynamic_cast auszuweichen und im Falle einer ungleichen ID eine Exception zu schmeissen. Ist ja schliesslich ein Fehler im User-Code, den zu verschleiern war eine dumme Idee.
Nexus schrieb:
Die Range hat weitere Methoden, sodass man sie nicht nur über Iteratoren ansprechen kann.
Welche waeren das denn?
Ich habe nicht wirklich viel Ahnung von Ranges, hast du mir nen Link?
-
@hustbaer: ich hatte deinen Post nicht gesehen... Ich denke, eine Iteratoren-Variante ist von daher gut, dass man sie mit bestehenden Algorithmen und Range-Based For verwenden kann. Hat eine reine Range mehr Optimierungspotential, oder was meinst du dazu?
Das Beispiel bezog sich auf meinen 2. Post im Thread.
@Kellerautomat: kennst du gerade ein Beispiel, wo -> und &* verschieden sind?
Eine Range kann z.B. Methoden anbieten, um sich selbst zu verkleinern oder eine Referenz auf das vorderste Element zurückzugeben. Auch eine Methode, die angibt, ob eine Range leer ist, ist nicht unüblich. So kann man direkt durch die Range iterieren, ohne Iteratoren. Du könntest mal Boost.Range oder die STLSoft RangeLib anschauen. Vielleicht kennt jemand weitere Bibliotheken...
-
Nexus schrieb:
@hustbaer: ich hatte deinen Post nicht gesehen... Ich denke, eine Iteratoren-Variante ist von daher gut, dass man sie mit bestehenden Algorithmen und Range-Based For verwenden kann. Hat eine reine Range mehr Optimierungspotential, oder was meinst du dazu?
Ich denke vermutlich ja, eine reine Range sollte in dem Fall schneller sein.
Kommt natürlich auch auf die Verwendung drauf an. Wenn die Range an genau so viel Stellen rumkopiert wird wie sonst die Iteratoren dann wird der Unterschied wohl nicht so gross sein.