用户定义类型的优先级队列

时间:2021-06-08 16:31:22

I have the below struct

我有下面的结构

struct node{
   float val;
   int count;

}

I have several objects of this struct. Now, I want to insert these objects into a priority queue of STL such that the priority queue orders the items by count. Any idea on how to do so? Preferably a min heap is preferred. I know how to do the above for primitive data types, not structs

我有这个结构的几个对象。现在,我想将这些对象插入到STL的优先队列中,以便优先级队列按计数排序项。你知道怎么做吗?最好是最小堆。我知道如何为原始数据类型(而不是struct)执行上述操作。

6 个解决方案

#1


11  

Overload the < operator:

过载 <操作符:< p>

bool operator<(const node& a, const node& b) {
  return a.count > b.count;
}

I have reversed the comparison to achieve min heap wihtout passing extra arguments to the priority queue. Now you use it like this:

我颠倒了比较,以实现最小堆,而不会向优先级队列传递额外的参数。现在你可以这样使用它:

priority_queue<node> pq;
...

Edit: take a look at this post which seems to be almost exact duplicate: STL Priority Queue on custom class

编辑:看看这篇几乎完全相同的文章:自定义类上的STL优先队列

#2


8  

#include <iostream>
#include <queue>
#include <vector>
using namespace std;
class Boxer{
    public:
        string name;
        int strength;
};
struct Comp{
    bool operator()(const Boxer& a, const Boxer& b){
        return a.strength<b.strength;
    }
};
int main(){
    Boxer boxer[3];
    boxer[0].name="uday", boxer[0].strength=23;
    boxer[1].name="manoj", boxer[1].strength=33;
    boxer[2].name="rajiv", boxer[2].strength=53;

    priority_queue< Boxer, vector<Boxer>, Comp> pq;
    pq.push(boxer[0]);
    pq.push(boxer[1]);
    pq.push(boxer[2]);
    Boxer b = pq.top();
    cout<<b.name;
    //result is Rajiv

    return 0;
}

#3


3  

  1. Using greater as comparison function you can use priority queue as min heap,

    使用较大的as比较函数可以使用优先队列作为最小堆,

    #include <bits/stdc++.h>
    
    using namespace std;
    
    int main()
    {
    priority_queue<int,vector<int>,greater<int> >pq;
    pq.push(1);
    pq.push(2);
    pq.push(3);
    
    while(!pq.empty())
    {
        int r = pq.top();
        pq.pop();
        cout<<r<< " ";
    }
    return 0;
    }
    
  2. Inserting value by changing their sign (using minus (-) for positive number and using plus (+) for negative number we can use priority queue in reversed order.

    插入值通过改变符号(使用-(-)表示正数,使用+(+)表示负数,我们可以使用顺序颠倒的优先级队列。

    int main()
    {
    priority_queue<int>pq2;
    pq2.push(-1); //for +1
    pq2.push(-2); //for +2
    pq2.push(-3); //for +3
    pq2.push(4);  //for -4
    
    while(!pq2.empty())
    {
        int r = pq2.top();
        pq2.pop();
        cout<<-r<<" ";
    }
    
    return 0;}
    
  3. For custom data types or classes we need a to tell priority queue a way of knowing on which order it will sort our data.

    对于自定义数据类型或类,我们需要a来告诉优先级队列,以便知道它将对数据排序。

    struct compare
    {
    bool operator()(const int & a, const int & b)
    {
        return a>b;
    }
    };
    
    int main()
    {
    
    priority_queue<int,vector<int>,compare> pq;
    pq.push(1);
    pq.push(2);
    pq.push(3);
    
    while(!pq.empty())
    {
    int r = pq.top();
    pq.pop();
    cout<<r<<" ";
    }
    
    return 0;
    }
    
  4. For custom structure or class you can use priority_queue in any order. Suppose, we want to sort people in descending order according to their salary and if tie then according to their age.

    对于自定义结构或类,可以按任何顺序使用priority_queue。假设,我们想要根据人们的薪水和年龄按降序进行分类。

    struct people
    {
        int age,salary;
    
    };
    struct compare{
    bool operator()(const people & a, const people & b)
        {
            if(a.salary==b.salary)
            {
                return a.age>b.age;
            }
            else
            {
                return a.salary>b.salary;
            }
    
    }
    };
    int main()
    {
    
        priority_queue<people,vector<people>,compare> pq;
        people person1,person2,person3;
        person1.salary=100;
        person1.age = 50;
        person2.salary=80;
        person2.age = 40;
        person3.salary = 100;
        person3.age=40;
    
    
        pq.push(person1);
        pq.push(person2);
        pq.push(person3);
    
        while(!pq.empty())
        {
            people r = pq.top();
            pq.pop();
            cout<<r.salary<<" "<<r.age<<endl;
    }
    
  5. Same result can be obtained by operator overloading :

    操作符重载也可以得到相同的结果:

    struct people
    {
    int age,salary;
    
    bool operator< (const people & p)const
    {
    if(salary==p.salary)
    {
        return age>p.age;
    }
    else
    {
        return salary>p.salary;
    }
    }};
    

    In main function :

    主要功能:

    priority_queue<people> pq;
    people person1,person2,person3;
    person1.salary=100;
    person1.age = 50;
    person2.salary=80;
    person2.age = 40;
    person3.salary = 100;
    person3.age=40;
    
    
    pq.push(person1);
    pq.push(person2);
    pq.push(person3);
    
    while(!pq.empty())
    {
    people r = pq.top();
    pq.pop();
    cout<<r.salary<<" "<<r.age<<endl;
    }
    

#4


2  

You need to provide operator< for that struct. Something like:

您需要为该结构提供操作符<。喜欢的东西:

bool operator<(node const& x, node const& y) {
    return x.count < y.count;
}

Now you can use a priority queue from the standard library.

现在可以使用标准库中的优先级队列。

#5


0  

We can define user defined comparator class:

我们可以定义用户定义的比较器类:

Code Snippet :

#include<bits/stdc++.h>
using namespace std;

struct man
{
  string name;
  int priority; 
};

class comparator
{
 public:
   bool operator()(const man& a, const man& b)
   {
        return a.priority<b.priority;
   }
};

int main()
{
   man arr[5];
   priority_queue<man, vector<man>, comparator> pq;

   for(int i=0; i<3; i++)
   {
     cin>>arr[i].name>>arr[i].priority;
     pq.push(arr[i]);
   }

   while (!pq.empty())
   {
     cout<<pq.top().name<<" "<<pq.top().priority;
     pq.pop();
     cout<<endl;
   }
   return 0;
}

#6


0  

Since C++11, you can write

因为c++ 11,所以你可以写

auto comparer = [](const auto& a, const auto& b) {
    return a.priority < b.priority;
};
std::priority_queue<Item, std::vector<Item>, decltype(comparer)> queue(comparer);

#1


11  

Overload the < operator:

过载 <操作符:< p>

bool operator<(const node& a, const node& b) {
  return a.count > b.count;
}

I have reversed the comparison to achieve min heap wihtout passing extra arguments to the priority queue. Now you use it like this:

我颠倒了比较,以实现最小堆,而不会向优先级队列传递额外的参数。现在你可以这样使用它:

priority_queue<node> pq;
...

Edit: take a look at this post which seems to be almost exact duplicate: STL Priority Queue on custom class

编辑:看看这篇几乎完全相同的文章:自定义类上的STL优先队列

#2


8  

#include <iostream>
#include <queue>
#include <vector>
using namespace std;
class Boxer{
    public:
        string name;
        int strength;
};
struct Comp{
    bool operator()(const Boxer& a, const Boxer& b){
        return a.strength<b.strength;
    }
};
int main(){
    Boxer boxer[3];
    boxer[0].name="uday", boxer[0].strength=23;
    boxer[1].name="manoj", boxer[1].strength=33;
    boxer[2].name="rajiv", boxer[2].strength=53;

    priority_queue< Boxer, vector<Boxer>, Comp> pq;
    pq.push(boxer[0]);
    pq.push(boxer[1]);
    pq.push(boxer[2]);
    Boxer b = pq.top();
    cout<<b.name;
    //result is Rajiv

    return 0;
}

#3


3  

  1. Using greater as comparison function you can use priority queue as min heap,

    使用较大的as比较函数可以使用优先队列作为最小堆,

    #include <bits/stdc++.h>
    
    using namespace std;
    
    int main()
    {
    priority_queue<int,vector<int>,greater<int> >pq;
    pq.push(1);
    pq.push(2);
    pq.push(3);
    
    while(!pq.empty())
    {
        int r = pq.top();
        pq.pop();
        cout<<r<< " ";
    }
    return 0;
    }
    
  2. Inserting value by changing their sign (using minus (-) for positive number and using plus (+) for negative number we can use priority queue in reversed order.

    插入值通过改变符号(使用-(-)表示正数,使用+(+)表示负数,我们可以使用顺序颠倒的优先级队列。

    int main()
    {
    priority_queue<int>pq2;
    pq2.push(-1); //for +1
    pq2.push(-2); //for +2
    pq2.push(-3); //for +3
    pq2.push(4);  //for -4
    
    while(!pq2.empty())
    {
        int r = pq2.top();
        pq2.pop();
        cout<<-r<<" ";
    }
    
    return 0;}
    
  3. For custom data types or classes we need a to tell priority queue a way of knowing on which order it will sort our data.

    对于自定义数据类型或类,我们需要a来告诉优先级队列,以便知道它将对数据排序。

    struct compare
    {
    bool operator()(const int & a, const int & b)
    {
        return a>b;
    }
    };
    
    int main()
    {
    
    priority_queue<int,vector<int>,compare> pq;
    pq.push(1);
    pq.push(2);
    pq.push(3);
    
    while(!pq.empty())
    {
    int r = pq.top();
    pq.pop();
    cout<<r<<" ";
    }
    
    return 0;
    }
    
  4. For custom structure or class you can use priority_queue in any order. Suppose, we want to sort people in descending order according to their salary and if tie then according to their age.

    对于自定义结构或类,可以按任何顺序使用priority_queue。假设,我们想要根据人们的薪水和年龄按降序进行分类。

    struct people
    {
        int age,salary;
    
    };
    struct compare{
    bool operator()(const people & a, const people & b)
        {
            if(a.salary==b.salary)
            {
                return a.age>b.age;
            }
            else
            {
                return a.salary>b.salary;
            }
    
    }
    };
    int main()
    {
    
        priority_queue<people,vector<people>,compare> pq;
        people person1,person2,person3;
        person1.salary=100;
        person1.age = 50;
        person2.salary=80;
        person2.age = 40;
        person3.salary = 100;
        person3.age=40;
    
    
        pq.push(person1);
        pq.push(person2);
        pq.push(person3);
    
        while(!pq.empty())
        {
            people r = pq.top();
            pq.pop();
            cout<<r.salary<<" "<<r.age<<endl;
    }
    
  5. Same result can be obtained by operator overloading :

    操作符重载也可以得到相同的结果:

    struct people
    {
    int age,salary;
    
    bool operator< (const people & p)const
    {
    if(salary==p.salary)
    {
        return age>p.age;
    }
    else
    {
        return salary>p.salary;
    }
    }};
    

    In main function :

    主要功能:

    priority_queue<people> pq;
    people person1,person2,person3;
    person1.salary=100;
    person1.age = 50;
    person2.salary=80;
    person2.age = 40;
    person3.salary = 100;
    person3.age=40;
    
    
    pq.push(person1);
    pq.push(person2);
    pq.push(person3);
    
    while(!pq.empty())
    {
    people r = pq.top();
    pq.pop();
    cout<<r.salary<<" "<<r.age<<endl;
    }
    

#4


2  

You need to provide operator< for that struct. Something like:

您需要为该结构提供操作符<。喜欢的东西:

bool operator<(node const& x, node const& y) {
    return x.count < y.count;
}

Now you can use a priority queue from the standard library.

现在可以使用标准库中的优先级队列。

#5


0  

We can define user defined comparator class:

我们可以定义用户定义的比较器类:

Code Snippet :

#include<bits/stdc++.h>
using namespace std;

struct man
{
  string name;
  int priority; 
};

class comparator
{
 public:
   bool operator()(const man& a, const man& b)
   {
        return a.priority<b.priority;
   }
};

int main()
{
   man arr[5];
   priority_queue<man, vector<man>, comparator> pq;

   for(int i=0; i<3; i++)
   {
     cin>>arr[i].name>>arr[i].priority;
     pq.push(arr[i]);
   }

   while (!pq.empty())
   {
     cout<<pq.top().name<<" "<<pq.top().priority;
     pq.pop();
     cout<<endl;
   }
   return 0;
}

#6


0  

Since C++11, you can write

因为c++ 11,所以你可以写

auto comparer = [](const auto& a, const auto& b) {
    return a.priority < b.priority;
};
std::priority_queue<Item, std::vector<Item>, decltype(comparer)> queue(comparer);