HILFE: Template kann nicht vom Template erben, wieso?



  • Hallo zusammen :),

    ich übe gerade Algorithmen und habe mir vorgenommen jeden einzelnen davon in C++ zu programmieren. Damit ich auch gleichzeitig für OOA übe, mache ich das alles mit Klassen und Templates und damit es etwas schwerer wird ist das ganze auch noch verschachtelt und mit Funktionen als Parameter usw. .

    Jetzt bin ich an einer Stelle, wo ein Template von einem Template erbt und irgendwie geht das nicht. Mir ist nicht klar wieso, vielleicht habe ich an der Stelle in der Vorlesung gepennt oder hab einfach nur was übersehen. Habe aber schon 100 Mal drüber geguckt und finde den Fehler nicht.

    Grundaufbau:

    class SortAlgorithmHelper;
    
    template<typename T>
    class SortAlgorithm : public SortAlgorithmHelper
    
    template<typename T>
    class SelectionSort : public SortAlgorithm<T>
    

    Klasse(HPP) SortAlgorithmHelper:

    #ifndef SORTALGORITHMHELPER_HPP
    #define	SORTALGORITHMHELPER_HPP
    
    #ifdef LINUX
    #include <sys/time.h>
    #else
    #include <windows.h>
    #endif
    
    typedef unsigned int uint;
    
    class SortAlgorithmHelper
    {
    private:
    #ifdef LINUX
        double start;
        struct timeval tm;
    #else
        LONGLONG g_Frequency, g_FirstCount, g_LastCount;
    #endif
    
        uint cswap, ccomp;
    
        double duration, temp_duration;
    
    protected:
        void startTimer();
        void pauseTimer();
        void resumeTimer();
        void stopTimer();
    
        void incrCompCounter();
        void incrSwapCounter();
    
    public:
        SortAlgorithmHelper();
    
        double getDuration();
    
        uint getComparesAmmount();
        uint getSwapsAmmount();
    };
    
    #endif	/* SORTALGORITHM_HPP */
    

    Template(HPP) SortAlgorithm:

    #ifndef SORTALGORITHM_HPP
    #define	SORTALGORITHM_HPP
    
    #include "SortAlgorithmHelper.hpp"
    
    template<typename T>
    class SortAlgorithm : public SortAlgorithmHelper
    {
    protected:
        uint n;
        T *a;
    
    public:
        SortAlgorithm(uint n, T (rand_func(const T*, const uint&))) : SortAlgorithmHelper(){
            this->n = n;
            this->a = SortAlgorithm::getRandArray<T>(n, rand_func);
        }
    
        SortAlgorithm(uint n, T *a) : SortAlgorithmHelper(){
            this->n = n;
            this->a = a;
        }
    
        virtual void sort(bool (llr(const T&, const T&)));
    
        ~SortAlgorithm(){
            delete[] this->a;
        }
    
    public: // ---- STATIC ----
        template<typename T>
        static void printArray(const T *a, uint n, void (print(const T&, uint&)));
    
        template<typename T>
        static T* getRandArray(uint n, T (rand_func(const T*, const uint&)));
    
        template<typename T>
        static void swap(T* l, T* r);
    };
    
    template<typename T>
    void SortAlgorithm::printArray(const T* a, uint n, void (print(const T&, uint&))){
        for(uint i = 0; i < n; i++){
            print(a[i], i);
        }
    }
    
    template<typename T>
    T* SortAlgorithm::getRandArray(uint n, T (rand_func(const T*, const uint&))){
        T *arr = new T[n];
        for(uint i = 0; i < n; i++){
            arr[i] = rand_func(arr, i);
        }
    
        return arr;
    }
    
    template<typename T>
    void SortAlgorithm::swap(T* l, T* r){
        T tmp = *l;
        *l = *r;
        *r = tmp;
    }
    
    #endif	/* SORTALGORITHM_HPP */
    

    Template(HPP) SelectionSort:

    #ifndef SELECTIONSORT_HPP
    #define	SELECTIONSORT_HPP
    
    #include "SortAlgorithm.hpp"
    
    template<typename T>
    class SelectionSort : public SortAlgorithm<T>
    {
    public:
        SelectionSort(uint n, T (rand_func(const T*, const uint&))) : SortAlgorithm(n, rand_func){
    
        }
    
        SelectionSort(uint n, T *a) : SortAlgorithm(n, a){
    
        }
    
        void sort(bool (llr(const T&, const T&))){ //llr is Left lower Right (x < y => true)
    
            this->startTimer();
    
            for(uint i = 0; i < this->n - 1; i++){
                uint k = i;
                for(uint c = i + 1; c < this->n; c++){
    
                    this->pauseTimer();
                    this->incrCompCounter();
                    this->resumeTimer();
    
                    if(llr(this->a[c], this->a[k])) k = c;
                }
    
                if(k != i){
                    this->pauseTimer();
                    this->incrSwapCounter();
                    this->resumeTimer();
    
                    SortAlgorithm::swap<T>(&this->a[i], &this->a[k]);
                }
            }
    
            this->stopTimer();
        }
    };
    #endif	/* SELECTIONSORT_HPP */
    

    In der SelectionSort Datei ist vieles unterstrichen von der IDE (NetBeans 😎 und der Compiler gibt folgendes aus:

    g++ -c -g -std=c++11 -MMD -MP -MF "build/Debug/Cygwin_4.x-Windows/main.o.d" -o build/Debug/Cygwin_4.x-Windows/main.o main.cpp
    In file included from SelectionSort.hpp:4:0,
    from main.cpp:9:
    SortAlgorithm.hpp:31:14: error: declaration of ‘class T’
    template<typename T>
    ^
    SortAlgorithm.hpp:6:10: error: shadows template parm ‘class T’
    template<typename T>
    ^
    SortAlgorithm.hpp:34:14: error: declaration of ‘class T’
    template<typename T>
    ^
    SortAlgorithm.hpp:6:10: error: shadows template parm ‘class T’
    template<typename T>
    ^
    SortAlgorithm.hpp:37:14: error: declaration of ‘class T’
    template<typename T>
    ^
    SortAlgorithm.hpp:6:10: error: shadows template parm ‘class T’
    template<typename T>
    ^
    SortAlgorithm.hpp:43:6: error: ‘template<class T> class SortAlgorithm’ used without template parameters
    void SortAlgorithm::printArray(const T* a, uint n, void (print(const T&, uint&))){
    ^
    SortAlgorithm.hpp:50:4: error: ‘template<class T> class SortAlgorithm’ used without template parameters
    T* SortAlgorithm::getRandArray(uint n, T (rand_func(const T*, const uint&))){
    ^
    SortAlgorithm.hpp:60:6: error: ‘template<class T> class SortAlgorithm’ used without template parameters
    void SortAlgorithm::swap(T* l, T* r){
    ^
    SelectionSort.hpp: In member function ‘void SelectionSort<T>::sort(bool ()(const T&, const T&))’:
    SelectionSort.hpp:30:17: error: ‘template<class T> class SortAlgorithm’ used without template parameters
    SortAlgorithm::swap<T>(&this->a[i], &this->a[k]);
    ^
    SelectionSort.hpp:30:38: error: expected primary-expression before ‘>’ token
    SortAlgorithm::swap<T>(&this->a[i], &this->a[k]);
    ^
    main.cpp: In function ‘int main(int, const char**)’:
    main.cpp:29:39: error: ‘template<class T> class SortAlgorithm’ used without template parameters
    SelectionSort<int> selSort(n, SortAlgorithm::getRandArray<int>(n, rand_func));
    ^
    main.cpp:29:67: error: expected primary-expression before ‘int’
    SelectionSort<int> selSort(n, SortAlgorithm::getRandArray<int>(n, rand_func));
    ^
    SelectionSort.hpp: In instantiation of ‘void SelectionSort<T>::sort(bool (
    )(const T&, const T&)) [with T = int]’:
    main.cpp:30:31: required from here
    SortAlgorithm.hpp:10:10: error: ‘uint SortAlgorithm<int>::n’ is private
    uint n;
    ^
    In file included from main.cpp:9:0:
    SelectionSort.hpp:14:37: error: within this context
    for(uint i = 0; i < this->n - 1; i++){
    ^
    In file included from SelectionSort.hpp:4:0,
    from main.cpp:9:
    SortAlgorithm.hpp:10:10: error: ‘uint SortAlgorithm<int>::n’ is private
    uint n;
    ^
    In file included from main.cpp:9:0:
    SelectionSort.hpp:16:35: error: within this context
    for(uint c = i + 1; c < this->n; c++){
    ^
    In file included from SelectionSort.hpp:4:0,
    from main.cpp:9:
    SortAlgorithm.hpp:11:8: error: ‘int* SortAlgorithm<int>::a’ is private
    T a;
    ^
    In file included from main.cpp:9:0:
    SelectionSort.hpp:22:31: error: within this context
    if(llr(this->a[c], this->a[k])) k = c;
    ^
    In file included from SelectionSort.hpp:4:0,
    from main.cpp:9:
    SortAlgorithm.hpp:11:8: error: ‘int
    SortAlgorithm<int>::a’ is private
    T a;
    ^
    In file included from main.cpp:9:0:
    SelectionSort.hpp:22:43: error: within this context
    if(llr(this->a[c], this->a[k])) k = c;
    ^
    In file included from SelectionSort.hpp:4:0,
    from main.cpp:9:
    SortAlgorithm.hpp:11:8: error: ‘int
    SortAlgorithm<int>::a’ is private
    T a;
    ^
    In file included from main.cpp:9:0:
    SelectionSort.hpp:30:48: error: within this context
    SortAlgorithm::swap<T>(&this->a[i], &this->a[k]);
    ^
    In file included from SelectionSort.hpp:4:0,
    from main.cpp:9:
    SortAlgorithm.hpp:11:8: error: ‘int
    SortAlgorithm<int>::a’ is private
    T *a;
    ^
    In file included from main.cpp:9:0:
    SelectionSort.hpp:30:61: error: within this context
    SortAlgorithm::swap<T>(&this->a[i], &this->a[k]);



  • Statt das zwanghaft alles als Klasse zu realisieren, solltest du es lieber vernünftig als Funktion machen.

    Du hast kein Problem mit Templates. Das funktioniert alles. Du hast lediglich an ein paar Stellen private, wo du protected brauchst.



  • Dein Ansatz ist falsch. Du möchtest irgendwas mit Templates, Vererbung und Sortieren machen und presst deshalb deine Sortieralgorithmen in irgend eine Klassenhierarchie, die nicht sinnvoll ist. Wenn man einen Hammer hat sieht halt schnell alles wie ein Nagel aus.

    Wie Marthog bereits gesagt hat ist es sinnvoller freie Funktionen zu verwenden, unter Verwerwendung des Iterator-Patterns. Du kannst Bubble-Sort zum Beispiel wie folgt implementieren:

    template <typename Iter>
    void bubble_sort(Iter begin, Iter end)
    {
        for ( auto i = begin; i != end; ++i )
    for ( auto j = i + 1; j != end; ++j )
    	    if ( *i > *j )
    		std::iter_swap(i,j);
    }
    


  • Dein Ansatz ist falsch. Du möchtest irgendwas mit Templates, Vererbung und Sortieren machen und presst deshalb deine Sortieralgorithmen in irgend eine Klassenhierarchie, die nicht sinnvoll ist. Wenn man einen Hammer hat sieht halt schnell alles wie ein Nagel aus.

    Wie Marthog bereits gesagt hat ist es sinnvoller freie Funktionen zu verwenden, unter Verwerwendung des Iterator-Patterns. Du kannst Bubble-Sort zum Beispiel wie folgt implementieren:

    template <typename Iter>
    void bubble_sort(Iter begin, Iter end)
    {
        for ( auto i = begin; i != end; ++i )
            for ( auto j = i + 1; j != end; ++j)
                if ( !(*i < *j) )
                    std::iter_swap(i,j);
    }
    

    Damit kannst du jeden Container, der entsprechende Iteratoren anbietet, sortieren.

    Mit

    template <typename Iter, typename Compare>
    void bubble_sort(Iter begin, Iter end, Compare cmp)
    {
        for ( auto i = begin; i != end; ++i )
            for ( auto j = i + 1; j != end; ++j )
                if ( !cmp(*i,*j) )
                    std::iter_swap(i,j);
    }
    

    kannst du zusätzlich noch eine Vergleichsfunktion angeben.

    Als Beispielcode:

    std::vector<int> vec {4, 3, 9, 1};
    
        std::cout << "Ascending:\n";
        bubble_sort(vec.begin(), vec.end());
        for ( auto i : vec )
            std::cout << i << '\n';
    
        std::cout << "Descending:\n";
        bubble_sort(vec.begin(), vec.end(),std::greater<int>());
        for ( auto i : vec )
            std::cout << i << '\n';
    


  • icarus2 schrieb:

    template <typename Iter, typename Compare>
    void bubble_sort(Iter begin, Iter end, Compare cmp)
    {
        for ( auto i = begin; i != end; ++i )
            for ( auto j = i + 1; j != end; ++j )
                if ( !cmp(*i,*j) )
                    std::iter_swap(i,j);
    }
    

    Du willst dich doch nicht auf Random Acces-Iteratoren beschränken, wenn das auch für Forward-Iteratoren geht.

    template <typename Iter, typename Compare>
    void bubble_sort(Iter first, Iter last, Compare cmp = std::less<void>()) {
        for (auto i=first; i!=last; ++i)
            for (auto j=std::next(i); j!=end; ++j)
                if (!cmp(*i, *j))
                    std::iter_swap(i, j);
    }
    


  • prevers schrieb:

    Du willst dich doch nicht auf Random Acces-Iteratoren beschränken, wenn das auch für Forward-Iteratoren geht.

    👍
    Habe ich in der Eile nicht darauf geachtet.


Log in to reply