Initializing the STL Priority Queue

Question

I am still confused in the priority queue in STL. Here is the goal I want to achieve, say: I have a structure called "Record" that contains a string word and an int counter. For example: I have a lot of records about them (in the sample program there are only 5), now I want to save the top N records (in example 3).

Now I know that I can overload the <operator in the records and put all the records in the vector, and then initialize priority_queue as:

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

However, as I understand it, managing the size of the vector myVec is not easy, because it does not sort as I wanted.

I really don't understand why the following cannot work:

 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: Thanks for your input, now I got his job. However, I prefer that someone can explain why the first version of the operator <overload works, the second (commented) will not work and has a long list of compiler errors.

 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 cannot magically know how to sort items. You have to say how to do it. The way to do this is to give priority_queue a functor type that, when called with two objects, returns whether the first argument is “less” than the second, however you want to define it. This functor is a template parameter for priority_queue .

The default parameter is std::less<type> , for which type (what you put in the queue) has an overloaded operator< . If this is not the case, then you either need to provide one, or you must provide the correct comparison functor.

For example:

 struct Comparator { bool operator()(const Record& lhs, const Record& rhs) { return lhs.count>rhs.count; } }; std::priority_queue<Record, std::vector<Record>, Comparator> myQ; 

The reason that only overloading on Record does not work is because you did not tell priority_queue that it was a comparison. In addition, the type used for comparison must be constructive by default, so priority_queue can create and destroy objects as it sees fit.

Although, to be honest, I don’t know why you don’t just paste them into std::set if you want to sort them. Or just run std::sort on std::vector elements.

Answer 2

Your code works with two small changes:

• Uncomment the definition of Record::operator<() as this is necessary for the default comparator for the default queue.
• Change the declaration to bool operator<(const Record &) const (note the additional const ), since the priority queue should be compared using references to const objects.

Alternatively, declare it as a free function, outside the class definition:

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

or define your own functor and specify this as the corresponding template argument:

 struct CompareRecords { bool operator()(const Record &l, const Record &r) {return l.count > r.count;} }; typedef priority_queue<Record, vector<Record>, CompareRecords> RecordQueue;