Octobre 2017
Volume 32, numéro 10
Cet article a fait l'objet d'une traduction automatique.
C++ - Des algorithmes aux coroutines en C++
Par Kenny Kerr
Il existe un algorithme de la bibliothèque Standard C++ appelé iota qui a cela toujours vous intrigue me. Il a un nom d’obtenir des informations et une fonction intéressante. L’iota word est le nom d’une lettre de l’alphabet grec. Elle est généralement utilisée en anglais très peu et souvent la valeur négative, pas le moins, dérivé d’un guillemet dans le livre de Matthew de témoigne de nouveau. Cette idée d’une très petite quantité participe à la fonction de l’algorithme iota. Il est destiné à remplir une plage avec des valeurs qui augmentent par une petite quantité, comme la valeur initiale est stockée et puis incrémentée jusqu'à ce que la plage a été remplie. À quelque chose comme ceci :
#include <numeric>
int main()
{
int range[10];
// Range: Random missile launch codes
std::iota(std::begin(range), std::end(range), 0);
// Range: { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 }
}
On dit souvent que les développeurs C++ doivent expunge naked toutes les boucles for et les remplacer par des algorithmes. Certes, l’algorithme iota qualifie comme il se substitue à la boucle que tout développeur C ou C++ a écrit sans aucun doute des milliers de fois. Vous pouvez imaginer à quoi peut ressembler votre implémentation de la bibliothèque Standard C++ :
namespace std
{
template <typename Iterator, typename Type>
void iota(Iterator first, Iterator last, Type value)
{
for (; first != last; ++first, ++value)
{
*first = value;
}
}
}
Par conséquent, Oui, vous ne souhaitez être interceptée dans une révision du code avec le code, comme cela. Sauf si vous êtes un développeur de la bibliothèque, bien sûr. Cela est idéal que l’algorithme iota m’évite d’avoir à écrire que boucle for, mais vous savez quelles informations ? J’ai en réalité jamais l’utilisé en production. L’article passe généralement quelque chose comme ceci : J’ai besoin d’une plage de valeurs. Il s’agit d’une telle fondamentale chose en informatique, il doit y avoir un algorithme standard pour qu’il. J’ai à nouveau parcourt la liste sur à bit.ly/2i5WZRc et trouver iota. Hmm, il a besoin d’une plage à remplir avec des valeurs. OK, quelle est la moins chère plage que trouver... J’ai ensuite imprimer les valeurs de s’assurer que j’ai reçu de droite à l’aide de... une boucle for :
#include <numeric>
#include <stdio.h>
int main()
{
int range[10];
std::iota(std::begin(range), std::end(range), 0);
for (int i : range)
{
printf("%d\n", i);
}
}
Pour être objective, la seule chose que j’aime dans ce code repose sur la plage de boucle. Le problème est que je ne simplement besoin ni choix de cette plage. Je ne souhaite pas obligé de créer un conteneur pour contenir les valeurs afin que je peux les parcourir. Que se passe-t-il si j’ai besoin de beaucoup plus de valeurs ? J’avais quantité écriture plutôt simplement le pour boucle moi-même :
#include <stdio.h>
int main()
{
for (int i = 0; i != 10; ++i)
{
printf("%d\n", i);
}
}
Pour d’insulte, cela implique la taper beaucoup moins de texte. Il que serait très pratique, cependant, s’il y a une fonction iota une certaine manière de générer une plage de valeurs pour une plage de boucle for basée à consommer sans avoir à utiliser un conteneur. J’ai récemment en parcourant un livre sur le langage Python et remarqué qu’il possède une fonction intégrée appelée plage. Je peux écrire le même programme dans Python comme suit :
for i in range(0, 10):
print(i)
Soyez prudent avec cette mise en retrait. Il est comment le langage Python représente les instructions composées. J’ai lu que Python a été nommée d’après un certain comédie British plutôt que la valeur snake nonvenomous. Je pense qu’a est l’auteur. C’est encore, la nature concise de ce code. Sûrement, puis-je obtenir quelque chose dans ces lignes en C++. En effet, c’est ce que je souhaite l’algorithme iota fournirait mais, hélas. Essentiellement, ce que je recherche est un algorithme de plage qui ressemble à ceci :
template <typename T>
generator<T> range(T first, T last)
{
return{ ... };
}
int main()
{
for (int i : range(0, 10))
{
printf("%d\n", i);
}
}
À ma connaissance, aucune fonction de ce genre n’existe, par conséquent, passons et générez-le. La première étape consiste à rapprocher de l’algorithme avec quelque chose de fiable qui peut agir comme une ligne de base pour le test. Le conteneur de vecteur standard C++ s’avère pratique dans de tels cas :
#include <vector>
template <typename T>
std::vector<T> range(T first, T last)
{
std::vector<T> values;
while (first != last)
{
values.push_back(first++);
}
return values;
}
Il est également très efficace d’illustrant la raison pour laquelle vous souhaitez créer un conteneur en premier lieu, ou même déterminer de quelle taille elle doit être, quel. Pourquoi doit il même y avoir une limite ? Cependant, cela est utile, car vous pouvez comparer facilement la sortie de ce générateur de plage à une autre plus efficace. Ainsi, il s’avère que l’écriture d’un générateur plus efficace n’est pas autrement difficile. Examinez Figure 1.
Générateur de la figure 1
template <typename T>
struct generator
{
T first;
T last;
struct iterator{ ... };
iterator begin()
{
return{ first };
}
iterator end()
{
return{ last };
}
};
template <typename T>
generator<T> range(T first, T last)
{
return{ first, last };
}
La fonction de plage crée simplement un générateur initialisé avec la même paire de valeurs de délimitation. Le générateur peut ensuite utiliser ces valeurs pour produire des itérateurs légers via les begin classique et les fonctions de membre de fin. La partie la plus fastidieuse est niveau se traduit par l’implémentation itérateur en grande partie réutilisable. L’itérateur peut simplement contenir une valeur donnée et incrémenter en fonction des besoins. Elle doit également fournir un ensemble d’alias de type pour décrire aux algorithmes standard. Cela n’est pas strictement nécessaire pour la simple plage boucle for basée, mais il est judicieux d’inclure un bit de vérification future de :
template <typename T>
struct generator
{
struct iterator
{
T value;
using iterator_category = std::input_iterator_tag;
using value_type = T;
using difference_type = ptrdiff_t;
using pointer = T const*;
using reference = T const&;
Incrémenter l’itérateur peut incrémenter simplement la valeur sous-jacente. Le formulaire postérieures à l’incrémentation peut être supprimé en toute sécurité :
iterator& operator++()
{
++value;
return *this;
}
iterator operator++(int) = delete;
L’autre fonction tout aussi importante fournie par un itérateur est celui de la comparaison. Une plage de boucle for basée il utilisera pour déterminer si elle a atteint la fin de la plage :
bool operator==(iterator const& other) const
{
return value == other.value;
}
bool operator!=(iterator const& other) const
{
return !(*this == other);
}
Enfin, une plage de boucle for basée pouvez déréférencer l’itérateur pour retourner la valeur actuelle de la plage. Pourrais supprimer l’opérateur d’appel de membre, car il n’est pas nécessaire pour la plage de boucle for basée, mais qui limiterait inutilement l’utilité des générateurs à être utilisée par d’autres algorithmes :
T const& operator*() const
{
return value;
}
T const* operator->() const
{
return std::addressof(value);
}
Il peut être que le générateur et la fonction de la plage de texte associée sont utilisées avec les objets sous forme de nombre plutôt que de simples primitives. Dans ce cas, vous pouvez également utiliser l’adresse du programme d’assistance, le numéro d’objet doit être lire des astuces avec l’opérateur & surcharge. Et voilà. Ma plage maintenant fonctionne comme prévu :
template <typename T>
generator<T> range(T first, T last)
{
return{ first, last };
}
int main()
{
for (int i : range(0, 10))
{
printf("%d\n", i);
}
}
Bien entendu, il n’est pas particulièrement flexible. J’ai généré l’iota de mes rêves, mais il est toujours un iota de ce que serait possible si je commuté vitesses et adopté les coroutines. Vous voyez, avec les coroutines que vous pouvez écrire tous les types de générateurs de beaucoup plus succinctement et sans avoir à écrire un nouveau modèle de classe de générateur de chaque genre de la plage que vous souhaitez produire. Imaginez que si vous seulement eu à écrire un générateur de plus, puis un large éventail de fonctions de plage pour produire plusieurs séquences à la demande. C’est ce que permettent les coroutines. Au lieu d’incorporer la base de connaissances de la génération iota d’origine dans le générateur, vous pouvez incorporer ces connaissances directement à l’intérieur de la fonction de plage et un modèle de classe de générateur unique qui fournit le lien entre le producteur et consommateur. Allons-y.
Je commence en incluant l’en-tête de la coroutine, qui fournit la définition du modèle de classe coroutine_handle :
#include <experimental/coroutine>
Je vais utiliser la coroutine_handle pour permettre au Générateur d’interagir avec l’ordinateur d’état représenté par une coroutine. Cette opération de requête et reprendre que nécessaire pour permettre à une plage de boucle for basée, ou une boucle quel : pour indiquer la progression de la coroutine produisant une extraction - plutôt que modèle d’émission de la consommation. Le générateur est quelque peu similaire à celle du générateur classique dans Figure 1. La principale différence est que plutôt que de mise à jour des valeurs directement, il déplace simplement la coroutine vers l’avant. Figure 2 fournit le plan.
Figure 2 Coroutine Générateur
template <typename T>
struct generator
{
struct promise_type{ ... };
using handle_type = std::experimental::coroutine_handle<promise_type>;
handle_type handle{ nullptr };
struct iterator{ ... };
iterator begin()
{
...
handle.resume();
...
}
iterator end()
{
return nullptr;
}
};
Il est donc aller un peu plus ici. Non seulement existe-t-il un itérateur qui permet à la plage de boucle for basée à interagir avec le Générateur de l’extérieur, mais il existe également un promise_type qui permet la coroutine interagir avec le Générateur de l’intérieur. Première, un peu de ménage : Rappelez-vous que la fonction de génération de valeurs ne sont pas être retournant un générateur directement, mais plutôt permettre au développeur d’utiliser les instructions co_yield les valeurs à partir de la coroutine, via le générateur, vers l’avant et vers le site d’appel. Prenez en compte la plus simple de générateurs de :
generator<int> one_two_three()
{
co_yield 1;
co_yield 2;
co_yield 3;
}
Notez comment le développeur crée jamais explicitement le type de retour coroutine. C’est le rôle du compilateur C++ comme il sont assemblées représenté par ce code de l’ordinateur d’état. Essentiellement, le compilateur C++ recherche le promise_type et l’utilise pour construire un frame coroutine logique. Ne vous inquiétez pas, le frame coroutine probablement disparaît une fois que le compilateur C++ est terminé optimisant le code dans certains cas. Néanmoins, le promise_type sert ensuite à initialiser le générateur soit renvoyé à l’appelant. Étant donné la promise_type, puis-je obtenir le handle représentant la coroutine afin que le générateur peut le lecteur à partir de l’extérieur dans :
generator(promise_type& promise) :
handle(handle_type::from_promise(promise))
{
}
Bien entendu, le coroutine_handle est une construction de très bas niveau et je ne souhaite pas à un développeur maintient un générateur accidentellement endommager l’ordinateur d’état à l’intérieur d’une coroutine active. La solution consiste simplement à implémenter une sémantique de déplacement et interdire les copies. Quelque chose comme ceci (tout d’abord, je vais lui donner un constructeur par défaut et expressément supprimer les membres de la copie spéciale) :
generator() = default;
generator(generator const&) = delete;
generator &operator=(generator const&) = delete;
Et puis je vais implémenter une sémantique de déplacement simplement en transfert la valeur du handle de la coroutine afin que les deux générateurs pointent jamais sur le même coroutine en cours d’exécution, comme indiqué dans Figure 3.
Figure 3 implémentation d’une sémantique de déplacement
generator(generator&& other) : handle(other.handle)
{
other.handle = nullptr;
}
generator &operator=(generator&& other)
{
if (this != &other)
{
handle = other.handle;
other.handle = nullptr;
}
return *this;
}
À présent, compte tenu du fait que la coroutine vise à partir de l’extérieur, il est important de se rappeler que le générateur a également la responsabilité de la destruction de la coroutine :
~generator()
{
if (handle)
{
handle.destroy();
}
}
Cela a réellement davantage le résultat de final_suspend sur le promise_type, mais qui sera enregistré pour un autre jour. Qui est suffisamment comptabilité pour l’instant. Examinons maintenant le promise_type du générateur. Le promise_type est un emplacement pratique pour se tout état tel qu’il soit inclus dans n’importe quel d’allocation effectuée pour le frame coroutine par le compilateur C++. Le générateur est ensuite un objet léger qui peut facilement déplacer et faire référence à cet état en fonction des besoins. Seuls deux éléments d’information dont j’ai besoin pour transmettre à partir de la coroutine de restauration à l’appelant. La première est la valeur à céder et le second est une exception qui a été levée :
#include <variant>
template <typename T>
struct generator
{
struct promise_type
{
std::variant<T const*, std::exception_ptr> value;
Bien que facultative, wfc pour encapsuler les objets exception_ptr std::optional, car l’implémentation d’exception_ptr dans Visual C++ est un peu coûteuse. Même un exception_ptr vide appelle lors de la construction et la destruction de la bibliothèque CRT. Encapsulant parfaitement à l’intérieur de facultatif permet d’éviter cette surcharge. Un modèle d’état plus précis est à utiliser une variante, comme j’illustré uniquement, pour contenir la valeur actuelle ou l’exception_ptr car ils s’excluent mutuellement. La valeur actuelle est simplement un pointeur vers la valeur est obtenue à l’intérieur de la coroutine. Il s’agit plus sûr, car la coroutine sera suspendu pendant que la valeur est lue et tout objet temporaire peut être soumise est en toute sécurité conservé pendant que la valeur est observée en dehors de la coroutine.
Une coroutine est initialement retourne à son appelant, il sollicite la promise_type pour produire la valeur de retour. Étant donné que le générateur peut être construit en donnant une référence à la promise_type, puis-je retrouver simplement cette référence ici :
promise_type& get_return_object()
{
return *this;
}
Une coroutine produisant un générateur n’est pas votre coroutine-activation d’accès concurrentiel par défaut et il est souvent simplement le générateur qui détermine la durée de vie et l’exécution de la coroutine. Par conséquent, j’indiquent au compilateur C++ que la coroutine doit être suspendu initialement afin que le générateur peut contrôler parcourant la coroutine, pour ainsi dire :
std::experimental::suspend_always initial_suspend()
{
return {};
}
De même, vous indiquer que la coroutine sera suspendu au moment du retour, au lieu d’ayant la coroutine détruire lui-même automatiquement :
std::experimental::suspend_always final_suspend()
{
return {};
}
Cela garantit que je peux toujours interroger l’état de la coroutine, via le promise_type allouée dans le cadre de la coroutine, une fois la coroutine terminée. Il est essentiel de M’autoriser à lire les exception_ptr en cas d’échec, voire simplement de savoir que la coroutine est effectuée. Si la coroutine lui-même détruit automatiquement lorsqu’elle est terminée, ne pourraient même être en mesure d’interroger le coroutine_handle, sans parler la promise_type, après un appel à reprendre la coroutine à son point de suspension finale. Capture la valeur à céder est assez simple :
std::experimental::suspend_always yield_value(T const& other)
{
value = std::addressof(other);
return {};
}
J’utilise simplement l’adresse pratique du programme d’assistance à nouveau. Un promise_type doit également fournir une fonction de return_void ou return_value. Même s’il n’est pas utilisé dans cet exemple, il donne une indication sur le fait que co_yield est simplement une abstraction sur co_await :
void return_void()
{
}
Mais nous y reviendrons. Ensuite, vous ajouterez un peu défense contre toute utilisation malveillante simplement pour faciliter l’utilisation pour le développeur de comprendre ce qui s’est produite. Vous voyez, un générateur de donner les valeurs implique que, sauf si la coroutine est terminée, une valeur disponible pour la lecture. Si une coroutine inclure une expression co_await, puis il peut en théorie suspend sans une valeur qui est présent et il n’y aura aucun moyen de transmettre ce fait à l’appelant. Pour cette raison, empêcher un développeur d’écrire une instruction co_await, comme suit :
template <typename Expression>
Expression&& await_transform(Expression&& expression)
{
static_assert(sizeof(expression) == 0,
"co_await is not supported in coroutines of type generator");
return std::forward<Expression>(expression);
}
Pour résumer les promise_type, j’ai besoin uniquement prendre en charge de l’interception, pour ainsi dire, toute exception qui a été levée. Le compilateur C++ garantit que membre d’unhandled_exception de la promise_type est appelée :
void unhandled_exception()
{
value = std::current_exception();
}
Vous pouvez ensuite, tout comme une commodité pour l’implémentation, fournissez une fonction pratique pour éventuellement lever de nouveau l’exception dans le contexte approprié :
void rethrow_if_failed()
{
if (value.index() == 1)
{
std::rethrow_exception(std::get<1>(value));
}
}
Suffisamment sur le promise_type. J’ai maintenant un générateur qu’il fonctionne, mais je vais simplement ajouter un itérateur simple afin que je peux facilement le lecteur à partir d’une plage de boucle. Comme avant, l’itérateur aura les alias de type réutilisable pour se décrire aux algorithmes standard. Toutefois, l’itérateur simplement conserve le coroutine_handle :
struct iterator
{
using iterator_category = std::input_iterator_tag;
using value_type = T;
using difference_type = ptrdiff_t;
using pointer = T const*;
using reference = T const&;
handle_type handle;
Incrémentation de l’itérateur est un peu plus complexe que l’itérateur iota plus simple, comme c’est le principal point auquel le générateur interagit avec la coroutine. Incrémenter l’itérateur implique que l’itérateur est valide et qu’il peut en fait être incrémenté. Étant donné que l’itérateur « fin » conserve un handle de nullptr, puis-je simplement fournir une comparaison d’itérateur, comme suit :
bool operator==(iterator const& other) const
{
return handle == other.handle;
}
bool operator!=(iterator const& other) const
{
return !(*this == other);
}
En supposant qu’il s’agit d’un itérateur valide, j’ai tout d’abord relancer la coroutine, ce qui permet de s’exécuter et générer sa valeur suivante. Je dois vérifier si l’exécution de cette remise la coroutine à une fin et dans ce cas, propager toute exception qui a été déclenchée à l’intérieur de la coroutine :
iterator &operator++()
{
handle.resume();
if (handle.done())
{
promise_type& promise = handle.promise();
handle = nullptr;
promise.rethrow_if_failed();
}
return *this;
}
iterator operator++(int) = delete;
Sinon, l’itérateur est considéré comme ont atteint sa fin et son handle est désactivée simplement de sorte qu’il compare avec succès par rapport à l’itérateur de fin. Gérer les besoins de précaution à prendre pour effacer la coroutine avant de lever toute exception non interceptée pour empêcher toute personne accidentellement la reprise de la coroutine au dernier point d’interruption, car cela entraînerait un comportement non défini. Le générateur membre de begin fonction effectue beaucoup de la même logique, pour vous assurer que je peux constamment propager toute exception qui est levée avant d’atteindre le premier point de suspension :
iterator begin()
{
if (!handle)
{
return nullptr;
}
handle.resume();
if (handle.done())
{
handle.promise().rethrow_if_failed();
return nullptr;
}
return handle;
}
La principale différence est que begin est un membre du générateur, qui détient le handle de la coroutine, et par conséquent doit effacer la coroutine gérez pas. Enfin et tout simplement, je peux implémenter itérateur déréférencement simplement en retournant une référence à la valeur actuelle stockée dans le promise_type :
T const& operator*() const
{
return *std::get<0>(handle.promise().value);
}
T const* operator->() const
{
return std::addressof(operator*());
}
Et j’ai terminé. Je peux écrire maintenant de manière tous les algorithmes, produisant des diverses séquences générées à l’aide de ce générateur généralisé. Figure 4 montre à quoi ressemble le Générateur de plage fantastique.
La figure 4, le Générateur de plage inspiration
template <typename T>
generator<int> range(T first, T last)
{
while (first != last)
{
co_yield first++;
}
}
int main()
{
for (int i : range(0, 10))
{
printf("%d\n", i);
}
}
Qui a besoin d’une plage limitée, quand même ? Comme vous avez maintenant un modèle d’extraction, je peux demander simplement à l’appelant décider quand ils avez suffisante, comme vous pouvez le voir dans Figure 5.
Générateur d’illimité figure 5
template <typename T>
generator<int> range(T first)
{
while (true)
{
co_yield first++;
}
}
int main()
{
for (int i : range(0))
{
printf("%d\n", i);
if (...)
{
break;
}
}
}
Les possibilités sont illimitées ! Il existe, bien sûr, plus aux générateurs et les coroutines et avons uniquement ne présente que succinctement ici. Me joindre prochaine pour plus d’informations sur les coroutines en C++. Vous pouvez trouver l’exemple complet de cet article sur dans l’Explorateur du compilateur : godbolt.org/g/NXHBZR.
Kenny Kerr est un auteur, programmeur de systèmes et le créateur de C + c++ / WinRT. Il est également une ingénierie à rebours de l’équipe Windows chez Microsoft où il conçoit l’avenir de C++ pour Windows, permettant aux développeurs d’écrire des applications hautes performances et attrayantes et des composants et incroyable simplicité.
Merci à l'expert technique suivant d'avoir relu cet article : Gor Nishanov