7

我试图通过将字母及其相应值保存到地图中然后将地图插入优先级队列来实现霍夫曼编码。尝试声明队列时出现参数转换错误。我到底应该把什么作为参数？我在这里得到的是我最好的猜测。

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;*/
}

我觉得问这个有点愚蠢，但彻底的谷歌搜索并没有让我得到答案。非常感谢您的帮助！

4

2 回答 2

13

您不能将地图用作priority_queue 的底层容器：priority_queue 必须可以自由地重新排序容器中的内容，这对于地图是不允许的。只能使用向量和双端队列（来自标准容器）。

因此，容器类型将类似于vector<pair<char, int> >. 然后，您需要一个较小/较大的操作，该操作仅考虑该对的第二个字段。

于 2010-12-19T21:35:30.547 回答
9

方法1，使用仿函数，

#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();
    }
}

方法2，使用函数和decltype()它

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);

上例中的 priority_queue 按值排序，

a - 12
d - 10
b - 9
c - 7
于 2016-10-22T11:14:17.947 回答