C++ Сортировка карты по значению Численно, ключ по алфавиту

Question

Я пытаюсь сделать эту частотную таблицу C++, а мой код ниже.

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

Когда я запускаю код с str дается как do be do bo., выход заключается в следующем

o 3 
d 2 
b 2 
e 1 

Так вот мой мыслительный процесс.

Я беру ввод str и помещаю его в массив и сортирую его по алфавиту, а затем помещаю этот массив в карту mymap. Затем я принимаю mymap и получаю частоту каждой строки и помещаю буквы в качестве клавиш и частоты в качестве значений на карте freq. Затем я использую функцию printmap() для упорядочивания карты по убыванию.

Однако, когда я это делаю, клавиши произвольно упорядочены. Так, например, в приведенной выше строке b 2 распечатывается после d 2, хотя они были в порядке, когда я дал карту freq функции printmap().

По существу, я ищу способ сортировки карты в функции printmap() по значению, а затем по ключу, поэтому результаты распечатываются по убыванию и по алфавиту.

Желаемый результат для do be do bo. выглядит следующим образом:

o 3 
b 2 
d 2 
e 1 

спасибо.

Answer 1

Не знаете, почему вы используете std::partial_sort здесь - он предназначен для сортировки только части ввода. Вместо этого попробуйте std::stable_sort: он будет сортировать входные данные, но не повлияет на порядок элементов, сравнивающих одинаковые. Это дает вам то, что вы хотите, так как ваш вход map уже отсортирован по возрастающему алфавитному ключу:

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

В качестве альтернативы, вы можете изменить вашу функцию сравнения, чтобы сравнить оба значение и ключ, и использовать простой 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"; 
    } 
}