Encontrar el valor mínimo en un mapa

Question

Tengo un mapa y quiero encontrar el valor mínimo (lado derecho) en el mapa. Ahora aquí es cómo lo hice

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; 

Esto funciona bien y yo soy capaz de obtener el valor mínimo el problema es cuando pongo este código dentro de mi clase no parece trabajar

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

también hay una mejor solución que no implique a escribir la función adicional compare

Answer 1

Usted tiene algunas opciones. El "mejor" forma de hacerlo es con un funtor, esto se garantiza que sea la más rápida de llamar:

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

(También puede anidar la clase CompareSecond dentro MyClass

Con el código. que tiene ahora, se puede modificar fácilmente para trabajar, sin embargo, sólo hacer que la función static y utilizar la sintaxis correcta:.

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

el problema es que esto:

bool MyClass::compare 

Requiere una instancia de la clase a la que se debe llamar. Es decir, no puede simplemente llamar al MyClass::compare, pero necesita someInstance.compare. Sin embargo, min_element necesita lo primero.

La solución fácil es hacer que sea static:

static bool MyClass::compare 

// ... 

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

Esto ya no requiere una instancia a ser llamado, y su código va a estar bien. Puede que fuera más general con un funtor, sin embargo:

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

Todo esto hace es agarrar el segundo de cada par y apoderarse de ellos, funciona con cualquier par. Podría hacerse para general, pero eso es demasiado.

Si necesita buscar por valor suficiente, le recomiendo que use Boost Bimap. Es un mapa bidireccional, por lo que tanto la clave como el valor se pueden usar para buscar. Simplemente obtendría el frente del mapa de la clave de valor.

Por último, siempre puede hacer un seguimiento del elemento mínimo yendo a su mapa. Cada vez que inserte un nuevo valor, verifique si es menor que su valor actual (y que probablemente sea un puntero a un par de mapas, comience como nulo) y, si es menor, apunte al nuevo más bajo. Solicitar lo más bajo se vuelve tan simple como desreferenciar un puntero.

Answer 3

De hecho, tengo otra pregunta: si necesita obtener regularmente el mínimo de los valores del lado derecho, ¿está seguro de que map es la mejor estructura?

Sugeriría usar Boost.MultiIndex en general para estos problemas de múltiples formas de indexar el mismo conjunto de objetos ... pero si solo necesita este bit "reverse-mapping" Boost.Bimap podría ser más fácil.

De esta manera usted no tendrá una búsqueda lineal cuando se busca el mínimo :)

Answer 4

En C++ 11 se puede hacer esto:

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

o ponerlo en una bonita función como (observe que no soy un gurú de la plantilla, lo que es probablemente equivocado en muchos sentidos):

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