CODEWITHSUNDEEP
c++stldictionarypriority-queuehuffman-code
Bobby
Bobby

Reputation: 79

C++ STL : Using map with priority_queue

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!

Upvotes: 7

Views: 19354

Answers (2)

zhazha
zhazha

Reputation: 3624

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

Upvotes: 9

Martin v. L&#246;wis
Martin v. L&#246;wis

Reputation: 127467

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.

Upvotes: 13

Related Questions