std::sort nach verschiedenen Objekteigenschaften mit Standardprädikaten (ohne Extrafunktion!)



  • question123 schrieb:

    @Knivil: Dann erklär mal das Konzept, das ich nicht verstanden habe.

    Wenn du nach unterschiedlichen Dingen sortieren moechtest, dann brauchst du unterschiedliche Vergleichsfuntkionen. Wie sollte es auch anders sein? Aussderm finde ich es recht praktisch, einen Funktor anzugeben.



  • knivil schrieb:

    Wenn du nach unterschiedlichen Dingen sortieren moechtest, dann brauchst du unterschiedliche Vergleichsfuntkionen.

    Jein. Die Vergleichsfunktionen existieren ja schon. Meine Frage war, ob ich z.B. dem greater-Prädikat beibringen kann, welche Objekteigenschaft (die ja alle im besten Fall sogar vom gleichen Typ sind, nämlich z.B. int ) es verwenden soll.



  • Hier wäre noch eine Möglichkeit ohne Boost:

    // Funktor-Templateklasse, die als Vergleichskriterium auf Memberfunktionen zugreift.
    template <typename ReturnType, typename Class>
    struct GreaterFunctor
    {
    	// Funktionstyp - const-Memberfunktion mit 0 Parametern (typische Getter)
    	typedef ReturnType (Class::*FunctionType)(void) const;
    
    	// Gespeicherter Funktionszeiger
    	FunctionType MyFunc;
    
    	// Konstruktor
    	GreaterFunctor(FunctionType NewFunc) 
    	: MyFunc(NewFunc) 
    	{
    	}
    
    	// Überladener Klammeroperator
    	bool operator() (const Class& Left, const Class& Right) const
    	{
    		return (Left.*MyFunc)() > (Right.*MyFunc)();
    	}	
    };
    
    // Hilfsfunktion, um Klasse und Rückgabetyp nicht mehr angeben zu müssen
    template <typename ReturnType, typename Class>
    GreaterFunctor<ReturnType, Class> Greater(ReturnType (Class::*Function)(void) const)
    {
    	return GreaterFunctor<ReturnType, Class>(Function);
    }
    

    Sieht zwar etwas mühsam aus, aber das kann ja ausgelagert werden. Dafür ist der Aufruf schön:

    std::sort(Vec.begin(), Vec.end(), Greater(&MyClass::GetVar));
    


  • Noch etwas mehr Abstraktion, indem man auch noch das Prädikat bestimmen kann:

    // Funktor-Templateklasse, die als Vergleichskriterium auf Memberfunktionen zugreift.
    template <typename ReturnType, typename Class, typename Predicate>
    struct CompareFunctor
    {
    	// Funktionstyp - const-Memberfunktion mit 0 Parametern (typischer Getter)
    	typedef ReturnType (Class::*FunctionType)(void) const;
    
    	// Gespeicherte Funktionszeiger
    	FunctionType MyFunc;
    	Predicate MyPred;
    
    	// Konstruktor
    	CompareFunctor(FunctionType NewFunc, Predicate NewPred = Predicate()) 
    	: MyFunc(NewFunc)
    	, MyPred(NewPred)
    	{
    	}
    
    	// Überladener Klammeroperator
    	bool operator() (const Class& Left, const Class& Right) const
    	{
    		return MyPred((Left.*MyFunc)(),(Right.*MyFunc)());
    	}	
    };
    
    // Hilfsfunktion, um Klasse und Rückgabetyp nicht mehr angeben zu müssen
    template <typename ReturnType, typename Class, typename Predicate>
    CompareFunctor<ReturnType, Class, Predicate> 
    	Compare(ReturnType (Class::*Function)(void) const, Predicate NewPred)
    {
    	return CompareFunctor<ReturnType, Class, Predicate>(Function, NewPred);
    }
    
    // Hilfsfunktion-Überladung für Standardprädikat std::less
    template <typename ReturnType, typename Class>
    CompareFunctor<ReturnType, Class, std::less<ReturnType> > 
    	Compare(ReturnType (Class::*Function)(void) const)
    {
    	return CompareFunctor<ReturnType, Class, std::less<ReturnType> >(Function);
    }
    

    Mögliche Aufrufe:

    std::sort(Vec.begin(), Vec.end(), Compare(&MyClass::GetVar));
    std::sort(Vec.begin(), Vec.end(), Compare(&MyClass::GetVar, std::greater<int>()));
    

    Das sieht zwar ziemlich kompliziert und nach viel Code aus, aber du bist damit sehr flexibel und sparst dir die einzelnen Vergleichsfunktionen. Ich hoffe, du kannst zumindest einen Teil davon brauchen. Wenn du noch Fragen hast, einfach stellen. Hoffentlich bist du nicht zu verwirrt... 😉

    Was mir noch nicht ganz gefällt, ist die Angabe des Typen, zum Beispiel für std::greater das <int> . Wahrscheinlich könnte man da mit Template-Templates etwas machen, aber mein Wissen reicht nicht bis dahin. Wäre gut, wenn das noch jemand ergänzen könnte. 🙂



  • Das kommt vom Aufruf her meiner ursprünglichen Wunschvorstellung ( std::sort(objects.begin(), objects.end(), std::greater<Object:: pt>); ) ja schon ziemlich nahe 🙂



  • @ Nexus bezüglich der gewünschten Template-Template-Parameter:

    template< typename S, typename T, T S::*some, template<typename X> class func = std::greater >
    class compare2
    {
    public:
        static bool compare( S& a, S& b ){ return func<T>()(a.*some, b.*some); }
    };
    


  • question123 schrieb:

    knivil schrieb:

    Wenn du nach unterschiedlichen Dingen sortieren moechtest, dann brauchst du unterschiedliche Vergleichsfuntkionen.

    Jein. Die Vergleichsfunktionen existieren ja schon. Meine Frage war, ob ich z.B. dem greater-Prädikat beibringen kann, welche Objekteigenschaft (die ja alle im besten Fall sogar vom gleichen Typ sind, nämlich z.B. int ) es verwenden soll.

    Sie existiert nicht! Die Objekte, die du sortieren willst sind keine int's oder andere primitive Typen.



  • Decimad schrieb:

    @ Nexus bezüglich der gewünschten Template-Template-Parameter

    Ah, vielen Dank. Grr, ich habs zuvor mit template <typename X> typename statt template <typename X> class versucht... 😉

    Also hier der Übersicht halber nochmals den ganzen Code. Ich hab die Templateparameter-Reihenfolge aus Konsistenzgründen verändert. CompareFunctor sollte man sowieso über die Funktion Compare() erstellen...

    // Funktor-Templateklasse, die als Vergleichskriterium auf Memberfunktionen zugreift.
    template <typename Predicate, typename ReturnType, typename Class>
    struct CompareFunctor
    {
    	// Funktionstyp - const-Memberfunktion mit 0 Parametern (typischer Getter)
    	typedef ReturnType (Class::*FunctionType)(void) const;
    
    	// Gespeicherter Funktionszeiger
    	FunctionType MyFunc;
    	Predicate MyPred;
    
    	// Konstruktor
    	CompareFunctor(FunctionType NewFunc, Predicate NewPred = Predicate()) 
    	: MyFunc(NewFunc)
    	, MyPred(NewPred)
    	{
    	}
    
    	// Überladener Klammeroperator
    	bool operator() (const Class& Left, const Class& Right) const
    	{
    		return MyPred((Left.*MyFunc)(),(Right.*MyFunc)());
    	}	
    };
    
    // Hilfsfunktion, um Klasse und Rückgabetyp nicht mehr angeben zu müssen
    template <template <typename X> class Predicate, typename ReturnType, typename Class>
    CompareFunctor<Predicate<ReturnType>, ReturnType, Class> 
    	Compare(ReturnType (Class::*Function)(void) const, Predicate<ReturnType> NewPred = Predicate<ReturnType>())
    {
    	return CompareFunctor<Predicate<ReturnType>, ReturnType, Class>(Function, NewPred);
    }
    
    // Hilfsfunktion-Überladung für Standardprädikat std::less
    template <typename ReturnType, typename Class>
    CompareFunctor<std::less<ReturnType>, ReturnType, Class> 
    	Compare(ReturnType (Class::*Function)(void) const)
    {
    	return CompareFunctor<std::less<ReturnType>, ReturnType, Class>(Function);
    }
    

    Eingesetzt sieht das dann so aus:

    std::sort(Vec.begin(), Vec.end(), Compare(&MyClass::GetVar));
    std::sort(Vec.begin(), Vec.end(), Compare<std::greater>(&MyClass::GetVar));
    std::sort(Vec.begin(), Vec.end(), Compare<std::greater>(&MyClass::GetVar, std::greater<int>()));
    

    question123, kommt das jetzt noch ein wenig näher? Ist es sogar schon gut genug? 🙂



  • Hey, das sieht doch fast wie die generalisierte Version meiner Lösung von der ersten Seite aus, mit Memberfunktionen anstatt Membervariablen - du klaust doch! 😉

    Snip.

    Viele Grüße,
    Michael

    PS: Ich mach hier nur Spaß 😉



  • Und man sieht wieder, wie aus einer simplen Sache unglaublich viel Code entsteht. Ich finde die vorgeschlagenen Loesungen schlecht.



  • So ist das halt in C++ 😉



  • knivil schrieb:

    Und man sieht wieder, wie aus einer simplen Sache unglaublich viel Code entsteht. Ich finde die vorgeschlagenen Loesungen schlecht.

    Sie entsprechen aber der Anforderung des Threaderstellers und das ist relevant. Wenn du die Funktionalität generisch implementieren willst, kommst du nicht um viel Code herum. Aber wie gesagt kann man das in einen eigenen Header auslagern und von dort aus wiederverwenden. Die Verwendung ist dafür sehr sauber und kann sich schnell mal auszahlen.

    Was für ein Problem hast du mit viel Code? Oder ist es eher eine fundamentale Abneigung als ein begründeter Einwand? Und du hast doch sicher einen besseren Vorschlag, oder?

    Nebenbei: Was denkst du, wie viel Code braucht Boost.Lambda?



  • question123 schrieb:

    Jein. Die Vergleichsfunktionen existieren ja schon.

    Nein tun sie nicht. Was glaubst du was greater<Object> macht? oder dein vorgeschlagenes greater<Object::element> ? Da wird ein Klassentemplate instantiiert, damit erzeugt der Compiler den Code für einen Funktor, der den operator> aufruft. Bei allen anderen vorgeschlagenen Lösungen wird so ein Funktor auf mehr oder weniger komplizierte Art vom Compiler zusammengebastelt - im einfachsten Fall ohne irgendwelche template-Instantiierung auf die handcodierte Art. Im allereinfachsten Fall ist es natürlich deine einfache Funktion, ohne dass irgendein Funktor-Objekt konstruiert werden müsste.
    Be einfachen Funktoren hat der Compiler gute Chancen dass ein Großteil des generierten oder selbstgetippten Codes wegoptimiert wird und lediglich die Essenz des Vergleichs übrig bleibt - nämlich der operator>.



  • Hey, eine der Varianten kam ohne Funktor aus! 🙂



  • knivil schrieb:

    Und man sieht wieder, wie aus einer simplen Sache unglaublich viel Code entsteht. Ich finde die vorgeschlagenen Loesungen schlecht.

    Du sagst ohnehin immer, dass Du alles schlecht findest ohne dabei irgendwelche Lösungen beizutragen. Mach doch einen besseren Vorschlag, wenn es so schlecht ist.

    Mal ganz davon abgesehen widersprichst Du Dir a) selbst, und b) ist die Menge an generiertem Code doch sehr überschaubar.



  • pumuckl schrieb:

    Nein tun sie nicht. Was glaubst du was greater<Object> macht? oder dein vorgeschlagenes greater<Object::element> ?

    Ich meinte mit "sie existieren schon" ein bisschen was anderes, nämlich nicht, dass dafür nicht extra Code (durch den Compiler) erzeugt werden müsste (was klar ist), sondern dass ich als Programmierer gerne auf bestehende Konstruktionen zurückgreifen würde.

    Nexus (und Decimad) haben ja eine sehr schöne und allgemein verwendbare Möglichkeit aufgezeigt. (Danke dafür schon mal, 👍!) Was mich wundert: Da das Problem, Objekte (Klasseninstanzen) nach verschiedenen Eigenschaften sortieren zu wollen, so selten nicht ist, dass C++ (inkl. STL) da keine Bordmittel hat...



  • Da halt ich es wie die Mathematiker. Sie koennen auch Beweise ablehnen, ohne einen richtigen zu liefern. Desweiteren entspricht es nicht den Anforderungen des Threadstellers:

    (ohne Extrafunktion!)

    Da das aber nicht moeglich ist (es wurden Extrafunktionen/Functoren geschrieben), warum sollte ich eine weitere (Un)loesung liefern. Ausserdem ist die Generalisierung ueber Templates genauso wie fruehzeitige Optimierung ...



  • knivil schrieb:

    Ausserdem ist die Generalisierung ueber Templates genauso wie fruehzeitige Optimierung ...

    OMG, da würde man ja etwas lernen.

    Die Lösung ist gut. Nicht ideal - aber das liegt an der Aufgabenstellung.



  • Hey, ich fand die Aufgabenstellung gut! 😉



  • Nexus schrieb:

    question123, kommt das jetzt noch ein wenig näher? Ist es sogar schon gut genug? 🙂

    Bin verwirrt. Ich krieg's nicht zum Laufen:
    minimal5.cxx:75: error: no matching function for call toCompare(int (some::*)())'`
    😕


Anmelden zum Antworten