logo标签列表

C++优先队列不遵守FIFO顺序。

c++priority-queuefifo
4

我正在使用STL优先队列来收集我自己的类Lettura的对象。

//---------LETTURA----------

enum Priority {zero, standard, urgent};

class Lettura{
public:
int valore;
char sensore;
Priority priorita;

Lettura():  valore(0),sensore('\0'),priorita(zero){}
Lettura(const int val, const char s='\0', const Priority p=zero):  valore(val),sensore(s), priorita(p){}

friend ostream& operator<<(ostream& out, const Lettura & lett);
};

我希望按照“priorita”降序的顺序弹出它们，但我也希望相同优先级的元素像普通队列一样按FIFO原则弹出。但是实际上，我得到的是随机顺序的相同优先级元素：

top: l5  urgent
top: l1  standard
top: l4  standard
top: l6  standard
top: l2  standard
top: l3  standard

我希望同等优先级的元素能按照先进先出(FIFO)的顺序排列:
top: l5  urgent
top: l1  standard
top: l2  standard
top: l3  standard
top: l4  standard
top: l6  standard

这是我的代码：

int main() {
std::priority_queue<Lettura, std::vector<Lettura>, std::less<Lettura> > coda;

Lettura l1(50,'a',standard);
Lettura l2(50,'b',standard);
Lettura l3(120,'c',standard);
Lettura l4(100,'d',standard);
Lettura l5(30,'e',urgent);
Lettura l6(35,'f',standard);

coda.push(l1);
coda.push(l2);
coda.push(l3);
coda.push(l4);
coda.push(l5);
coda.push(l6);


cout<<"top: "<<coda.top()<<"\n";    coda.pop();
cout<<"top: "<<coda.top()<<"\n";    coda.pop();
cout<<"top: "<<coda.top()<<"\n";    coda.pop();
cout<<"top: "<<coda.top()<<"\n";    coda.pop();
cout<<"top: "<<coda.top()<<"\n";    coda.pop();
cout<<"top: "<<coda.top()<<"\n";    coda.pop();
}

我已经实现了以下比较方法：
bool operator<(const Lettura& l1, const Lettura& l2){
return l1.priorita < l2.priorita;
}

bool operator<=(const Lettura& l1, const Lettura& l2){
return l1.priorita <= l2.priorita;
}

我也尝试了不同的队列构造函数，但没有成功:

std::priority_queue<Lettura> coda;
std::priority_queue<Lettura, std::vector<Lettura>, std::less_equal<Lettura> > coda;

有人能帮助我吗？

你展示的是11、12、13、14、15等数值，但是却推送了50、50、100等数值。你使用的是哪些数值？ - Vlad from Moscow
这些不是11、12...而是l1、l2、l3...用'L'而不是'1'。 - Andrea Giusti
4个回答
8

你的代码似乎是能够正常工作的，因为你将紧急项目放在首位。在基于堆的优先队列中，没有按插入时间进行子排序，因此你会以未定义的顺序获取具有相同优先级的项目，除非它们的优先级高于其他项目。你需要添加一个额外的字段，比如放入队列的时间，并在比较操作符中使用该字段和你的优先枚举，以便对项目进行排序。

4
这里有另一种可能的stable_priority_queue实现，它保持了priority_queue提供的相同接口。
template <class T>
struct stable_element
{
    stable_element(T&& o, std::size_t c)
        : object_(std::move(o))
        , insertion_order_(c)
    {
    }
    stable_element(const T& o, std::size_t c)
        : object_(o)
        , insertion_order_(c)
    {
    }
    operator T() { return object_; }

    T object_;
    std::size_t insertion_order_;
};

template <class T>
bool operator<(const stable_element<T>& lhs, const stable_element<T>& rhs)
{
    return (lhs.object_ < rhs.object_) || (!(rhs.object_ < lhs.object_) && (rhs.insertion_order_ < lhs.insertion_order_));
}

template <class T,
          class Container = std::vector<stable_element<T>>,
          class Compare = std::less<typename Container::value_type>>
class stable_priority_queue : public std::priority_queue<stable_element<T>, Container, Compare>
{
    using stableT = stable_element<T>;
    using std::priority_queue<stableT, Container, Compare>::priority_queue;
public:
    const T& top() { return this->c.front().object_; }
    void push(const T& value) {
        this->c.push_back(stableT(value, counter_++));
        std::push_heap(this->c.begin(), this->c.end(), this->comp);
    }
    void push(T&& value) {
        this->c.push_back(stableT(std::move(value), counter_++));
        std::push_heap(this->c.begin(), this->c.end(), this->comp);
    }
    template<class ... Args>
    void emplace(Args&&... args) {
        this->c.emplace_back(T(std::forward<Args>(args)...), counter_++);
        std::push_heap(this->c.begin(), this->c.end(), this->comp);
    }
    void pop() {
        std::pop_heap(this->c.begin(), this->c.end(), this->comp);
        this->c.pop_back();
        if (this->empty()) counter_ = 0;
    }

protected:
    std::size_t counter_ = 0;
};

在std::priority_queue中，有受保护的成员 c 和 comp ，分别对应基础容器和比较函数对象。通过继承自std::priority_queue的这种方法，我们需要修改 top 、 push 、 emplace 和 pop 的行为。每个函数的std::priority_queue文档提供了这些函数在 c 和 comp 成员上执行的操作的实现。这对于使用 stable_element<T>重写修改后的成员函数非常有帮助。
要在OPs用例中使用此stable_priority_queue，我们只需提供一个 bool operator<(const Lettura& l, const Lettura& r) { return l.priorita < r.priorita; }来按所需排序优先级即可。
enum Priority
{
    zero, standard, urgent
};

inline std::ostream& operator <<(std::ostream& os, const Priority& p)
{
    switch (p) {
        case zero:
            os << "zero"; break;
        case standard:
            os << "standard"; break;
        case urgent:
            os << "urgent"; break;
    }
    return os;
}

class Lettura
{
public:
    int      valore;
    char     sensore;
    Priority priorita;

    Lettura()
        : valore(0)
        , sensore('\0')
        , priorita(zero) {}

    Lettura(const int val, const char s = '\0', const Priority p = zero)
        : valore(val)
        , sensore(s)
        , priorita(p) {}

    friend std::ostream& operator <<(std::ostream& out, const Lettura& lett)
    {
        return out << "{ valore: " << lett.valore << ", sensore: " << lett.sensore << ", priorita: " << lett.priorita
                   << " }";
    }
};

bool operator<(const Lettura& l, const Lettura& r)
{
    return l.priorita < r.priorita;
}

int main()
{
    stable_priority_queue<Lettura> coda;

    Lettura l1(50, 'a', standard);
    Lettura l2(50, 'b', standard);
    Lettura l3(120, 'c', standard);
    Lettura l5(30, 'e', urgent);
    Lettura l6(35, 'f', standard);

    coda.push(l1);
    coda.push(l2);
    coda.push(l3);
    coda.emplace(100, 'd', standard);
    coda.emplace(l5);
    coda.emplace(l6);

    while (!coda.empty()) {
        std::cout << "top: " << coda.top() << "\n";
        coda.pop();
    }
}

输出：

top: { valore: 30, sensore: e, priorita: urgent }
top: { valore: 50, sensore: a, priorita: standard }
top: { valore: 50, sensore: b, priorita: standard }
top: { valore: 120, sensore: c, priorita: standard }
top: { valore: 100, sensore: d, priorita: standard }
top: { valore: 35, sensore: f, priorita: standard }

这是一个涉及IT技术的演示，点击此处可以进行实时观看。
你能加上一些解释吗？ - user9478968
1
@ConfusedByCode，我扩展了我的答案。希望现在更清楚了。 - Jon Ringle
0
这是一个稳定优先队列的简单实现。
它尝试通过在队列为空时将插入计数器清零来抵抗排序耗尽的情况：
#include <iostream>
#include <string>
#include <queue>
#include <algorithm>


enum Priority
{
    zero, standard, urgent
};

inline std::ostream& operator <<(std::ostream& os, const Priority& p)
{
    switch (p) {
        case zero:
            return os << "zero";
        case standard:
            return os << "standard";
        case urgent:
            return os << "urgent";
    }
}

class Lettura
{
public:
    int      valore;
    char     sensore;
    Priority priorita;

    Lettura()
        : valore(0)
        , sensore('\0')
        , priorita(zero) {}

    Lettura(const int val, const char s = '\0', const Priority p = zero)
        : valore(val)
        , sensore(s)
        , priorita(p) {}

    friend std::ostream& operator <<(std::ostream& out, const Lettura& lett)
    {
        return out << "{ valore: " << lett.valore << ", sensore: " << lett.sensore << ", priorita: " << lett.priorita
                   << " }";
    }
};


template<class T, class Comp>
struct stable_priority_queue
{
    using counter_type = std::size_t;

    struct Proxy
    {
        Proxy(T&& o, counter_type c)
            : object(std::move(o))
            , insertion_order_(c) {}

        Proxy(const T& o, counter_type c)
            : object(o)
            , insertion_order_(c) {}

        T            object;
        counter_type insertion_order_;
    };

    struct ProxyComp
    {
        bool operator ()(Proxy const& l, Proxy const& r) const
        {
            if (major_order_(l.object, r.object))
                return true;
            if (major_order_(r.object, l.object))
                return false;
            return minor_order_(l.insertion_order_, r.insertion_order_);
        }

        Comp           major_order_;
        std::greater<> minor_order_;
    };


    decltype(auto) push(T item)
    {
        return queue_.emplace(std::move(item), counter_++);
    }

    T const& top() const
    {
        return queue_.top().object;
    }

    void pop()
    {
        queue_.pop();
        if (queue_.empty())
            counter_ = 0;
    }

    std::priority_queue<Proxy, std::vector<Proxy>, ProxyComp> queue_;
    counter_type                                              counter_ = 0;
};

struct lower_priority
{
    bool operator ()(const Lettura& l, const Lettura& r) const
    {
        return l.priorita < r.priorita;
    }
};

int main()
{
    stable_priority_queue<Lettura, lower_priority> coda;

    Lettura l1(50, 'a', standard);
    Lettura l2(50, 'b', standard);
    Lettura l3(120, 'c', standard);
    Lettura l4(100, 'd', standard);
    Lettura l5(30, 'e', urgent);
    Lettura l6(35, 'f', standard);

    coda.push(l1);
    coda.push(l2);
    coda.push(l3);
    coda.push(l4);
    coda.push(l5);
    coda.push(l6);


    std::cout << "top: " << coda.top() << "\n";
    coda.pop();
    std::cout << "top: " << coda.top() << "\n";
    coda.pop();
    std::cout << "top: " << coda.top() << "\n";
    coda.pop();
    std::cout << "top: " << coda.top() << "\n";
    coda.pop();
    std::cout << "top: " << coda.top() << "\n";
    coda.pop();
    std::cout << "top: " << coda.top() << "\n";
    coda.pop();
}

预期结果：

top: { valore: 30, sensore: e, priorita: urgent }
top: { valore: 50, sensore: a, priorita: standard }
top: { valore: 50, sensore: b, priorita: standard }
top: { valore: 120, sensore: c, priorita: standard }
top: { valore: 100, sensore: d, priorita: standard }
top: { valore: 35, sensore: f, priorita: standard }
-4
2
从那个链接中并不明显是编译器的错误还是标准的错误 - 这只是你认为它应该如何工作的观点，我不想在这里深入讨论。无论哪种情况，这都对 OP 没有帮助。 - user2100815
@latedeveloper 这意味着你不了解关于堆（heaps）的算法。这些算法在许多算法书籍中都有详细描述。在谈论算法之前，请先阅读它们。书中描述了如何选择元素。 - Vlad from Moscow
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接