Trouver la valeur minimale dans une carte

Question

J'ai une carte et je veux trouver la valeur minimum (côté droit) sur la carte. En ce moment, 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 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; 
} 

Il existe également une meilleure solution n'impliquant pas l'écriture de la fonction supplémentaire compare

Answer 1

Vous avez quelques options. La « meilleure » façon de le faire est avec un foncteur, cela est garanti d'être le plus rapide d'appeler:

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 la classe CompareSecond dans MyClass

Avec le code. vous avez maintenant, vous pouvez facilement modifier pour travailler, mais juste faire fonctionner static et utilisez la syntaxe correcte.

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

Answer 2

le problème est que ceci:

bool MyClass::compare 

Nécessite une instance de la classe à appeler. Autrement dit, vous ne pouvez pas simplement appeler MyClass::compare, mais vous avez besoin de . Cependant, min_element a besoin de l'ancien.

La solution facile est de faire static:

static bool MyClass::compare 

// ... 

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

Cela exige non plus une instance d'être appelé sur, et votre code sera bien. Vous pouvez le rendre plus général avec un foncteur, cependant:

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

Tout cela ne fait saisir la seconde de chaque paire et les attraper, fonctionne avec toute paire. Cela pourrait être fait pour le général, mais c'est un peu trop.

Si vous avez besoin de rechercher suffisamment de valeur, je vous recommande d'utiliser Bimap de Boost. C'est une carte bidirectionnelle, donc la clé et la valeur peuvent être utilisées pour la recherche. Vous obtiendriez simplement le recto de la carte de valeur-clé. Enfin, vous pouvez toujours garder une trace de l'élément minimum entrant dans votre carte. Chaque fois que vous insérez une nouvelle valeur, vérifiez si elle est inférieure à votre valeur actuelle (et cela devrait être probablement un pointeur vers une paire de cartes, démarrez-la comme nulle), et si elle est inférieure, pointez sur la nouvelle plus basse. Demander le plus bas devient aussi simple que de déréférencer un pointeur.

Answer 3

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

Je suggère d'utiliser 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 seulement besoin de ce "reverse-mapping" bit Boost.Bimap pourrait s'avérer plus facile.

De cette façon, vous ne serez pas une recherche linéaire lorsque vous cherchez le minimum :)

Answer 4

En C++ 11 vous pouvez le faire:

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 une belle fonction comme cette (notez que je ne suis pas un gourou de modèle, ce qui est probablement mal à bien des égards):

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