La norme C ++ 20 apparaîtra bientôt, dans laquelle, très probablement, le concept de
gammes sera ajouté, mais peu de gens savent ce qu'ils sont et ce avec quoi ils mangent. Je ne pouvais pas trouver accessible à un large public de sources en langue russe sur cette bête, donc dans cet article, je voudrais en parler davantage, basé sur une conférence d'Arno Schödl
"From Iterators to Ranges: The Upcoming Evolution Of the STL" de Meeting C ++ 2015- de l'année. J'essaierai de rendre cet article aussi clair que possible pour ceux qui rencontrent ce concept pour la première fois, et en même temps, je parlerai de toutes sortes de puces comme des adaptateurs d'intervalle pour ceux qui connaissent déjà ce concept et veulent en savoir plus.
Bibliothèques avec plages
Au moment d'écrire ces lignes, il existe trois bibliothèques principales qui implémentent des intervalles:
La première bibliothèque, en fait, est l'ancêtre de ce concept (ce qui n'est pas surprenant, car il n'y a rien dans la collection de bibliothèques
Boost :)). La seconde est la bibliothèque d'Eric Niebler, qui sera décrite plus loin. Et enfin, la dernière bibliothèque, comme vous pouvez le deviner, a été écrite par think-cell, qui, pourrait-on dire, a développé et amélioré Boost.Range.
Pourquoi les intervalles sont notre avenir?
Pour ceux qui ne connaissent pas le concept d'intervalle, nous définissons ce concept non trivial comme celui qui a un début et une fin (une
paire d'itérateurs ).
Considérons maintenant la tâche suivante: il y a un vecteur, il faut en supprimer tous les éléments répétitifs. Selon la norme actuelle, nous le résoudrions comme ceci:
std::vector<T> vec=...; std::sort( vec.begin(), vec.end() ); vec.erase( std::unique( vec.begin(), vec.end() ), vec.end() );
Dans ce cas, nous indiquons le nom du vecteur jusqu'à
6 fois! Cependant, en utilisant le concept d'intervalles (combinant des itérateurs au début et à la fin du vecteur en un seul objet), vous pouvez écrire plusieurs fois plus facilement en spécifiant le vecteur souhaité
une seule
fois :
tc::unique_inplace( tc::sort(vec) );
Lesquels des intervalles sont actuellement dans la norme actuelle?
Dans la norme C ++ 11, une boucle basée sur une plage et un accès universel au début / à la fin des conteneurs ont été ajoutés, et dans la dernière norme C ++ 17, rien de nouveau lié aux intervalles n'a été ajouté.
for ( int& i : <range_expression> ) { ... }
std::begin/end(<range_expression>)
Intervalles futurs
Arrêtons-nous maintenant sur la bibliothèque Range V3 mentionnée précédemment. Eric Nibler, son créateur, comme son projet de maison a créé les
spécifications techniques de la
gamme , modifiant la bibliothèque d'
algorithmes pour prendre en charge les intervalles. Cela ressemble à ceci:
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 ); } }
Sur son site, il y a un aperçu de ce qu'il veut standardiser, c'est la
gamme V3 .
Que peut-on envisager?
Tout d'abord, les
conteneurs (vecteur, chaîne, liste, etc.), car ils ont un début et une fin. Il est clair que les conteneurs ont leurs propres éléments, c'est-à-dire que lorsque nous parlons de conteneurs, nous faisons référence à tous leurs éléments. De même, lors de la copie et de la déclaration d'une constante (copie profonde et cohérence). Deuxièmement, les
vues peuvent également être considérées comme des intervalles. Les vues ne sont qu'une paire d'itérateurs pointant respectivement vers le début et la fin. Voici leur mise en œuvre la plus simple:
template<typename It> struct iterator_range { It m_itBegin; It m_itEnd; It begin() const { return m_itBegin; } It end() const { return m_itEnd; } };
Les vues, à leur tour, ne se réfèrent qu'aux éléments, donc la copie et la cohérence sont paresseuses (cela n'affecte pas les éléments).
Adaptateurs d'intervalle
Les inventeurs d'intervalles ne se sont pas arrêtés là, car sinon ce concept serait plutôt inutile. Par conséquent, ils ont introduit un tel concept d'adaptateurs de gamme.
Transformer l'adaptateur
Considérez la tâche suivante: laissez un vecteur
int donné, dans lequel nous devons trouver le premier élément égal à 4:
std::vector<int> v; auto it = ranges::find(v, 4);
Imaginons maintenant que le type du vecteur ne soit pas int, mais une sorte de structure complexe auto-écrite, mais dans laquelle il y a un int, et la tâche est toujours la même:
struct A { int id; double data; }; std::vector<A> v={...}; auto it = ranges::find_if( v, [](A const& a) { return a.id == 4; } );
Il est clair que ces deux codes sont similaires en sémantique, cependant, ils diffèrent considérablement dans la syntaxe, car dans ce dernier cas, nous avons dû écrire manuellement une fonction qui traverse le champ
int . Mais si vous utilisez un adaptateur de transformation (adaptateur de
transformation ), tout semble beaucoup plus succinct:
struct A { int id; double data; }; std::vector<A> v={...}; auto it = ranges::find( tc::transform(v, std::mem_fn(&A::id)), 4);
En fait, l'adaptateur de transformation «transforme» notre structure en créant une classe wrapper autour du champ int. Il est clair que le pointeur pointe vers le champ
id , mais si nous voulions qu'il pointe vers la structure entière, nous devons l'ajouter à la fin de
.base () . Cette commande encapsule le champ, grâce auquel le pointeur peut parcourir toute la structure:
auto it = ranges::find( tc::transform(v, std::mem_fn(&A::id)), 4).base();
Voici un exemple d'implémentation d'un adaptateur de transformation (il se compose d'itérateurs, chacun ayant son propre foncteur):
template<typename Base, typename Func> struct transform_range { struct iterator { private: Func m_func;
Adaptateur de filtre
Et si, dans la dernière tâche, nous devions trouver non pas le premier élément de ce type, mais «filtrer» le champ
entier de
int pour la présence de tels éléments? Dans ce cas, nous utiliserions un adaptateur de filtre:
tc::filter( v, [](A const& a) { return 4 == a.id; } );
Notez que le filtre est exécuté paresseusement pendant les itérations.
Et voici son implémentation naïve (quelque chose comme ça est implémenté dans Boost.Range):
template<typename Base, typename Func> struct filter_range { struct iterator { private: Func m_func;
Comme nous pouvons le voir, deux itérateurs sont nécessaires ici au lieu d'un, comme c'était le cas dans l'adaptateur de transformation. Le deuxième itérateur est nécessaire afin de ne pas dépasser accidentellement les limites du conteneur lors des itérations.
Quelques optimisations
Ok, mais à quoi ressemble l'itérateur de
tc :: filter (tc :: filter (tc :: filter (...))) ?
Boost.range
Dans le cadre de l'implémentation ci-dessus, cela ressemble à ceci:
Les faibles de cœur ne regardent pas!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;
De toute évidence, c'est
terriblement inefficace.
Gamme v3
Voyons comment optimiser cet adaptateur. L'idée d'Eric Nibler était de mettre des informations générales (un foncteur et un pointeur à la fin) dans l'objet adaptateur, puis nous pouvons stocker un lien vers cet objet adaptateur et l'itérateur souhaité
*m_rng
m_it
Ensuite, dans le cadre d'une telle implémentation, un triple filtre ressemblera à ceci:
Tykm_rng3
m_it3
m_rng2
m_it2
m_rng1
m_it1
Ce n'est toujours pas parfait, bien que parfois plus rapide que la mise en œuvre précédente.
think-cell, concept d'index
Considérons maintenant la solution think-cell. Ils ont introduit le soi-disant
concept d'index pour résoudre ce problème. Un index est un tel itérateur qui effectue toutes les mêmes opérations qu'un itérateur régulier, mais il le fait en se référant aux intervalles.
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; ... };
Nous montrons comment combiner un index avec un itérateur régulier.
Il est clair qu'un itérateur régulier peut également être considéré comme un index. Dans le sens inverse, la compatibilité peut être implémentée, par exemple, comme suit:
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; } ... };
Ensuite, le triple filtre sera mis en œuvre de manière très efficace:
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; ... };
Dans le cadre d'une telle implémentation, l'algorithme fonctionnera rapidement quelle que soit la profondeur du filtre.
Intervalles avec les conteneurs lvalue et rvalue
Voyons maintenant comment les intervalles fonctionnent avec les conteneurs lvalue et rvalue:
lvalue
La plage V3 et think-cell se comportent de la même manière avec lvalue. Supposons que nous ayons un code comme celui-ci:
auto rng = view::filter(vec, pred1); bool b = ranges::any_of(rng, pred2);
Ici, nous avons un vecteur précédemment déclaré qui se trouve dans la mémoire (lvalue), et nous devons créer un intervalle, puis travailler en quelque sorte avec lui. Nous créons une vue en utilisant
view :: filter ou
tc :: filter et devenons heureux, il n'y a pas d'erreur, et nous pouvons ensuite utiliser cette vue, par exemple, dans any_of.
Gamme V3 et rvalue
Cependant, si notre vecteur n'était pas encore en mémoire (par exemple, si nous venions de le créer), et nous aurions fait face à la même tâche, alors nous aurions essayé d'écrire et face à une erreur:
auto rng = view::filter(create_vector(), pred1);
Pourquoi est-elle apparue? La vue sera un lien suspendu vers rvalue car nous créons un vecteur et le mettons directement dans un filtre, c'est-à-dire qu'il y aura un lien rvalue dans le filtre, qui pointera alors vers quelque chose d'inconnu lorsque le compilateur passe à la ligne suivante et qu'une erreur se produit. Afin de résoudre ce problème, la gamme V3 a proposé une
action :
auto rng = action::filter(create_vector(), pred1);
L'action fait tout à la fois, c'est-à-dire qu'elle prend simplement un vecteur, filtre par prédicat et le place dans un intervalle. Cependant, l'inconvénient est qu'il n'est plus paresseux, et think-cell a essayé de corriger ce inconvénient.
think-cell et rvalue
Think-cell a fait en sorte qu'au lieu de visualiser un conteneur soit créé:
auto rng = tc::filter(creates_vector(), pred1); bool b = ranges::any_of(rng, pred2);
Par conséquent, nous ne rencontrons pas une erreur similaire, car dans leur implémentation, le filtre collecte le conteneur rvalue au lieu du lien, cela se produit donc paresseusement. Dans la gamme V3, ils ne voulaient pas faire cela, car ils craignaient qu'il y ait des erreurs en raison du comportement du filtre en tant que vue ou en tant que conteneur, mais think-cell est convaincu que les programmeurs comprennent comment le filtre se comporte, et la plupart des erreurs surviennent précisément à cause de cette "paresse".
Intervalles du générateur
Nous généralisons le concept d'intervalles. En fait, il existe des intervalles sans itérateurs. Ils sont appelés
gammes de générateurs . Supposons que nous ayons un widget GUI (un élément d'interface) et que nous appelions un widget move. Nous avons une fenêtre qui demande de déplacer son widget, nous avons également un bouton dans la zone de
liste , et une autre fenêtre devrait également faire défiler ses widgets, c'est-à-dire que nous appelons
traverse_widgets , qui relie les éléments à un foncteur (
vous pouvez dire qu'il y a une fonction d'énumération où vous connectez le foncteur, et la fonction liste tous les éléments qu'elle a dans ce foncteur ).
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)); } }
Cela rappelle un peu l'espacement des widgets, mais il n'y a pas d'itérateurs ici. Les écrire directement serait inefficace et surtout très difficile. Dans ce cas, nous pouvons dire que de telles structures sont également considérées comme des intervalles. Ensuite, dans de tels cas, il existe une utilisation de méthodes d'intervalle utiles, telles que
any_of :
mouse_hit_any_widget=tc::any_of( [] (auto func) { traverse_widgets(func); }, [] (auto const& widget) { return widget.mouse_hit(); } );
think-cell essaie d'implémenter des méthodes pour qu'elles aient la même interface pour toutes sortes d'intervalles:
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; } }
En utilisant
tc :: enumerate , la différence entre les intervalles est cachée, car une telle implémentation adhère au concept d'
itération interne (ce que les concepts d'
itération externe et
interne sont décrits plus en détail dans la leçon), cependant, cette implémentation a ses inconvénients, à savoir,
std :: any_of s'arrête dès que
true est rencontré. Ils essaient de résoudre ce problème, par exemple, en ajoutant des exceptions (les
intervalles de générateur dits
interrompus ).
Conclusion
Je déteste la boucle for basée sur la plage, car elle motive les gens à l'écrire là où ils sont nécessaires et là où ils ne sont pas nécessaires, car la concision du code empire souvent, par exemple, les gens écrivent ceci:
bool b = false; for (int n : rng) { if ( is_prime(n) ) { b = true; break; } }
à la place:
bool b = tc::any_of( rng, is_prime );