C++ 如何在地图中找到最小值？

How can I find the minimum value in a map?

提问by Sunny

I have a mapand I want to find the minimum value (right-hand side) in the map. Here is how I did it:

我有一个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;

The code above works fine and I'm able to get the minimum value. However, when I put this code inside my class as follows, it doesn't seem to work:

上面的代码工作正常，我能够得到最小值。但是，当我将此代码放入我的类中时，它似乎不起作用：

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

How can I make the code work with my class? Also, is there a better solution which doesn't require writing the additional comparefunction?

我怎样才能使代码与我的班级一起工作？另外，是否有更好的解决方案不需要编写附加compare功能？

采纳答案by rlbond

You have a few options. The "best" way to do this is with a functor, this is guaranteed to be the fastest to call:

你有几个选择。做到这一点的“最佳”方法是使用functor，这保证是最快的调用：

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

(You can also nest the CompareSecondclass inside MyClass.

（您也可以将CompareSecond类嵌套在MyClass.

With the code you have now, you can easily modify it to work, however. Just make the function staticand use the correct syntax:

但是，使用您现在拥有的代码，您可以轻松修改它以使其正常工作。只需创建函数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; 
}

回答by Timmmm

In C++11 you can do this:

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

Or put it in a nice function like this (note I'm not a template guru; this is probably wrong in many ways):

或者把它放在这样一个不错的函数中（注意我不是模板专家；这在很多方面可能是错误的）：

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

---

---

With C++14, it further simplifies to:

使用 C++14，它进一步简化为：

min_element(pairs.begin(), pairs.end(),
            [](const auto& l, const auto& r) { return l.second < r.second; });

回答by GManNickG

The problem is that this:

问题在于：

bool MyClass::compare

Requires an instance of the class to be called on. That is, you can't just call MyClass::compare, but you need someInstance.compare. However, min_elementneeds the former.

需要调用类的实例。也就是说，你不能只调用MyClass::compare，但你需要someInstance.compare. 但是，min_element需要前者。

The easy solution is to make it static:

简单的解决方案是static：

static bool MyClass::compare

// ...

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

This no longer requires an instance to be called on, and your code will be fine. You can make it more general with a functor, though:

这不再需要调用实例，您的代码就可以了。不过，您可以使用函子使其更通用：

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

All this does is grab the second from each pair and grab them, works with any pair. It could be made for general, but that's a bit too much.

所有这一切都是从每对中抓住第二个并抓住它们，适用于任何一对。它可以用于一般用途，但这有点太多了。

If you need to look up by value enough, I recommend you use Boost's Bimap. It's a bi-directional map, so both the key and value can be used to lookup. You would simply get the front of the value-key map.

如果您需要足够多地按值查找，我建议您使用 Boost 的Bimap。这是一个双向映射，因此键和值都可以用于查找。您只需获得值键映射的前面即可。

Lastly, you can always just keep track of the minimum element going into your map. Every time you insert a new value, check if it's lower than your current value (and that should be probably be a pointer to a map pair, start it as null), and if it's lower, point to the new lowest. Requesting the lowest becomes as simple as dereferencing a pointer.

最后，您始终可以跟踪进入地图的最小元素。每次插入新值时，请检查它是否低于当前值（这可能应该是指向映射对的指针，将其作为空值开始），如果较低，则指向新的最低值。请求最低的就像取消引用一个指针一样简单。

回答by Matthieu M.

I actually have another question: if you need to regularly obtain the minimum of the right-hand side values are you sure than a mapis the best structure ?

我实际上还有另一个问题：如果您需要定期获得右侧值的最小值，您确定 amap是最佳结构吗？

I would suggest using Boost.MultiIndexin general for these problems of multiple ways of indexing the same set of objects... but if you only need this "reverse-mapping" bit Boost.Bimapmight prove easier.

我建议Boost.MultiIndex一般使用多种方法来解决这些问题，以索引同一组对象……但如果您只需要这个“反向映射”位Boost.Bimap可能会更容易。

This way you won't have a linear search when looking for the minimum :)

这样你在寻找最小值时不会有线性搜索:)

回答by honk

C++14

C++14

As mentioned in Jonathan Geisler'scomment on Timmmm's answer, C++14allows lambda functionparameters to be declared with the autotype specifier. As a result, you can shorten Timmmm's lambda-based min_elementline (and improve its readability) as follows:

正如乔纳森·盖斯勒 (Jonathan Geisler)对Timmmm 回答的评论中所述，C++14允许使用类型说明符声明lambda 函数参数auto。因此，您可以min_element按如下方式缩短 Timmmm 的基于 lambda 的行（并提高其可读性）：

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

Note 1: If you put this line into your MyClass::getMin()function, you have to return it->second. However, to account for an empty map, you should adapt the returnline as follows (or similar):

注意 1：如果将此行放入MyClass::getMin()函数中，则必须 return it->second。但是，为了说明空地图，您应该return按如下方式（或类似方式）调整该行：

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

Note 2: As also mentioned by Lance Diduck, you should be passing the map by constreference to your getMin()function. The way you did it, you are creating an unnecessary copy of the whole map.

注意 2：正如Lance Diduck所提到的，您应该通过const引用您的getMin()函数来传递地图。您这样做的方式是创建整个地图的不必要副本。

Code on Ideone

Ideone 上的代码