c++11 标准模板（STL）（std::priority_queue）（四）-Toy模板网

这篇具有很好参考价值的文章主要介绍了c++11 标准模板（STL）（std::priority_queue）（四）。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

适配一个容器以提供优先级队列

std::priority_queue

定义于头文件 <queue>

template<

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

> class priority_queue;

priority_queue 是容器适配器，它提供常数时间的（默认）最大元素查找，对数代价的插入与释出。

可用用户提供的 Compare 更改顺序，例如，用 std::greater<T> 将导致最小元素作为 top() 出现。

用 priority_queue 工作类似管理某些随机访问容器中的堆，优势是不可能突然把堆非法化。

模板形参

T - 存储的元素类型。若 T 与 Container::value_type 不是同一类型则行为未定义。 (C++17 起)

Container

用于存储元素的底层容器类型。容器必须满足序列容器 (SequenceContainer) 的要求，而其迭代器必须满足遗留随机访问迭代器 (LegacyRandomAccessIterator) 的要求。另外，它必须提供拥有通常语义的下列函数：

front()
push_back()
pop_back()

标准容器 std::vector 和 std::deque 满足这些要求。

Compare - 提供严格弱序的比较 (Compare) 类型。

注意比较 (Compare) 形参的定义，使得若其第一参数在弱序中先于其第二参数则返回 true 。但因为 priority_queue 首先输出最大元素，故“先来”的元素实际上最后输出。即队列头含有按照比较 (Compare) 所施加弱序的“最后”元素。

元素访问

访问栈顶元素

std::priority_queue<T,Container,Compare>::top

const_reference top() const;

返回到 priority_queue 顶元素的引用。此元素将在调用 pop() 时被移除。若使用默认比较函数，则返回的元素亦为优先队列中最大的元素。

参数

（无）

返回值

到顶元素的引用，如同以调用 c.front() 获得。

复杂度

常数。

修改器

插入元素，并对底层容器排序

std::priority_queue<T,Container,Compare>::push

void push( const value_type& value );
void push( value_type&& value );		(C++11 起)

推给定的元素 value 到 priority_queue 中。

1) 等效地调用 c.push_back(value); std::push_heap(c.begin(), c.end(), comp);

2) 等效地调用 c.push_back(std::move(value)); std::push_heap(c.begin(), c.end(), comp);

参数

value

要推入的元素值

返回值

（无）

复杂度

对数次比较加 Container::push_back 的复杂度。

删除栈顶元素

std::priority_queue<T,Container,Compare>::pop

void pop();

从 priority_queue 移除顶元素。等效地调用 std::pop_heap(c.begin(), c.end(), comp); c.pop_back(); 。

参数

（无）

返回值

（无）

复杂度

对数次比较加 Container::pop_back 的复杂度。

交换内容

std::priority_queue<T,Container,Compare>::swap

void swap( priority_queue& other ) noexcept(/* see below */);

(C++11 起)

交换容器适配器与 other 的内容。等效地调用 using std::swap; swap(c, other.c); swap(comp, other.comp); 。

参数

other

要交换内容的容器适配器

返回值

（无）

示例

noexcept 规定：

noexcept(noexcept(swap(c, other.c)) && noexcept(swap(comp, other.comp)))

上述表达式中，用与 C++17 std::is_nothrow_swappable 特性所用的相同方式查找标识符 swap 。

(C++17 前)

noexcept 规定：

noexcept(std::is_nothrow_swappable<Container>::value && std::is_nothrow_swappable<Compare>::value)

(C++17 起)

复杂度

与底层容器相同（典型地为常数）。

调用示例

#include <iostream>
#include <forward_list>
#include <string>
#include <iterator>
#include <algorithm>
#include <functional>
#include <queue>
#include <deque>
#include <time.h>

using namespace std;

struct Cell
{
    int x;
    int y;

    Cell() = default;
    Cell(int a, int b): x(a), y(b) {}

    Cell &operator +=(const Cell &cell)
    {
        x += cell.x;
        y += cell.y;
        return *this;
    }

    Cell &operator +(const Cell &cell)
    {
        x += cell.x;
        y += cell.y;
        return *this;
    }

    Cell &operator *(const Cell &cell)
    {
        x *= cell.x;
        y *= cell.y;
        return *this;
    }

    Cell &operator ++()
    {
        x += 1;
        y += 1;
        return *this;
    }


    bool operator <(const Cell &cell) const
    {
        if (x == cell.x)
        {
            return y < cell.y;
        }
        else
        {
            return x < cell.x;
        }
    }

    bool operator >(const Cell &cell) const
    {
        if (x == cell.x)
        {
            return y > cell.y;
        }
        else
        {
            return x > cell.x;
        }
    }

    bool operator ==(const Cell &cell) const
    {
        return x == cell.x && y == cell.y;
    }
};

std::ostream &operator<<(std::ostream &os, const Cell &cell)
{
    os << "{" << cell.x << "," << cell.y << "}";
    return os;
}

template<typename _Tp, typename _Sequence = vector<_Tp>,
         typename _Compare  = less<typename _Sequence::value_type> >
void queuePrint(const std::string &name,
                const std::priority_queue<_Tp, vector<_Tp>, _Compare> &queue)
{
    std::cout << name ;
    std::priority_queue<_Tp, vector<_Tp>, _Compare> queuep = queue;
    while (queuep.size() > 0)
    {
        std::cout << queuep.top() << " ";
        queuep.pop();
    }
    std::cout << std::endl;
}

struct Compare
{
    Compare() {}
    bool operator()(const Cell &a, const Cell &b)const
    {
        if (a.x == b.x)
        {
            return a.y < b.y;
        }
        return a.x < b.x;
    }
};

int main()
{
    std::cout << std::boolalpha;

    std::mt19937 g{std::random_device{}()};
    srand((unsigned)time(NULL));

    auto generate = []()
    {
        int n = std::rand() % 10 + 110;
        Cell cell{n, n};
        return cell;
    };

    std::vector<Cell> vector1(6);
    std::generate(vector1.begin(), vector1.end(), generate);
    std::cout << "vector1:  ";
    std::copy(vector1.begin(), vector1.end(), std::ostream_iterator<Cell>(std::cout, " "));
    std::cout << std::endl;

    //2) 以 cont 的内容复制构造底层容器 c 。
    std::priority_queue<Cell> queue1(std::less<Cell>(), vector1);

    while (!queue1.empty())
    {
        //返回到 priority_queue 顶元素的引用。
        //此元素将在调用 pop() 时被移除。
        //若使用默认比较函数，则返回的元素亦为优先队列中最大的元素。
        //const_reference
        std::cout << "queue1.front() before: " << queue1.top() << " ";
        //从 queue 移除顶元素。等效地调用 c.pop_back()
        queue1.pop();
        std::cout << std::endl;
    }
    std::cout << std::endl;

    std::priority_queue<Cell> queue2;
    int index = 0;
    while (index < 6)
    {
        Cell cell = generate();
        if (queue2.size() % 2 == 0)
        {
            //推给定的元素 value 到 queue 尾。
            //1) 等效地调用 c.push_back(value)
            queue2.push(cell);
        }
        else
        {
            //推给定的元素 value 到 queue 尾。
            //2) 等效地调用 c.push_back(std::move(value)),移动语义
            queue2.push(std::move(cell));
        }
        std::cout << "queue2.top() : " << queue2.top() ;
        queue2.pop();
        std::cout << std::endl;
        index++;
    }
    std::cout << std::endl;

    std::priority_queue<Cell> queue3;
    index = 0;
    while (index < 6)
    {
        int n = std::rand() % 10 + 110;
        //推入新元素到 queue 结尾。原位构造元素，即不进行移动或复制操作。
        //以与提供给函数者准确相同的参数调用元素的构造函数。
        //等效地调用 c.emplace_back(std::forward<Args>(args)...);
        queue3.emplace(n, n);
        std::cout << "queue3.front() : " << queue3.top() ;
        std::cout << std::endl;
        queue3.pop();
        index++;
    }
    std::cout << std::endl;

    std::vector<Cell> vector2(6);
    std::generate(vector2.begin(), vector2.end(), generate);
    std::cout << "vector2:  ";
    std::copy(vector2.begin(), vector2.end(), std::ostream_iterator<Cell>(std::cout, " "));
    std::cout << std::endl;
    std::vector<Cell> vector3(6);
    std::generate(vector3.begin(), vector3.end(), generate);
    std::cout << "vector3:  ";
    std::copy(vector3.begin(), vector3.end(), std::ostream_iterator<Cell>(std::cout, " "));
    std::cout << std::endl;
    std::cout << std::endl;

    std::priority_queue<Cell> queue4(std::less<Cell>(), vector2);
    std::priority_queue<Cell> queue5(std::less<Cell>(), vector3);
    std::cout << "swap before:  " << std::endl;
    queuePrint("queue4:   ", queue4);
    queuePrint("queue5:   ", queue5);
    //交换容器适配器与 other 的内容。
    //等效地调用 using std::swap; swap(c, other.c);
    queue4.swap(queue5);
    std::cout << "swap after:  " << std::endl;
    queuePrint("queue4:   ", queue4);
    queuePrint("queue5:   ", queue5);

    return 0;
}