C++ Sort Map By Value Numerically, Key Alphabetically

Question

I'm trying to make this frequency table with c++, and my code is below.

#include <iostream>
#include <iomanip>
#include <string>
#include <algorithm>
#include <map>
#include <vector>
#include <cassert>

using namespace std;

typedef std::pair<std::string, int> mypair;

struct IntCmp {
    bool operator()(const mypair &lhs, const mypair &rhs) {
        return lhs.second < rhs.second;
    }
};

string removeSpaces(string input) {
    input.erase(std::remove(input.begin(),input.end(),' '),input.end());
    input.erase(std::remove(input.begin(), input.end(), '\t'), input.end());
    input.erase(std::remove(input.begin(), input.end(), '.'), input.end());
    return input;
}

void printmap(const std::map<std::string,int> &mymap, int size) {
    std::vector<mypair> myvec(mymap.begin(), mymap.end());
    assert(myvec.size() >= size);
    std::partial_sort(myvec.begin(), myvec.begin() + size, myvec.end(), IntCmp());

    for(int i = size; i --> 0;) {
        std::cout << myvec[i].first << " " << myvec[i].second << "\n";
    }
}

int main() {
    string str;

    cout << "Enter text:\n";
    cin >> str;
    cout << "Frequencies:\n";

    str = "do be do bo.";

    str = removeSpaces(str);
    int size = str.size();
    string *array = new string[size];
    for(int i = 0; i < size; ++i) {
        array[i] = str[i];
    }
    sort(array, array+size);
    map<int, string> mymap;
    for(int i = 0; i < size; ++i) {
        mymap[i] = array[i];
    }
    map<string, int> freq;
    for(int i = 0; i < size; ++i) {
        if(freq.count(mymap[i]) == 0) {
            //Not found
            freq[mymap[i]] = 1;
        }
        else {
            //Found
            freq.at(mymap[i]) = freq.at(mymap[i]) + 1;
        }
    }
    int mapsize = freq.size();
    printmap(freq, mapsize);
}

When I run the code with the str given as do be do bo., the output is as follows

o 3
d 2
b 2
e 1

So here's my thought process.

I take the input str and put it in an array, and sort that array alphabetically, and then put that array into the map mymap. Then, I take mymap and get the frequency of each string and put the letters as the keys and the frequency as the values in the map freq. Then, I use the printmap() function to order the map by value descending.

However, when I do this, the keys are randomly ordered. So, for example, in the string presented above, b 2 is printed out after d 2, even though they were in order when I gave the freq map to the printmap() function.

Essentially, I'm looking for a way to sort the map in the printmap() function by value, and then by key, so the results are printed out by descending value and alphabetical key.

The desired result for the do be do bo. is as follows:

o 3
b 2
d 2
e 1

Thanks.

possible duplicate of [std::map, how to sort by value, then by key](http://stackoverflow.com/questions/19842035/stdmap-how-to-sort-by-value-then-by-key) — vsoftco, May 06 '15 at 19:30

nneonneo · Accepted Answer · 2015-05-06T19:25:56.977

Not sure why you're using std::partial_sort here - it's meant for sorting only part of the input. Try std::stable_sort instead: it will sort the input, but will not affect the order of elements that compare equal. This gives you what you want since your input map is already sorted by increasing alphabetical key:

struct IntCmp {
    bool operator()(const mypair &lhs, const mypair &rhs) {
        return lhs.second > rhs.second; // note reversed comparison here to sort by descending order
    }
};

void printmap(const std::map<std::string,int> &mymap, int size) {
    std::vector<mypair> myvec(mymap.begin(), mymap.end());
    assert(myvec.size() >= size);
    std::stable_sort(myvec.begin(), myvec.end(), IntCmp());

    // note we now iterate forwards because the sort comparison is reversed
    for(const auto &item : myvec) {
        std::cout << item.first << " " << item.second << "\n";
    }
}

Alternatively, you could alter your comparison function to compare both the value and the key, and use a plain std::sort:

struct IntCmp {
    bool operator()(const mypair &lhs, const mypair &rhs) {
        if(lhs.second == rhs.second) return lhs.first < rhs.first; // this is the "secondary" comparison, used if the frequencies are equal
        return lhs.second > rhs.second; // note reversed comparison here to sort by descending order
    }
};

void printmap(const std::map<std::string,int> &mymap, int size) {
    std::vector<mypair> myvec(mymap.begin(), mymap.end());
    assert(myvec.size() >= size);
    std::sort(myvec.begin(), myvec.end(), IntCmp());

    // note we now iterate forwards because the sort comparison is reversed
    for(const auto &item : myvec) {
        std::cout << item.first << " " << item.second << "\n";
    }
}

C++ Sort Map By Value Numerically, Key Alphabetically

1 Answers1