0

取自这里http://www.cplusplus.com/reference/queue/priority_queue/

Compare
A binary predicate that takes two elements (of type T) as arguments and returns a bool.
The expression comp(a,b), where comp is an object of this type and a and b are elements in the container, shall return true if a is considered to go before b in the strict weak ordering the function defines.

在编写比较函数时，有什么方法可以告诉哪个元素在队列中等待的时间更长？

假设每当要插入新元素时都会调用 compare 函数，'a' 是否总是新项目而 'b' 是已经在队列中的元素？或者它的工作方式不同？

我的想法是这样的：

bool my_class::operator()(const my_class &a, const my_class &b) {
    //Lower priority comes first
    return (a.get_priority() < b.get_priority());
}

当“a”和“b”的优先级相同时，“b”被赋予优先级，因为它在队列中的时间更长。

感谢您对 std::queue 如何工作以及我如何实现目标的任何反馈。

4

2 回答 2

1

假设每当要插入新元素时都会调用 compare 函数，'a' 是否总是新项目而 'b' 是已经在队列中的元素？或者它的工作方式不同？

正如下面的 Dietmar Kühl 所指出的，当谓词是参数的顺序与插入元素的顺序有任何关系时，不能保证。

当“a”和“b”的优先级相同时，“b”被赋予优先级，因为它在队列中的时间更长。

使用这样的东西：

static unsigned long count = 0;
std::priority_queue<std::pair<my_class,unsigned long>> queue;

当您将项目插入队列时，count也插入前一个并增加它：

queue.push(std::make_pair(obj, count++));

现在count可以用作“时间戳”，所以只需在您的compare函数中执行此操作。

class MyComparator{
public:  
  bool operator()(const std::pair<my_class,unsigned long>& a, const std::pair<my_class,unsigned long>& b)  const
    {
       if (a.first == b.first)
          return a.second < b.second;
       return a.first < b.first;
    }
};

这是一个小例子：

#include <queue>
#include <utility>
#include <vector>
#include <iostream>


class MyComparator{
    public:
      bool operator()(const std::pair<int,unsigned long>& a, const std::pair<int,unsigned long>& b)
        {
           if (a.first == b.first)
              return b.second  < a.second;
           return a.first < b.first;
        }
    };

unsigned long count = 0;
int main()
{
        std::priority_queue<std::pair<int,unsigned long>, std::vector<std::pair<int, unsigned long> >, MyComparator> queue;

        queue.push(std::make_pair(4, count++));
        queue.push(std::make_pair(4, count++));
        queue.push(std::make_pair(5, count++));
        queue.push(std::make_pair(3, count++));

        while(queue.size() > 0)
        {
                std::cout << "[" << queue.top().first << ", " << queue.top().second << "]" << std::endl;
                queue.pop();
        }

        return 0;

}

输出：

[5, 2]
[4, 0]
[4, 1]
[3, 3]
于 2013-09-16T08:35:59.487 回答
0

为对象保留一个时间戳，并在对象插入队列时设置它。然后只需使用该时间戳作为比较条件的一部分。

于 2013-09-16T08:30:53.013 回答