kann man (Template)Structs mit statischen Informationen schachteln und das dann zur Kompilezeit (per Recursion) wie eine Liste nutzen?
-
ist sowas moeglich? C++17
Mit template-Spezialisierung per size_t koennte man auch kompiletime Bäume machenstruct info // _0 { static constexpr auto name = "erster"; static struct _1 { static constexpr auto name = "zweiter"; static struct _2 { static constexpr auto name = "dritter"; static struct _3 { static constexpr auto name = "vierter"; } n; } n; } n; }; int main() { info::n.name; info::n.n.n.name; //--> waeren diese Helper moeglich? //static_assert(get_list_element<info, 0>::name == info::name, ""); //static_assert(get_list_element<info, 3>::name == info::n.n.n.name, ""); //static_assert(get_list_size<info> == 4); // da braucht man bestimmt eine Ende-Kennung oder sowas }
-
Was auf jeden Fall geht ist die Knoten des Baums klassisch in den Typen zu codieren:
#include <iostream> #include <type_traits> template <typename L, typename R> struct Node { using left = L; using right = R; }; template <typename L, typename R> struct Node1 : Node<L, R> { static constexpr auto name = "erster"; static constexpr int value = 1; }; template <typename L, typename R> struct Node2 : Node<L, R> { static constexpr auto name = "zweiter"; static constexpr int value = 2; }; template <typename L, typename R> struct Node3 : Node<L, R> { static constexpr auto name = "dritter"; static constexpr int value = 3; }; template <typename L, typename R> struct Node4 : Node<L, R> { static constexpr auto name = "vierter"; static constexpr int value = 4; }; template <typename L, typename R> struct Node5 : Node<L, R> { static constexpr auto name = "fünfter"; static constexpr int value = 5; }; template <int value> void print_compile_time_constant_int() { std::cout << value << std::endl; } struct NotFoundNode { static constexpr auto name = "Not Found"; static constexpr int value = -1; }; template <typename Node, int search_value> struct Find { using left_result_ = typename Find<typename Node::left, search_value>::type; using right_result_ = typename Find<typename Node::right, search_value>::type; using type = std::conditional_t< (Node::value == search_value), Node, std::conditional_t< std::is_same_v<right_result_, NotFoundNode>, left_result_, right_result_ > >; }; template <int search_value> struct Find<void, search_value> { using type = NotFoundNode; }; template <typename Tree, int search_value> constexpr const char* find_name() { return Find<Tree, search_value>::type::name; } // // Tree: // // Node1 // / \ // Node2 Node3 // / \ // Node4 Node5 // using Tree = Node1<Node2<Node4<void, void>, Node5<void, void>>, Node3<void, void>>; auto main() -> int { std::cout << Tree::left::right::name << std::endl; print_compile_time_constant_int<Tree::left::right::value>(); std::cout << Find<Tree, 5>::type::name << std::endl; print_compile_time_constant_int<Find<Tree, 5>::type::value>(); std::cout << find_name<Tree, 5>() << std::endl; std::cout << Find<Tree, 99>::type::name << std::endl; print_compile_time_constant_int<Find<Tree, 99>::type::value>(); std::cout << find_name<Tree, 99>() << std::endl; return 0; };
Vielleicht schafft man es sogar, den Baum irgendwie in ein
constexpr
-Objekt unterzubringen, das man irgendwie so oder ähnlich initialisieren kann:constexpr Node root{ "erster", 1, Node{ "zweiter", 2, Node{ "vierter", 4 }, Node{ "fünfter", 5 } }, Node{ "dritter", 3 } };
Dazu fehlt mir aber gerade die Kreavtivität. Das dürfte nicht ganz leicht sein, das so hinzubekommen. Vielleicht hat ja der ein- oder andere hier noch ein paar Tricks auf Lager, um sowas umzusetzen
Edit:
Find
hinzugefügt, um einen Knoten rekursiv im Baum zu suchen.
-
-
@Columbo sagte in kann man (Template)Structs mit statischen Informationen schachteln und das dann zur Kompilezeit (per Recursion) wie eine Liste nutzen?:
Cool, ich dachte mir schon dass das irgendwie geht. Werd ich mir mal ansehen, und mir ein paar Tricks abschauen. Mittlerweile komme ich mir nämlich schon was altmodisch vor mit solchen Lösungen wie ich sie da oben vorgeschlagen habe
-
Die Methode "get_list_element" klingt für mich nach compile time reflection. Daher Metainformationen darüber wie das Objekt bzw. der Baum aufgebaut ist. Hat C++ nicht, kann man mit Aufwand nachbauen. Ob das wirklich ein Anwendungsfall ist, wo es das wert ist, ist ne andere Frage.
-
Hatte vorhin deine eigentliche Frage nicht richtig erfasst, daher ging meine Antwort wahrscheinlich an dem vorbei, was du eigentlich wissen willst.
Bezüglich deiner Frage zu den Helpern: Ja, die sind möglich und könnten z.B. so aussehen (C++17):
#include <iostream> #include <cstddef> struct info { static constexpr auto name = "erster"; static constexpr struct _1 { static constexpr auto name = "zweiter"; static constexpr struct _2 { static constexpr auto name = "dritter"; static constexpr struct _3 { static constexpr auto name = "vierter"; } n{}; } n{}; } n{}; }; template <typename T, typename = void> struct has_n : std::false_type { }; template <typename T> struct has_n<T, std::void_t<decltype(std::declval<T>().n)>> : std::true_type { }; template <typename T, typename = void> struct has_name : std::false_type { }; template <typename T> struct has_name<T, std::void_t<decltype(std::declval<T>().name)>> : std::true_type { }; template <typename L, std::size_t I, typename = void> struct get_list_element; template <typename L, std::size_t I> struct get_list_element<L, I, std::enable_if_t<I == 0 && has_name<L>::value>> { static constexpr auto name = L::name; }; template <typename L, std::size_t I> struct get_list_element<L, I, std::enable_if_t<I != 0 && has_n<L>::value>> { static constexpr auto name = get_list_element<decltype(L::n), I - 1>::name; }; template <typename L, typename Enabled = void> struct get_list_size { static constexpr std::size_t value = 0; }; template <typename L> struct get_list_size<L, std::enable_if_t<!has_n<L>::value && has_name<L>::value>> { static constexpr std::size_t value = 1; }; template <typename L> struct get_list_size<L, std::enable_if_t<has_n<L>::value>> { static constexpr std::size_t value = get_list_size<decltype(L::n)>::value + 1; }; template <typename L> inline constexpr std::size_t get_list_size_v = get_list_size<L>::value; auto main() -> int { static_assert(get_list_element<info, 0>::name == info::name, ""); static_assert(get_list_element<info, 3>::name == info::n.n.n.name, ""); static_assert(get_list_size_v<info> == 4); std::cout << get_list_element<info, 0>::name << std::endl; std::cout << get_list_element<info, 1>::name << std::endl; std::cout << get_list_element<info, 2>::name << std::endl; std::cout << get_list_element<info, 3>::name << std::endl; std::cout << get_list_size_v<info> << std::endl; return 0; };
Das ist mit dem
has_n
undhas_name
natürlich sehr spezifisch an deine vorgegebenenstruct
s angepasst und lässt sich sicher auch noch etwas eleganter formulieren. Erstmal nur ein Proof of Concept.Deine "Ende-Kennung" ist hier, dass kein
n
-Member vorhanden ist. Ist einname
-Member vorhanden, wird dasstruct
aber dennoch als Listen-Knoten erkannt (siehe Spezialisierungen in Zeilen 44 und 62). Will man das etwas allgemeiner formulieren, würde man diesen Member vielleicht besservalue
nennen.
-
Das sieht doch schon mal sehr gut aus - danke Finnegan
template <typename L, std::size_t I> struct get_list_element<L, I, std::enable_if_t<I != 0 && has_n<L>::value>> { static constexpr auto name = get_list_element<decltype(L::n), I - 1>::name; };
hier koennte man doch auch nur den Knoten liefern - und ganz auf die name spezialisierung verzichten, oder?
(falls man noch mehr Attribute in einem Knoten haben will)und einen richtigen Baum könnten man erreichen wenn man auf jeder Ebene ein Template macht das man dann mit <size_t> und dem Index spezialisiert, und darin den struct mit den namen steckt, oder am Ende einer Ebenen alles noch in einen Childs tuple
Warum soll das nicht moeglich sein? Mir ist oft unklar wie es genau aussehen muss, aber das meiste geht - auch ohne massive Anstrengungen
Ob das wirklich ein Anwendungsfall ist, wo es das wert ist, ist ne andere Frage.
Ich habe einen Konkreten Anwendungsfall der durch solche Techniken komplett auf Generatoren/Boilerplate-Code verzichten kann, Kompiletime-Bäume würden mein Szenario komplett Kompiletime-Safe machen, mit der absolut gleichen Funktionalität, und da problemlos in der cpp versteckbar auch noch fast vollständig inlinebar - es scheitert weniger an C++, oft eher an den fehlenden Ideen wie man etwas gut und richtig Umsetzt das nicht eine 08/15 Anforderungen ist - und ja mir ist Overengeneering ein Begriff aber ist sehe auch viel Underengeneering das von Leuten als "praktikabel und lesebarer" verkauft wird weil sie es selbst nicht besser können und alle anderen auf Ihr Niveau reduzieren wollen - das geht nicht, das ist nicht sinnvoll hört man all zu oft
-
@llm sagte in kann man (Template)Structs mit statischen Informationen schachteln und das dann zur Kompilezeit (per Recursion) wie eine Liste nutzen?:
hier koennte man doch auch nur den Knoten liefern - und ganz auf die name spezialisierung verzichten, oder?
(falls man noch mehr Attribute in einem Knoten haben will)Wie schon erwähnt ist das an deine Vorgaben angepasst. Das lässt sich auch kürzer und allgemeiner formulieren. Die Namen der Member muss man aber dennoch mit in den TMP-Code einweben, da wir leider noch keine Compile-Time Reflection in C++ haben.
und einen richtigen Baum könnten man erreichen wenn man auf jeder Ebene ein Template macht das man dann mit <size_t> und dem Index spezialisiert, und darin den struct mit den namen steckt, oder am Ende einer Ebenen alles noch in einen Childs tuple
Für einen binären Baum würden schon
left
undright
-Member anstatt desn
ausreichen. Für einen fixen Verzweigungsgrad oder einen mit zumindest fester Obergrenze reichen vorgegebene Member-Namen wie z.B.child0
bischildN
.Du solltest dir aber auch mal die "Constainer" von Arcoth anschauen:
@Columbo sagte in kann man (Template)Structs mit statischen Informationen schachteln und das dann zur Kompilezeit (per Recursion) wie eine Liste nutzen?:
Das habe ich zwar bisher nur überflogen, aber wenn sich diese Container tatsächlich alle als
constexpr
-Objekte instanzieren lassen, sieht mir das nach einer wesentlich eleganteren und flexibleren Lösung aus. Da hast du dann wahrscheinlich Datenstrukturen, die sich z.B. ähnlich einerstd::map
verwenden lassen, aberconstexpr
-Werte zürückgeben. Diese sollten sich ebenfalls instatic_assert
oder sogar in Template-Argumenten verwenden lassen.
-
Noch mal vielen Dank Finnegan, dein Beispiel hilft mir wirklich sehr, die Arcoth container schaue ich mir auch an