在地图中寻找最大值

Question

我一直在编写一个简单的程序，用于查找向量的最大值、最小值、中位数、方差、众数等。一切都顺利进行，直到我遇到了众数。

我认为，我应该能够循环遍历向量，并对每个出现的数字递增地设置地图上的键值。找到具有最高值的键将是出现最多次的键。与其他键进行比较将告诉我它是单个多重还是没有模式答案。

这里是导致我困扰已久的代码块。

map<int,unsigned> frequencyCount;
// This is my attempt to increment the values
// of the map everytime one of the same numebers 
for(size_t i = 0; i < v.size(); ++i)
    frequencyCount[v[i]]++;

unsigned currentMax = 0;
unsigned checked = 0;
unsigned maax = 0;
for(auto it = frequencyCount.cbegin(); it != frequencyCount.cend(); ++it )
    //checked = it->second;
    if (it ->second > currentMax)
    {
        maax = it->first;
    }
    //if(it ->second > currentMax){
    //v = it->first

cout << " The highest value within the map is: " << maax << endl;

整个程序可以在这里查看。http://pastebin.com/MzPENmHp

- Sh0gun

Answer 1

您可以使用std::max_element来查找最高的映射值（以下代码需要 C++11）：

std::map<int, size_t> frequencyCount;
using pair_type = decltype(frequencyCount)::value_type;

for (auto i : v)
    frequencyCount[i]++;

auto pr = std::max_element
(
    std::begin(frequencyCount), std::end(frequencyCount),
    [] (const pair_type & p1, const pair_type & p2) {
        return p1.second < p2.second;
    }
);
std::cout << "A mode of the vector: " << pr->first << '\n';

- Robᵩ

---

请返回翻译后的文本：http://en.wikipedia.org/wiki/C%2B%2B11#Lambda_functions_and_expressions http://en.wikipedia.org/wiki/Anonymous_function#C.2B.2B_.28since_C.2B.2B11.29 - Robᵩ

pair<..> 中的 int 不应该是 const 的吗，也就是说应该是 pair<const int, unsigned> 吗？ - thomasa88

@thomasa88 是的，应该这样做，这将节省许多不必要的转换时间。顺便说一句，如果有C++14可用，只需使用auto即可。 - Humam Helfawi

@HumamHelfawi auto 在 C++11 中已经存在，特别是用于上面的代码，但不适用于 map，因为你显然不能在没有 rvalue 的情况下推断出类型。此外，是否有任何记录这种“很多不必要的转换时间”的来源？ - underscore_d

auto在C++11中作为lambda变量被引入，但它是C++14的一部分。请参见此处：https://dev59.com/No_ea4cB1Zd3GeqPLj2E 关于类型转换时间，请参见此处的已接受答案：https://dev59.com/g1wY5IYBdhLWcg3wh4Pc - Humam Helfawi

Answer 2

只需几行代码即可完成，以下是完整的可用代码示例：

#include <iostream>
#include <algorithm>
#include <map>
int main() {
    std::map<char,int> x = { { 'a',1 },{ 'b',2 },{'c',0} };
    std::map<char,int>::iterator best
        = std::max_element(x.begin(),x.end(),[] (const std::pair<char,int>& a, const std::pair<char,int>& b)->bool{ return a.second < b.second; } );
    std::cout << best->first << " , " << best->second << "\n";
}

- Janek_Kozicki

---

为什么每个人都使用std::而不是using namespace？ - user55924

避免命名空间污染。在大型项目中，污染可能会成为真正的障碍。甚至由于链接器混淆来自不同命名空间的相同类名而导致崩溃：https://gitlab.com/yade-dev/trunk/-/issues/57 - Janek_Kozicki

使用范围：std::ranges::max_element(x, [](std::pair<char, int> a, std::pair<char, int> b) { return a.second < b.second; }) - mheyman

Answer 3

你的代码中从未改变过currentMax。

map<int,unsigned> frequencyCount;
for(size_t i = 0; i < v.size(); ++i)
    frequencyCount[v[i]]++;

unsigned currentMax = 0;
unsigned arg_max = 0;
for(auto it = frequencyCount.cbegin(); it != frequencyCount.cend(); ++it ) }
    if (it ->second > currentMax) {
        arg_max = it->first;
        currentMax = it->second;
    }
}
cout << "Value " << arg_max << " occurs " << currentMax << " times " << endl;

找众数的另一种方法是对向量进行排序，然后循环遍历一次，跟踪值改变的索引。

- YXD

---

对于一个大的地图，最好使用地图成员函数（可能结合二分查找），例如std::map::upper_bound，以提高速度。 - Erik Alapää

Answer 4

这是基于Rob上面的精彩答案而编写的模板函数。

template<typename KeyType, typename ValueType> 
std::pair<KeyType,ValueType> get_max( const std::map<KeyType,ValueType>& x ) {
  using pairtype=std::pair<KeyType,ValueType>; 
  return *std::max_element(x.begin(), x.end(), [] (const pairtype & p1, const pairtype & p2) {
        return p1.second < p2.second;
  }); 
}

例子：

std::map<char,int> x = { { 'a',1 },{ 'b',2 },{'c',0}}; 
auto max=get_max(x);
std::cout << max.first << "=>" << max.second << std::endl; 

输出：b=>2

- daknowles

Answer 5

我们可以通过使用max_element()函数轻松做到这一点。

代码片段：

---

#include <bits/stdc++.h>
using namespace std;

bool compare(const pair<int, int>&a, const pair<int, int>&b)
{
   return a.second<b.second;
}

int main(int argc, char const *argv[])
{
   int n, key, maxn;
   map<int,int> mp;

   cin>>n;

   for (int i=0; i<n; i++)
   {
     cin>>key;
     mp[key]++;
   }

   maxn = max_element(mp.begin(), mp.end(), compare)->second;

   cout<<maxn<<endl;

   return 0;
 }

- rashedcs

Answer 6

在使用STL迭代器获取最小值/最大值/范围时，根据需要可以重复使用键或值比较器对象来替代比较器API。

http://www.cplusplus.com/reference/map/multimap/key_comp/ http://www.cplusplus.com/reference/map/multimap/value_comp/

==

例子：

// multimap::key_comp
#include <iostream>
#include <map>

int main ()
{
  std::multimap<char,int> mymultimap;

  std::multimap<char,int>::key_compare mycomp = mymultimap.key_comp();

  mymultimap.insert (std::make_pair('a',100));
  mymultimap.insert (std::make_pair('b',200));
  mymultimap.insert (std::make_pair('b',211));
  mymultimap.insert (std::make_pair('c',300));

  std::cout << "mymultimap contains:\n";

  char highest = mymultimap.rbegin()->first;     // key value of last element

  std::multimap<char,int>::iterator it = mymultimap.begin();
  do {
    std::cout << (*it).first << " => " << (*it).second << '\n';
  } while ( mycomp((*it++).first, highest) );

  std::cout << '\n';

  return 0;
}


Output:
mymultimap contains:
a => 100
b => 200
b => 211
c => 300

==

- mav_2k

Answer 7

你已经快到成功的边缘了：在maax = it->first;之后添加currentMax = it->second;即可。

但是使用map来查找最大值有点过度：只需要扫描这个向量并存储您发现更高数字的索引即可：与您已经编写的非常相似，只是更简单。

- CapelliC

Answer 8

作为习惯使用 Boost 库的人，使用 Rob 提出的 匿名函数的替代方案是以下实现 std::max_element 的方法：

std::map< int, unsigned >::const_iterator found = 
        std::max_element( map.begin(), map.end(),
                         ( boost::bind(&std::map< int, unsigned >::value_type::second, _1) < 
                           boost::bind(&std::map< int, unsigned >::value_type::second, _2 ) ) );

- dr_g

Answer 9

最好使用内部比较器 map::value_comp()。

例如：

#include <algorithm>
...
auto max = std::max_element(freq.begin(), freq.end(), freq.value_comp());
std::cout << max->first << "=>" << max->second << std::endl

将输出为：

Key => Value

- shed

---

以下代码将无法正常工作。auto p = std::max_element(freq.begin(), freq.end(), freq.value_comp()); 因为 > std::map::value_comp 返回一个比较对象，可用于比较两个元素，以确定第一个元素的键是否在第二个元素之前。因此，p 将指向 map 中的最后一个元素。 - ivan2kh

那是错误的比较器。请参考http://www.cplusplus.com/reference/map/map/value_comp/。 - mmdanziger