std::std::priority_queue 稳定吗？

Question

std::priority_queue

稳定吗？
即，具有相同优先级的元素是否按照与容器输入到队列中的顺序相同的顺序从队列中弹出？

Answer 1

不。试试这个：

#include <iostream>
#include <queue>

int main() {

    struct s { public: int x, y; };
    auto cmp = [](const s& s1, const s& s2) { return s1.x > s2.x; };
    std::priority_queue<s, std::vector<s>, decltype(cmp)> q(cmp);
    q.push({ 2, 1 });
    q.push({ 1, 1 });
    q.push({ 1, 2 });
    q.push({ 1, 3 });
    q.push({ 1, 2 });
    q.push({ 1, 1 });

    for (; !q.empty(); q.pop())
        std::cout << '(' << q.top().x << ", " << q.top().y << ')' << std::endl;
}

结果：

(1, 1)
(1, 2)
(1, 1)
(1, 2)
(1, 3)
(2, 1)