deque中的修改類接口
由于deque是雙端隊(duì)列,所以有頭插頭刪和尾插尾刪操作。
下面的棧和隊(duì)列的底層都是通過(guò)的deque實(shí)現(xiàn)的。
為什么要用deque作為其底層數(shù)據(jù)結(jié)構(gòu)呢?
主要是因?yàn)椋簵:完?duì)列都只需在一頭進(jìn)行操作,故不需要迭代器,只要具有pushback和popback的功能即可,在元素增長(zhǎng)時(shí)deque比vector效率更高、內(nèi)存使用率高,所以用deque作為底層數(shù)據(jù)結(jié)構(gòu)更合適。
讓客戶滿意是我們工作的目標(biāo),不斷超越客戶的期望值來(lái)自于我們對(duì)這個(gè)行業(yè)的熱愛(ài)。我們立志把好的技術(shù)通過(guò)有效、簡(jiǎn)單的方式提供給客戶,將通過(guò)不懈努力成為客戶在信息化領(lǐng)域值得信任、有價(jià)值的長(zhǎng)期合作伙伴,公司提供的服務(wù)項(xiàng)目有:域名注冊(cè)、雅安服務(wù)器托管、營(yíng)銷軟件、網(wǎng)站建設(shè)、宜陽(yáng)網(wǎng)站維護(hù)、網(wǎng)站推廣。
根據(jù)文檔里的內(nèi)容我們可以看到stack中有這些接口。
在使用時(shí)要包含stack頭文件
因?yàn)槠涞讓邮怯胐eque實(shí)現(xiàn)的:所以有關(guān)它的模擬實(shí)現(xiàn)也就是對(duì)deque的一個(gè)封裝。
例如:
template<class T,class Container=deque<T>>
class stack//棧
{
public:
stack()
{
}
void push(const T&data)
{
_con.push_back(data);
}
private:
Container _con;
}
注意隊(duì)列不同的是由front和back操作,分別是隊(duì)首和隊(duì)尾元素。
底層使用堆實(shí)現(xiàn)的!
創(chuàng)建優(yōu)先隊(duì)列的默認(rèn)是按照大堆(比較參數(shù)是less)方式!也就是說(shuō)每個(gè)根節(jié)點(diǎn)都大于它的孩子節(jié)點(diǎn)。
對(duì)于內(nèi)置類型可以直接使用greater比較器,但是對(duì)于自定義類型需要提供比較器規(guī)則并在自定義類型中增加> 、<等比較規(guī)則
構(gòu)造函數(shù):std::priority_queue<int, std::vector<int>, std::greater<int> >
third (myints,myints+4);
上例是構(gòu)造了一個(gè)小堆類型的優(yōu)先級(jí)隊(duì)列
它的模板參數(shù)列表:template<class T, class Container=vector<T>, class Compare=less<T>>
所以如果想要用小堆創(chuàng)建對(duì)象時(shí)要把第三個(gè)參數(shù)改為great。
這里我們把庫(kù)函數(shù)中的less這個(gè)函數(shù)拿來(lái)看一下:
template<class _Ty = void>
struct less
: public binary_function<_Ty, _Ty, bool>
{ // functor for operator<
bool operator()(const _Ty& _Left, const _Ty& _Right) const
{ // apply operator< to operands
return (_Left < _Right);
}
};
如果在優(yōu)先級(jí)隊(duì)列內(nèi)存放自定義類型數(shù)據(jù),需要需要用戶提供<、>的重載,有時(shí)也要對(duì)提供比較器規(guī)則,參考less和greater在庫(kù)函數(shù)中的實(shí)現(xiàn),即對(duì)()進(jìn)行重載。
模擬實(shí)現(xiàn)優(yōu)先級(jí)隊(duì)列:
namespace mine
{
template <class T, class Container = vector<T>, class Compare = less<T>>//默認(rèn)(less)創(chuàng)建的是大堆
class priority_queue
{
public:
priority_queue()
:c()
{}
template<class Iterator>
priority_queue(Iterator first, Iterator last)//區(qū)間構(gòu)造,將root進(jìn)行向下調(diào)整
: c(first, last)
{
// 將c中的元素調(diào)整成堆的結(jié)構(gòu)
int count = c.size();
int root = ((count - 2) >> 1);
for (; root >= 0; root--)
AdjustDown(root);
}
void push(const T & data)
{
c.push_back(data);
AdjustUP(c.size()-1);//傳入下標(biāo)
}
void pop()//頭刪的話先將頭元素與最后一個(gè)元素交換,把最后一個(gè)元素刪掉后再執(zhí)行向下排序
{
if (empty())
return;
else
{
swap(c.front(), c.back());
c.pop_back();
AdjustDown(0);
}
}
int size()const
{
return c.size();
}
bool empty()const
{
return c.empty();
}
const T & top()const
{
return c.front();
}
private:
//這里的向上調(diào)整和向下調(diào)整都是大堆模式
void AdjustDown(int parent)//向下調(diào)整算法,把較小元素調(diào)整下去
{
int child = parent * 2 + 1;//child代表下標(biāo)
while (child < c.size())
{
//找到以parent為根的較大的孩子
//如果根有右孩子并且左孩子比右孩子小,讓child等于右孩子
//即child此時(shí)為較大的孩子
if (child + 1 < c.size() && com(c[child], c[child + 1]))
{
child = child + 1;
}
//如果孩子節(jié)點(diǎn)比父親節(jié)點(diǎn)大則交換
if (com(c[parent], c[child]))
{
swap(c[child], c[parent]);
parent = child;
child = parent * 2 + 1;
}
else
return;
}
}
void AdjustUP(int child)//向上調(diào)整算法,將較大元素調(diào)整上去
{
int parent = (child - 1) >> 1;
while (child)//沒(méi)有到根的話繼續(xù)循環(huán)
{
//如果父親節(jié)點(diǎn)比孩子節(jié)點(diǎn)小,交換
//將較大節(jié)點(diǎn)調(diào)整到根位置
if (com(c[parent], c[child]))
{
swap(com(c[parent], c[child]));
child = parent;
parent = (child - 1) >> 1;
}
else
{
return;
}
}
}
private:
Container c;
Compare com;
};
}
這里最重要的就是向上調(diào)整和向下調(diào)整算法,同時(shí)也要注意比較規(guī)則在其中的用法。詳細(xì)過(guò)程見(jiàn)代碼注釋。
網(wǎng)站名稱:STL中有關(guān)deque、stack、queue、priority_queue
分享鏈接:http://muchs.cn/article34/jpispe.html
成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián),為您提供網(wǎng)站排名、網(wǎng)站營(yíng)銷、ChatGPT、網(wǎng)站策劃、營(yíng)銷型網(wǎng)站建設(shè)、外貿(mào)網(wǎng)站建設(shè)
聲明:本網(wǎng)站發(fā)布的內(nèi)容(圖片、視頻和文字)以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主,如果涉及侵權(quán)請(qǐng)盡快告知,我們將會(huì)在第一時(shí)間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng),如需處理請(qǐng)聯(lián)系客服。電話:028-86922220;郵箱:631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載,或轉(zhuǎn)載時(shí)需注明來(lái)源: 創(chuàng)新互聯(lián)