C++ 提升优先级队列行为

Question

我试图找出 boost 优先级队列到底是如何实现的，但我很困惑。

头文件（main.hpp）：

#ifndef MAIN_HPP
#define MAIN_HPP

#include <cstddef>
#include <cstdint>
#include <iostream>

#include <boost/heap/priority_queue.hpp>

typedef std::int32_t int32_t;

typedef struct st {
    int32_t num;
    int32_t f;

    st() {
        std::cout << "DEFAULT" << std::endl;
        this->f = 0;
    }

    st(int32_t num) {
        std::cout << "creation\t" << num << std::endl;
        this->num = num;
        this->f = 0;
    }

    ~st() {
        std::cout << "del\t" << num << std::endl;
        f = 1;
    }
} st;

typedef struct st_c0 {
    bool operator()(const st& st0, const st& st1) const {
        return (st0.num > st1.num);
    }
} st_c0;

typedef struct st_c1 {
    bool operator()(const st* st0, const st* st1) const {
        return (st0->num > st1->num);
    }
} st_c1;

#endif

#include "main.hpp"

int main() {
    boost::heap::priority_queue<st, boost::heap::compare<st_c0>> q0;
    boost::heap::priority_queue<st*, boost::heap::compare<st_c1>> q1;
    st y = st(5);
    q0.push(st(44));
    q0.push(y);
    q0.empty();
    std::cout << y.f << std::endl;
    return 0;
}

我得到的输出是：

creation        5
creation        44
del     44
del     44
del     44
del     44
del     44
del     5
del     5
del     5
0
del     5
del     5
del     44

对象创建和删除的顺序没有意义。优先级队列的内部是如何工作的，它们的最佳实践是什么（存储指针与存储对象）？

Answer 1

您没有计算将为您的 class.

自动创建的 copy-constructor

在您的情况下，您不会自动获得移动构造函数，但看到编译器可以在何处进行移动而不是复制仍然很高兴。

如果您将 st 更改为例如：


struct st {
    int32_t num;
    int32_t f;

    st() {
        std::cout << this << "\tctor default" << std::endl;
        this->f = 0;
    }

    st(int32_t num) : num(num), f(0) {
        std::cout << this << "\tctor num\t" << num << std::endl;
    }

    st(st const& other) : num(other.num), f(other.f) {
        std::cout << this << "\tctor copy\t" << num << "\t (from " << &other << ")" << std::endl; 
    }

    st(st&& other): num(other.num), f(other.f) {
        std::cout << this << "\tctor move\t" << num << "\t (from " << &other << ")" << std::endl;
    }

    st& operator=(st const& other) {
        num = other.num;
        f = other.f;
        std::cout << this << "\tassign copy\t" << num << "\t (from " << &other << ")" << std::endl;
        return *this;
    }

    st& operator=(st&& other) {
        num = other.num;
        f = other.f;
        std::cout << this << "\tassign move\t" << num << "\t (from " << &other << ")" << std::endl;
        return *this;
    }

    ~st() {
        std::cout << this << "\tdtor\t\t" << num << std::endl;
    }
};

godbolt example

您将更好地了解正在发生的事情：

// construct y
0x7fffd8f3b1e8  ctor num    5
// call to push(st(44))
0x7fffd8f3b238  ctor num    44
0x7fffd8f3b1b4  ctor copy   44   (from 0x7fffd8f3b238)
0x97cec0        ctor move   44   (from 0x7fffd8f3b1b4)
0x7fffd8f3b1b4  dtor        44
0x7fffd8f3b164  ctor move   44   (from 0x97cec0)
0x7fffd8f3b178  ctor move   44   (from 0x7fffd8f3b164)
0x97cec0        assign move 44   (from 0x7fffd8f3b178)
0x7fffd8f3b178  dtor        44
0x7fffd8f3b164  dtor        44
0x7fffd8f3b238  dtor        44
// call to push(y)
0x7fffd8f3b1b4  ctor copy   5    (from 0x7fffd8f3b1e8)
0x97cee8        ctor move   5    (from 0x7fffd8f3b1b4)
0x97cee0        ctor copy   44   (from 0x97cec0)
0x97cec0        dtor        44
0x7fffd8f3b1b4  dtor        5
0x7fffd8f3b164  ctor move   5    (from 0x97cee8)
0x7fffd8f3b178  ctor move   5    (from 0x7fffd8f3b164)
0x97cee8        assign move 44   (from 0x97cee0)
0x97cee0        assign move 5    (from 0x7fffd8f3b178)
0x7fffd8f3b178  dtor        5
0x7fffd8f3b164  dtor        5
// after main()
0x7fffd8f3b1e8  dtor        5
0x97cee0        dtor        5
0x97cee8        dtor        44

所以分解一下：

1. 压入第一个元素
- 您的 st 已构建，然后复制并移动了几次。
- 它最终在 0x97cec0 中结束（从堆中分配的存储空间）
1. 推动第二个元素
- 第二次调用触发调整大小，因此必须将 44 移动到新分配
- 5 也被复制并移动了一点
- 5 和 44 交换到位，因此优先级队列正确排序
1. empty()
- 什么都不做（会 return 正确，因为容器包含元素）
- 如果要删除所有元素，请使用 clear()。
1. 主要 returns
- y 被破坏
- 优先队列被破坏并为st的

尽管 boost::heap::priority_queue<st, boost::heap::compare<st_c0>> 的实施执行了多少副本/移动，但无法保证，因此这可能随时更改。

指针与对象

一般来说，只要对象很小且易于复制/移动，您就会使用它们。

如果您使用指针，您的对象根本不会被复制或移动，只有指向它的指针，所以如果您的对象很大和/或复制/移动成本很高，这会更好。

但是对于裸指针，您还需要手动 delete 它们，如果可能的话，我建议改用智能指针，例如：

boost::heap::priority_queue<boost::shared_ptr<st>, boost::heap::compare<TODO>> q0;

这样您的 ``st` 就会自动释放并且您不必手动删除它们。

C++ 提升优先级队列行为

C++ Boost Priority Queue Behavior

c++

memory

heap

boost

priority-queue

指针与对象