如何找到地图中的最小值？

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

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

---

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

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

Answer 2

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

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

Answer 3

C++14

正如 Jonathan Geisler 的评论中提到的 蒂姆的回答，C++14 允许 lambda 函数 参数使用 auto 类型说明符进行声明。因此，您可以缩短 Timmmm 基于 lambda 的 min_element< /a> 行（并提高其可读性）如下：

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：正如 Lance Diduck，您应该通过 const 传递地图引用您的 getMin() 函数。按照您的方式，您正在创建整个地图的不必要的副本。

Ideone 上的代码

Answer 4

问题在于：

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。它是一个双向映射，因此键和值都可以用于查找。您只需获取值键映射的前面即可。

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

Answer 5

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

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

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