инициализация для очереди приоритетов STL

Question

Я все еще запутался в очереди приоритетов в STL. Вот цель, которую я хочу достичь, скажем: у меня есть структура под названием «Запись», которая содержит строковое слово и счетчик int. Например: у меня много записей о них (в примерной программе всего 5), теперь я хочу сохранить верхние N записей (в примере 3).

теперь я знаю, что я мог бы перегрузить оператор < в записи, и поставить все записи в векторе, а затем инициализировать priority_queue как:

priority_queue< Record, vector<Record>, less<Record> > myQ (myVec.begin(),myVec.end()); 

Однако, как я понял, это не так легко контролировать размер вектора myVec, потому что он не отсортирован так, как я хотел.

Я действительно не понимаю, почему следующее не может работать:

struct Record 
{ 
    string word; 
    int count; 
    Record(string _word, int _count): word(_word), count(_count) { }; 
    /* 
     bool operator<(const Record& rr) 
     { 
      return this->count>rr.count; 
     } 
    */ 
    bool operator() (const Record& lhs, const Record& rhs) 
    { 
     return lhs.count>rhs.count; 
    } 
}; 

void test_minHeap() 
{ 
    priority_queue<Record> myQ; 
    Record arr_rd[] = {Record("William", 8), 
         Record("Helen", 4), 
         Record("Peter", 81), 
         Record("Jack", 33), 
         Record("Jeff", 64)}; 
    for(int i = 0; i < 5; i++) 
    { 
     if(myQ.size() < 3) 
     { 
      myQ.push(arr_rd[i]); 
     } 
     else 
     { 
      if(myQ.top().count > arr_rd[i].count) 
       continue; 
      else 
      { 
       myQ.pop(); 
       myQ.push(arr_rd[i]); 
      } 
     } 
    } 

    while(!myQ.empty()) 
    { 
     cout << myQ.top().word << "--" << myQ.top().count << endl; 
     myQ.pop(); 
    } 
} 

Edit: Спасибо за ваш вклад, теперь я получил его working.However, я предпочитаю, если кто-то может объяснить, почему первый вариант оператора <, перегрузка работает, вторая (прокомментированная) не будет работать и имеет длинный список ошибок компилятора.

friend bool operator< (const Record& lhs, const Record& rhs) 
{ 
    return lhs.count>rhs.count; 
} 

/* 
bool operator<(const Record& rRecord) 
{ 
    return this->count>rRecord.count; 
} 
    */ 

Answer 1

std::priority_queue не может волшебно знать, как сортировать элементы. Вы должны сказать, как это сделать. Способ сделать это - дать priority_queue тип функтора, который при вызове с двумя объектами возвращает, является ли первый аргумент «меньше» второго, однако вы хотите определить его. Этот функтор является параметром шаблона для priority_queue.

Параметр по умолчанию - std::less<type>, который требует, чтобы type (то, что вы помещаете в очередь) имеет перегруженный operator<. Если это не так, то вам либо нужно предоставить один, либо вы должны предоставить правильный функтор сравнения.

Например:

struct Comparator 
{ 
    bool operator()(const Record& lhs, const Record& rhs) 
    { 
    return lhs.count>rhs.count; 
    } 
}; 

std::priority_queue<Record, std::vector<Record>, Comparator> myQ; 

Причина, по которой не работает только с перегрузкой на Record потому, что вы не сказали priority_queue, что это сравнение. Кроме того, тип, используемый для сравнения, должен быть по умолчанию конструктивным, так что priority_queue может создавать и уничтожать объекты по своему желанию.

Хотя, если честно, я не знаю, почему вы не просто вставляете их в std::set, если хотите их отсортировать. Или просто запустите std::sort на std::vector предметов.

Answer 2

Ваш код делает работы, с двумя небольшими изменениями:

• раскомментировать определение Record::operator<(), так что требуется по умолчанию компаратора приоритетной очереди в.
• Измените объявление на bool operator<(const Record &) const (обратите внимание на дополнительные const), так как очередь приоритетов должна сравниваться с использованием ссылок на объекты const.

В качестве альтернативы, объявить его в качестве свободной функции, вне определения класса:

bool operator<(const Record &l, const Record &r) {return l.count > r.count;} 

или определить свой собственный функтор, и предусматривает, что в качестве соответствующего аргумента шаблона:

struct CompareRecords 
{ 
    bool operator()(const Record &l, const Record &r) {return l.count > r.count;} 
}; 

typedef priority_queue<Record, vector<Record>, CompareRecords> RecordQueue;