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

Question

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

Теперь я знаю, что могу перегрузить оператор <в записи и поместить все записи в вектор, а затем инициализировать priority_queue следующим образом: </p>

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: Спасибо за ваш вклад, теперь у меня все получилось. Однако я предпочел бы, если бы кто-то мог объяснить, почему первая версия оператора <перегрузки работает, вторая (закомментированная) не будет работать и имеет длинный список ошибок компилятора. </p>

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;