Example: Sort Array by Frequency (using std::map) in C++

// Sort Array by Frequency (using std::map)
#include <iostream>
#include <vector>
#include <map>
#include <algorithm> // For std::sort

using namespace std;

// Custom comparator function for sorting pairs
bool comparePairs(const pair<int, int>& a, const pair<int, int>& b) {
    // Sort by frequency in descending order
    if (a.second != b.second) {
        return a.second > b.second;
    }
    // If frequencies are same, sort by value in ascending order
    return a.first < b.first;
}

int main() {
    // Step 1: Define the input array
    vector<int> arr = {2, 5, 2, 8, 5, 6, 8, 8};
    cout << "Original array: ";
    for (int x : arr) {
        cout << x << " ";
    }
    cout << endl;

    // Step 2: Count frequencies of each element using a map
    map<int, int> frequencyMap;
    for (int x : arr) {
        frequencyMap[x]++;
    }

    // Step 3: Transfer map contents to a vector of pairs
    // Each pair will store {element, frequency}
    vector<pair<int, int>> frequencyVector;
    for (auto const& [element, freq] : frequencyMap) {
        frequencyVector.push_back({element, freq});
    }

    // Step 4: Sort the vector of pairs using the custom comparator
    sort(frequencyVector.begin(), frequencyVector.end(), comparePairs);

    // Step 5: Construct the sorted result array
    vector<int> sortedArr;
    for (const auto& p : frequencyVector) {
        // Add the element 'p.first' 'p.second' times to the result
        for (int i = 0; i < p.second; ++i) {
            sortedArr.push_back(p.first);
        }
    }

    // Step 6: Print the sorted array
    cout << "Sorted array by frequency: ";
    for (int x : sortedArr) {
        cout << x << " ";
    }
    cout << endl;

    return 0;
}