Trouver la valeur minimale dans une Carte

J'ai une carte et je veux trouver la valeur minimale (à droite) dans la carte. Droit maintenant, voici comment je l'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;

Cela fonctionne bien et je suis en mesure d'obtenir la valeur minimale le problème est que quand je mets ce code dans ma classe, 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; 
}

Aussi est-il une meilleure solution n'impliquant 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é.

OriginalL'auteur Sunny | 2010-04-17

c++map stl

11

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...

OriginalL'auteur rlbond

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

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.

OriginalL'auteur Timmmm

2

Le problème est que cela:
```
bool MyClass::compare
```
Nécessite une instance de la classe. 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:
```
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.

OriginalL'auteur GManNickG
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.

OriginalL'auteur Matthieu M.

Vous devez vous connecter pour publier un commentaire.