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

Ich habe hier mal einen Schnellbeispiel mit Daten-Member-Zeigern gebastelt:

#include <iostream>

struct some
{
	int a;
	int b;
};

template< typename S, typename T >
class compare {
public:
    compare( T S::*memptr )
        : memptr_(memptr)
    {
    }

    bool operator()( const S& a, const S& b ) {
        return a.*memptr_ < b.*memptr_;
    }

private:
    T S::*memptr_;
};

template< typename S, typename T >
compare< S, T > make_compare( T S::*some )
{
    return compare<S, T>( some );
}

int main(int argc, char* argv[])
{
    some d,e;
    std::cout << make_compare( &some::a )( d, e );

    return 0;
}

Vielleicht ist das ja was für dich.

Viele Grüße,
Michael

knivil

vollkommen unnötige Neuprogrammieren des Vergleichsoperators auskommt?!?

Du hast das Konzept nicht verstanden. Sicher kann man sich auch ad hoc was mit lambda / also boost::bind basteln, aber es ist immernoch eine neue Vergleichsfunktion.

pumuckl

schau mal nach boost::lambda

//sort by pt
std::sort(objects.begin(), objects.end(), _1._pt < _2._pt);
//sort by e
std::sort(objects.begin(), objects.end(), _1._e < _2._e);

Kürzer und zur Compile-Zeit:

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

struct some
{
	int a;
	int b;
};

int main(int argc, char* argv[])
{
	some d,e;	
	std::cout << compare2< some, int, &some::a >::compare( d, e );

	return 0;
}

Kann man das irgendwie leicht auf einen Template-Parameter bringen?
Ist das Boost-Lambda-Beispiel zur Compile-Zeit ausgewertet?

Viele Grüße,
Michael

question123

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

@Decimad: Elementzeiger sind also mein Freund. Wobei das ja letztendlich nichts anderes macht, als jedes Mal eine Vergleichsfunktion zu erstellen, aber auf eine elegantere Weise als sie jedes Mal selbst zu schreiben Ich war noch ein wenig am Grübeln über Deine Konstruktion mit compare und make_compare , aber Du hast ja schon eine kürzere Variante gezeigt. Das gefällt mir schon ganz gut und leistet auch das, was ich mir vorgestellt habe. (Bis auf halt die Tatsache, dass es für jede Objekteigenschaft extra Code erzeugt...)

question123

Decimad schrieb:

Ist das Boost-Lambda-Beispiel zur Compile-Zeit ausgewertet?

Ich denke ja, denn die Dokumentation sagt: "While it is possible to write incredibly complex lambda expressions, it probably isn't a good idea. Compiling such expressions may end up requiring a lot of memory at compile time, and being slow to compile." Auch scheinen die mit boost-Lambda-Ausdrückten erstellten Funktionen von der Laufzeit her mit selbstgeschriebenen Funktoren vergleichbar zu sein (auch siehe Doku).

Naja, ich meinte, ob zum Auswerten der Ausdrücke ein temporäres Funktor-Objekt für den Lambda-Ausdruck entsteht. Das dessen Typ schon bei der Compile-Zeit zusammengebastelt wird (Und sehr kompliziert werden kann), ist ja klar. Ich muss mir wohl mal die Sourcen anschauen, ist ja schon komfortabel Ich hab nur wie immer bei boost Respekt vor den kryptischen Namen und dem von Sonderfällen durchzogenen Quelltext
So kleine proof-of-concept Beispiele zum Einstieg wären da mal toll

Viele Grüße,
Michael

knivil

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.

question123

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.

Nexus

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));

Nexus

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.

question123

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); }
};

knivil

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.

Nexus

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ß

knivil

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++

Nexus

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?

pumuckl

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