Wie finde ich den kleinsten Wert in einer map?

Ich habe eine map und ich möchten, finden Sie den minimalen Wert (rechts) in der Karte. Hier ist, wie ich es gemacht habe:

bool compare(std::pair<std::string ,int> i, pair<std::string, int> j) {
  return i.second < j.second;
}
////////////////////////////////////////////////////
std::map<std::string, int> mymap;

mymap["key1"] = 50;
mymap["key2"] = 20;
mymap["key3"] = 100;

std::pair<char, int> min = *min_element(mymap.begin(), mymap.end(), compare); 
std::cout << "min " << min.second<< " " << std::endl;

Den code oben funktioniert einwandfrei und ich bin in der Lage, um den minimalen Wert. Allerdings, wenn ich diesen code in meine Klasse wie folgt, es scheint nicht zu funktionieren:

int MyClass::getMin(std::map<std::string, int> mymap) {
  std::pair<std::string, int> min = *min_element(mymap.begin(), mymap.end(), 
                                                 (*this).compare);
                                                 //Error probably due to "this".
  return min.second; 
}

bool MyClass::compare(
    std::pair<std::string, int> i, std::pair<std::string, int> j) { 
  return i.second < j.second; 
}

Wie kann ich den code mit meiner Klasse? Außerdem gibt es eine bessere Lösung, die nicht bedürfen der Schriftform die weitere compare Funktion?

  • Die Funktion getMin sollte vorbei das argument mit der const-Referenz und nicht als Wert. Auch Sie haben ein problem, wenn die Karte hat keine Elemente überhaupt, so denken Sie daran, nicht dereferecing der iterator vor makig sicher, dass end() zurückgegeben wird.
InformationsquelleAutor Sunny | 2010-04-17
  1. 14

    Haben Sie ein paar Optionen. Der "beste" Weg, dies zu tun ist mit einem Funktor, das ist garantiert der Schnellste zu sein, zu rufen:

    typedef std::pair<std::string, int> MyPairType;
struct CompareSecond
{
    bool operator()(const MyPairType& left, const MyPairType& right) const
    {
        return left.second < right.second;
    }
};



int MyClass::getMin(std::map<std::string, int> mymap) 
{
  std::pair<std::string, int> min 
      = *min_element(mymap.begin(), mymap.end(), CompareSecond());
  return min.second; 
}

    (Sie können auch nest die CompareSecond Klasse in MyClass.

    Mit dem code, den Sie jetzt haben, können Sie leicht ändern Sie es zu arbeiten, jedoch. Stellen Sie einfach die Funktion static und die richtige syntax verwenden:

    static bool 
MyClass::compare(std::pair<std::string, int> i, std::pair<std::string, int> j) 
{ 
  return i.second < j.second; 
}

int MyClass::getMin(std::map<std::string, int> mymap) 
{
  std::pair<std::string, int> min = *min_element(mymap.begin(), mymap.end(), 
                                                 &MyClass::compare);
  return min.second; 
}
    • Ich traf die Schaltfläche format für Sie. Müssen Sie die template-Argumente des funktors, oder übergeben Sie eine nicht verwendete argument, um eine Fabrik. Oder die Vorlage, die operator() statt für die gesamte Klasse... das ist der beste Weg, yeah :vP .
    • Ich bin damit einverstanden, operator() werden sollte, vorgefertigte best practice. Aber ich denke, der code soll veranschaulichen den Punkt. Was meinst du mit "geben Sie die template-Argumente"? Meinst du ableiten von binary_function? Ich glaube nicht, dass es erforderlich ist min_element...
    InformationsquelleAutor rlbond
  2. 13

    In C++11 können Sie dies tun:

    auto it = min_element(pairs.begin(), pairs.end(),
                      [](decltype(pairs)::value_type& l, decltype(pairs)::value_type& r) -> bool { return l.second < r.second; });

    Oder legen Sie es in eine nette Funktion wie folgt aus (beachten Sie, ich bin nicht eine Vorlage guru; dies ist wohl falsch in vielerlei Hinsicht):

    template<typename T>
typename T::iterator min_map_element(T& m)
{
    return min_element(m.begin(), m.end(), [](typename T::value_type& l, typename T::value_type& r) -> bool { return l.second < r.second; });
}

    Mit C++14, weiter vereinfacht zu:

    min_element(pairs.begin(), pairs.end(),
            [](const auto& l, const auto& r) { return l.second < r.second; });
    • Ich habe meine lambda-mehr succient, die nur mit auto für die parameter-Typen l und r. Das erfordert C++14, jedoch.
    InformationsquelleAutor Timmmm
  3. 2

    Das problem ist, dass diese:

    bool MyClass::compare

    Erfordert eine Instanz der Klasse aufgerufen werden. Das heißt, Sie können nicht einfach anrufen MyClass::compare, aber Sie müssen someInstance.compare. Allerdings min_element muss der ehemalige.

    Die einfache Lösung ist, um es static:

    static bool MyClass::compare

//...

min_element(mymap.begin(), mymap.end(), &MyClass::compare);

    Dies ist nicht mehr erforderlich, eine Instanz aufgerufen werden, und Ihr code wird in Ordnung sein. Sie können machen es die mehr der Regel mit einem Funktor, wenn:

    struct compare2nd
{
    template <typename T>
    bool operator()(const T& pLhs, const T& pRhs)
    {
        return pLhs.second < pRhs.second;
    }
};

min_element(mymap.begin(), mymap.end(), compare2nd());

    All dies tut, ist schnappen Sie sich den zweiten von jedem paar und Sie greifen, funktioniert mit jedem paar. Es könnte gemacht werden für Allgemeine, aber das ist ein bisschen zu viel.

    Wenn Sie nachschlagen müssen Wert genug ist, empfehle ich Euch die Verwendung von Boost ist Bimap. Es ist eine bi-direktionale anzeigen, also beide den Schlüssel und den Wert kann verwendet werden, um nachschlagen. Einfach die front der value-Taste anzeigen.

    Schließlich können Sie immer verfolgen Sie die minimalen Elemente in Ihre Karte. Jedes mal, wenn Sie legen Sie einen neuen Wert ein, prüfen Sie, ob es niedriger ist als Ihr Aktueller Wert (und das sollte wahrscheinlich ein Zeiger auf einen map-pair-Mädchen, starten Sie es als null), und wenn es niedriger ist, zeigen Sie auf die neue niedrigste. Die Beantragung der niedrigsten wird so einfach wie das dereferenzieren eines Zeigers.

    InformationsquelleAutor GManNickG
  4. 2

    Ich habe eigentlich eine andere Frage: wenn Sie regelmäßig erhalten, ist das minimum der rechten Seite Werte, sind Sie sicher, dass als ein map ist die beste Struktur ?

    Ich würde vorschlagen, mit Boost.MultiIndex im Allgemeinen für diese Probleme von mehreren Möglichkeiten der Indexierung den gleichen Satz von Objekten... aber wenn Sie müssen nur dieses "reverse-mapping" bit Boost.Bimap könnte sich als einfacher erweisen.

    Diese Weise werden Sie nicht haben eine lineare Suche das minimum 🙂

    • Ich nehme an, es ist noch kein streng standards-gesegnet container für wenn ich bin Häufig da ich mich zu versuchen, um die max/min-Werte von einer Karte?
    • Nein, es ist nicht. Der Standard stellt nur die häufigsten Strukturen, und keine Unterstützungs-Doppel-Indizierung. Boost.MultiIndex und zu Steigern.Bimap sind ziemlich stabil (seit Jahren), oder Sie müssen tun Sie es selbst.
    InformationsquelleAutor Matthieu M.
  5. 0

    C++14

    Wie bereits in Jonathan Geisler ' s Kommentar auf Timmmm Antwort, C++14 ermöglicht lambda-Funktion Parameter deklariert werden, mit der auto Typ Bezeichner. Als Ergebnis, können Sie verkürzen Timmmm ist die lambda-basierte min_element Linie (und zur Verbesserung seiner Lesbarkeit) wie folgt:

    auto it = std::min_element(std::begin(mymap), std::end(mymap),
                           [](const auto& l, const auto& r) { return l.second < r.second; });

    Hinweis 1: Wenn Sie diese Zeile in Ihre MyClass::getMin() Funktion, Sie müssen zurück it->second. Jedoch, zu berücksichtigen, für eine leere Karte, die Sie anpassen sollten, die return Zeile wie folgt (oder ähnlich):

    return it == mymap.end() ? -1 : it->second;

    Hinweis 2: Wie auch erwähnt Lance Diduck, sollten Sie die übergabe der Karte durch const Verweis auf Ihre getMin() Funktion. Die Art und Weise Sie es getan haben, erstellen Sie eine unnötige Kopie der gesamten Karte.

    Code auf Ideone

    InformationsquelleAutor honk
Schreibe einen Kommentar