Der C ++ 20-Standard wird bald erscheinen, der wahrscheinlich das Konzept der
Bereiche hinzufügen wird, aber nur wenige Menschen wissen, was sie sind und womit sie essen. Ich konnte es keinem breiten Publikum russischsprachiger Quellen über dieses Biest zugänglich machen, daher möchte ich in diesem Artikel mehr über ihn sprechen, basierend auf einem Vortrag von Arno Schödl
"Von Iteratoren zu Bereichen: Die bevorstehende Entwicklung der STL" von Meeting C ++ 2015- des Jahres. Ich werde versuchen, diesen Artikel für diejenigen, die zuerst auf dieses Konzept stoßen, so verständlich wie möglich zu machen, und gleichzeitig werde ich über alle Arten von Chips wie Intervalladapter für diejenigen sprechen, die bereits mit diesem Konzept vertraut sind und mehr erfahren möchten.
Bibliotheken mit Bereichen
Zum Zeitpunkt dieses Schreibens gibt es drei Hauptbibliotheken, die Intervalle implementieren:
Die erste Bibliothek ist in der Tat der Vorläufer dieses Konzepts (was nicht überraschend ist, da die Sammlung der
Boost- Bibliotheken nichts enthält :)). Die zweite ist die Bibliothek von Eric Niebler, die später beschrieben wird. Und schließlich wurde die letzte Bibliothek, wie Sie sich vorstellen können, von think-cell geschrieben, die Boost.Range entwickelt und verbessert hat.
Warum sind Intervalle unsere Zukunft?
Für diejenigen, die mit dem Konzept eines Intervalls nicht vertraut sind, definieren wir dieses nicht triviale Konzept als das, das einen Anfang und ein Ende hat (ein
Paar Iteratoren ).
Betrachten wir nun die folgende Aufgabe: Es gibt einen Vektor, aus dem alle sich wiederholenden Elemente entfernt werden müssen. Nach dem aktuellen Standard würden wir es so lösen:
std::vector<T> vec=...; std::sort( vec.begin(), vec.end() ); vec.erase( std::unique( vec.begin(), vec.end() ), vec.end() );
In diesem Fall geben wir den Namen des Vektors bis zu
6 Mal an! Mit dem Konzept der Intervalle (Kombination von Iteratoren am Anfang und Ende des Vektors zu einem Objekt) können wir jedoch um ein Vielfaches einfacher schreiben, indem wir den gewünschten Vektor nur
einmal angeben :
tc::unique_inplace( tc::sort(vec) );
Welche der Intervalle liegen derzeit im aktuellen Standard?
Im C ++ 11-Standard wurde ein bereichsbasierter for-Schleifen- und universeller Zugriff auf den Anfang / das Ende von Containern hinzugefügt, und im letzten C ++ 17-Standard wurde nichts Neues in Bezug auf Intervalle hinzugefügt.
for ( int& i : <range_expression> ) { ... }
std::begin/end(<range_expression>)
Zukünftige Intervalle
Lassen Sie uns nun auf die zuvor erwähnte Range V3-Bibliothek eingehen. Eric Nibler, sein Schöpfer, erstellte als sein
Heimprojekt die technische Spezifikation des Bereichs und modifizierte die
Algorithmusbibliothek , um Intervalle zu unterstützen. Es sieht ungefähr so aus:
namespace ranges { template< typename Rng, typename What > decltype(auto) find( Rng && rng, What const& what ) { return std::find( ranges::begin(rng), ranges::end(rng), what ); } }
Auf seiner Website gibt es eine Vorschau auf das, was er standardisieren möchte, dies ist
Range V3 .
Was kann Bereich berücksichtigt werden?
Zunächst
Container (Vektor, String, Liste usw.), weil sie einen Anfang und ein Ende haben. Es ist klar, dass Container ihre eigenen Elemente haben, dh wenn wir uns auf Container beziehen, beziehen wir uns auf alle ihre Elemente. Ebenso beim Kopieren und Deklarieren einer Konstanten (tiefes Kopieren und Konsistenz). Zweitens können
Ansichten auch als Intervalle betrachtet werden. Ansichten sind nur zwei Iteratoren, die auf den Anfang bzw. das Ende zeigen. Hier ist ihre einfachste Implementierung:
template<typename It> struct iterator_range { It m_itBegin; It m_itEnd; It begin() const { return m_itBegin; } It end() const { return m_itEnd; } };
Ansichten beziehen sich wiederum nur auf Elemente, sodass das Kopieren und die Konsistenz verzögert sind (dies wirkt sich nicht auf die Elemente aus).
Intervalladapter
Die Erfinder der Intervalle hörten hier nicht auf, denn sonst wäre dieses Konzept eher nutzlos. Daher führten sie ein solches Konzept als Bereichsadapter ein.
Adapter transformieren
Betrachten Sie die folgende Aufgabe: Es sei ein
int- Vektor angegeben, in dem das erste Element gleich 4 gefunden werden muss:
std::vector<int> v; auto it = ranges::find(v, 4);
Stellen wir uns nun vor, dass der Typ des Vektors nicht int ist, sondern eine komplexe selbstgeschriebene Struktur, in der sich jedoch ein int befindet und die Aufgabe immer noch dieselbe ist:
struct A { int id; double data; }; std::vector<A> v={...}; auto it = ranges::find_if( v, [](A const& a) { return a.id == 4; } );
Es ist klar, dass diese beiden Codes in der Semantik ähnlich sind, sie unterscheiden sich jedoch erheblich in der Syntax, da wir im letzteren Fall manuell eine Funktion schreiben mussten, die durch das
int- Feld läuft. Wenn Sie jedoch einen Transformationsadapter (
Transformationsadapter ) verwenden, sieht alles viel prägnanter aus:
struct A { int id; double data; }; std::vector<A> v={...}; auto it = ranges::find( tc::transform(v, std::mem_fn(&A::id)), 4);
Tatsächlich „transformiert“ der transformierende Adapter unsere Struktur, indem er eine Wrapper-Klasse um das int-Feld erstellt. Es ist klar, dass der Zeiger auf das
ID- Feld zeigt, aber wenn wir
möchten , dass er auf die gesamte Struktur zeigt, müssen wir am Ende von
.base () hinzufügen. Dieser Befehl kapselt das Feld, wodurch der Zeiger die gesamte Struktur durchlaufen kann:
auto it = ranges::find( tc::transform(v, std::mem_fn(&A::id)), 4).base();
Hier ist eine Beispielimplementierung eines Transformationsadapters (er besteht aus Iteratoren, von denen jeder seinen eigenen Funktor hat):
template<typename Base, typename Func> struct transform_range { struct iterator { private: Func m_func;
Filteradapter
Und wenn wir in der letzten Aufgabe nicht das erste derartige Element finden mussten, sondern das
gesamte Feld von
int auf das Vorhandensein solcher Elemente "filtern" mussten? In diesem Fall würden wir einen Filteradapter verwenden:
tc::filter( v, [](A const& a) { return 4 == a.id; } );
Beachten Sie, dass der Filter während der Iterationen träge ausgeführt wird.
Und hier ist seine naive Implementierung (so etwas ist in Boost.Range implementiert):
template<typename Base, typename Func> struct filter_range { struct iterator { private: Func m_func;
Wie wir sehen können, sind hier zwei Iteratoren erforderlich, anstatt wie im Transformationsadapter. Der zweite Iterator ist erforderlich, um bei Iterationen nicht versehentlich die Grenzen des Containers zu überschreiten.
Einige Optimierungen
Ok, aber wie sieht der Iterator von
tc :: filter (tc :: filter (tc :: filter (...))) aus ?
Boost.range
Im Rahmen der obigen Implementierung sieht es folgendermaßen aus:
Die schwachen Herzen sehen nicht zu!m_func3
m_it3
m_func2
m_it2
m_func1
m_it1;
m_itEnd1;
m_itEnd2
m_func1
m_it1;
m_itEnd1;
m_itEnd3
m_func2
m_it2
m_func1
m_it1;
m_itEnd1;
m_itEnd2
m_func1
m_it1;
m_itEnd1;
Offensichtlich ist dies
schrecklich ineffizient.
Bereich v3
Lassen Sie uns überlegen, wie Sie diesen Adapter optimieren können. Eric Niblers Idee war es, allgemeine Informationen (einen Funktor und einen Zeiger auf das Ende) in das Adapterobjekt einzufügen, und dann können wir einen Link zu diesem Adapterobjekt und dem gewünschten Iterator speichern
*m_rng
m_it
Dann sieht unter einer solchen Implementierung ein Dreifachfilter ungefähr so aus:
Tykm_rng3
m_it3
m_rng2
m_it2
m_rng1
m_it1
Dies ist immer noch nicht perfekt, obwohl es manchmal schneller ist als die vorherige Implementierung.
Denkzelle, Indexkonzept
Betrachten Sie nun die Think-Cell-Lösung. Sie führten das sogenannte
Indexkonzept ein , um dieses Problem zu lösen. Ein Index ist ein solcher Iterator, der dieselben Operationen wie ein regulärer Iterator ausführt, dies jedoch unter Bezugnahme auf Intervalle.
template<typename Base, typename Func> struct index_range { ... using Index = ...; Index begin_index() const; Index end_index() const; void increment_index( Index& idx ) const; void decrement_index( Index& idx ) const; reference dereference( Index& idx ) const; ... };
Wir zeigen, wie ein Index mit einem regulären Iterator kombiniert wird.
Es ist klar, dass ein regulärer Iterator auch als Index betrachtet werden kann. In der entgegengesetzten Richtung kann die Kompatibilität beispielsweise wie folgt implementiert werden:
template<typename IndexRng> struct iterator_for_index { IndexRng* m_rng; typename IndexRng::Index m_idx; iterator& operator++() { m_rng.increment_index(m_idx); return *this; } ... };
Dann wird der Dreifachfilter sehr effizient implementiert:
template<typename Base, typename Func> struct filter_range { Func m_func; Base& m_base; using Index = typename Base::Index; void increment_index( Index& idx ) const { do { m_base.increment_index(idx); } while ( idx != m_base.end_index() && !m_func(m_base.dereference_index(idx)) ); } };
template<typename IndexRng> struct iterator_for_index { IndexRng* m_rng; typename IndexRng::Index m_idx; ... };
Im Rahmen einer solchen Implementierung arbeitet der Algorithmus unabhängig von der Filtertiefe schnell.
Intervalle mit lvalue- und rvalue-Containern
Nun wollen wir sehen, wie Intervalle mit lvalue- und rvalue-Containern funktionieren:
lWert
Bereich V3 und Think-Cell verhalten sich mit lvalue gleich. Angenommen, wir haben folgenden Code:
auto rng = view::filter(vec, pred1); bool b = ranges::any_of(rng, pred2);
Hier haben wir einen zuvor deklarierten Vektor, der im Speicher liegt (lWert), und wir müssen ein Intervall erstellen und dann irgendwie damit arbeiten. Wir erstellen eine Ansicht mit
view :: filter oder
tc :: filter und freuen uns, dass es keine Fehler gibt, und wir können diese Ansicht dann beispielsweise in any_of verwenden.
Bereich V3 und rWert
Wenn sich unser Vektor jedoch noch nicht im Speicher befindet (zum Beispiel, wenn wir ihn nur erstellt haben) und wir uns der gleichen Aufgabe gestellt hätten, würden wir versuchen zu schreiben und einen Fehler feststellen:
auto rng = view::filter(create_vector(), pred1);
Warum ist es entstanden? Die Ansicht ist ein hängender Link zu rvalue, da wir einen Vektor erstellen und ihn direkt in einen Filter einfügen. Das heißt, der Filter enthält einen rvalue-Link, der auf etwas Unbekanntes verweist, wenn der Compiler zur nächsten Zeile wechselt und ein Fehler auftritt. Um dieses Problem zu lösen, hat Range V3 folgende
Maßnahmen ergriffen:
auto rng = action::filter(create_vector(), pred1);
Die Aktion erledigt alles auf einmal, dh sie nimmt einfach einen Vektor, filtert nach Prädikaten und legt ihn in ein Intervall. Das Minus ist jedoch, dass es nicht mehr faul ist, und think-cell hat versucht, dieses Minus zu beheben.
Denkzelle und Wert
Think-Cell hat es so gemacht, dass anstelle der Ansicht ein Container erstellt wird:
auto rng = tc::filter(creates_vector(), pred1); bool b = ranges::any_of(rng, pred2);
Infolgedessen tritt kein ähnlicher Fehler auf, da der Filter in seiner Implementierung den rvalue-Container anstelle des Links sammelt, sodass dies träge geschieht. Range V3 wollte dies nicht tun, weil sie befürchteten, dass es Fehler geben würde, weil sich der Filter entweder als Ansicht oder als Container verhält. Think-cell ist jedoch davon überzeugt, dass Programmierer verstehen, wie sich der Filter verhält, und Die meisten Fehler entstehen gerade wegen dieser "Faulheit".
Generatorintervalle
Wir verallgemeinern das Konzept der Intervalle. Tatsächlich gibt es Intervalle ohne Iteratoren. Sie werden
Generatorbereiche genannt . Angenommen, wir haben ein GUI-Widget (ein Schnittstellenelement) und rufen ein Verschiebungs-Widget auf. Wir haben ein Fenster, in dem Sie aufgefordert werden, das Widget zu verschieben, wir haben auch eine Schaltfläche im
Listenfeld , und ein anderes Fenster sollte auch durch die Widgets scrollen,
dh wir rufen
traverse_widgets auf , das die Elemente mit einem Funktor verbindet (
Sie können sagen, dass es eine Aufzählungsfunktion gibt, in der Sie sich befinden Schließen Sie den Funktor an, und die Funktion listet alle Elemente auf, die in diesem Funktor enthalten sind .
template<typename Func> void traverse_widgets( Func func ) { if (window1) { window1->traverse_widgets(std::ref(func)); } func(button1); func(listbox1); if (window2) { window2->traverse_widgets(std::ref(func)); } }
Dies erinnert etwas an den Widget-Abstand, aber hier gibt es keine Iteratoren. Sie direkt zu schreiben wäre ineffizient und vor allem sehr schwierig. In diesem Fall können wir sagen, dass solche Strukturen auch als Intervalle betrachtet werden. In solchen Fällen werden dann nützliche Intervallmethoden verwendet, z. B.
any_of :
mouse_hit_any_widget=tc::any_of( [] (auto func) { traverse_widgets(func); }, [] (auto const& widget) { return widget.mouse_hit(); } );
think-cell versucht, Methoden so zu implementieren, dass sie für alle Arten von Intervallen dieselbe Schnittstelle haben:
namespace tc { template< typename Rng > bool any_of( Rng const& rng ) { bool bResult = false; tc::enumerate( rng, [&](bool_context b) { bResult = bResult || b; } ); return bResult; } }
Bei Verwendung von
tc :: enumerate wird der Unterschied zwischen den Intervallen ausgeblendet, da eine solche Implementierung dem Konzept der
internen Iteration entspricht (was die Konzepte der
externen und
internen Iteration in der Vorlesung ausführlicher beschrieben werden). Diese Implementierung hat jedoch ihre Nachteile, nämlich
std :: any_of stoppt, sobald
true gefunden wird. Sie versuchen, dieses Problem zu lösen, indem sie beispielsweise Ausnahmen hinzufügen (die sogenannten
unterbrochenen Generatorintervalle ).
Fazit
Ich hasse die bereichsbasierte for-Schleife, weil sie die Leute dazu motiviert, sie zu schreiben, wo immer sie gebraucht wird und wo sie nicht gebraucht wird. Aufgrund dessen verschlechtert sich die Prägnanz des Codes häufig, zum Beispiel schreiben die Leute Folgendes:
bool b = false; for (int n : rng) { if ( is_prime(n) ) { b = true; break; } }
stattdessen:
bool b = tc::any_of( rng, is_prime );