vector mit structs sortieren

windschief

Huhuuu ich brauche mal wieder eure Hilfe.

und zwar habe ich ein struct:

template <typename T> struct haus{
    int zimmer;
    bla bla....
};

und einen vector von häuserm

vector<haus<T> > stadt;

jetzt möchte ich die Häuser absteigend sortieren (z.b. nach der anzahl der zimmer).
Ich habe mir bereits einen

operator()<

gebaut... allerding macht:

sort(stadt.begin(),stadt.end());

eine aufsteigende liste... wie kann ich ihm sagen, dass er absteigend sortieren soll?

Ich habe bereits versucht meinen struct mit operator() zu erweitern, aber das hat irgendwie nicht geklappt... wäre das der richtige weg? Dann muss ich da nochmal nachschauen... oder geht es auch anders?

Kóyaánasqatsi

Inwiefern absteigend? Du meinst umgekehrt? Ich weiß generell nicht ob die std::sort in diesem Fall das macht was du möchtest. Ich würde nochmal die Operatorenüberladung angehen.

windschief

genau, also operator()< sortiert aufsteigend... und ich bräuchte sozusagen >...>.
Also die sort funktioniert wie es soll... (nur ich will es "umgedreht").
(ich habe jetzt in der operator()< funktion einfach andersrum sortiert, aber das ist ja "unsauber" und so will ich es nicht lassen)

okay was genau meinst du mit operatorüberladung?
den operator() in mein struct packen?
was genau muss ich denn dafür machen?

Blue-Tiger

von Haus aus nimmt std::sort immer operator<. Wenn du das nicht willst, musst du deine eigene Sortierfunktion schreiben und std::sort als 3. Parameter mitgeben:

bool newsort(const Haus& lhs, const Haus& rhs)
{
    return !(lhs < rhs);
}

sort(stadt.begin(),stadt.end(), newsort);

EDIT: Erklaerung hinzugefuegt

Kóyaánasqatsi

std::sort dürfte es egal sein, in welcher Reihenfolge der Container vor liegt. Wie es trotzdem ginge:

std::sort(Container.rbegin(), Container.rend(), funk);

Wegen der Operatorenüberladung, schau mal in einem Tutorial nach, muss jetzt zocken xD

Kahino

Sofern du kleine Datenmengen hast wo das Rumschieben nicht so auffällt, könntest du das einfach einfach ganz normal sortieren und dann mit reverse umkehren.

Nexus

windschief schrieb:

wie kann ich ihm sagen, dass er absteigend sortieren soll?

Schreib dir keinen operator< für Dinge wie Häuser. Man sollte sich sofern möglich an die Konvention halten, Operatoren nur dann zu überladen, wenn sich die Semantik eindeutig ergibt. Bei einem Haus kann vieles verglichen werden (Höhe? Grundfläche? Anzahl Zimmer? Preis?).

Schreibe dir Sortierfunktionen oder -funktoren. Beispiel mit Funktionszeiger:

bool hat_weniger_zimmer(const haus& lhs, const haus& rhs)
{
    return lhs.anzahl_zimmer < rhs.anzahl_zimmer;
}

bool hat_mehr_zimmer(const haus& lhs, const haus& rhs)
{
    return lhs.anzahl_zimmer > rhs.anzahl_zimmer;
}

Anwendung:

// aufsteigend sortieren
std::sort(stadt.begin(), stadt.end(), &hat_weniger_zimmer); 

// absteigend sortieren
std::sort(stadt.begin(), stadt.end(), &hat_mehr_zimmer);

Du findest auch einiges, wenn du in der Forensuche nach Funktoren suchst.

Kóyaánasqatsi schrieb:

Inwiefern absteigend? Du meinst umgekehrt?

Ich denke, der Begriff "absteigend" sollte genügend klar sein...

windschief schrieb:

Huhuuu ich brauche mal wieder eure Hilfe.

...

Ich habe mir bereits einen
operator()<
gebaut... allerding macht:
sort(stadt.begin(),stadt.end());
eine aufsteigende liste... wie kann ich ihm sagen, dass er absteigend sortieren soll?

definiere operator>() und sortiere mit

#include <functional>
...
sort(stadt.begin(),stadt.end(), std::greater<haus<T> >());

Lars

http://www.codeproject.com/KB/cpp/Sort.aspx

windschief

vielen vielen dank für eure antworten! In der Theorie hab ichs verstanden..

hab jetzt eine funktion sort geschrieben:

template<typename T> bool nodeSort(const node<T>& n1, const node<T>& n2){
  return true;
};

aufgerufen mit:

std::sort(list.begin(),list.end(),&nodeSort);

nur leider bekomme ich folgenden fehler:

error: no matching function for call to ‘sort(__gnu_cxx::__normal_iterator<node<double>*, std::vector<node<double>, std::allocator<node<double> > > >, __gnu_cxx::__normal_iterator<node<double>*, std::vector<node<double>, std::allocator<node<double> > > >, <unresolved overloaded function type>)’

windschief

scheinbar kennt er die funktion sort() nicht... oder muss ich anders aufrufen?

#include <algorithm>

hab ich eingebunden..

kann es auch ein Problem mit den Templateargumenten sein? Muss ich hierfür noch irgendwas übergeben.. kann ja eigentlich nicht sein.

Th69

Du mußt noch den genauen Typparameter bei deiner Template-Funktion angeben, z.B.

nodeSort<int>

windschief

vielen vielen Dank!
es klappt

ist es ein Unterschied ob ich:

sort(list.begin(),list.end(),&nodeSort<int>);

oder

sort(list.begin(),list.end(),nodeSort<int>);

schreibe?
passiert was unterschiedliches?

windschief

noch was:

wie genau sortiert sort?
Ich bekomme einen Speicherzugriffsfehler beim sortieren.
Wenn ich mir vorm sortieren die Objekte anzeigen lasse, ist alles in Ordnung.
Ich hab jetzt mal in meine nodeSort funktion eine Ausgabe eingebaut, hier werden Objekte miteinander verglichen die garnicht existieren..
Bsp:

Vorher im vector Häuser mit Zimmer 1-10...
Beim Sortieren taucht auf einmal ein Haus mit 80 Zimmern auf..

NodeSort benutzt ja const Objekte, also dürften sie eigentlich nicht verändert werden.. Was kann denn da schief gehen?

camper

windschief schrieb:

hab jetzt eine funktion sort geschrieben:
template<typename T> bool nodeSort(const node<T>& n1, const node<T>& n2){
  return true;
};

Das ist keine zulässige Vergleichsfunktion, weil es keine strenge schwache Ordnung darstellt, sie ist nicht irreflexiv.

windschief schrieb:

Ich bekomme einen Speicherzugriffsfehler beim sortieren.

Bei der Vergleichsfunktion nicht überraschend, denn die bewirkt undefiniertes Verhalten.

windschief

was genau heißt "irreflexiv"?
sorry das war nur der einfachhalthalber, du hast natürlich recht, so kann ich keine Sortierung herstellen.
ich habe folgendes (viell ist das ja auch falsch):

template<typename T> bool nodeSort(const node<T>& n1,const node<T>& n2){
  if(n1.nr < n2.nr) return true;
  else if(n1.nr == n1.nr){
    if(n1.name > n2.name) return true;
  }
  return false;
};

ist das in Ordnung?

camper

windschief schrieb:

was genau heißt "irreflexiv"?

Dass die Relation nicht gilt, wenn sie auf das selbe Objekt angewendet wird. nodeSort(x,x) muss false ergeben.

windschief schrieb:

template<typename T> bool nodeSort(const node<T>& n1,const node<T>& n2){
  if(n1.nr < n2.nr) return true;
  else if(n1.nr == n1.nr){
    if(n1.name > n2.name) return true;
  }
  return false;
};

ist das in Ordnung?

nein, es sollte

else if(n1.nr == [i]n2[/i].nr){

heißen. Sonst ist die Relation nicht asymmetrisch.

windschief

danke danke danke!!!!!!!!!
sowas fällt einem nie auf, selbst wenn man stunden schaut...

und ich habe wieder gelernt, den "original" code zu posten...

Mich würde jetzt aber noch interessieren (falls es jemand weiß), woher diese "nicht existierenden Objekte" kamen, und mit welchem sortierungsalgo gearbeitet wird.

knivil

Ich verweise gern immer auf: http://www.developia.de/developia/viewarticle.php?cid=31792 .

Blue-Tiger

windschief schrieb:

Mich würde jetzt aber noch interessieren (falls es jemand weiß), woher diese "nicht existierenden Objekte" kamen, und mit welchem sortierungsalgo gearbeitet wird.

Wie bereits gesagt: eine "ungueltige" Sortierfunktion erzeugt undefiniertes Verhalten ==> es kann alles moegliche passieren, vermutlich ist irgendwo ueber die Speichergrenzen raus gelesen worden.

Der Standard schreibt den genauen Algo nicht vor, d.h. die Compilerhersteller duerfen selbst waehlen, welchen Sortieralgorithmus sie verwenden (solang er in O(n log n) laeuft, IIRC). In der Praxis wird meist Introsort (eine Art gepimpter Quicksort) verwendet.