Как я могу найти минимальное значение на карте?

Question

У меня есть 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?

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

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

Answer 3

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

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

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

Answer 4

Проблема в том, что это:

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

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

Answer 5

C ++ 14

Как уже упоминалось в Комментарий Джонатана Гейслера Ответ Тимммма , C ++ 14 позволяет лямбдаПараметры функции должны быть объявлены с помощью спецификатора типа auto.В результате вы можете укоротить строку min_element на основе лямбды Тиммма (и улучшить ее читабельность) следующим образом:

auto it = std::min_element(std::begin(mymap), std::end(mymap),
                           [](const auto& l, const auto& r) { return l.second < r.second; });

Примечание 1: Если вы поместите эту строку в свой MyClass::getMin() функция, вы должны вернуть it->second.Однако, чтобы учесть пустую карту, вы должны адаптировать строку return следующим образом (или аналогично):

return it == mymap.end() ? -1 : it->second;

Примечание 2. Как также упоминается Лэнс Дидук , выдолжен передавать карту по const ссылке на вашу функцию getMin().Таким образом, вы создаете ненужную копию всей карты.

Код на Ideone