Constructing a priority queue of vectors

Question

I am looking for a simple STL implementation of a priority queue of vectors. Each vector has exactly 4 elements. I want to sort my priority queue on the basis of the 3rd element of each vector. The vector with the lowest 3rd element should come at the top(min priority queue of vectors).

How to implement this in C++?

Also, if anybody has the actually STL implementation of default priority queue, please provide a link. Like the official implementation inside the STL.

Solution 1

You have to create your own comparator to compare elements of the priority_queue.

Something like this:

// How to compare elements
struct my_comparator
{
    // queue elements are vectors so we need to compare those
    bool operator()(std::vector<int> const& a, std::vector<int> const& b) const
    {
        // sanity checks
        assert(a.size() == 4);
        assert(b.size() == 4);

        // reverse sort puts the lowest value at the top    
        return a[2] > b[2];
    }
};

// for usability wrap this up in a type alias:
using my_priority_queue = std::priority_queue<std::vector<int>, std::vector<std::vector<int>>, my_comparator>;

int main()
{
    my_priority_queue mpq;

    mpq.push({1, 2, 1, 4});
    mpq.push({1, 2, 2, 4});
    mpq.push({1, 2, 3, 4});

    // etc ...
}

Solution 2

Please consider using STL data-structure priority_queue. I faced similar problem before and this code should help.

I think before posting answers we need to check if our answer builds correctly. So this is working program but you should not use using namespace std;, please change it with std:::

#include <functional>
#include <queue>
#include <vector>
#include <iostream>

using namespace std;

template<typename T> void print_queue(T& q) {
    while(!q.empty()) {
        vector<int> tmp;
        tmp = q.top();
        std::cout << tmp[2] << " ";
        q.pop();
    }
    std::cout << '\n';
}

struct Compare {
    bool operator()(vector<int> const & a, vector<int> const & b)
    { return a[2] > b[2]; }
};

int main()
{

    vector<int> v1;
    vector<int> v2;
    vector<int> v3;
    vector<int> v4;

    priority_queue< vector<int>, vector< vector<int> >, Compare > pr_q;

    int a[5] = { 1,2,3,4 };
    v1.insert(v1.end(), a, a+4); v1[2] = 11; // v1 = {1, 2, 11, 4}
    v2.insert(v2.end(), a, a+4); v2[2] = -1; // v1 = {1, 2, -1, 4}
    v3.insert(v3.end(), a, a+4); v3[2] = 22; // v1 = {1, 2, 22, 4}
    v4.insert(v4.end(), a, a+4); v4[2] = 31; // v1 = {1, 2, 31, 4}

    pr_q.push(v1);
    pr_q.push(v2);
    pr_q.push(v3);
    pr_q.push(v4);

    print_queue(pr_q);

    return 0;
}

Comments

[Eziz Durdyyev]

I know that some improvements and corrections could be applied but I think it answers the question. So, cheers!

[as2d3]

The comparator sign should be 'greater than' because by default priority queue are implemented using max-heap and not min-heaps. I think you should change the compare sign.

[S Abhishek]

Print the maximum vector that is in a queue Define priority queue like this priority_queue<vector<int> > "Queuename";