Defining custom compare function for std::map

Question

I am trying to make a character frequency map that, on every insert, puts the character with the highest frequency at the start of the map.

So, it would be like a std::map<char, int> and I would iterate the string and do map[string[i]]++ to increment the frequency count for each character. On every increment, the map would sort itself like a priority queue and put the key-value pair with the highest frequency at the beginning of the map so I can retrieve with map.begin().

I tried to make a custom comparator for std::map, but some incomprehensible error messages came out.

#include <map>
#include <string>

using namespace std;

struct cmpByValue
{
    bool operator()(const pair<char, int>& p1, const pair<char, int>& p2)
    {
        return p1.second > p2.second;
    }
};

int main(void)
{
    map<char, int, cmpByValue> freq_map;
    string s = "ASDASDASD";
    for (int i=0; i<s.size(); ++i)
    {
        freq_map[s[i]]++;
    }
    return 0;
}

I know that std::map automatically sorts the elements based on the keys, but since I want it to sort by frequency, it would have to sort by value instead of key.

Is this possible?

Answer 1

What you are attempting to do with std::map (or any associative container, for that matter) is simply not feasible, as it sorts its elements on keys only, not on their mapped values. You can't make std::map move its elements around when the values change, only when the keys change.

So, you will have to sort your std::map elements after you are done calculating all of the frequency values, eg:

#include <map>
#include <string>
#include <vector>
#include <utility>
#include <algorithm>

using namespace std;

using freqMap = map<char, int>;
using freqMapElement = typename map<char, int>::value_type;

bool cmpByValue(const freqMapElement* p1, const freqMapElement* p2)
{
    return p1->second > p2->second;
}

int main()
{
    string s = "ASDASDASD";

    freqMap freq_map;
    for (auto c : s)
    {
        freq_map[c]++;
    }

    vector<freqMapElement*> freq_vec;
    freq_vec.reserve(freq_map.size());
    for (auto &elem : freq_map)
    {
        freq_vec.push_back(&elem);
    }
    sort(freq_vec.begin(), freq_vec.end(), cmpByValue);

    freqMapElement* top = *freq_vec.begin();
    // use top as needed...

    return 0;
}

Online Demo

---

That being said - since you stated:

On every increment, the map would sort itself like a priority queue and put the key-value pair with the highest frequency at the beginning of the map so I can retrieve with map.begin().

Then you could simply use std::priority_queue instead, eg:

#include <map>
#include <string>
#include <queue>

using namespace std;

using freqMap = map<char, int>;
using freqMapElement = typename freqMap::value_type;

struct cmpByValue
{
    bool operator()(const freqMapElement* p1, const freqMapElement* p2)
    {
        return p1->second > p2->second;
    }
};

int main()
{
    string s = "ASDASDASD";

    freqMap freq_map;
    for (auto c : s)
    {
        freq_map[c]++;
    }

    priority_queue<
        freqMapElement*,
        std::vector<freqMapElement*>,
        cmpByValue> pq;

    for (auto &elem : freq_map)
    {
        pq.push(&elem);
    }

    freqMapElement* top = pq.top();
    // use top as needed...

    return 0;
}

Online Demo