std::priority_queue::priority_queue

来自cppreference.com
(1)
explicit priority_queue( const Compare& compare = Compare(),
                         const Container& cont = Container() );
(C++11 前)
priority_queue( const Compare& compare, const Container& cont );
(C++11 起)
explicit priority_queue( const Compare& compare = Compare(),
                         Container&& cont = Container() );
(2) (C++11 起)
priority_queue( const priority_queue& other );
(3)
priority_queue( priority_queue&& other );
(4) (C++11 起)
template< class Alloc >
explicit priority_queue( const Alloc& alloc );
(5) (C++11 起)
template< class Alloc >
priority_queue( const Compare& compare, const Alloc& alloc );
(6) (C++11 起)
template< class Alloc >

priority_queue( const Compare& compare, const Container& cont,

                const Alloc& alloc );
(7) (C++11 起)
template< class Alloc >

priority_queue( const Compare& compare, Container&& cont,

                const Alloc& alloc );
(8) (C++11 起)
template< class Alloc >
priority_queue( const priority_queue& other, const Alloc& alloc );
(9) (C++11 起)
template< class Alloc >
priority_queue( priority_queue&& other, const Alloc& alloc );
(10) (C++11 起)
template< class InputIt >

priority_queue( InputIt first, InputIt last,

                const Compare& compare, const Container& cont );
(11) (C++11 起)
template< class InputIt >

priority_queue( InputIt first, InputIt last,
                const Compare& compare = Compare(),

                Container&& cont = Container() );
(12) (C++11 起)

从各种数据源构造容器适配器的新底层容器。

@1以 cont 的内容复制构造底层容器 c 。以 compare 的内容复制构造比较函数对象 comp 。调用 std::make_heap(c.begin(), c.end(), comp)此亦为默认构造函数。 (C++11 前)

2)std::move(cont) 移动构造底层容器 c 。以 comp 的内容复制构造比较函数 compare 。调用 std::make_heap(c.begin(), c.end(), comp)此亦为默认构造函数。 (C++11 起)
3) 复制构造函数。以 other.c 的内容复制构造适配器。以 other.comp 构造比较函数对象。(隐式声明)
4) 移动构造函数。以 std::move(other.c) 构造适配器,以 std::move(other.comp) 构造比较函数对象。(隐式声明)
5-10) 仅若 std::uses_allocator<container_type, Alloc>::value == true ,即若底层容器是具分配器容器(对所有标准库容器为 true )才定义下列构造函数。
5)alloc 为分配器构造底层容器。等效地调用 c(alloc) 。值初始化 comp
6)alloc 为分配器构造底层容器。等效地调用 c(alloc) 。从 compare 复制构造 comp
7)alloc 为分配器,构造拥有 cont 内容的底层容器,如同以 c(cont, alloc) 。从 compare 复制构造 comp 。然后调用 std::make_heap(c.begin(), c.end(), comp)
8)alloc 为分配器,用移动语义构造拥有 cont 内容的底层容器,如同以 c(std::move(cont), alloc) 。从 compare 复制构造 comp 。然后调用 std::make_heap(c.begin(), c.end(), comp)
9) 构造拥有 other.c 内容的底层容器,并以 alloc 为分配器。等效地调用 c(other.c, alloc) 。从 other.comp 复制构造 comp
10) 用移动语义构造拥有 other 内容的适配器,同时以 alloc 为分配器。等效地调用 c(std::move(other.c), alloc) 。从 other.comp 移动构造 comp
11)cont 复制构造 c ,从 compare 复制构造 comp 。然后调用 c.insert(c.end(), first, last); ,再调用 std::make_heap(c.begin(), c.end(), comp);
12)std::move(cont) 移动构造 c ,从 std::move(compare) 移动构造 comp 。然后调用 c.insert(c.end(), first, last); ,再调用 std::make_heap(c.begin(), c.end(), comp);

目录

[编辑] 参数

alloc - 用于底层容器所有内存分配的分配器
other - 用作源初始化底层容器的另一容器适配器
cont - 用作源初始化底层容器的容器
compare - 用于初始化底层比较函数对象的比较函数对象
first, last - 要初始化的元素范围
类型要求
-
Alloc 必须满足 Allocator 的要求。
-
Container 必须满足 Container 的要求。仅若 Container 满足具分配器容器 (AllocatorAwareContainer) 的要求才定义构造函数 (5-10)
-
InputIt 必须满足 InputIterator 的要求。

[编辑] 复杂度

1,3) O(N) 次比较,其中 Ncont.size()
另外,调用 O(N)value_type 的构造函数,其中 Ncont.size()
2) {math|O(N)}} 次比较,其中 Ncont.size()
4-6) 常数。
7) O(N) 次比较,其中 Ncont.size()
另外,调用 O(N)value_type 的构造函数,其中 Ncont.size()
8) O(N) 次比较,其中 Ncont.size()
9)other 的大小成线性。
10) 常数。
11) O(N) 次比较,其中 Ncont.size() + std::distance(first, last)
另外,调用 O(N)value_type 的构造函数,其中 Ncont.size()
12) O(N) 次比较,其中 Ncont.size() + std::distance(first, last)

[编辑] 示例

#include <queue>
#include <vector>
#include <iostream>
#include <functional>
 
int main()
{
    std::priority_queue<int> c1;
    c1.push(5);
    std::cout << c1.size() << '\n';
 
    std::priority_queue<int> c2(c1);
    std::cout << c2.size() << '\n';
 
    std::vector<int> vec={3, 1, 4, 1, 5};
    std::priority_queue<int> c3(std::less<int>(), vec);
    std::cout << c3.size() << '\n';
}

输出:

1
1
5

[编辑] 带定制比较器的示例

#include <iostream>
#include <queue>
#include <vector>
#include <utility>
 
using my_pair_t = std::pair<size_t,bool>;
 
using my_container_t = std::vector<my_pair_t>;
 
int main()
{
    auto my_comp =
        [](const my_pair_t& e1, const my_pair_t& e2) 
        { return e1.first > e2.first; };
    std::priority_queue<my_pair_t,
                        my_container_t,
                        decltype(my_comp)> queue(my_comp);
    queue.push(std::make_pair(5, true));
    queue.push(std::make_pair(3, false));
    queue.push(std::make_pair(7, true));
    std::cout << std::boolalpha;
    while(!queue.empty()) 
    {
        const auto& p = queue.top();
        std::cout << p.first << " " << p.second << "\n";
        queue.pop();
    }
}

输出:

3 false
5 true
7 true

[编辑] 参阅

赋值给容器适配器
(公开成员函数) [编辑]