Default-Typen und -Werte bei Funktions-Templates



  • Hallo,

    ich bin gerade an Funktions-Templates dran und habe ein Problem, bei dem ich nicht weiterkomme.

    Ich habe mir ein paar Templates für das Finden des Medians einer unsortierten Reihe geschrieben. Die Funktionen erwarten zwei Iteratoren und eine Vergleichs-Funktion:

    //Median.h
    #pragma once
    template <class Iterator, class Compare>
    Iterator spalte_auf(Iterator begin, Iterator end, Compare comp) {
        Iterator tind = begin + (end - begin) / 2;
        std::swap(*tind, *begin);
        for (tind = begin++; begin != end; ++begin) {
            if (comp(*begin, *tind)) {
                std::swap(*begin, *(tind + 1));
                std::swap(*tind, *(tind + 1));
                tind++;
            }
        }
        return tind;
    }
    
    template <class Iterator, class Compare>
    Iterator finde_ktes(Iterator begin, Iterator end, int k, Compare comp){
        Iterator nbegin = begin;
        while (true){
            Iterator tind = spalte_auf(begin, end, comp);
            if (tind - nbegin < k - 1) {
                begin = tind + 1;
            }
            else if (tind - nbegin > k - 1) {
                end = tind;
            }
            else
                return tind;
        }
    }
    
    template <class Iterator, class Compare>
    Iterator getMedian(Iterator begin, Iterator end, Compare comp) {
        return finde_ktes(begin, end, (end - begin) / 2, comp);
    }
    
    //main.cpp
    #include <iostream>
    #include <vector>
    #include "Median.h"
    using namespace std;
    
    int main(){
    
        vector<unsigned> data;
        data.push_back(7);	data.push_back(1);	data.push_back(4);
        data.push_back(8);	data.push_back(2);	data.push_back(9);
        data.push_back(5);	data.push_back(6);	data.push_back(3);
    
        cout << *getMedian(data.begin(), data.end(), less<unsigned>()) << endl;
    
        return EXIT_SUCCESS;
    }
    

    Jetzt wollte ich das ganze so erweitern, dass die Templates standarmäßig std::less verwenden und ich eine Funktion nur übergeben muss, wenn es eine andere sein soll. Ich konnte das bisher aber leider nur so lösen, dass ich jedes Template zweimal implementiere:

    template<class Iterator>
    Iterator spalte_auf(Iterator begin, Iterator end) {
        return spalte_auf(begin, end, std::less<decltype(*begin)>());
    }
    
    template <class Iterator>
    Iterator finde_ktes(Iterator begin, Iterator end, int k){
        return finde_ktes(begin, end, k, std::less<decltype(*begin)>());
    }
    
    template <class Iterator>
    Iterator getMedian(Iterator begin, Iterator end) {
        return getMedian(begin, end, std::less<decltype(*begin)>());
    }
    

    Gibt es dafür noch eine andere/bessere Möglichkeit? Ich hatte an "Standartwerte", wie bei Funktionen gedacht:

    //Median.h
    template<class Iterator, class Compare = decltype(std::less)>
    Iterator getMedian(Iterator begin, Iterator end, Compare comp = std::less<decltype(*begin)>()) {
        return finde_ktes(begin, end, (end - begin) / 2, comp);
    }
    

    Aber dann bekomme ich folgende Fehlermeldung:

    1> ...\main.cpp(55): error C2783: "Iterator getMedian(Iterator,Iterator,Compare)": template-Argument für "Compare" konnte nicht hergeleitet werden.
    1> ...\median.h(57): Siehe Deklaration von 'getMedian'

    Ich vermute, dass es daran liegt, dass ich in der Zeile

    template<class Iterator, class Compare = decltype(std::less)>
    

    noch den Typ von *begin brauche, aber wie komme ich da ran, ohne ihn extra mit zu übergen?

    Kann mir jemand sagen ob, und wenn ja wie, das richtig geht?

    Viele Grüße
    Matze



  • Dir ist schon klar, dass std::nth_element dir den Median in O(n) gibt anstelle in O(n^2) wie bei deiner Implementierung?



  • Btw

    template<class Iterator, class Compare = decltype(std::less<std::decay<decltype(*std::declval<Iterator>())>::type>
    Iterator getMedian(Iterator begin, Iterator end, Compare comp = std::less<decltype(*begin)>()) {
        return finde_ktes(begin, end, (end - begin) / 2, comp);
    }
    

    könnte gehen.

    Viel einfacher ist aber eine Überladung

    template<class Iterator>
    Iterator getMedian(Iterator begin, Iterator end) {
        return finde_ktes(begin, end, (end - begin) / 2, std::less<decltype(*begin)>);
    }
    
    template<class Iterator, class Compare>
    Iterator getMedian(Iterator begin, Iterator end, Compare comp) {
        return finde_ktes(begin, end, (end - begin) / 2, comp);
    }
    


  • nth_user schrieb:

    Dir ist schon klar, dass std::nth_element dir den Median in O(n) gibt anstelle in O(n^2) wie bei deiner Implementierung?

    1. Vergleichst du gerade den mittleren Aufwand von nth_element mit dem maximalen Aufwand meines Algoritmus, was wohl etwas unfair ist.

    2. Darum geht es hier doch gar nicht...



  • nth_user schrieb:

    Viel einfacher ist aber eine Überladung

    Hatte ich auch schon überlegt, dann habe ich aber viel doppelten Code.

    Das andere muss ich erst mal nachvollziehen.

    Danke!



  • MatzeHHC schrieb:

    Hatte ich auch schon überlegt, dann habe ich aber viel doppelten Code.

    Hast du nicht, wenn die eine Funktion die andere aufruft. Codeduplizierung ist anders.

    Ich würde auch Überladung nehmen. Ist einfacher, lesbarer, wartbarer und löst keinen Augenkrebs aus.


  • Mod

    decltype(std::less<std::decay<decltype(*std::declval<Iterator>())>::type
    

    ➡

    std::less<typename std::iterator_traits<Iterator>::value_type>
    

  • Mod

    @Nexus: Wenn man das fertigstellt, sieht es so aus:

    template< typename RandomIter,
              typename Compare = std::less<typename std::iterator_traits<RandomIter>::value_type> >
    RandomIter getMedian( RandomIter begin, RandomIter end, Compare comp = {} )
    {
    	auto mid_iter = begin + (end - begin)/2;
    	std::nth_element(begin, mid_iter, end, comp);
    	return mid_iter;
    }
    

    Findest du das tatsächlich hässlich?



  • Arcoth schrieb:

    std::less<typename std::iterator_traits<Iterator>::value_type>
    

    Danke, so geht es! (zumindest, wenn ich das gleiche Konstrukt dann im Funktionskopf verwende:

    template<class Iterator, class Compare = std::less<typename std::iterator_traits<Iterator>::value_type>>
    Iterator getMedian(Iterator begin, Iterator end, Compare comp = std::less<typename std::iterator_traits<Iterator>::value_type>()) {
        return finde_ktes(begin, end, (end - begin) / 2, comp);
    }
    

    Das ist wahrscheinlich auch besser so, da

    decltype(*begin)
    

    unsigned& statt unsigned liefert...

    Nexus schrieb:

    MatzeHHC schrieb:

    Hatte ich auch schon überlegt, dann habe ich aber viel doppelten Code.

    Hast du nicht, wenn die eine Funktion die andere aufruft. Codeduplizierung ist anders.

    Ich würde auch Überladung nehmen. Ist einfacher, lesbarer, wartbarer und löst keinen Augenkrebs aus.

    Stimmt, ich war gerade verwirrt, weil nth_user wirklich die Funktionen 2 mal geschrieben hat.

    Was ich jetzt besser finde weiß ich aber noch nicht 😃

    Danke für eure Hilfe!

    Gruß
    Matze


  • Mod

    zumindest, wenn ich das gleiche Konstrukt dann im Funktionskopf verwende:

    Warum nicht einfach {}? Lass mich raten: VC++?



  • Arcoth schrieb:

    Warum nicht einfach {}? Lass mich raten: VC++?

    Die Schreibweise kenne ich nicht 😮
    Was bedeutet das?

    Funktioniert aber (Visual Studio 2013).



  • Arcoth schrieb:

    Findest du das tatsächlich hässlich?

    Man braucht doch eine gewisse Zeit, um anhand der Signatur herauszufinden, wie die Funktion aufgerufen werden kann. Aber das geht noch im Vergleich zu nth_users Version.

    Muss bei deinem Code Compare nicht default-konstruierbar sein? Das könnte eine unnötige Einschränkung darstellen...


  • Mod

    Was bedeutet das?

    Das nennt sich list-initialization. In diesem Fall führt es dazu, dass der Default-Konstruktor aufgerufen wird (falls vorhanden und implizit aufrufbar).

    Muss bei deinem Code Compare nicht default-konstruierbar sein?

    Nein 😉

    §14.7.1/3 schrieb:

    Unless a call is to a function template explicit specialization [...], a default argument for a function template [..] is implicitly instantiated when the function is called in a context that requires the value of the default argument.

    struct A
    {
    	A(int){}
    	A() = delete;
    };
    
    template<typename T >
    void F( T = {} ){}
    
    int main()
    {
    	F( A{4} );
    }
    

Log in to reply