map sortieren

SeppJ

map schrieb:

ist schwierig bei einem assoziativen array. ich möchte halt den kleinsten wert mit dem key herausfinden. nur weiß ich nicht, wie das geht. so ist die ausdrucksweise wahrscheinlich korrekt. könnt ihr mir helfen?

Bilde mal grammatikalisch korrekte Sätze, ich weiß immer noch nicht was du willst. Willst den den key zu einem bestimmten (dem kleinsten) value herausfinden?

Ja, genau das möchte ich machen. Ich brauche den Key zum kleinsten Wert. Ich weiß aber leider nicht, wie ich das mache

Danke

Nexus

map schrieb:

Ich brauche den Key zum kleinsten Wert. Ich weiß aber leider nicht, wie ich das mache

map.begin()->first

ne, damit kriege ich nicht den kleinsten Wert, sondern das erste Element.

Ich habe ein std::map. Die Keys sind Strings und die Values sind Integer. Jetzt brauche ich den Key, bei das integer Value am kleinsten ist.

Mit Nexus' Code kann was nicht stimmen, weil bei mir einfach der erste Key zurückgegeben wird.

Vielen Dank schonmal

SeppJ

Nexus schrieb:

map schrieb:

Ich brauche den Key zum kleinsten Wert. Ich weiß aber leider nicht, wie ich das mache
map.begin()->first

So wie ich das verstehe, will er das genaue Gegenteil.

Dafür könntest du entweder std::min_element auf die gesamte map loslassen oder (falls du noch andere als das kleinste brauchst) die Werte umgekehrt in eine andere Datenstruktur speichern, beispielsweise in eine andere map.

Maxi

Vielleicht geht das mit boost::bimap relativ einfach?

Nexus

Sorry, hab das zu schnell gelesen und "kleinsten Key" verstanden.

Ja, Boost.Bimap ist in beide Richtungen sortiert. Kommt halt drauf an, wie oft man die Suche benötigt. Falls eher selten, würde ich auch std::min_element() nehmen.

hey,

min_element hört sich doch gut an. Jetzt bin ich nur noch zu doof, das anzuwenden. Wenn die Keys Strings sind, warum kann ich das dann nicht schreiben:

string a = min_element(length.begin(), length.end());

ach ja: die fehlermeldung lautet, nachdem ich algorithm eingebunden habe:

error C2440: 'Initialisierung': 'std::_Tree<_Traits>::iterator' kann nicht in 'std::basic_string<_Elem,_Traits,_Ax>' konvertiert werden
1>

??? Was mache ich falsch ? hä?

ich habs jetzt so gemacht:

typedef std::map<string, int> IntVector ;
	typedef IntVector::iterator IntVectorIt ;

	IntVectorIt location ;

	location = min_element(length.begin(), length.end());
	cout << *location;

Leider funktioniert die Ausgabe nicht.

Binärer Operator '<<': Es konnte kein Operator gefunden werden, der einen rechtsseitigen Operanden vom Typ 'std::pair<_Ty1,_Ty2>' akzeptiert (oder keine geeignete Konvertierung möglich)

Könnt ihr mir bitte nochmal helfen?

Danke

nein, ich spame nicht

Mir fällt gerade ein: Mit min_element kriege ich doch gar nicht den key. Ich brauche den key zum kleinsten Element.

Bitte helft mir!

HighLigerBiMBam

Wahrscheinlich must du die map durchlaufen und den key des kleinsten gefunden elements der Klassen speichern. Mir ist kein anderer Weg bekannt.

Nexus

Du bekommst von min_element() einen Iterator auf den value_type der Map – also das Schlüssel-Wert-Paar. Um den Schlüssel zu extrahieren, musst du auf first zugreifen.

Ausserdem solltest du einen Funktor an min_element() übergeben, der Values vergleicht. Momentan wird das ganze Paar verglichen, d.h. die Schlüssel ( std::pair::first ) werden zuerst verglichen, dann die Werte ( std::pair::second ). Und da die Schlüssel immer verschieden sind, kommt es gar nie zum Wertvergleich.

Möglicherweise wäre eine Schleife einfacher.

HighLigerBiMBam

Ist das die Antwort deines Problems?

#include <iostream> 
#include <string>
#include <map>

using namespace std; 

int main() 
{
	map<string, int > stlmap;
	pair<string, int> paar;

	paar = make_pair("test1",15);
	stlmap.insert(paar);
	paar = make_pair("test2",10);
	stlmap.insert(paar);
	paar = make_pair("test3",7);
	stlmap.insert(paar);
	paar = make_pair("test4",5);
	stlmap.insert(paar);
	paar = make_pair("test5",8);
	stlmap.insert(paar);

	int minwert = 50;
	string minkey;
	for(map<string,int>::iterator i = stlmap.begin(); i != stlmap.end(); ++i){
		if ( (*i).second < minwert){
			minwert = (*i).second;
			minkey = (*i).first;
		}
	}

	cout << "minwert: " << minwert << endl;
	cout << "minkey : " << minkey << endl;

	cin.get();
    return 0; 
}

Hallo!
Mit HighLigerBiMBam' Hilfe habe ich es wohl hinbekommen. Danke! Mir bleiben aber noch ein paar Fragen, weil das Zeugs ja auch verstehen möchte. Könnt ihr mich bitte korrigieren, wenn etwas nicht stimmt:

Du deklarierst einen Iterator, den du an den Anfang der map stellst und der bis zum letzten Element durchsaust. Ich verstehe noch nicht so ganz, was "first" und was "second" macht. Wenn irgendein Wert kleiner als "minval" ist, dann bekommt minval diesen Wert zugewiesen und minkey den dazugehörigen Key.

Greife ich mit "first" auf den Key zu und mit "second" auf das entsprechende value zu? Irgendwie finde ich in der Referenz nicht die richtige Stelle.

Vielen Dank

freakC++

Guten Morgen!

Ich lese mit Interesse diesen Thread. Ich habe jetzt auch eine Frage. Sollte man "minval" nicht lieber mit "INT_MAX" initialisieren, denn ich frage mich, ob das Prinzip auch funktionieren würde, wenn das Array Werte enthält die größer als 50 sind?

Viele Grüße
freakC++

SeppJ

map schrieb:

Du deklarierst einen Iterator, den du an den Anfang der map stellst und der bis zum letzten Element durchsaust. Ich verstehe noch nicht so ganz, was "first" und was "second" macht. Wenn irgendein Wert kleiner als "minval" ist, dann bekommt minval diesen Wert zugewiesen und minkey den dazugehörigen Key.

Greife ich mit "first" auf den Key zu und mit "second" auf das entsprechende value zu? Irgendwie finde ich in der Referenz nicht die richtige Stelle.

Vielen Dank

Du vermutest richtig:
http://www.cplusplus.com/reference/stl/map/ In dem Link steht, dass die Map die Werte in einem sogenannten pair speichert:
http://www.cplusplus.com/reference/std/utility/pair/
first und second sind, wie der Name schon sagt, der erste und der zweite Teil des Pairs, der key und der value.

freakC++ schrieb:

Ich lese mit Interesse diesen Thread. Ich habe jetzt auch eine Frage. Sollte man "minval" nicht lieber mit "INT_MAX" initialisieren, denn ich frage mich, ob das Prinzip auch funktionieren würde, wenn das Array Werte enthält die größer als 50 sind?

Ja. Oder besser noch mit numeric_limits<int>::max() . Oder mit dem ersten gefundenen Wert. Ich vermute mal, dass HighLigerBiMBam dies nicht gemacht hat, um den Nutzer map nicht auch noch mit numeric_limits zu verwirren.

SeppJ

Der Vollständigkeit halber, so geht das mit min_element:

#include <iostream>
#include <string>
#include <map>
#include <algorithm>

using namespace std;

bool compare_second(pair<string, int> lhs, pair<string, int> rhs)
{
  return lhs.second < rhs.second;
}

int main()
{
    map<string, int > stlmap;
    stlmap.insert(make_pair("test1",15));
    stlmap.insert(make_pair("test2",10));
    stlmap.insert(make_pair("test3",7));
    stlmap.insert(make_pair("test4",5));
    stlmap.insert(make_pair("test5",8));

    map<string, int >::iterator minimum = min_element(stlmap.begin(), stlmap.end(), compare_second);

    cout << "minwert: " << minimum->second << endl;
    cout << "minkey : " << minimum->first << endl;

    return 0;
}

Auch nicht so schwer, oder?

HighLigerBiMBam

SeppJ schrieb:

Ich vermute mal, dass HighLigerBiMBam dies nicht gemacht hat, um den Nutzer map nicht auch noch mit numeric_limits zu verwirren.

Wenn es offensichtlich ist, dass der Fragesteller sich mit der Materie nicht auskennt, sollte man immer zu den einfachen Beispielen greifen. KISS ist immer das Beste um ein Problem zu erklären, auch wenn es nicht die schönste Lösung ist, welche uns von SeppJ nun bereit gestellt wurde!

Letztlich kann jeder die einfachen Beispiele verstehen und weiter optimieren.