C ++ STL: использование карты с priority_queue - PullRequest
Новая
       55

C ++ STL: использование карты с priority_queue

4 голосов
/ 20 декабря 2010

Я пытаюсь реализовать кодирование Хаффмана, сохраняя буквы и их соответствующие значения в карте, а затем вставляя карту в очередь с приоритетами.Я получаю ошибку преобразования параметров, когда пытаюсь объявить свою очередь.Что именно я должен указать в качестве параметров?То, что я имею здесь, было моим лучшим предположением. 

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

Я чувствую себя глупо, спрашивая это, но тщательное поиск в Google не дало мне ответа.Большое спасибо за помощь!

Ответы [ 2 ]

10 голосов
/ 20 декабря 2010

Вы не можете использовать карту в качестве основного контейнера для priority_queue: priority_queue должен быть свободным, чтобы переупорядочить вещи в контейнере, что недопустимо для карт.Можно использовать только vector и deque (из стандартных контейнеров).

Таким образом, тип контейнера будет выглядеть примерно так: vector<pair<char, int> >.Затем вам нужна операция меньше / больше, которая учитывает только второе поле пары.

4 голосов
/ 22 октября 2016

метод 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() 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);

priority_queue в приведенном выше примере отсортировано по значению, 

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