I tried to find out exactly how the boost priority queue is implemented and I am confused.

Header file (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;
}

The output I get is:

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

The order of object creation and deletion does not make sense. How do the internals of the priority queue work, and what is the best practice for them (storing pointers vs storing objects)?

CodePudding user response：

You aren't accounting for the copy-constructor that will automatically be created for your class.

In your case you wouldn't automatically get a move-constructor, but it's still nice to see where the compiler could do a move instead of a copy.

If you change your st to e.g.:

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

you'll get a better picture of what's going on:

// 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

So to break it down:

• 1. pushing the first element
  • your st is constructed and after that copied & moved a few times.
  • it finally ends up in 0x97cec0 (the allocated storage from the heap)
• 2. pushing the second element
  • the second call triggers a resize, so the 44 must be moved to a new allocation
  • the 5 also gets copied & moved a bit
  • the 5 & 44 are swaped into place, so the priority queue is correctly sorted
• 3. empty()
  • does nothing (would return true, because the container contains elements)
  • if you want to delete all elements use clear().
• 4. after main returns
  • y gets destructed
  • the priority queue gets destructed and calls the destructor for both st's

There are no guarantees though how many copies / moves the implementation of boost::heap::priority_queue<st, boost::heap::compare<st_c0>> does, so this might change at any time.

Pointers vs Objects

In general you would use objects whenever they are small and easy to copy / move.

If you use pointers your object won't be copied or moved at all, only the pointer to it, so this would be better if your objects are large and / or expensive to copy / move.

But with bare pointers you also need to delete them manually, if possible i would recommend to use smart pointers instead, e.g.:

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

that way your ``st`'s autmatically get freed & you don't have to manually delete them.