CODEWITHSUNDEEP
c++c++11stl
as2d3
as2d3

Reputation: 905

Constructing a priority queue of vectors

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.

Upvotes: 5

Views: 22302

Answers (6)

S Abhishek
S Abhishek

Reputation: 1

#include<iostream>
#include<queue>

using namespace std; 

priority_queue<vector<int>> pq; 

void max(vector<int> v) 
{ 
    for(int i=0; i<v.size();i++) 
    { 
        cout<<v[i]<<" "; 
    } 
    cout<<endl; 
    return; 
} 

int main() 
{ 
    vector<int> inp1{10,20,30,40}; 
    vector<int> inp2{10,20,35,40}; 
    vector<int> inp3{30,25,10,50};
    vector<int> inp4{20,10,30,40};
    vector<int> inp5{5,10,30,40};

    pq.push(inp1); 
    pq.push(inp2); 
    pq.push(inp3); 
    pq.push(inp4); 
    pq.push(inp5); 
    max(pq.top()); 
}

Upvotes: 0

S Abhishek
S Abhishek

Reputation: 1

#include #include

using namespace std;

void max(vector<int> v) 
{ 
for(int i=0; i<v.size();i++) 
{ 
    cout<<v[i]<<" "; 
} 
cout<<endl; 
};

struct my_comparator
{
    bool operator()(vector<int> const& a,vector<int> const& b) const
    {
        return a>b;
    }
};

priority_queue<vector<int>, vector<vector<int>>, my_comparator>pq;

int main() 
{
    vector<int> inp1{10,20,30,40}; 
    vector<int> inp2{10,20,35,40}; 
    vector<int> inp3{30,25,10,50};
    vector<int> inp4{20,10,30,40};
    vector<int> inp5{5,10,30,40};

    pq.push(inp1); 
    pq.push(inp2); 
    pq.push(inp3); 
    pq.push(inp4); 
    pq.push(inp5); 

    max(pq.top()); 
}

Upvotes: -1

Galik
Galik

Reputation: 48605

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

Upvotes: 10

Eziz Durdyyev
Eziz Durdyyev

Reputation: 1158

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

Upvotes: 3

marcks
marcks

Reputation: 422

Galiks example is good. I would however not put the sanity check in the comparator if following the principle of one function - one task. More details on http://en.cppreference.com/w/cpp/container/priority_queue. Using lambda we can implement it as follows:

#include <vector>
#include <queue>

int main(){
    auto cmp = [](std::vector<int> left, std::vector<int> right) { return(left[2]) > (right[2]);};

    std::priority_queue<std::vector<std::vector<int>>, std::vector<std::vector<int>>, decltype(cmp)> q(cmp);

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

    return 0;
}

Upvotes: 0

jan_v
jan_v

Reputation: 21

You may use std::priority_queue with a custom comparator.

using QueueElement = std::vector<int>;

auto compare_third_element = [](const QueueElement& lhs, const QueueElement& rhs) 
                             { 
                                assert(lhs.size() > 2 && rhs.size() > 2);
                                return lhs[2] > rhs[2]; 
                             };

using MyPriorityQueue = std::priority_queue < QueueElement, std::vector<QueueElement>, decltype(compare_third_element)>;
MyPriorityQueue my_queue(compare_third_element);

my_queue.emplace(QueueElement{ 0,0,2 });
my_queue.emplace(QueueElement{ 0,0,3 });
my_queue.emplace(QueueElement{ 0,0,1 });

Upvotes: 0

Related Questions