Stack or multiset?

Question

I have to store the number of occurences of each number (C++). An example input can look like this:

1
2
2
1
1

after the data is stored, I can use it in a stack fashion (I will always need the number of occurences of 2 first and only then 1, for example). Is it ok to take the input using a multiset, and then move the data to a stack (the number of inputs can be large and time complexity is a priority), as I am a little confused here.

Answer 1

It sounds like you want a std::priority_queue based on the count of each of the numbers.

It could look like this:

#include <iostream>
#include <queue>
#include <tuple>
#include <unordered_map>

int main() {
    std::unordered_map<int, unsigned> counts; // used for counting

    // read numbers and count:
    for(int num; std::cin >> num;) ++counts[num];

    using V = std::pair<int, unsigned>;

    // Copy the `pair<int, unsigned>`s into a priority queue that is sorted
    // on the count. Higher count puts them higher in the queue.
    std::priority_queue<V, std::vector<V>, bool (*)(const V&, const V&)> queue(
        counts.begin(), counts.end(), [](const V& lhs, const V& rhs) {
            return std::tie(lhs.second, lhs.first) <
                   std::tie(rhs.second, rhs.first);
        });

    // Extract values from the queue:
    while(not queue.empty()) {
        auto[num, count] = queue.top();
        queue.pop();
        std::cout << "number: " << num << " count: " << count << '\n';
    }
}

Demo