C++ STL : Using map with priority_queue

Question

I'm trying to implement Huffman coding by saving letters and their corresponding values into a map then inserting the map into a priority queue. I am getting a parameter conversion error when I try to declare my queue. What exactly am I supposed to put as the parameters? What I have here was my best guess.

void main()
{
 ifstream doc("doc.txt"); 
 map<char, int> C;
 char letter;
 while(!doc.eof()){
  doc.get(letter);
  if(letter >= 'a' && letter <= 'z')
   C[letter]++;
 }
 priority_queue<int, map<char,int>, greater<int> > Q(C); //also tried greater<map<char,int>>
 /*map<char, int>::const_iterator it;
 for(it = C.begin(); it != C.end(); it++)
  cout<<it->first<<" "<<it->second<<endl;*/
}

I feel kind of dumb asking this but thorough googling did not get me the answer. Thanks a lot for the help!

Answer 1

You cannot use a map as the underlying container for a priority_queue: the priority_queue must be free to reorder things in the container, which is not allowed for maps. Only vector and deque can be used (from the standard containers).

So, the container type would be something like vector<pair<char, int> >. Then, you need a less/greater operation that only takes the second field of the pair into account.

Answer 2

method 1, using a functor,

#include <unordered_map>
#include <vector>
#include <iostream>
#include <queue>
using namespace std;

typedef pair<char, int> PAIR;

int main(int argc, char *argv[]) {
    unordered_map<char, int> dict = {{'a', 12}, {'b', 9}, {'c', 7}, {'d', 10},};
    struct cmp {
        bool operator()(const PAIR &a, const PAIR &b) {
            return a.second < b.second;
        };
    };
    priority_queue<PAIR, vector<PAIR>, cmp> pq(dict.begin(), dict.end());
    while (!pq.empty()) {
        PAIR top = pq.top();
        cout << top.first << " - " << top.second << endl;
        pq.pop();
    }
}

method 2, using a function and decltype() it

auto cmp = [](const PAIR &a, const PAIR &b) {
    return a.second < b.second;
};
priority_queue<PAIR, vector<PAIR>, decltype(cmp)> pq(
        dict.begin(), dict.end(), cmp);

the priority_queue in above example is sorted by value,

a - 12
d - 10
b - 9
c - 7