快捷導(dǎo)航

C++中STL的優(yōu)先隊(duì)列priority_queue詳解

更新時(shí)間：2023年08月23日 10:03:14 作者：吃代碼的喵醬-i

這篇文章主要介紹了C++中STL的優(yōu)先隊(duì)列priority_queue詳解,今天講一講優(yōu)先隊(duì)列(priority_queue),實(shí)際上,它的本質(zhì)就是一個(gè)heap,我從STL中扒出了它的實(shí)現(xiàn)代碼,需要的朋友可以參考下

淺談C++ STL中的優(yōu)先隊(duì)列(priority_queue)

首先函數(shù)在頭文件中，歸屬于命名空間std，使用的時(shí)候需要注意。

隊(duì)列有兩種常用的聲明方式：

std::priority_queue<T> pq;
std::priority_queue<T, std::vector<T>, cmp> pq;

第一種實(shí)現(xiàn)方式較為常用，接下來(lái)我給出STL中的對(duì)應(yīng)聲明，再加以解釋。

template<class _Ty,
    class _Container = vector<_Ty>,
    class _Pr = less<typename _Container::value_type> >
    class priority_queue

大家可以看到，默認(rèn)模板有三個(gè)參數(shù)，第一個(gè)是優(yōu)先隊(duì)列處理的類(lèi)，第二個(gè)參數(shù)比較有特點(diǎn)，是容納優(yōu)先隊(duì)列的容器。

實(shí)際上，優(yōu)先隊(duì)列是由這個(gè)容器+C語(yǔ)言中關(guān)于heap的相關(guān)操作實(shí)現(xiàn)的。

這個(gè)容器默認(rèn)是vector，也可以是dequeue，因?yàn)楹笳吖δ芨鼜?qiáng)大，而性能相對(duì)于vector較差，考慮到包裝在優(yōu)先隊(duì)列后，后者功能并不能很好發(fā)揮，所以一般選擇vector來(lái)做這個(gè)容器。

第三個(gè)參數(shù)比較重要，支持一個(gè)比較結(jié)構(gòu)，默認(rèn)是less，默認(rèn)情況下，會(huì)選擇第一個(gè)參數(shù)決定的類(lèi)的<運(yùn)算符來(lái)做這個(gè)比較函數(shù)。

接下來(lái)開(kāi)始坑爹了，雖然用的是less結(jié)構(gòu)，然而，隊(duì)列的出隊(duì)順序卻是greater的先出！

就是說(shuō)，這里這個(gè)參數(shù)其實(shí)很傲嬌，表示的意思是如果!cmp，則先出列，不管這樣實(shí)現(xiàn)的目的是啥，大家只能接受這個(gè)實(shí)現(xiàn)。

實(shí)際上，這里的第三個(gè)參數(shù)可以更換成greater，像下面這樣：

std::priority_queue<T, std::vector<T>, greater<T>> pq;

一般大家如果是自定義類(lèi)就干脆重載<號(hào)時(shí)注意下方向了，沒(méi)人在這里麻煩，這個(gè)選擇基本上是在使用int類(lèi)還想小值先出列時(shí)。

從上面的剖析我們也就知道了，想要讓自定義類(lèi)能夠使用優(yōu)先隊(duì)列，我們要重載小于號(hào)。

class Student
{
    int id;
    char name[20];
    bool gender;
    bool operator < (Student &a) const
    {
        return id > a.id;
    }
};

就拿這個(gè)例子說(shuō)，我們想讓id小的先出列，怎么辦，就要很違和的給這個(gè)小于符號(hào)重載成實(shí)際上是大于的定義。

如果我們不使用自定義類(lèi)，又要用非默認(rèn)方法去排序怎么辦？

就比如說(shuō)在Dijkstra中，我們當(dāng)然不會(huì)用點(diǎn)的序號(hào)去排列，無(wú)論是正序還是反序，我們想用點(diǎn)到起點(diǎn)的距離這個(gè)值來(lái)進(jìn)行排序，我們?cè)鯓幼瞿兀?/p>

優(yōu)先隊(duì)列默認(rèn)使用的是小于結(jié)構(gòu)，而上文的做法是為我們的自定義類(lèi)去定義新的小于結(jié)構(gòu)來(lái)符合優(yōu)先隊(duì)列，我們當(dāng)然也可以自定義比較結(jié)構(gòu)。

自定義方法以及使用如下，我直接用Dijkstra代碼來(lái)說(shuō)明：

int cost[MAX_V][MAX_V];
int d[MAX_V], V, s;
//自定義優(yōu)先隊(duì)列l(wèi)ess比較函數(shù)
struct cmp
{
    bool operator()(int &a, int &b) const
    {
        //因?yàn)閮?yōu)先出列判定為!cmp，所以反向定義實(shí)現(xiàn)最小值優(yōu)先
        return d[a] > d[b];
    }
};
void Dijkstra()
{
    std::priority_queue<int, std::vector<int>, cmp> pq;
    pq.push(s);
    d[s] = 0;
    while (!pq.empty())
    {
        int tmp = pq.top();pq.pop();
        for (int i = 0;i < V;++i)
        {
            if (d[i] > d[tmp] + cost[tmp][i])
            {
                d[i] = d[tmp] + cost[tmp][i];
                pq.push(i);
            }
        }
    }
}

優(yōu)先隊(duì)列的日常使用，了解上面那些就已經(jīng)足夠。下面給出優(yōu)先隊(duì)列的所有成員函數(shù)的STL實(shí)現(xiàn)方法，希望你看完沒(méi)有一臉臥槽的感覺(jué)。c就是你聲明時(shí)候的那個(gè)vector或者其他容器。

    void push(value_type&& _Val)
        {    // insert element at beginning
        c.push_back(_STD move(_Val));
        push_heap(c.begin(), c.end(), comp);
        }
    template<class... _Valty>
        void emplace(_Valty&&... _Val)
        {    // insert element at beginning
        c.emplace_back(_STD forward<_Valty>(_Val)...);
        push_heap(c.begin(), c.end(), comp);
        }
    bool empty() const
        {    // test if queue is empty
        return (c.empty());
        }
    size_type size() const
        {    // return length of queue
        return (c.size());
        }
    const_reference top() const
        {    // return highest-priority element
        return (c.front());
        }
    void push(const value_type& _Val)
        {    // insert value in priority order
        c.push_back(_Val);
        push_heap(c.begin(), c.end(), comp);
        }
    void pop()
        {    // erase highest-priority element
        pop_heap(c.begin(), c.end(), comp);
        c.pop_back();
        }

到此這篇關(guān)于C++中STL的優(yōu)先隊(duì)列priority_queue詳解的文章就介紹到這了,更多相關(guān)STL的優(yōu)先隊(duì)列內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

您可能感興趣的文章: