Wie finde die x größten Elemente einer Map -

Michael E.

Öhm, du kannst dir das Kopieren auch sparen und meinen Code benutzen.

Benja_m

Michael E. schrieb:

Den größten int-Wert bekommst du so raus:
...

Ich suche ja aber nicht nur den größten Wert, sondern die x (2, 45, 156) größten Werte ...

Michael E.

Ich dacht, das würdest du jetzt selbst rauskriegen, wenn man dir erst mal zeigt, wie man den größten Wert bekommt.

Benja_m

*bing*

Michael E. schrieb:

#include <utility>

struct SmallerThan
{
	bool operator()(std::pair<const Object, int> &lhs, std::pair<const Object, int> &rhs)
    {
        return lhs.second < rhs.second;
    }
};

std::nth_element(myMap.begin(), myMap.end(), SmallerThan());
}

Obiges müsste dann ja mein Problem lösen, oder ?

Bin nicht so fit in den std-Algorithmen ...

Michael E.

Mist, jetzt hab ich mich selbst in was verrannt.

nth_element geht leider nicht, weil das nen Random Access Iterator erwartet, den map aber nicht bietet. Man könnte die Map natürlich aufsplitten, sodass die schon gefundenen Elemente rausfallen. Ist aber im Endeffekt alles viel zu aufwendig.

Nimm tim_gs Vorschlag oder sowas:

erstelle einen Vektor mit int-Wert + Zeiger
kopiere int-Wert von map in vector und speicher Position im Zeiger
sortiere vector

Wäre auch nicht sehr effizient, da bei jedem Aufruf der Funktion erneut nach dem n-größtem Element gesucht wird und diese Zeit summiert sich auf Dauer. Vlt findet sich noch eine effizientere Möglichkeit.

Michael E.

Der Vektor ist solange gültig, wie sich die map nicht verändert. Diese Abhängigkeit wirst du nie rauskriegen. Also versteh ich nicht, worauf du hinauswillst

Benja_m

wenn die daten benötigt werden, ist die map in ihrem endzustand. es wird nichts weiter hinzugefügt oder gelöscht oder sortiert o.ä.
sie bleibt so, wie sie ist und wird auch ziemlich bald (nach der noch fehlenden suche der größten elemente) gelöscht.

habe ich mich wohl ein wenig schlecht ausgedrückt folgendes möchte ich damit sagen. wenn das größte element gesucht wird, muss der Container durchlaufen werden. wenn das zweitgrößte element gesucht wird, muss der Container durchlaufen werden. wenn das ... usw.

wei der variante mit dem kopieren wird der container lediglich einmal durchlaufen und nach neuem Index geordnet sortiert. ich werde austesten, wie groß sich die Unterschiede im Bezug auf die Performance sind.

kennt niemand eine andere möglichkeit oder hat jemand eine andere Idee das problem zu lösen?

bis jetzt habe ich keine schnellere möglichkeit gefunden, als die kopie in einem Container vom typ multimap (s. Post oben).

Benja_m

ich machs jetzt so:

ich kopiere alle ints in einen vector
diesen vector lasse ich sortieren.
ich picke mir das x-te element heraus und speichere dessen wert.

dann gehe ich die ursprünhliche map einmal komplett durch und vergleiche jedes element mit dem aus dem vector gespeicherten element. wenn es größer ist, dann habe ich eines der x geforderten elemente gefunden.
das funktioniert auch

Benja_m

*buddel*

lucky_tux schrieb:

bei der variante mit dem kopieren wird der container lediglich einmal durchlaufen und nach neuem Index geordnet sortiert.

Wenn ich das folgendermaßen tue:

map<Obj, int> map;
multimap<int, Obj> mulmap;

map<Obj, int>::iterator it;

for (it = map.begin(); it != map.end(); it++)
{
    mulmap.insert(make_pair(it->second, it->first));
}

multimap<int, Obj>::iterator iter;

for (iter = mulmap.begin(); iter != mulmap.end(); iter++)
{
  cout << iter->first << endl;
}

Dann sind die Schlüssel NICHT auf- oder absteigend sortiert, sondern relativ willkürlich.
Beispielsweise

2 1 1 2 2 3 3 3 3 2 3 1 2 3 3 3 2  usw

Das ist nicht befriedigend, weil ich sicherstellen muss, dass die ganz großen Zahlen (gibt auch welche im 100er Bereich) ganz vorne stehen.

Hat da jemand spontan eine Idee ?

Würde eine solche Konstruktion mein Problem lösen?
Falls ja, was bräuchte man da zusätzlich ? Vergleichsoperation oderso ?

vector<pair<int, Obj> > vec;

map<Obj, int> map;
map<Obj, int>::iterator it;

for (it = map.begin(); it != map.end(); it++)
{
    vec.push_back(make_pair(it->second, it->first));
}

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

Benja_m

[selbstgespräch]

natürlich ist die ausgabe des iterators über die multimap sortiert. ich habe in meinem code einen kleinen fehler drin, den ich hier im beispiel natürlich nicht habe. deswegen funktionierte das nicht. also alls im lot.
[/selbstgespräch]