Как я могу найти минимальное значение в карте?
У меня есть a map и я хочу найти минимальное значение (правая сторона) в карте. Вот то, как я сделал это:
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;
Код выше хорошо работает, и я могу получить минимальное значение. Однако, когда я поместил этот код в своем классе следующим образом, это, кажется, не работает:
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;
}
Как я могу заставить код работать с моим классом? Кроме того, есть ли лучшее решение, которое не требует записи дополнительного compare функция?
3 ответа
У вас есть несколько вариантов. «Лучший» способ сделать это - использовать функтор , он гарантированно будет самым быстрым для вызова:
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;
}
(Вы также можете вложить класс CompareSecond внутрь MyClass .
Имея код, который у вас есть сейчас, вы можете легко изменить его для работы. Просто сделайте функцию статической и используйте правильный синтаксис:
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;
}
У меня действительно есть другой вопрос: если вам нужно регулярно получать минимум правых значений, уверены ли вы, что карта ] является лучшей структурой?
Я бы предложил использовать Boost.MultiIndex в целом для решения этих проблем, связанных с несколькими способами индексирования одного и того же набора объектов ... но если вам нужно только это "обратное отображение" "бит Boost.Bimap может оказаться проще.
Таким образом, у вас не будет линейного поиска при поиске минимума :)
Проблема в том, что это:
bool MyClass::compare
Требует вызова экземпляра класса. То есть вы не можете просто вызвать MyClass :: compare , но вам понадобится someInstance.compare . Однако min_element нуждается в первом.
Простое решение - сделать его статическим :
static bool MyClass::compare
// ...
min_element(mymap.begin(), mymap.end(), &MyClass::compare);
Это больше не требует вызова экземпляра, и ваш код будет в порядке. Тем не менее, вы можете сделать его более общим с помощью функтора:
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());
Все, что он делает, это захватывает второй из каждой пары и захватывает их, работает с любой парой. Это можно было сделать для общего пользования, но это многовато.
Если вам нужно достаточно много искать по значению, я рекомендую вам использовать Boost Bimap . Это двунаправленная карта, поэтому для поиска можно использовать как ключ, так и значение. Вы просто получите начало карты значений ключей.
Наконец, вы всегда можете просто отслеживать минимальный элемент на вашей карте. Каждый раз, когда вы вставляете новое значение, проверяйте, не ниже ли оно вашего текущего значения (и это, вероятно, должно быть указателем на пару карт, начните с нуля), и если оно ниже, укажите на новое самое низкое значение. Запрос самого низкого уровня становится таким же простым, как разыменование указателя.