Sortierung einer Map

[Skared]

Servus,

ich versuche eine Map zu Sortieren nach den Key´s in den Objekten jedoch gelingt mir das nicht.

Hier einmal mein Code:

int main(int argc, const char* argv[])
{
	std::map<int, CTest*> test_map;

	for (int i = 1; i <= 5; i++)
	{
		char buffer[10];
    
		sprintf_s(buffer, "Test_%d", i);
		
		CTest * pTest = new CTest(10 + i, buffer);

		test_map.insert(std::pair<int, CTest*>(test_map.size() + 1, pTest));
	}
	
	std::stable_sort(test_map.begin(), test_map.end(), 
		[](std::pair<int, CTest*> a, std::pair<int, CTest*> b)
	{
		return a.second->GetKey() > b.second->GetKey();
	});

	return 0;
}

könnte mir jemand einen Denkanstoß geben?

Lg Skared

[Ein ehemaliger Benutzer]

@skared
Eine map ist nach ihrem Schlüssel sortiert und kann nicht umsortiert werden.

OT: benutze std::string, nicht char Arrays und sprintf.

[Skared]

also kann ich eine Map nicht sortieren wie eine std::list?

[Ein ehemaliger Benutzer]

@skared
Nein, eine map kann nicht sortiert werden.

OT Eine std::list kann nur mit ihrer eingebauten sort Funktion sortiert werden.

[wob]

@skared Maps sind immer nach ihrem Key sortiert. Dies ist so, damit du in log-Zeit einen Wert wieder finden kannst bzw. in log-Zeit einen Wert einfügen kannst. Wenn du die Daten in einer Map hast und diese sortiert ausgeben willst, kannst du dir z.B. einen vector von map-iteratoren (oder pointern auf die pairs in der Map) erzeugen und diesen sortieren. Vielleicht ist map auch der falsche Datentyp für dich? Oder der Key ist nicht der richtige?

[SeppJ]

@wob sagte in Sortierung einer Map:

@skared Maps sind immer nach ihrem Key sortiert. Dies ist so, damit du in log-Zeit einen Wert wieder finden kannst bzw. in log-Zeit einen Wert einfügen kannst. Wenn du die Daten in einer Map hast und diese sortiert ausgeben willst, kannst du dir z.B. einen vector von map-iteratoren (oder pointern auf die pairs in der Map) erzeugen und diesen sortieren. Vielleicht ist map auch der falsche Datentyp für dich? Oder der Key ist nicht der richtige?

Sie sind schon sortiert! Man braucht sie nicht zu sortieren. Einfach durch den Iterator durchgehen!

[Skared]

Also eine List lässt sich auf diesem Weg sehr schön sortieren @manni66

int main(int argc, const char* argv[])
{
	std::list<CTest*> test_list;

	for (int i = 1; i <= 5; i++)
	{
		char buffer[10];
    
		sprintf_s(buffer, "Test_%d", i);
		
		CTest * pTest = new CTest(10 + i, buffer);

		test_list.push_back(pTest);
	}
	
	std::stable_sort(test_list.begin(), test_list.end(),
		[](CTest * a, CTest * b)
	{
		return a->GetId() > b->GetId();
	});

	return 0;
}

Leider brauche ich die map für ein wxDataViewCtrl und den Key in den Objekten für die Sortierung.

Aber für mich ist es auch okay wenn ich die Objekte sortiert in einer list habe da ich die map für das wxDataViewCtrl eh immer neu erstellen muss.

VIelen Dank euch erstmal

[DocShoe]

Glaube nicht, dass manni das nicht wüsste...

[wob]

@seppj sagte in Sortierung einer Map:

Sie sind schon sortiert! Man braucht sie nicht zu sortieren. Einfach durch den Iterator durchgehen!

Ja, aber nach dem map-Key. @skared möchte aber nicht nach test_map.first, sondern nach test_map.second->GetKey() sortieren. Und das geht eben nur über einen Umweg.

Dieser Code hier: test_map.insert(std::pair<int, CTest*>(test_map.size() + 1, pTest)); verwundert mich allerdings, weil hier als map-Key immer eine fortlaufende Zahl genommen wird. Dann kann man auch gleich einen std::vector nehmen.

[wob]

@skared sagte in Sortierung einer Map:

Also eine List lässt sich auf diesem Weg sehr schön sortieren

Nein, stable_sort nimmt RandomAccessIterator als Parameter, eine std::list hat aber nur bidirektionale Iteratoren. Wundert mich, dass das funktioniert. Siehe hier: https://en.cppreference.com/w/cpp/algorithm/stable_sort unter "Type requirements".

PS: habs gerade mal ausprobiert, und - wie erwartet - das kompiliert nicht, weil die Iteratoren kein "Minus" können.

[Caligulaminus]

@wob Microsoft akzeptiert auch bidirektionale Iteratoren.
https://msdn.microsoft.com/de-de/library/z02ba27t.aspx

[wob]

@caligulaminus Boah, furchtbare Übersetzung, aber "schlimmste Fall ist O( n (Protokoll N ) 2)" (log = Protokoll, hahaha, selten so gelacht) soll wohl heißen, dass Microsoft dann nicht garantiert in N log N sortiert. Wobei list::sort angeblich "Approximately N log N comparisons, where N is the number of elements in the list.", also auch nur ungefähr. Ich dachte immer, dass man list::sort nimmt, weil man mit BiDis schlechter sortieren kann.

[Columbo]

Eine Option in diesem Fall (ebenfalls nach einem Teil des Werts sortieren) ist Boosts Bimap, die noch eine zweite Datenstruktur verwaltet, die Quasi als eine umgekehrte Map fungiert. Du wirst vielleicht einen Wrapper fuer den Value einsetzen muessen, ich sehe naemlich beim fluechtigen Ueberblicken der Referenz keinen Weg, einen eigenen value comparator einzusetzen.

[Skared]

@wob Die map brauche ich nur für die wxDataViewCtrl map. Die braucht als Key 1-MaxCount.

ich selbst brauche eigentlich nur eine liste die alle Objekte enthält.

@wob sagte in Sortierung einer Map:

Und das geht eben nur über einen Umweg

Könntest du mir den Umweg erläutern?

[firefly]

@skared sagte in Sortierung einer Map:

@wob Die map brauche ich nur für die wxDataViewCtrl map. Die braucht als Key 1-MaxCount.

ich selbst brauche eigentlich nur eine liste die alle Objekte enthält.

Du könntest einen pointer auf diese Objekte in einer zusätzlichen Container speichern, welche du dann nach deinen Kritieren sortierst.
Dadurch musst du aber zwei Container verwalten. z.b. Wenn du ein Element aus der map entfernst, muss das Element auch aus dem 2. Container entfernt werden.

[Skared]

Dann mache ich es via Liste wo die Objekte enthalten sind, sortiere diese Liste je nach bedarf und erstelle daraus die Map für das wxDataViewCtrl.

Vielen Dank an alle, somit ich meine Frage geklärt

Lg Skared

[wob]

@skared sagte in Sortierung einer Map:

@wob Die map brauche ich nur für die wxDataViewCtrl map. Die braucht als Key 1-MaxCount.

Das würde ich gern hinterfragen. Warum ist diese Map so aufgebaut? Warum wurde hier eine Map verwendet?

Zum Sortieren so ähnlich wie das hier:

std::map<int, string> m;
m[1] = "Welt"; m[2] = "Hallo";
std::vector<decltype(m)::value_type*> vit;
vit.reserve(m.size());
std::transform(m.begin(), m.end(), back_inserter(vit), [](auto& p){return &p;});
sort(vit.begin(), vit.end(), [](const auto &a, const auto &b){return a->second < b->second;});
for (auto &p: vit)cout << p->second << '\n';

[Skared]

@wob sagte in Sortierung einer Map:

Das würde ich gern hinterfragen. Warum ist diese Map so aufgebaut?

Es geht auch eine List. Vergiss das ich sagte das es eine map sein muss. Wurde schon geändert und läuft nun wunderbar

[hustbaer]

@skared sagte in Sortierung einer Map:

Es geht auch eine List.

Ich hoffe du meinst damit nen vector.

Kann es sein dass du aus dem Java Umfeld kommst? Oder woher die Liebe zu List? Ich meine, man nimmt aus gutem Grund in C++ kaum jemals std::list.

[Skared]

@hustbaer sagte in Sortierung einer Map:

Kann es sein dass du aus dem Java Umfeld kommst? Oder woher die Liebe zu List? Ich meine, man nimmt aus gutem Grund in C++ kaum jemals std::list.

Ja ich möchte mir jedoch auch einmal c++ anschauen.

Und zu deiner anderen Frage: ist es nicht schneller eine Liste zu bearbeiten(löschen/hinzufügen) als bei einem vector?

Lg Skared