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

[question123]

Hi,

folgendes Problem wurmt mich schon länger, ich habe bisher aber keine richtig befriedigende Lösung gefunden, weder in Foren noch in Unterhaltungen mit anderen Programmierern.

Ich habe eine Klasse (im Beispiel Object) mit verschiedenen Eigenschaften, die Standardtypen (int, float) sind, nach denen ich einen Vektor mit von dieser Klasse abgeleiteten Objekten sortieren möchte:

[cpp]
#include <vector>
#include <algorithm>
#include <functional>
#include <iostream>

class Object {
  public:
    long pt() const {return _pt;};
    long e()  const {return _e;};
    Object(long pt, long e) : _pt(pt), _e(e) { }

    // used for one possible way of sorting
    bool operator> (const Object &p) const {
      return this->pt() > p.pt(); // uses [b]pt[/b] property
    }

  private:
      long _pt;  
      long _e;
};

// another way of sorting  
bool ugly_extra_function1(Object const& a, Object const& b) {
       return (a.pt() < b.pt()); // uses [b]pt[/b]
}

bool ugly_extra_function2(Object const& a, Object const& b) {
       return (a.e() < b.e());   // uses [b]e[/b]
}

int main() {
        std::vector<Object>objects;

        objects.push_back(Object(3,30));
        objects.push_back(Object(7,70));
        objects.push_back(Object(2,20));
        objects.push_back(Object(8,80));

        // like this:
        std::sort(objects.begin(), objects.end(), std::greater<Object>());
        // but this can only sort by one object property (which is hard-coded in Object::operator>, here pt )

        // or like this: 
        std::sort(objects.begin(), objects.end(), ugly_extra_function1);
        // allows sorting by e as well:
        std::sort(objects.begin(), objects.end(), ugly_extra_function2);

        // Still: I would prefer something like:
        // std::sort(objects.begin(), objects.end(), std::greater<Object::pt>);
        // std::sort(objects.begin(), objects.end(), std::greater<Object::e>);
        // But this does not work :-(

        for ( std::vector<Object>::const_iterator it = objects.begin(); it !=objects.end(); ++it)
          std::cout << it->pt() << " " << it->e() << std::endl;

        return 0;
}
[/cpp]

Im Code sind verschiedene Möglichkeiten zur Sortierung erklärt, und auch das, was mich stört.

Denn: Muss ich wirklich für jede Eigenschaft nochmal eine Vergleichsfunktion schreiben? Das sind doch alles Standardtypen, die schon eine eingebaute Vergleichsfunktion haben!

Es wundert mich irgendwie, dass C++ da keine elegantere Methode à la

std::sort(objects.begin(), objects.end(), std::greater<Object::pt>);

anbieten soll, die ohne das eigentlich vollkommen unnötige Neuprogrammieren des Vergleichsoperators auskommt?!?

[jencas]

Nimm einen Funktor und gib dem mit, nach welchem Attribut sortiert werden soll.

[question123]

jencas schrieb:

Nimm einen Funktor und gib dem mit, nach welchem Attribut sortiert werden soll.

Hm - wie sage ich denn dem Funktor, welche Eigenschaft er verwenden soll, sprich wie übergebe ich ihm einen Verweis auf die entsprechende Klasseneigenschaft? Spontan sehe ich da auch wieder nur eine if -Abfrage als Möglichkeit:

Das ist halt auch wieder eine Extra-Funktion, die ich schreiben muss -- und wahrscheinlich ist es sogar noch ineffizienter als mehrere Vergleichsfunktionen zu schreiben und dann davon eine zu verwenden, weil das dann ohne if auskommt. Oder hab ich Dich falsch verstanden?

[Gast]

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

[Gast]

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

[Gast]

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

[Gast]

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

[Gast]

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.

[Gast]

So ist das halt in C++