Ich arbeite an einem C ++ - Projekt, das häufige Interaktion mit einer Baumstruktur erfordert, was viele rekursive Funktionen bedeutet, und ich suche nach Möglichkeiten, den Code zu verbessern. Ich bin neulich auf corecursion gestoßen, und ich bin daran interessiert, diese Strategie für meine Anwendung zu erkunden.
Ich konnte jedoch keine Beispiele finden, wie man eine Kernkursion mit C ++ durchführen könnte. Um meine Frage spezifisch zu machen, wie kann ich diese Baumüberquerung mit Hilfe von Corcursion in C ++ machen?
%Vor% Wenn das nur eine schlechte Idee ist, lass es mich wissen. Das heißt, im Internet eine einige Antwort zu haben, wäre für diejenigen, die dies in Zukunft tun wollen, nützlich. Es gibt keine Fragen zu SO passend zu [c++] corecursion und der Rest des Internets scheint keine nützlichen Informationen zu diesem Thema zu haben.
Das Folgende ist fast identisch mit der angegebenen Python-Implementierung und Sie können es jetzt in der Produktion verwenden:
Live auf Coliru %Vor%
Um Zuweisungen / Freigaben zu vermeiden, würde ich es wahrscheinlich so machen:
%Vor%Also gibt es ein paar Ansätze.
Sie können auf das erwartete Keyword warten, wie vorgeschlagen, aber das scheint langfristig zu sein. Wenn Sie auf warten warten, hier ist jemand, der Ertrag mit abwartet , was zumindest auf den ersten Blick sollte in C ++ funktionieren.
Sie können einen generierenden Iterator-Helper schreiben oder einen aus dem Boost borgen und daraus einen Generator machen.
Sie können ein veränderbares Lambda verwenden, das in std::function gespeichert ist, und möglicherweise ein std::experimental::optional (oder optional Boost) zurückgeben.
Aber die meisten machen es einfach schön. Also lass uns hässlich werden. Ich werde dies in C ++ 14 schreiben, weil faul.
%Vor%Der Baumtyp benötigt freie Funktionen, um Wert zu erhalten, links und rechts und einen Operator! um zu sagen, ob es null ist. Und es muss kopierbar sein (ein Zeiger würde es tun).
Verwenden:
%Vor%Das ist jetzt hässlich - wir pflegen den Status beispielsweise manuell.
Ein magischerer Weg kommt über mich, glaube ich, aber das ist nicht standardisiert.
Ein Generator-Iterator würde die hässliche Schnittstelle hinter einer Iterator-Fascade ausblenden, aber der Status wird immer noch manuell verwaltet.
Sie können vielleicht mit lambdas etwas Besonderes machen, aber ich bin mir nicht sicher, ob ein Lambda seinen eigenen Typ zurückgeben kann. Könnte sein. (G: {} - & gt; {G, Vielleicht X} oder so)
Nun, weil es großartig ist, hier ist die n4134 vorgeschlagene await / yield Lösung.
was im Grunde eine Zeile-zu-Zeile-Übersetzung des Python-Codes ist. Ich habe eine vec_of Hilfsfunktion geschrieben, um [] in Python zu ersetzen.
Verwenden:
%Vor%das ist hübsch.
Interessante Frage. Das Problem ist mehr über die Art von yield , obwohl Co-Iteratoren.
Wenn Sie in C ++ yield benötigen, müssen Sie eine iteratorähnliche Zustandsmaschine implementieren, die eigentlich der Idee der Co-Rekursion entspricht.
Ein funktionierendes Beispiel würde die Implementierung einer Baumklasse erfordern, aber hier ist eine Teilimplementierung von BFS, die im Grunde genommen die Strategie im Wiki-Artikel verwendet (etwas behoben, weil ihr Algorithmus etwas albern ist)
%Vor% Technisch müssen Sie ihre yield Generator-Strategie nicht nachahmen, um dies zu tun. Anstatt die Klasse zu definieren, können Sie die Warteschlange einfach direkt in Ihrem Code verwenden.
Das unterscheidet sich etwas vom Wikipedia-Algorithmus, weil ... nun, der Wiki-Algorithmus ist nicht ideal. Sie sind meistens identisch, aber das Wikipedia-Beispiel ist eine Art Warteschlange für arme Leute.
Tags und Links c++ corecursion