C++ move()函数及priority_queue队列使用记录

简介

priority_queue 是一个拥有权值观念的 queue，它允许加入新的元素、移除旧的元素、查看 priority_queue 中权值之最的元素等功能。priority_queue 只允许在底端加入元素，并从顶端取出元素，除此之外没有其它存取元素的途径。

priority_queue 提供常数时间的最大元素(默认)查找，对数代价的插入与释放。可为用户提供的 compare 更改顺序，例如，用 std::greater<T> 将导致最小元素作为 top() 出现。用 priority_queue 工作类似管理某些随机访问容器中的堆，优势是不可能突然把堆非法化。

虽然priority_queue 的名字中带有 queue，但是其底层的逻辑结构是堆。缺省情况下 priority_queue 利用一个大顶堆完成(底层存储结构是 vector)。堆结构能满足 priority_queue 所需要的”按照权值高低自动排序”的特性。这里要弄清楚的一点是：priority_queue 底层缺省使用 vector存 储数据，这是它的存储结构。而在逻辑上，它将序列视为一颗完全二叉树的顺序存储结构，利用完全二叉树中双亲结点和孩子结点之间的关系，在当前无序区间中选择关键字最大(或最小)的元素。

最近刷leetcode题，使用了move()函数及优先队列（堆）priority_queue数据结构，记录一下！

1.move函数

move(obj)函数的功能是把obj当做右值处理，可以应用在对象的移动上。

右值引用

为了支持移动操作，新标准引入了一种新的引入类型——右值引用，所谓右值引用就是必须绑定到右值的引用。通过&&而不是&来获得右值引用。

注意，如果仅仅是定义右值引用，那么obj本身不会被移走，在作为参数时会发生obj被移走：如下：

string str = "test";
    string&& r = move(str);
    cout<< r <<endl;
    cout<< str <<endl;
    string t(r);
    cout<< t <<endl;
    cout<< str <<endl;

运行结果：

 这时候r和str都可以使用。

但是，若左值不使用右值引用，move则会销毁变量obj，之后都不能使用它，如：

string str = "test";
    string&& r = move(str);
    cout<< r <<endl;
    cout<< str <<endl;
    string t(move(r));
    cout<< t <<endl;
    cout<< str <<endl;

结果为：

 2.priority_queue队列

优先队列是一种容器适配器，采用了堆这样的数据结构，保证了第一个元素总是整个优先队列中最大的(或最小的)元素。

优先队列默认使用vector作为底层存储数据的容器，在vector上使用了堆算法将vector中的元素构造成堆的结构，所以其实我们就可以把它当作堆，凡是需要用堆的位置，都可以考虑优先队列。

STL 中，priority_queue 容器适配器的定义如下：

template <typename T,
        typename Container=std::vector<T>,
        typename Compare=std::less<T> >
class priority_queue{
    //......
}

priority_queue 容器适配器模板类最多可以传入 3 个参数，它们各自的含义如下：
typename T：指定存储元素的具体类型；
typename Container：指定 priority_queue 底层使用的基础容器，默认使用 vector 容器。(STL 序列式容器中只有 vector 和 deque 容器符合条件。)

typename Compare：指定容器中评定元素优先级所遵循的排序规则，默认使用std::less按照元素值从大到小进行排序，还可以使用std::greater按照元素值从小到大排序，但更多情况下是使用自定义的排序规则。

使用优先队列创建大、小堆

//大根堆
priority_queue<int, std::deque<int>, std::greater<int>> values;
//默认是大根堆
priority_queue<int>values;
//小根堆
priority_queue<int, std::vector<int>, std::less<int>>values;

作为队列有其队列的成员函数

使用优先队列，可以维护好最大/最小值；以及一些其他规则的一些比较（这个需要进行重载，目前还没遇到）。

插入堆的时间复杂度最大为O(nlogn)。