Finding the max value in a map

Question

I've been doing a basic program to find the max, min, median, variance, mode etc. of a vector. Everything went fine until I got to the mode.

The way I see it, I should be able to loop through the vector, and for each number that occurs I increment a key on the map. Finding the key with the highest value would then be the one that occurred the most. Comparing to other keys would tell me if it's a single multiple or no mode answer.

Here's the chunk of code that's been causing me so much trouble.

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;

The entire program can be seen here. http://pastebin.com/MzPENmHp

Submarginal

Answer 1

You never changed currentMax in your code.

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;

Another way to find the mode is to sort the vector and loop through it once, keeping track of the indices where the values change.

Various

For a large map, it should be faster to use a map member function (maybe combined with binary search), std::map::upper_bound? – Parbuckle

Answer 2

You can use std::max_element to find the highest map value (the following code requires 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';

Exhalant

Hi Rob, how to understand the function? Is it a overload of operator[]? [](const pair<int, unsigned>& p1, const pair<int, unsigned>& p2) { return p1.second < p2.second; } – Eye

en.wikipedia.org/wiki/… en.wikipedia.org/wiki/… – Subsistent

Shouldn't the int in pair<..> be const, i.e. pair<const int, unsigned>? – Lindeman

@Lindeman yes it should and it would save much much unnecessary casting time. BTW if C++14 available just use auto instead. – Domineer

@HumamHelfawi auto already existed in C++11 and is specifically used above, but not for the map because you obviously can't deduce a type without an rvalue. Also, are there any sources documenting this "much unnecessary casting time"? – Telephonist

auto is included in c++ 11 but as lambda variable. it is c++ 14 see this #32646862 about casting time see the accepted answer here : #32510683 – Domineer

#include <algourithem> include this lib – Verde

What is it's time complexity? – Magneton

Answer 3

This can be done in few lines, here's a full working snippet:

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

Brotherinlaw

why everyone uses std:: instead of using namespace? – Apish

to avoid namespace pollution. Pollution can be a real hindrance in large projects. Even crashes due to linker confusing same class name coming from different namespaces: gitlab.com/yade-dev/trunk/-/issues/57 – Brotherinlaw

With ranges: std::ranges::max_element(x, [](std::pair<char, int> a, std::pair<char, int> b) { return a.second < b.second; }) – Archaism

@Brotherinlaw why not use pair<char, int> as a return type of std::max_element – Untouchability

Because en.cppreference.com/w/cpp/algorithm/max_element returns an iterator. – Brotherinlaw

Answer 4

Here's a templated function based on Rob's excellent answer above.

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

Example:

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

Outputs: b=>2

Counterglow

Answer 5

We can easily do this by using max_element() function.

Code Snippet :

---

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

Typhoon

Answer 6

We may reuse key or, value comparator objects as per requirements in place of comparator api, while fetching min/max/ranges over any STL iterator.

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

==

Example:

// 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

==

Rakia

Answer 7

you are almost there: simply add currentMax = it->second; after maax = it->first;

but using a map to locate the max is overkill: simply scan the vector and store the index where you find higher numbers: very similar to what you already wrote, just simpler.

Jokester

Answer 8

As someone accustomed to using Boost libraries, an alternative to using the anonymous function proposed by Rob is the following implementation of 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 ) ) );

Slicker

Answer 9

2024

C++20: use views::values as argument to ranges::max_element:

*ranges::max_element(views::values(my_map));

Working example:

#include <algorithm>
#include <iostream>
#include <map>
#include <ranges>

using namespace std;

int main()
{
    map<int, int> my_map {{5, 1}, {4, 2}, {2, 5}, {3, 3}, {1, 4}};
    cout << *ranges::max_element(views::values(my_map));

    return 0;
}

Midyear

Answer 10

Beter use inner comparator map::value_comp().

For example:

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

will output:

Key => Value

Nucellus

The code below will not work. auto p = std::max_element(freq.begin(), freq.end(), freq.value_comp()); Since > std::map::value_comp Returns a comparison object that can be used to > compare two elements to get whether the key of the first one goes > before the second. So p will point to the last element in map. – Kristy

That's the wrong comparator. See cplusplus.com/reference/map/map/value_comp – Mcmillian