开发者

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

目录
  • 简介
  • 1.move函数
    • 右值引用
  •  2.priority_queue队列

    简介

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

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

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

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

    1.move函数

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

    右值引用

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

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

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

    运行结果:

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

     这时候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;

    结果为:

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

     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;

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

    成员函数功能
    empty()如果 priority_queue 为空的话,返回 true;反之,返回 false。
    size()返回 priority_queue 中存储元素的个数。
    top()返回 priority_queue 中第一个元素的引用形式
    push(const T& obj)根据既定的排序规则,将元素 obj 的副本存储到 priority_queue 中适当的位置。
    push(T&& obj)根据既定的排序规则,将元素 obj 移动存储到 priority_queue 中适当的位置。
    emplace(Args&&… args)Args&&… args 表示构造一个存储类型的元素所需要的数据(对于类对象来说,可能需要多个数据构造出一个对象)。此函数的功能是根据既定的排序规则,在容器适配器适当的位置直接生成该新元素。
    swap(priority_queue& other)将两个 priority_queue 容器适配器中的元素进行互换,需要注意的是,进行互换的 2 个 priority_queue 容器适配器中存储的元素类型以及底层采用的基础容器类型,都必须相同
    pop()移除 priority_queue 容器适配器中第一个元素。

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

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

    到此这篇关于C++ move()函数及priority_queue队列使用记录的文章就介绍到这了,更多相关C++ move()函数及priority_queue队列内容请搜索我们以前的文章或继续浏览下面的相开发者_JS教程关文章希望大家以后多多支持我们!

    0

    上一篇:

    下一篇:

    精彩评论

    暂无评论...
    验证码 换一张
    取 消

    最新开发

    开发排行榜