5

I'm still confused about priority queue in STL. Here is the objective I wanna achieve, say: I have a structure called Record, which contains a string word and a int counter. For example: I have many records of these (in the sample program, only 5), now I want to keep top N records(in sample, 3).

I know now that I could overload operator < in Record, and put all records in a vector, and then initialize the priority_queue like: 

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

However, as I understood, it's not easy to control the size of vector myVec because it's not sorted as I wanted.

I really don't understand why the following can not 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 it working.However, I prefer if someone could explain why the first version of operator< overload works, the second one (commented out one) won't 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;
}
    */
WilliamLou
  • 1,914
  • 6
  • 27
  • 38
  • You realize that you don't have `operator<` overloaded for `Record` - it is commented out. – Björn Pollex Oct 27 '11 at 07:05
  • because I don't want to go the 1st way in my post. I overload operator () instead – WilliamLou Oct 27 '11 at 07:08
  • `operator()` is the function-call operator, and you overload for it makes zero sense. If you want to order objects, overload the appropriate comparison operator. – Björn Pollex Oct 27 '11 at 07:13
  • [This answer of mine](http://stackoverflow.com/questions/7803634/sorting-a-vectorstruct-alphabetically/7803650#7803650) to another question is basically what you want. – Björn Pollex Oct 27 '11 at 07:15
  • You may need to write your own comparison functor, if you want to overload operator() instead of operator<. The default functor, (less), expects operator<, so that's what you have to give it. – Darcy Rayner Oct 27 '11 at 07:16
  • Similar post [here](http://stackoverflow.com/questions/19535644/how-to-use-the-priority-queue-stl-for-objects) – Rick Smith Mar 13 '15 at 23:35

2 Answers2

12

std::priority_queue cannot magically know how to sort the elements. You must tell it how to do so. The way to do that is to give priority_queue a functor type which, when called with two objects, returns whether the first argument is "less than" the second, however you want to define that. This functor is a template parameter to the priority_queue.

The default parameter is std::less<type>, which requires that type (what you're putting in the queue) has an overloaded operator<. If it doesn't, then you either have to provide one or you have to provide a proper 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 doesn't work with just an overload on Record is because you didn't tell the priority_queue that it was the comparison. Also, the type used for comparison needs to be default constructable, so that the priority_queue can create and destroy the objects at will.

Though to be honest, I don't know why you don't just stick them in a std::set if you want to sort them. Or just run std::sort on the std::vector of items.

Nicol Bolas
  • 449,505
  • 63
  • 781
  • 982
  • 1
    `Though to be honest, I don't know why you don't just stick them in a std::set if you want to sort them. Or just run std::sort on the std::vector of items.` Priority queue can initialise in O(n) if we already have all the elements. While set or sort will take O(logn) . See [this](https://stackoverflow.com/questions/44650882/time-complexity-of-a-priority-queue-in-c) – Kaustubh Pandey Jul 18 '20 at 18:38
  • If we want to extract top k we can do it in O(K log(n) ) while same thing with sort or set will remain O(n log(n) ). – Kaustubh Pandey Jul 18 '20 at 19:32
4

Your code does work, with two small changes:

  • Uncomment the definition of Record::operator<(), since that's needed by the priority queue's default comparator.
  • Change the declaration to bool operator<(const Record &) const (note the extra const), since the priority queue has to compare 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 provide that as the appropriate 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;
Mike Seymour
  • 249,747
  • 28
  • 448
  • 644