C++容器適配與棧的實(shí)現(xiàn)及dequeque和優(yōu)先級詳解
容器適配器
我們可以看出，棧中沒有空間配置器（內(nèi)存池），而是適配器
適配器是一種設(shè)計(jì)模式(設(shè)計(jì)模式是一套被反復(fù)使用的、多數(shù)人知曉的、經(jīng)過分類編目的、代碼設(shè)計(jì)經(jīng)驗(yàn)的總結(jié))，該種模式是將一個(gè)類的接口轉(zhuǎn)換成客戶希望的另外一個(gè)接口
棧的實(shí)現(xiàn)
#include<vector>
#include<iostream>
using namespace std;
namespace myspace
{
template<class T>
class Stack
{
public:
void push(const T& x)
{
_con.push_back(x);
}
void pop()
{
_con.pop_back();
}
T& top()
{
return _con.back();//back接口訪問尾部的數(shù)據(jù)
}
T& top()const
{
return _con.back();//back接口訪問尾部的數(shù)據(jù)
}
bool empty()
{
return _con.empty();
}
size_t size()const
{
return _con.size();
}
private:
vector<T> _con;
};
}此時(shí)這個(gè)棧并不是適配器，因?yàn)榈讓颖粚懰懒?，底層是用vector實(shí)現(xiàn)的，如果想讓它適配，加上適配器即可
此時(shí)就是適配器
list
注意隊(duì)列不能用vector，編譯會(huì)報(bào)錯(cuò)，因?yàn)椴恢С诸^刪，沒有pop_front
queque實(shí)現(xiàn)
namespace myspace
{
template<class T, class Container = deque<T>>
class queue
{
public:
void push(const T& x)
{
_con.push_back(x);
}
void pop()
{
_con.pop_front();
}
T& back()
{
return _con.back();
}
T& front()
{
return _con.front();
}
const T& back() const
{
return _con.back();
}
const T& front() const
{
return _con.front();
}
bool empty() const
{
return _con.empty();
}
size_t size() const
{
return _con.size();
}
private:
Container _con;
};
}dequeque
我們發(fā)現(xiàn)棧和隊(duì)列都有一個(gè)dequeque
dequeque不是隊(duì)列，是vector和list的結(jié)合體
1.支持任意位置的插入刪除
2.支持隨機(jī)訪問
deque并不是真正連續(xù)的空間，而是由一段段連續(xù)的小空間拼接而成的，實(shí)際deque類似于一個(gè)動(dòng)態(tài)的二維數(shù)組，其底層結(jié)構(gòu)如下圖所示：
雙端隊(duì)列底層是一段假象的連續(xù)空間，實(shí)際是分段連續(xù)的，為了維護(hù)其“整體連續(xù)”以及隨機(jī)訪問的假象，落在了deque的迭代器身上，因此deque的迭代器設(shè)計(jì)就比較復(fù)雜，如下圖所示：
dequeque的缺陷
vector比較，deque的優(yōu)勢是：頭部插入和刪除時(shí)，不需要搬移元素，效率特別高，而且在擴(kuò)容時(shí)，也不需要搬移大量的元素，因此其效率是必vector高的。
與list比較，其底層是連續(xù)空間，空間利用率比較高，不需要存儲(chǔ)額外字段。 但是，deque有一個(gè)致命缺陷：不適合遍歷，因?yàn)樵诒闅v時(shí)，deque的迭代器要頻繁的去檢測其是否移動(dòng)到某段小空間的邊界，導(dǎo)致效率低下（中間的插入刪除效率很低），
而序列式場景中，可能需要經(jīng)常遍歷，因此在實(shí)際中，需要線性結(jié)構(gòu)時(shí)，大多數(shù)情況下優(yōu)先考慮vector和list，deque的應(yīng)用并不多，而目前能看到的一個(gè)應(yīng)用就是，STL用其作為stack和queue的底層數(shù)據(jù)結(jié)構(gòu)
測試之后，dequeque顯然效率低
void test_op()
{
srand(time(0));
const int N = 100000;
vector<int> v;
v.reserve(N);
deque<int> dp;
for (int i = 0; i < N; ++i)
{
auto e = rand();
v.push_back(e);
dp.push_back(e);
}
int begin1 = clock();
sort(v.begin(), v.end());
int end1 = clock();
int begin2 = clock();
sort(dp.begin(), dp.end());
int end2 = clock();
printf("vector sort:%d\n", end1 - begin1);
printf("deque sort:%d\n", end2 - begin2);
}優(yōu)先級隊(duì)列
priority_queque
優(yōu)先級隊(duì)列的底層是堆（二叉樹的堆）
第二個(gè)參數(shù)容器適配器，第三個(gè)參數(shù)仿函數(shù)，less是大的優(yōu)先級高
后面?zhèn)z個(gè)參數(shù)給缺省值，測試優(yōu)先級隊(duì)列，默認(rèn)大的優(yōu)先級高
也可以用一個(gè)區(qū)間去初始化
把第三個(gè)參數(shù)改為greater，就是小的優(yōu)先級高
習(xí)題
class Solution {
public:
int findKthLargest(vector<int>& nums, int k) {
priority_queue<int> pq(nums.begin(),nums.end());
while(--k)
{
pq.pop();
}
return pq.top();
}
};215. 數(shù)組中的第K個(gè)最大元素 - 力扣（LeetCode）
優(yōu)先級隊(duì)列模擬實(shí)現(xiàn)
namespace myspace
{
//大堆
template<class T,class Container=vector<T>>
class priority_queque
{
public:
template<class InputerIterator>
priority_queque(InputerIterator first, InputerIterator last)//迭代器區(qū)間
{
while (first < last)
{
_con.push_back(*first);
++first;
}
//建堆
for (int i = (_con.size() - 1 - 1)/2;i>=0;--i)
{
adjust_down(i);
}
}
priority_queque()//默認(rèn)構(gòu)造，不然會(huì)報(bào)錯(cuò)，因?yàn)樯厦娴牡鲄^(qū)間這個(gè)函數(shù)跟構(gòu)造函數(shù)同名
{}
void adjust_up(size_t child)
{
size_t parent = (child - 1) / 2;
while (child>0)
{
if (_con[parent] < _con[child])
{
std::swap(_con[parent], _con[child]);
child = parent;
parent = (child - 1) / 2;
}
else
{
break;
}
}
}
void adjust_down(size_t parent)
{
size_t child = parent * 2 + 1;
while (child < _con.size())
{
if (child + 1 < _con.size() && _con[child + 1] > _con[child])
{
++child;
} //選出最大的孩子
if (_con[child] > _con[parent])
{
std::swap(_con[child],_con[parent]);
parent = child;
child = parent * 2 + 1;
}
else
{
break;
}
}
}
void push(const T& x)//（大堆）堆的插入
{
_con.push_back(x);
adjust_up(_con.size()-1);//尾插后向上跳轉(zhuǎn)
}
void pop()//刪除堆頂數(shù)據(jù)
{
std::swap(_con[0], _con[_con.size() - 1]);
_con.pop_back();
adjust_down(0);
}//對頂數(shù)據(jù)和最后一個(gè)數(shù)據(jù)交換，之后刪除最后一個(gè)數(shù)據(jù)，然后向下調(diào)整堆
const T& top()
{
return _con[0];
}
bool empty()
{
return _con.empty();
}
size_t size()const
{
return _con.size();
}
private:
Container _con;
};
}
int main()
{
int a[]= { 156,132,156,156,31,5,15,31,364,15 };
myspace::priority_queque<int> pq(a,a+sizeof(a)/sizeof(int));
while (!pq.empty())
{
cout << pq.top() << " ";
pq.pop();
}
return 0;
}
優(yōu)先級隊(duì)列要控制比較大小的邏輯，上面的寫法我們以大堆為例但是這樣把優(yōu)先級隊(duì)列給寫死了，如果把里面的>改為<則會(huì)變成小堆，但是這樣比較麻煩。上面我們只傳了倆個(gè)參數(shù)，還有一個(gè)參數(shù)沒傳，第三個(gè)參數(shù)是仿函數(shù)
仿函數(shù)
仿函數(shù)/函數(shù)對象——是個(gè)類，重載的是operator（），類對象可以像函數(shù)一樣去使用，本質(zhì)就是重載
（）也是一個(gè)運(yùn)算符
跟sort不同，sort傳的是函數(shù)模板，傳的是對象，而這里傳的是類模板，傳的是類型
這里的lsFunc不是函數(shù)名，而是一個(gè)類對象
這倆個(gè)等價(jià)
不僅有l(wèi)ess，還有g(shù)reater
namespace myspace
{
template<class T>
class less
{
public:
bool operator()(const T& l, const T& r)const
{
return l < r;
}
};
template<class T>
class greater
{
public:
bool operator()(const T& l, const T& r)const
{
return l > r;
}
};
}
我們將這里全部改成小于號(hào)
傳入仿函數(shù)
這樣就可以去替換小于號(hào)
小堆
大堆
完整代碼
namespace myspace
{
//大堆
template<class T,class Container=vector<T>,class Compare=less<T>>
class priority_queque
{
public:
template<class InputerIterator>
priority_queque(InputerIterator first, InputerIterator last)//迭代器區(qū)間
{
while (first < last)
{
_con.push_back(*first);
++first;
}
//建堆
for (int i = (_con.size() - 1 - 1)/2;i>=0;--i)
{
adjust_down(i);
}
}
priority_queque()//默認(rèn)構(gòu)造，不然會(huì)報(bào)錯(cuò)，因?yàn)樯厦娴牡鲄^(qū)間這個(gè)函數(shù)跟構(gòu)造函數(shù)同名
{}
Compare com;
void adjust_up(size_t child)
{
size_t parent = (child - 1) / 2;
while (child>0)
{
if (com(_con[parent] , _con[child]))
{
std::swap(_con[parent], _con[child]);
child = parent;
parent = (child - 1) / 2;
}
else
{
break;
}
}
}
void adjust_down(size_t parent)
{
size_t child = parent * 2 + 1;
while (child < _con.size())
{
if (child + 1 < _con.size() && com(_con[child],_con[child + 1]) )
{
++child;
} //選出最大的孩子
if ( com(_con[parent],_con[child]))
{
std::swap(_con[child],_con[parent]);
parent = child;
child = parent * 2 + 1;
}
else
{
break;
}
}
}
void push(const T& x)//（大堆）堆的插入
{
_con.push_back(x);
adjust_up(_con.size()-1);//尾插后向上跳轉(zhuǎn)
}
void pop()//刪除堆頂數(shù)據(jù)
{
std::swap(_con[0], _con[_con.size() - 1]);
_con.pop_back();
adjust_down(0);
}//對頂數(shù)據(jù)和最后一個(gè)數(shù)據(jù)交換，之后刪除最后一個(gè)數(shù)據(jù)，然后向下調(diào)整堆
const T& top()
{
return _con[0];
}
bool empty()
{
return _con.empty();
}
size_t size()const
{
return _con.size();
}
private:
Container _con;
};
}
namespace myspace
{
template<class T>
class less
{
public:
bool operator()(const T& l, const T& r)const
{
return l < r;
}
};
template<class T>
class greater
{
public:
bool operator()(const T& l, const T& r)const
{
return l > r;
}
};
}
int main()
{
int a[]= { 156,132,156,156,31,5,15,31,364,15 };
myspace::priority_queque<int,vector<int>,less<int>> pq(a,a+sizeof(a)/sizeof(int));
while (!pq.empty())
{
cout << pq.top() << " ";
pq.pop();
}
return 0;
}到此這篇關(guān)于C++容器適配與棧的實(shí)現(xiàn)及dequeque和優(yōu)先級詳解的文章就介紹到這了,更多相關(guān)C++容器適配內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！
相關(guān)文章
都說STL是數(shù)據(jù)容器與算法的高度組合,在前面的文章中我們介紹了常見的幾種容器,vector、list、map、deque等,今天我們再來介紹下STL中常用的一些算法,需要的朋友可以參考下2024-02-02
C語言數(shù)據(jù)結(jié)構(gòu)中堆排序的分析總結(jié)
堆是計(jì)算機(jī)科學(xué)中一類特殊的數(shù)據(jù)結(jié)構(gòu)的統(tǒng)稱，通常是一個(gè)可以被看做一棵完全二叉樹的數(shù)組對象。而堆排序是利用堆這種數(shù)據(jù)結(jié)構(gòu)所設(shè)計(jì)的一種排序算法。本文將通過圖片詳細(xì)介紹堆排序，需要的可以參考一下2022-04-04
這篇文章主要為大家介紹了C語言堆棧括號(hào)匹配問題示例詳解，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進(jìn)步，早日升職加薪2021-11-11
本文主要介紹C語言 結(jié)構(gòu)體的知識(shí)，學(xué)習(xí)C語言肯定需要學(xué)習(xí)結(jié)構(gòu)體，這里詳細(xì)說明了結(jié)構(gòu)體并附示例代碼，供大家參考學(xué)習(xí)，有需要的小伙伴可以參考下2021-10-10
VC創(chuàng)建DLL動(dòng)態(tài)鏈接庫的方法
這篇文章主要介紹了VC創(chuàng)建DLL動(dòng)態(tài)鏈接庫的方法,實(shí)例分析VC創(chuàng)建動(dòng)態(tài)鏈接庫的完整步驟,需要的朋友可以參考下2015-05-05
Pimpl（Pointer?to?Implementation）是一種常見的?C++?設(shè)計(jì)模式,用于隱藏類的實(shí)現(xiàn)細(xì)節(jié),本文將通過一個(gè)較為復(fù)雜的例子,展示如何使用智能指針來實(shí)現(xiàn)?Pimpl?慣用法,需要的可以參考下2023-09-09
這篇文章介紹C語言常見排序算法之插入排序(直接插入排序,希爾排序),主要分享介紹的是插入排序的兩種常用算法，直接插入排序和希爾排序，需要的朋友可以參考一下2022-07-07
Qt+Quick實(shí)現(xiàn)圖片演示器的開發(fā)
這篇文章主要為大家詳細(xì)介紹了Qt如何利用Quick實(shí)現(xiàn)圖片演示器的開發(fā)，文中的示例代碼講解詳細(xì)，對我們學(xué)習(xí)Qt有一定的幫助，需要的可以參考一下2023-01-01
STL區(qū)間成員函數(shù)及區(qū)間算法總結(jié)
這篇文章主要匯總介紹了STL區(qū)間成員函數(shù)及區(qū)間算法，有需要的小伙伴可以參考下。2015-07-07
C語言循環(huán)語句之重復(fù)執(zhí)行特定的代碼塊
在C語言中分支和循環(huán)語句是實(shí)現(xiàn)條件執(zhí)行和重復(fù)執(zhí)行的重要工具,下面這篇文章主要給大家介紹了關(guān)于C語言循環(huán)語句之重復(fù)執(zhí)行特定的代碼塊的相關(guān)資料,文中通過代碼介紹的非常詳細(xì),需要的朋友可以參考下2024-01-01