可预先分配空间的 std::priority_queue

william

2024-04-29 约 700 字预计阅读 2 分钟

警告

本文最后更新于 2024-04-29，文中内容可能已过时。

c++ 标准库 <queue> 提供了优先队列 priority_queue，以 log(1) 的算法获取队列头部、并以 log(n) 的算法插入元素。其原型为

1
2
3
4
5


template<
    class T,
    class Container = std::vector<T>,
    class Compare = std::less<typename Container::value_type>
> class priority_queue;

模板

T: 元素类型
Container: 提供以下操作的容器，一般是 std::vector<T>
- front(), e.g., std::vector::front(),
- push_back(), e.g., std::deque::push_back(),
- pop_back(), e.g., std::vector::pop_back().
Compare: 比较元素间大小的运算，可以是 operator()、functor、lambda expression。默认是 std::less，即从大到小排序。

数据成员

std::priority_queue 包含了 protected 的数据成员

c：这个是底层的容器，用于存储元素的内存空间。如果我们使用 std::vector<T> 作为存储容器，则可以通过这个进行预先分配内存空间，以避免在运行时的动态扩张，进而可以提供程序性能。
comp：比较函数

预先分配容器的存储空间

利用 std::priority_queue 里面的容器存储 c（为 protected），我们可以写一个继承类，并提供 reserve 接口。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25


#include <queue>

template <class T,
          class Container = std::vector<T>,
          class Compare = std::less<typename Container::value_type>>
class reservable_priority_queue: public std::priority_queue<T, Container, Compare>
{
public:
    using size_type = typename std::priority_queue<T, Container, Compare>::size_type;

    reservable_priority_queue(size_type capacity = 0)
    {
        reserve(capacity);
    };

    void reserve(size_type capacity)
    {
        this->c.reserve(capacity);
    }

    size_type capacity() const
    {
        return this->c.capacity();
    }
};

完整代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61


#include <queue>
#include <iostream>
using namespace std;

template <class T,
          class Container = std::vector<T>,
          class Compare = std::less<typename Container::value_type>>
class reservable_priority_queue: public std::priority_queue<T, Container, Compare>
{
public:
    using size_type = typename std::priority_queue<T, Container, Compare>::size_type;

    reservable_priority_queue(size_type capacity = 0)
    {
        reserve(capacity);
    };

    void reserve(size_type capacity)
    {
        this->c.reserve(capacity);
    }

    size_type capacity() const
    {
        return this->c.capacity();
    }
};

struct entry_t
{
    int seq {-1};
    double val {.0};
};

struct cmp_t
{
    bool operator()(const entry_t& lhs, const entry_t& rhs)
    {
        return lhs.seq >= rhs.seq;
    }
};

int main()
{
    reservable_priority_queue<entry_t, std::vector<entry_t>, cmp_t> q;
    q.reserve(10000);
    std::cout << q.capacity() << '\n';

    for (int i = 0; i < 10; ++i)
    {
        q.emplace(entry_t{i, i*i*1.0});
    }
    while (!q.empty())
    {
        auto& e = q.top();
        cout << "seq:" << e.seq
             << ", val:" << e.val
             << endl;
        q.pop();
    }
}

测试结果：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14


 g++ pq.cpp -std=c++17
 ./a.out

10000
seq:0, val:0
seq:1, val:1
seq:2, val:4
seq:3, val:9
seq:4, val:16
seq:5, val:25
seq:6, val:36
seq:7, val:49
seq:8, val:64
seq:9, val:81

赞赏

支付宝

微信