Найти минимальное значение на карте

Question

У меня есть карта, и я хочу найти минимальное значение (правую сторону) на карте. Сейчас вот как я это сделал

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 функции

Answer 1

У вас есть несколько вариантов. «Лучший» способ сделать это с функтора, это гарантированно будет самым быстрым назвать:

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 и использовать правильный синтаксис:.

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

проблема заключается в том, что это:

bool MyClass::compare 

Требуется экземпляр класса, подлежащего вызову. То есть вы не можете просто позвонить MyClass::compare, но вам нужно someInstance.compare. Однако min_element нуждается в первом.

Простое решение не сделать его static:

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's Bimap. Это двунаправленная карта, поэтому и ключ, и значение могут использоваться для поиска. Вы просто получили бы карту карты значений.

Наконец, вы всегда можете просто отслеживать минимальный элемент, входящий в вашу карту. Каждый раз, когда вы вставляете новое значение, проверьте, меньше ли оно вашего текущего значения (и это должно быть, вероятно, указателем на пару карт, запустите его как null), а если оно ниже, укажите на новый минимум. Запрос самого низкого значения становится таким же простым, как разыменование указателя.

Answer 3

У меня на самом деле есть другой вопрос: если вам нужно регулярно получать минимальные значения правой стороны, вы уверены, что map - лучшая структура?

Я бы предложил использовать Boost.MultiIndex в целом для этих проблем с несколькими способами индексирования одного и того же набора объектов ... но если вам нужно только это «обратное отображение», бит Boost.Bimap может оказаться проще.

Таким образом, вы не будете иметь линейный поиск при поиске минимума :)

Answer 4

В C++ 11 вы можете сделать это:

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

Или поставить его в хорошей функции, как (обратите внимание, что я не шаблон гуру, это, вероятно, неправильно во многих отношениях):

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