Comment puis-je trouver la valeur minimale dans une carte?

J'ai un map et je veux trouver la valeur minimale (à droite) dans la carte. Voici comment j'ai fait:

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;

Le code ci-dessus fonctionne bien et je suis en mesure d'obtenir la valeur minimale. Cependant, quand je mets ce code à l'intérieur de ma classe comme suit, il ne semble pas fonctionner:

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; 
}

Comment puis-je rendre le code du travail avec les élèves de ma classe? Aussi, est-il une meilleure solution qui ne nécessite pas l'écriture supplémentaires compare fonction?

  • Le getMin fonction doit être en train de passer l'argument par référence const, et non par valeur. Aussi, vous aurez un problème lorsque la carte n'a pas d'éléments à tous, donc envisager de ne pas dereferecing l'itérateur avant makig sûr end() n'a pas été retourné.
InformationsquelleAutor Sunny | 2010-04-17
  1. 14

    Vous avez un peu d'options. La "meilleure" façon de le faire est avec un foncteur, c'est la garantie d'être le plus rapide à l'appel:

    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; 
}

    (Vous pouvez également imbriquer les CompareSecond classe à l'intérieur de MyClass.

    Avec le code que vous avez maintenant, vous pouvez facilement la modifier pour fonctionner, cependant. Juste faire de la fonction static et d'utiliser la bonne syntaxe:

    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; 
}
    • J'ai touché le bouton format pour vous. Vous devez spécifier les arguments de modèle pour le foncteur ou de passer un inutilisés argument d'une usine. Ou le modèle de la operator() au lieu de l'ensemble de la classe... c'est le meilleur moyen, ouais :vP .
    • Je suis d'accord, operator() devrait être basée sur des modèles de meilleures pratiques. Cependant, je pense que le code devrait illustrer ce point. Qu'entendez-vous par "spécifier les arguments de modèle"? Entendez-vous tirer de binary_function? Je ne crois pas que c'est nécessaire pour min_element...
    InformationsquelleAutor rlbond
  2. 13

    En C++11, vous pouvez faire ceci:

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

    Ou le mettre dans un joli fonction comme ceci (notez que je ne suis pas un modèle guru; c'est probablement faux, dans de nombreux moyens):

    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; });
}

    Avec C++14, il simplifie à:

    min_element(pairs.begin(), pairs.end(),
            [](const auto& l, const auto& r) { return l.second < r.second; });
    • J'ai fait mon lambda plus succient en utilisant simplement auto pour les types de paramètres l et r. Que peut exiger le C++14, cependant.
    InformationsquelleAutor Timmmm
  3. 2

    Le problème est que cela:

    bool MyClass::compare

    Requiert une instance de la classe à être appelé. Qui est, vous ne pouvez pas simplement appeler MyClass::compare, mais vous avez besoin someInstance.compare. Cependant, min_element besoins de l'ancien.

    La solution facile est de le faire static:

    static bool MyClass::compare

//...

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

    Cela ne nécessite plus une instance d'être appelée, et votre code sera bien. Vous pouvez la rendre plus générale avec un foncteur, si:

    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());

    De tout cela, c'est prendre la deuxième à partir de chaque paire et de les attraper, fonctionne avec n'importe quelle paire. Il pouvait être fait pour le général, mais c'est un peu trop.

    Si vous avez besoin de regarder par la valeur assez, je vous recommande d'utiliser l'amplification du Bimap. C'est un bi-directionnelle de la carte, donc à la fois la clé et la valeur peut être utilisé pour la recherche. Vous pouvez tout simplement obtenir le devant de la valeur-clé de la carte.

    Enfin, vous pouvez toujours garder une trace de l'élément minimum d'aller dans votre carte. Chaque fois que vous insérez une nouvelle valeur, vérifier si elle est inférieure à celle de votre valeur actuelle (et qui doit être sans doute être un pointeur sur une carte paire, de la lancer, null), et si c'est inférieur, point de nouveaux plus bas. Demande le plus faible devient aussi simple qu'un déréférencement d'un pointeur.

    InformationsquelleAutor GManNickG
  4. 2

    En fait, j'ai une autre question: si vous avez besoin d'obtenir régulièrement le minimum de la droite des valeurs êtes-vous sûr qu'un map est la meilleure structure ?

    Je conseille Boost.MultiIndex en général pour ces problèmes de multiples façons d'indexer le même ensemble d'objets... mais si vous avez uniquement besoin de cette "reverse-mapping" peu Boost.Bimap pourrait s'avérer plus facile.

    De cette façon, vous n'aurez pas un linéaire de recherche lors de la recherche pour le minimum 🙂

    • Je suppose qu'il n'existe toujours pas strictement les normes béni conteneur pour cela si je suis souvent de me trouver en essayant d'obtenir les valeurs max/min d'une carte?
    • Non, il n'est pas. La Norme fournit seulement les structures les plus communes, et aucun support double indexation. Coup de pouce.MultiIndex et Boost.Bimap sont assez stables (depuis des années), ou que vous avez à faire vous-même.
    InformationsquelleAutor Matthieu M.
  5. 0

    C++14

    Comme mentionné dans Jonathan Geisler du commentaire sur Timmmm réponse, C++14 permet fonction lambda paramètres à être déclarée avec le auto spécificateur de type. Comme un résultat, vous pouvez raccourcir Timmmm du lambda-fondé min_element ligne (et en améliorer la lisibilité) comme suit:

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

    Note 1: Si vous ajoutez cette ligne dans votre MyClass::getMin() fonction, vous devez retourner it->second. Toutefois, pour tenir compte d'une carte vide, vous devez adapter la return ligne comme suit (ou similaire):

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

    Remarque 2: Comme l'a également mentionné Lance Diduck, vous devriez être en train de passer la carte en const référence à votre getMin() fonction. La façon dont vous l'avez fait, vous êtes la création d'un inutile copie de l'ensemble de la carte.

    Code sur Ideone

    InformationsquelleAutor honk