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 machen 🙂

    struct 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.


  • |  Mod



  • @Columbo sagte in kann man (Template)Structs mit statischen Informationen schachteln und das dann zur Kompilezeit (per Recursion) wie eine Liste nutzen?:

    @Finnegan https://github.com/Arcoth/Constainer/wiki

    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 und has_name natürlich sehr spezifisch an deine vorgegebenen structs 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 ein name-Member vorhanden, wird das struct 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 besser value 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

    @Leon0402

    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 und right-Member anstatt des n ausreichen. Für einen fixen Verzweigungsgrad oder einen mit zumindest fester Obergrenze reichen vorgegebene Member-Namen wie z.B. child0 bis childN.

    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?:

    @Finnegan https://github.com/Arcoth/Constainer/wiki

    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 einer std::map verwenden lassen, aber constexpr-Werte zürückgeben. Diese sollten sich ebenfalls in static_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


Anmelden zum Antworten