簡(jiǎn)介

priority_queue 是一個(gè)擁有權(quán)值觀念的 queue，它允許加入新的元素、移除舊的元素、查看 priority_queue 中權(quán)值之最的元素等功能。priority_queue 只允許在底端加入元素，并從頂端取出元素，除此之外沒有其它存取元素的途徑。

priority_queue 提供常數(shù)時(shí)間的最大元素(默認(rèn))查找，對(duì)數(shù)代價(jià)的插入與釋放。可為用戶提供的 compare 更改順序，例如，用 std::greater<T> 將導(dǎo)致最小元素作為 top() 出現(xiàn)。用 priority_queue 工作類似管理某些隨機(jī)訪問容器中的堆，優(yōu)勢(shì)是不可能突然把堆非法化。

雖然priority_queue 的名字中帶有 queue，但是其底層的邏輯結(jié)構(gòu)是堆。缺省情況下 priority_queue 利用一個(gè)大頂堆完成(底層存儲(chǔ)結(jié)構(gòu)是 vector)。堆結(jié)構(gòu)能滿足 priority_queue 所需要的”按照權(quán)值高低自動(dòng)排序”的特性。這里要弄清楚的一點(diǎn)是：priority_queue 底層缺省使用 vector存 儲(chǔ)數(shù)據(jù)，這是它的存儲(chǔ)結(jié)構(gòu)。而在邏輯上，它將序列視為一顆完全二叉樹的順序存儲(chǔ)結(jié)構(gòu)，利用完全二叉樹中雙親結(jié)點(diǎn)和孩子結(jié)點(diǎn)之間的關(guān)系，在當(dāng)前無序區(qū)間中選擇關(guān)鍵字最大(或最小)的元素。

最近刷leetcode題，使用了move()函數(shù)及優(yōu)先隊(duì)列（堆）priority_queue數(shù)據(jù)結(jié)構(gòu)，記錄一下！

1.move函數(shù)

move(obj)函數(shù)的功能是把obj當(dāng)做右值處理，可以應(yīng)用在對(duì)象的移動(dòng)上。

右值引用

為了支持移動(dòng)操作，新標(biāo)準(zhǔn)引入了一種新的引入類型——右值引用，所謂右值引用就是必須綁定到右值的引用。通過&&而不是&來獲得右值引用。

注意，如果僅僅是定義右值引用，那么obj本身不會(huì)被移走，在作為參數(shù)時(shí)會(huì)發(fā)生obj被移走：如下：

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

運(yùn)行結(jié)果：

 這時(shí)候r和str都可以使用。

但是，若左值不使用右值引用，move則會(huì)銷毀變量obj，之后都不能使用它，如：

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

結(jié)果為：

 2.priority_queue隊(duì)列

優(yōu)先隊(duì)列是一種容器適配器，采用了堆這樣的數(shù)據(jù)結(jié)構(gòu)，保證了第一個(gè)元素總是整個(gè)優(yōu)先隊(duì)列中最大的(或最小的)元素。

優(yōu)先隊(duì)列默認(rèn)使用vector作為底層存儲(chǔ)數(shù)據(jù)的容器，在vector上使用了堆算法將vector中的元素構(gòu)造成堆的結(jié)構(gòu)，所以其實(shí)我們就可以把它當(dāng)作堆，凡是需要用堆的位置，都可以考慮優(yōu)先隊(duì)列。

STL 中，priority_queue 容器適配器的定義如下：

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

priority_queue 容器適配器模板類最多可以傳入 3 個(gè)參數(shù)，它們各自的含義如下：
typename T：指定存儲(chǔ)元素的具體類型；
typename Container：指定 priority_queue 底層使用的基礎(chǔ)容器，默認(rèn)使用 vector 容器。(STL 序列式容器中只有 vector 和 deque 容器符合條件。)

typename Compare：指定容器中評(píng)定元素優(yōu)先級(jí)所遵循的排序規(guī)則，默認(rèn)使用std::less按照元素值從大到小進(jìn)行排序，還可以使用std::greater按照元素值從小到大排序，但更多情況下是使用自定義的排序規(guī)則。

使用優(yōu)先隊(duì)列創(chuàng)建大、小堆

//大根堆
priority_queue<int, std::deque<int>, std::greater<int>> values;
//默認(rèn)是大根堆
priority_queue<int>values;
//小根堆
priority_queue<int, std::vector<int>, std::less<int>>values;

作為隊(duì)列有其隊(duì)列的成員函數(shù)

使用優(yōu)先隊(duì)列，可以維護(hù)好最大/最小值；以及一些其他規(guī)則的一些比較（這個(gè)需要進(jìn)行重載，目前還沒遇到）。

插入堆的時(shí)間復(fù)雜度最大為O(nlogn)。

到此這篇關(guān)于C++ move()函數(shù)及priority_queue隊(duì)列使用記錄的文章就介紹到這了,更多相關(guān)C++ move()函數(shù)及priority_queue隊(duì)列內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

最新評(píng)論