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

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

using namespace std;

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

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 an unordered_map
    unordered_map<int, int> frequencyUnorderedMap;
    for (int x : arr) {
        frequencyUnorderedMap[x]++;
    }

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

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

    // Step 5: Construct the sorted result array
    vector<int> sortedArr;
    for (const auto& p : frequencyVector) {
        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;
}