template-Prädikatproblem

ACnut

Hallo!
Ich muss euch wieder einmal belästigen
Es eght um die folgende Aufgabenstellung (eigentlich um die zweite Teilaufgabe):

Implementieren Sie einen
generischen Algorithmus, der die Sortierung eines über Iteratoren gegebenen Bereichs in einem
Container prüft. Folgende 4 Fälle sollen dabei unterschieden werden:
Der Bereich ist aufsteigend sortiert.
Der Bereich ist absteigend sortiert.
Alle Elemente sind gleich oder der Bereich ist leer.
Der Bereich ist unsortiert.
Definieren Sie einen entsprechenden Enumerationstypen und verwenden diesen als Rückgabetyp
für Ihren Algorithmus.
1
Implementieren sie weiters eine überladene Variante mit einem Prädikat als dritten Parameter, das
die für die Sortierung relevante Vergleichsfunktion angibt.
Achten Sie darauf, dass Ihr Algorithmus auch für Container mit sequentiellem Zugriff funktioniert.

Den ersten Teil hab ich schon implementiert, allerdings die Frage mit dem Prädikat verstehe ich nicht ganz.
Muss ich hier den Container nach der Überprüfung (wie und ob der Container sortiert ist) nachher dann sortieren?
Was soll der Funktor tun?

Falls es wie beim ersten Teil sollte (nur Überprüfung auf Sortierung):
//sorttype ist Rückgabewert vom Datentyp enum

template <typename titor, typename funktion>
	sortType überladenefunktion (titor begin, titor end, funktion f)
{
//blabla
}

dann kann ich das Prädikat ja nicht innerhalb der Funktionstemplate-definition (das Wort gibts wahrscheinlich nicht :D), sopmit kann ich keine Iteratoren vom Typ TItor mitgeben (oder?), dass heißt ich müsste mich auf einen Datentypen spezialisieren (int, double,...)

z.b:

bool f(int i, int j)
	{
return (i<j);
	}

wobei ich nach meinem jetzigen Beispielverständnis nicht weiß, wie ich mit einem Prädikat die 4 Fälle abdecken soll?

Sone

ACnut schrieb:

Funktionstemplate-definition (das Wort gibts wahrscheinlich nicht :D)

Nicht im Duden.

Was soll der Funktor tun?

Ganz einfach. Diese Version mit dem Prädikat ist in der STL beliebt - das Prädikat ist einfach ein Funktionsobjekt, dass zwei Objekte entsprechenden Typs nimmt und einen bool (bzw. einen zu bool konvertierbaren Wert) zurückgibt.

Das Prädikat gibt einfach an, ob ein Objekt in der Sortierung vor dem zweiten kommt oder nicht. Also ob das erste der Funktion übergebene Objekt beim sortieren vor das zweite kommt oder nicht.

dass heißt ich müsste mich auf einen Datentypen spezialisieren (int, double,...)

Naja, es gibt vordefinierte Funktoren wie std::greater_equal - die musst du nur noch mit einer Parameterliste qualifizieren und instantiieren, also greater_equal<int>() , und an die Funktion übergeben.
Genauso kannst du auch deine Prädikate flexibler gestalten.

wobei ich nach meinem jetzigen Beispielverständnis nicht weiß, wie ich mit einem Prädikat die 4 Fälle abdecken soll?

Nein nein. Dein Funktionstemplate prüft. Dein Prädikat macht nur einen simplen Vergleich, auf dem alles aufbaut.
Ein Beispiel:

volkard

ACnut schrieb:

Den ersten Teil hab ich schon implementiert,

Fein. Da kommt irgendwo if(*a<*b) vor.

ACnut schrieb:

allerdings die Frage mit dem Prädikat verstehe ich nicht ganz.

Dann kommt halt if(f(*a,*b)) vor.
Beachte, daß if(*a>*b) nicht mehr direkt darstellbar ist, aber das gleichwertige if(*b<*a) geht wieder als if(f(*b,*a)).

ACnut schrieb:

Was soll der Funktor tun?

Er soll erlauben, daß zum Beispiel Strings nur nach dem Anfangsbuchstaben auf Sortiertheit geprüft werden können oder unter Vernachlässigung der Groß-Kleinschreibung.

ACnut schrieb:

dann kann ich das Prädikat ja nicht innerhalb der Funktionstemplate-definition (das Wort gibts wahrscheinlich nicht :D), sopmit kann ich keine Iteratoren vom Typ TItor mitgeben (oder?), dass heißt ich müsste mich auf einen Datentypen spezialisieren (int, double,...)

z.b:
bool f(int i, int j)
	{
return (i<j);
	}

Ja, das ist angemessen.

ACnut schrieb:

wobei ich nach meinem jetzigen Beispielverständnis nicht weiß, wie ich mit einem Prädikat die 4 Fälle abdecken soll?

Ein Prädikat ist eine Funktion (oder Funktor oder Programm, was soll der Geiz), die bool zurückgibt. Das Prädikat soll hier nur sagen, ob i kleiner als j ist. Die 4 Fälle stellt weiterhin Deine große Funktion fest.

Sone

Der Standard sagt bspw. über diese Prädikate:

A function object type is an object type (3.9) that can be the type of the postﬁx-expression in a function call
(5.2.2, 13.3.1.1).
A function object is an object of a function object type. In the places where one would
expect to pass a pointer to a function to an algorithmic template (Clause 25), the interface is speciﬁed to
accept a function object. This not only makes algorithmic templates work with pointers to functions, but
also enables them to work with arbitrary function objects.

Es macht die Algos sehr flexibel, wenn sie alle aufrufbaren Entitäten nutzen können, anstatt bspw. nur Funktionszeiger (und daraus folgend nur Funktionen selbst, keine Funktoren o.ä.).

template<typename Arithmetic>
struct Even /// Ein Objekt vom Typ Even<...> prüft, ob eine Zahl gerade ist oder nicht
{
    bool operator()( Arithmetic lhs )
    {
        return lhs % 2 == 0;
    }
};

#include <iostream>
#include <algorithm>
#include <iterator>

int main()
{
    int arr[]{4, 2, 3, 7, 9, 6, 3, 5};

    std::partition( std::begin(arr), std::end(arr), Even<int>() );

    std::copy( std::begin(arr), std::end(arr), std::ostream_iterator<int>(std::cout, ", ") );
}

Ausgabe:

4, 2, 6, 7, 9, 3, 3, 5,

ACnut

Sone schrieb:

dass heißt ich müsste mich auf einen Datentypen spezialisieren (int, double,...)

Naja, es gibt vordefinierte Funktoren wie std::greater_equal - die musst du nur noch mit einer Parameterliste qualifizieren und instantiieren, also greater_equal<int>() , und an die Funktion übergeben.
Genauso kannst du auch deine Prädikate flexibler gestalten.

Ein Beispiel:

ok und wie mach ich das mit dem datentypen ohne das prädikat nur auf einen datentypen zu spezialisieren?

Fein. Da kommt irgendwo if(*a<*b) vor.

genau und noch mehr :p a>b & a==b

Ein Prädikat ist eine Funktion (oder Funktor oder Programm, was soll der Geiz), die bool zurückgibt. Das Prädikat soll hier nur sagen, ob i kleiner als j ist. Die 4 Fälle stellt weiterhin Deine große Funktion fest.

ok eure antworten sind schlüssig, bis auf die oben genannte frage,
bei der ich folgendes brauche:

Ein Beispiel:

oder erklärung

volkard

ACnut schrieb:

Fein. Da kommt irgendwo if(*a<*b) vor.

genau und noch mehr :p a>b & a==b

Du kannst a>b ausdrücken als b<a
Du kannst a>=b ausdrücken als !(a<b)
Du kannst a!=b ausdrücken als a<b || b<a
Und == und <= wirste selber rausfinden.

ACnut schrieb:

ok eure antworten sind schlüssig, bis auf die oben genannte frage,
bei der ich folgendes brauche:

Ein Beispiel:

oder erklärung

Weitere Erklärung fällt mir nicht ein und das Beispiel wäre schon die fertige Lösung, mag ich heute mal nicht machen.

ACnut

Sone schrieb:

template<typename Arithmetic>
struct Even /// Ein Objekt vom Typ Even<...> prüft, ob eine Zahl gerade ist oder nicht
{
    bool operator()( Arithmetic lhs )
    {
        return lhs % 2 == 0;
    }
};

#include <iostream>
#include <algorithm>
#include <iterator>

int main()
{
    int arr[]{4, 2, 3, 7, 9, 6, 3, 5};

    std::partition( std::begin(arr), std::end(arr), Even<int>() );

    std::copy( std::begin(arr), std::end(arr), std::ostream_iterator<int>(std::cout, ", ") );
}

Ausgabe:

4, 2, 6, 7, 9, 3, 3, 5,

ok, das Beispiel ist eh gekommen entschuldigung für meine hektik
wieso geht das mit dem struct. ich dachte in eine struct kann ma keine funktionen reinpacken, daher muss man funktionen implementieren?

also wenn ich das beispiel (von dir) richtig verstanden habe, dann wird mit dem template eine implizite datentypkonvertierung durchgeführt, simt muss ich mich nicht auf einen speziellen datentyp fixieren?

bei meinem beispiel würde das prädikat dann also so aussehen?:

struct comparison /// Ein Objekt vom Typ Even<...> prüft, ob eine Zahl gerade ist oder nicht
[code="cpp"]template<typename Arithmetic>
{
bool operator()( Arithmetic lhs, Arithmetic rhs )
{
return lhs < rhs;
}
};

bin zu müde um neues Wissen aufzunehmen muss schlafen gehen
Implementierung erfolgt morgen

bis dahin gute Nacht
:good night sleep: : on

ACnut

volkard schrieb:

ACnut schrieb:

Fein. Da kommt irgendwo if(*a<*b) vor.

genau und noch mehr :p a>b & a==b

Du kannst a>b ausdrücken als b<a
Du kannst a>=b ausdrücken als !(a<b)
Du kannst a!=b ausdrücken als a<b || b<a
Und == und <= wirste selber rausfinden.

ACnut schrieb:

ok eure antworten sind schlüssig, bis auf die oben genannte frage,
bei der ich folgendes brauche:

Ein Beispiel:

oder erklärung

Weitere Erklärung fällt mir nicht ein und das Beispiel wäre schon die fertige Lösung, mag ich heute mal nicht machen.

ich schreibe eindeutig zu langsam

aber mit meinem ersten prädikat

bool f(int i, int j)
    {
return (i<j);
    }

dürfte die negation nicht funktionen oder? weils ja auf die funktion zeigt.
aber mit @Sone struct-Definition sollte die Negation auch funktioneren, oder?

so jetzt aber wirklich die letzte Antwort für heute. ein auge ist schon zu

volkard

ACnut schrieb:

volkard schrieb:

ACnut schrieb:

Fein. Da kommt irgendwo if(*a<*b) vor.

genau und noch mehr :p a>b & a==b

Du kannst a>b ausdrücken als b<a
Du kannst a>=b ausdrücken als !(a<b)
Du kannst a!=b ausdrücken als a<b || b<a
Und == und <= wirste selber rausfinden.

ACnut schrieb:

ok eure antworten sind schlüssig, bis auf die oben genannte frage,
bei der ich folgendes brauche:

Ein Beispiel:

oder erklärung

Weitere Erklärung fällt mir nicht ein und das Beispiel wäre schon die fertige Lösung, mag ich heute mal nicht machen.

ich schreibe eindeutig zu langsam

aber mit meinem ersten prädikat
bool f(int i, int j)
    {
return (i<j);
    }
dürfte die negation nicht funktionen oder? weils ja auf die funktion zeigt.
aber mit @Sone struct-Definition sollte die Negation auch funktioneren, oder?

so jetzt aber wirklich die letzte Antwort für heute. ein auge ist schon zu

Hör nicht auf Sone, der ist Templateverliebt. Löse erstmal die Aufgabe vernünftig.

Klar geht das.
Dein Prädikat ist gut.

Du sollst doch nicht das Prädikat negieren, sondern dessen Berechnungsergebnis, den bool.
statt if( a>=b ) schreibe man if( !(a<b) )
Also bei Verwendeung des Prädikats if( !(f(a,b)) )

(Danach kannste Dein Prädikat durch Sones Prädikat austauschen ohne, daß die gesuchte Funktion verändert werden muss, ist aber erstmal eine Unwichtige Spielerei.)

ACnut

und wieder einmal habt ihr mich gerettet
ein bisschen aussagenlogik sollte ich allerdings auch noch üben

gut wann brauch ich die Konstruktion mit dem struct und wieso funktioniert das(müsste statt dem struct nicht class stehen)?

hochachtungsvoll
ACnut

Nathan

struct und class unterscheiden sich nur in zwei Aspekten:
Bei struct ist defaultmäßig alles im public Bereich, bei class im private und bei der Vererbung ist es defaultmäßig public bei struct und private bei class.
Ansonsten sind sie gleich.
Da bei struct alles public ist, nutzt man sie häufig, wenn man nur Daten speichern will und keine Funktionen braucht (abgesehen von Konstruktoren, Aggregat-Initialisierung ist nciht ganz das Wahre). class nutzt man sobald Kapselung im Spiel ist.
Deshalb kamst du vielleicht zu der fälschlichen, dass man bei struct keine Memberfunktionen haben kann.

ACnut

wieder was neues gelernt

danke