initialization for STL priority queue

Question

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

Solution 1

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.

Solution 2

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;

Comments

[Yunfei Chen]

For the second one you will get unknown typename 'Record' error if you try to use it.......

[Yunfei Chen]

First one will give you two many parameters for this function....

[Kaustubh Pandey]

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

[Kaustubh Pandey]

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) ).