C++容器適配與棧的實現(xiàn)及dequeque和優(yōu)先級詳解
容器適配器
我們可以看出，棧中沒有空間配置器（內(nèi)存池），而是適配器
適配器是一種設(shè)計模式(設(shè)計模式是一套被反復(fù)使用的、多數(shù)人知曉的、經(jīng)過分類編目的、代碼設(shè)計經(jīng)驗的總結(jié))，該種模式是將一個類的接口轉(zhuǎn)換成客戶希望的另外一個接口
棧的實現(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;
};
}此時這個棧并不是適配器，因為底層被寫死了，底層是用vector實現(xiàn)的，如果想讓它適配，加上適配器即可
此時就是適配器
list
注意隊列不能用vector，編譯會報錯，因為不支持頭刪，沒有pop_front
queque實現(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)棧和隊列都有一個dequeque
dequeque不是隊列，是vector和list的結(jié)合體
1.支持任意位置的插入刪除
2.支持隨機(jī)訪問
deque并不是真正連續(xù)的空間，而是由一段段連續(xù)的小空間拼接而成的，實際deque類似于一個動態(tài)的二維數(shù)組，其底層結(jié)構(gòu)如下圖所示：
雙端隊列底層是一段假象的連續(xù)空間，實際是分段連續(xù)的，為了維護(hù)其“整體連續(xù)”以及隨機(jī)訪問的假象，落在了deque的迭代器身上，因此deque的迭代器設(shè)計就比較復(fù)雜，如下圖所示：
dequeque的缺陷
vector比較，deque的優(yōu)勢是：頭部插入和刪除時，不需要搬移元素，效率特別高，而且在擴(kuò)容時，也不需要搬移大量的元素，因此其效率是必vector高的。
與list比較，其底層是連續(xù)空間，空間利用率比較高，不需要存儲額外字段。 但是，deque有一個致命缺陷：不適合遍歷，因為在遍歷時，deque的迭代器要頻繁的去檢測其是否移動到某段小空間的邊界，導(dǎo)致效率低下（中間的插入刪除效率很低），
而序列式場景中，可能需要經(jīng)常遍歷，因此在實際中，需要線性結(jié)構(gòu)時，大多數(shù)情況下優(yōu)先考慮vector和list，deque的應(yīng)用并不多，而目前能看到的一個應(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)先級隊列
priority_queque
優(yōu)先級隊列的底層是堆（二叉樹的堆）
第二個參數(shù)容器適配器，第三個參數(shù)仿函數(shù)，less是大的優(yōu)先級高
后面?zhèn)z個參數(shù)給缺省值，測試優(yōu)先級隊列，默認(rèn)大的優(yōu)先級高
也可以用一個區(qū)間去初始化
把第三個參數(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個最大元素 - 力扣（LeetCode）
優(yōu)先級隊列模擬實現(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)造，不然會報錯，因為上面的迭代器區(qū)間這個函數(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ù)和最后一個數(shù)據(jù)交換，之后刪除最后一個數(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)先級隊列要控制比較大小的邏輯，上面的寫法我們以大堆為例但是這樣把優(yōu)先級隊列給寫死了，如果把里面的>改為<則會變成小堆，但是這樣比較麻煩。上面我們只傳了倆個參數(shù)，還有一個參數(shù)沒傳，第三個參數(shù)是仿函數(shù)
仿函數(shù)
仿函數(shù)/函數(shù)對象——是個類，重載的是operator（），類對象可以像函數(shù)一樣去使用，本質(zhì)就是重載
（）也是一個運算符
跟sort不同，sort傳的是函數(shù)模板，傳的是對象，而這里傳的是類模板，傳的是類型
這里的lsFunc不是函數(shù)名，而是一個類對象
這倆個等價
不僅有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;
}
};
}
我們將這里全部改成小于號
傳入仿函數(shù)
這樣就可以去替換小于號
小堆
大堆
完整代碼
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)造，不然會報錯，因為上面的迭代器區(qū)間這個函數(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ù)和最后一個數(shù)據(jù)交換，之后刪除最后一個數(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++容器適配與棧的實現(xiàn)及dequeque和優(yōu)先級詳解的文章就介紹到這了,更多相關(guān)C++容器適配內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！
相關(guān)文章
這篇文章主要介紹了C語言 sprintf 函數(shù)，文章主要包括sprintf 函數(shù)簡介、sprintf 函數(shù)使用和簡單說明了一下sprintf、fprintf、printf 函數(shù)區(qū)別,需要的朋友可以參考一下文章的具體內(nèi)容2021-10-10
Windows 環(huán)境下使用 Qt 連接 MySQL
這篇文章主要介紹了Windows 環(huán)境下使用 Qt 連接 MySQL的相關(guān)資料,需要的朋友可以參考下2017-07-07
這篇文章主要介紹了C語言中求余運算符的使用，具有很好的參考價值，希望對大家有所幫助。如有錯誤或未考慮完全的地方，望不吝賜教2023-02-02
C語言實現(xiàn)時區(qū)轉(zhuǎn)換函數(shù)的實例
這篇文章主要介紹了C語言實現(xiàn)時區(qū)轉(zhuǎn)換函數(shù)的實例的相關(guān)資料,這里分析需求并提供實現(xiàn)代碼，需要的朋友可以參考下2017-08-08
學(xué)習(xí)過C語言的小伙伴知道：C語言是面向過程的，關(guān)注的是過程，分析出求解問題的步驟，通過函數(shù)調(diào)用逐步解決問題，這篇文章主要介紹了C++面向?qū)ο笾袠?gòu)造函數(shù)使用2022-10-10
本篇文章是對第K大數(shù)問題以及算法概要進(jìn)行了詳細(xì)的分析介紹，需要的朋友參考下2013-05-05
最近我學(xué)習(xí)了C++中的STL庫中的vector容器，對于常用容器，我們不僅要會使用其常用的函數(shù)接口，我們還有明白這些接口在其底層是如何實現(xiàn)的。所以特意整理出來一篇博客供我們學(xué)習(xí)2022-08-08
這篇文章主要為大家詳細(xì)介紹了C語言實現(xiàn)掃雷項目，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價值，感興趣的小伙伴們可以參考一下2021-07-07
緩存處理函數(shù)storageKeySuffix操作示例解析
這篇文章主要介紹了淺析緩存處理函數(shù)storageKeySuffix操作示例，有需要的朋友可以借鑒參考下,希望能夠有所幫助,祝大家多多進(jìn)步,早日升職加薪2023-08-08
select函數(shù)實現(xiàn)高性能IO多路訪問的關(guān)鍵示例深入解析
這篇文章主要為大家介紹了select函數(shù)實現(xiàn)高性能IO多路訪問的關(guān)鍵示例深入解析,有需要的朋友可以借鑒參考下,希望能夠有所幫助,祝大家多多進(jìn)步,早日升職加薪2023-09-09