C++ unordered_map sortieren

[Hardliner93]

Hallo zusammen,
im Rahmen einer Programmieraufgabe habe ich folgendes Problem:

ich habe Objekte von meinem eigenen Typ Year, in dem u.A. eine Jahreszahl und deren zugehörige Durchschnittstemperatur gespeichert sind. In einer Teilaufgabe soll ich nun alle Jahre (131 an der Zahl) fallend nach Durchschnittstemperatur sortiert in eine Datei schreiben.

Bisher habe ich versucht, eine unordered_map<int, double> zu verwenden und mit Paaren von Jahr und Durchschnittstemperaturen zu füllen und diese dann zu sortieren, mit der normalen std::sort Sortierfunktion aus dem <algorithm>-Include, aber erfolglos.

unordered_map<int, double> sorted_years; // map, die später sortiert sein soll
for (int i = 0; i < years.size(); i++){ //vector<Year*> enthält alle Year-Objekte
	sorted_years.insert(make_pair(years.at(i)->getYear(), years.at(i)->getAvgTemp()));
}

//Sortierversuch:
sort(sorted_years.begin(), sorted_years.end(), compare_temps);

//compare-Funktion
bool compare_temps(pair<int, double> lhs, pair<int, double> rhs){
	return (lhs.second < rhs.second);
}

Könnt ihr mir weiterhelfen wo der Fehler ist bzw. ob es möglicherweise eine elegantere Lösung gibt?

Über Vorschläge bin ich sehr dankbar,
Gruß Hardliner

 

[kuddlmuddl]

Nimm doch einfach eine Map? Die ist immer automatisch sortiert. Der kannst du auch eigene Compare Funktionen geben.
Könntest auch map<double, int> machen und nicht nur int, double, dann brauchst du nichtmal ne eigene compare Funktion.
unordered_map sagt ja schon der Name ^^ sollte sich aber eigtl auch sortieren lassen hätte ich erwartet.

Woher weißt du dass dein sortieren keinen Erfolg hatte? Sieht auf den ersten Blick ganz gut aus.

 

[sash2k2]

Warum sortierst du nicht gleich den vector? Eine extra compare Funktion hast du ja bereits geschrieben. Nur leider nutzt du die vollen Möglichkeiten der Compare Funktion noch nichts aus. Du kannst nämlich direkt die Year Objekte anhand der Durchschnittstemp. vergleichen.

vector<Year*> years;

sort(years.begin(), years.end(), compare_temps);

bool compare_temps(const Year* lhs, const Year* rhs) {
   return (lhs->getAvgTemp() > rhs->getAvgTemp());
}

Beachte das ">" in der compare Funktion, da du ja absteigend sortieren willst.

 

[Hardliner93]

Das mit der map<double, int> habe ich versucht, aber es gibt Jahre, in denen die Durchschnittstemperatur gleich ist, deshalb sind dann Werte verschwunden. Und das Sortieren hatte beim Kompilieren Fehler ausgegeben.

Ergänzung (11. Juni 2013)

@sash2k2:
gute Idee, das müsste funktionieren, danke!
werde es kurz testen

Ergänzung (11. Juni 2013)

Es hat funktioniert! vielen Dank!

 

[d0zer]

Beudetet das, wenn ich aufsteigend sortieren will, brauch ich das compare Argument nicht nutzen?

Sondern nur

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

?

 

[Hardliner93]

in dem Fall musst du entweder den operator "<" überladen oder doch eine Methode schreiben, weil du eigene Typen ja nicht standardmäßig vergleichen kannst

 

[d0zer]

Du bist nicht zufällig an der Hochschule Darmstadt?


Also wenn ich die Version mit 2 Argumenten nehme dann muss ich den < Operator überladen und dann gehts?
Oder eigene comapre Methode schreiben dafür die Operatorüberladung weglassen?

 

[Hardliner93]

Zufällig schon wie kommst du jetzt darauf? ^^

normal schon, also dann

bool Year::operator< (const Year& other_year){
        return this->getAvgTemp() < other_year.getAvgTemp();
}

 

[d0zer]

Bearbeite auch gerade diese Klausur mit den Durchschnittswerten

 

[Hardliner93]

Alles klar

 

[kuddlmuddl]

Das mit der map<double, int> habe ich versucht, aber es gibt Jahre, in denen die Durchschnittstemperatur gleich ist, deshalb sind dann Werte verschwunden. Und das Sortieren hatte beim Kompilieren Fehler ausgegeben.

Für den Fall gibts multimaps, hätte ich evtl sagen sollen.
Sortieren ist dann nicht mehr nötig, da die map beim insert automatisch immer sortiert.

 

[Hardliner93]

Ja, das ist ein sehr guter Hinweis, danke! dadurch wäre das Problem der doppelten Key-Werte gelöst!

 

[d0zer]

Hardliner hab dir mal ne PN geschickt. Wäre cool wenn du sie beantworten könntest

 

[sash2k2]

Noch ein Nachtrag zum Thema map und multimap: Natürlich funktioniert diese Vorgehensweise auch, dass bedeutet aber nicht, das sie auch gut/empfehlenswert ist. Zum einen ist es langsamer (alleine der ganze Overhead für die map Datenstruktur), und zum anderen ist der Aufruf einer klar definierten und übersichtlichen Funktion wie sort() für denjenigen, der dein Programm liest, verständlicher, als sich mit den spezifischen Eigenschaften spezieller Datenstrukturen auskennen zu müssen.

 

[Dese]

eine map auf diese weise für sortierung zu verwenden ist nicht nur irgendwie irre, es ist auch falsch.

map garantiert als datenstruktur nicht, dass die keys sortiert sind. das ist zwar der fall, aber es ist eine interne eigenschaft (zweckmäßige eigenschaft).

unsorted_map gibt's deswegen, weil auf diese eigenschaft verzichtet wurde, um anderes efifzienter zu machen.

der funktionale unterschied einer map gegenüber einer unordered_map ist die möglichkeit über die keys zu iterieren, wobei dabei eine gewisse ordnung beachtet wird. wie das aber erreicht wird ist aus verwender sicht nicht garantiert.

das kann sich ändern und damit verdammt teuer werden, wenn du dich darauf verläßt, dass die elemente effizient in sortierter reihenfolge durchlaufen werden.

 

[Hancock]

@Dese:

Das ist bei C++ nicht der Fall ("strikt weak ordering"). Du kannst für map's explizit ein Sortieroperator angeben(siehe 3. Template-Parameter).
Und map wird diese Reihenfolge immer einhalten (sonst wären lower_bound und upper_bound ja nicht wohldefiniert).

 

[WingX]

Wenn das ne Klausur ist (Grundlagen Programmierung?), wäre es dann nicht die bevorzugte Lösung, die Objekte in einen Vector oder eine Liste hineinzusortieren mittels eines trivialen Sortieralgrithmus á la Mergesort oder Quicksort oder Bubblesort? Vielleicht noch einen Abstrakten Datentypen á la verkettete Liste oder sowas... Da würde sich dann ein Insertsort anbieten

 

[Hardliner93]

Ja das war auch die Lösung die ich im Endeffekt eingebaut habe, die Map stand nur ganz am Anfang im Raum bis sash2k2 die einfache Lösung mit dem Vector beigetragen hat die Diskussion ging danach nur irgendwie weiter

 

[Dese]

@Dese:

Das ist bei C++ nicht der Fall ("strikt weak ordering"). Du kannst für map's explizit ein Sortieroperator angeben(siehe 3. Template-Parameter).
Und map wird diese Reihenfolge immer einhalten (sonst wären lower_bound und upper_bound ja nicht wohldefiniert).

nein. es bedeutet, dass man in einem strikt weak ordering traversieren kann! es sagt nichts darüber aus, ob die daten intern tatsächlich sortiert gehalten werden und auch nichts über die kosten einer einer geordneten traversierung.

im übrigen sind diese sogar meist gar nicht sortiert vorhanden sondern als binärer suchbaum intern vorhanden:
http://www.cplusplus.com/reference/map/map/
"Maps are typically implemented as binary search trees."

 

[Hancock]

Ja dann ist in deiner Spreche ein Array ja auch nicht sortiert (MMU so mal als Hinweis).
Ich kann mit bei einer map darauf verlassen, dass ich mit dem iterator die Werte sortiert bekomme (und zwar aufsteigend).

Ich glaube, das Problem ist, das du und ich eine verschiedene Vorstellung von "sortiert" haben.