C++?STL容器適配器使用指南
??適配器
??適配器是一種設(shè)計(jì)模式(設(shè)計(jì)模式是一套被反復(fù)使用的、多數(shù)人知曉的、經(jīng)過分類編目的、代碼設(shè)計(jì)經(jīng)驗(yàn)的總結(jié))，該種模式是將一個(gè)類的接口轉(zhuǎn)換成客戶希望的另外一個(gè)接口。例如：
容器適配器讓一種已存在的容器類型采用另一種不同的抽象類型的工作方式實(shí)現(xiàn)。也就是對(duì)一種容器封裝來實(shí)現(xiàn)其他的容器。知道了容器適配器接下來先來講stack。
??stack容器適配器
??stack的介紹
??1.stack應(yīng)用在后進(jìn)先出的上下文環(huán)境中，只能在容器的一端進(jìn)行入數(shù)據(jù)和出數(shù)據(jù)。
?? 2.stack的底層容器可以是任何標(biāo)準(zhǔn)的容器類模板或者一些其他特定的容器類，這些容器類應(yīng)該支持以下操作：
empty：判空操作
back：獲取尾部元素操作
push_back：尾部插入元素操作
pop_back：尾部刪除元素操作??
3.標(biāo)準(zhǔn)容器vector、deque、list均符合這些需求，默認(rèn)情況下，如果沒有為stack指定特定的底層容器，默認(rèn)情況下使用deque。
??stack的使用
??主要的接口
有了string,vector,list的基礎(chǔ)再玩這個(gè)stack就會(huì)很簡(jiǎn)單。
??數(shù)據(jù)結(jié)構(gòu)有棧的詳細(xì)講解，這里就不詳細(xì)使用了。
stack<int> st; //入棧 st.push(1); st.push(2); st.push(3); st.push(4); st.pop();//出棧 cout << st.top() << endl;//取棧頂數(shù)據(jù) cout << st.empty() << endl;//判空
??stack的模擬實(shí)現(xiàn)
我們可以用vector來模擬實(shí)現(xiàn)。
namespace gpy
{
template<class T>
class stack
{
public:
stack(){}
void push(const T& x)
{
_v.push_back(x);
}
void pop()
{
_v.pop_back();
}
T& top()
{
return _v.back();
}
size_t size()const
{
return _v.size();
}
bool empty()const
{
return _v.empty();
}
private:
std::vector<T> _v;
};
}
??queue
??queue的介紹
隊(duì)列是一種容器適配器，專門用于在FIFO上下文(先進(jìn)先出)中操作，其中從容器一端插入元素，另一端提取元素。
隊(duì)列作為容器適配器實(shí)現(xiàn)，容器適配器即將特定容器類封裝作為其底層容器類，queue提供一組特定的成員函數(shù)來訪問其元素。元素從隊(duì)尾入隊(duì)列，從隊(duì)頭出隊(duì)列。
底層容器可以是標(biāo)準(zhǔn)容器類模板之一，也可以是其他專門設(shè)計(jì)的容器類。該底層容器應(yīng)至少支持以下操作:
- empty：檢測(cè)隊(duì)列是否為空
- size：返回隊(duì)列中有效元素的個(gè)數(shù)
- front：返回隊(duì)頭元素的引用
- back：返回隊(duì)尾元素的引用
- push_back：在隊(duì)列尾部入隊(duì)列
- pop_front：在隊(duì)列頭部出隊(duì)列
標(biāo)準(zhǔn)容器類deque和list滿足了這些要求。默認(rèn)情況下，如果沒有為queue實(shí)例化指定容器類，則使用標(biāo)準(zhǔn)容器deque。
??queue的使用
跟stack差不多這里就簡(jiǎn)單的使用一下
??queue的模擬實(shí)現(xiàn)
??stack可以使用vector實(shí)現(xiàn)，但是不能實(shí)現(xiàn)queue。vector的頭插頭刪需要挪動(dòng)數(shù)據(jù)效率會(huì)變低所以標(biāo)準(zhǔn)庫中沒有提供頭插頭刪的接口。queue就可以用list來模擬實(shí)現(xiàn)。
namespace gpy
{
template <class T>
class queue
{
public:
queue(){}
void push(const T& x)
{
_lt.push_back(x);//queue的push就是list的尾插
}
void pop()
{
_lt.pop_front();//queue的pop就是list的頭刪
}
T& front(){return _lt.front();}
const T& front()const{ return _lt.front(); }
T& back(){ return _lt.back(); }
const T& back()const{ return _lt.back(); }
size_t size()const{ return _lt.size(); }
bool empty()const{ return _lt.empty(); }
private:
std::list<T> _lt;
};
}
??deque容器
??vector優(yōu)點(diǎn)：尾插尾刪的效率高，支持隨機(jī)訪問，cpu高速緩存命中率很高缺點(diǎn)：空間不夠，增容代價(jià)大，一般增2倍，但增容后我只用了很少的一段空間那其他的空間就浪費(fèi)了。中間和頭部的插入刪除效率低O(N)，需要挪動(dòng)數(shù)據(jù)，??list優(yōu)點(diǎn)：
1.按需申請(qǐng)空間，不會(huì)造成空間浪費(fèi)
2.任意位置的插入刪除效率都高
缺點(diǎn)：不支持隨機(jī)訪問， CPU高速緩存命中率低
改進(jìn)：用中控?cái)?shù)組-指針數(shù)組
這就是deque，雙端隊(duì)列和隊(duì)列沒有關(guān)系。在deque中，中控?cái)?shù)組叫map,開的數(shù)組叫緩沖區(qū)。 deque(雙端隊(duì)列)：是一種雙開口的"連續(xù)"空間的數(shù)據(jù)結(jié)構(gòu)，雙開口的含義是：可以在頭尾兩端進(jìn)行插入和刪除操作，且時(shí)間復(fù)雜度為O(1)，與vector比較，頭插效率高，不需要搬移元素；與list比較，空間利用率比較高。
它不是正真連續(xù)的空間，底層結(jié)構(gòu)如上圖。deque要支持隨機(jī)訪問叫要實(shí)現(xiàn)迭代器，它的迭代器很復(fù)雜簡(jiǎn)單了解。
這里就不多講解，感興趣的可以看侯捷老師的《stl源碼剖析》。
??deque卻沒有那么牛逼優(yōu)缺點(diǎn)：
1.它最大優(yōu)點(diǎn)就是做stack和queue的默認(rèn)適配器，stack和queue只在頭尾操作，
2.它中間插入刪除還是要挪動(dòng)數(shù)據(jù)，很麻煩效率低
3.deque是糅合了vector和list，它沒有vector隨機(jī)訪問效率高，任意位置的插入刪除效率沒有l(wèi)ist高。
??priority-queue
??priority-queue的使用
優(yōu)先級(jí)隊(duì)列默認(rèn)使用vector作為其底層存儲(chǔ)數(shù)據(jù)的容器，在vector上又使用了堆算法將vector中元素構(gòu)造成堆的結(jié)構(gòu)，因此priority_queue就是堆，所有需要用到堆的位置，都可以考慮使用priority_queue。注意：默認(rèn)情況下priority_queue是大堆。
priority_queue<int> pq;//默認(rèn)是大堆
pq.push(10);
pq.push(5);
pq.push(13);
pq.push(4);
pq.push(9);
while (!pq.empty())
{
cout << pq.top() << " ";
pq.pop();
}
cout << endl;
??默認(rèn)是大的優(yōu)先級(jí)高，如果要變成小的優(yōu)先級(jí)高，需要再傳一個(gè)模板參數(shù)greater
??priority-queue的模擬實(shí)現(xiàn)
初始結(jié)構(gòu)，下面都是按大堆實(shí)現(xiàn)的
namespace gpy
{
template <class T,Container =vector<T>>
class priority_queue
{
public:
priority_queue(){}
private:
Containter _con;
};
}
??首先實(shí)現(xiàn)尾插
當(dāng)插入一個(gè)數(shù)就和parent比較，比parent大就向上調(diào)整.
標(biāo)準(zhǔn)庫給的“<”是大堆，我們?cè)谀M的時(shí)候也用“<”.
void AdjustUp(size_t child)
{
size_t parent = (child - 1) / 2;
while (child > 0)
{
if (_con[parent] < _con[child])
{
swap(_con[parent], _con[child]);
child = parent;
parent = (child - 1) / 2;
}
else
{
break;
}
}
}
void push(const T& x)
{
_con.push_back(x);
//從尾開始調(diào)
AdjustUp(_con.size()-1);
}
??pop，如果直接pop就不能還保持是堆的結(jié)構(gòu)，先把堆頂?shù)臄?shù)和最后一個(gè)數(shù)交換在刪除這個(gè)數(shù)，此時(shí)2邊都還滿足堆這是在向下調(diào)整
先從0處開始，選出左右2個(gè)孩子中大的和parent比較，比parent大的就交換。
void AdjustDown(size_t parent)
{
size_t child = parent * 2 + 1;
while (child<_con.size())
{
//選出大的孩子
if (child + 1 < _con.size() && _con[child] < _con[child + 1])
{
++child;
}
if (_con[parent] < _con[child])
{
swap(_con[parent], _con[child]);
parent = child;
child = parent * 2 + 1;
}
else
{
break;
}
}
}
void pop()
{
swap(_con[0],_con[_con.size()-1]);
_con.pop_back();
AdjustDown(0);
}
??其他的接口就簡(jiǎn)單了
const T& top()const
{
return _con[0];//取堆頂?shù)臄?shù)據(jù)
}
size_t size()const
{
return _con.size();
}
bool empty()const
{
return _con.empty();
}
??測(cè)試一下
那如果要是按低的優(yōu)先級(jí)來該怎么辦呢？這是就要用到仿函數(shù)了。
??仿函數(shù)就是像函數(shù)一樣可以使用。
template<class T>
struct Less
{
bool operator()(const T& l, const T& r)
{
return l < r;
}
};
bool Less1(int l, int r)
{
return l < r;
}
就是類里面重載了運(yùn)算符。有了仿函數(shù)就可以把上面的代碼在改進(jìn)改進(jìn)，在多傳一個(gè)模板參數(shù)
namespace gpy
{
template<class T>
struct less
{
bool operator()(const T& l, const T& r)
{
return l < r;
}
};
template<class T>
struct greater
{
bool operator()(const T& l, const T& r)
{
return l > r;
}
};
template <class T, class Container = vector<T>,class Compare = less<T>>
class priority_queue
{
public:
Compare com;
void AdjustUp(size_t child)
{
size_t parent = (child - 1) / 2;
while (child > 0)
{
//if (_con[parent] < _con[child])
if (com(_con[parent],_con[child]))
{
swap(_con[parent], _con[child]);
child = parent;
parent = (child - 1) / 2;
}
else
{
break;
}
}
}
void AdjustDown(size_t parent)
{
size_t child = parent * 2 + 1;
while (child<_con.size())
{
//選出大的孩子
//if (child + 1 < _con.size() && _con[child] < _con[child + 1])
if (child+1 < _con.size() && com(_con[child],_con[child+1]))
{
++child;
}
//if (_con[parent] < _con[child])
if (com(_con[parent],_con[child]))
{
swap(_con[parent], _con[child]);
parent = child;
child = parent * 2 + 1;
}
else
{
break;
}
}
}
void push(const T& x)
{
_con.push_back(x);
//從尾開始調(diào)
AdjustUp(_con.size()-1);
}
void pop()
{
swap(_con[0],_con[_con.size()-1]);
_con.pop_back();
AdjustDown(0);
}
const T& top()const
{
return _con[0];//取堆頂?shù)臄?shù)據(jù)
}
size_t size()const
{
return _con.size();
}
bool empty()const
{
return _con.empty();
}
private:
Container _con;
};
}
??
本篇文章到這就結(jié)束了，歡迎大家一起交流！
到此這篇關(guān)于C++ STL容器適配器使用指南的文章就介紹到這了,更多相關(guān)C++ STL容器適配器內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！
相關(guān)文章
這篇文章主要分下工的是18個(gè)C語言必背的經(jīng)典程序，下面文章我們就來看看實(shí)例，需要的小伙伴可以參考一下喲，希望對(duì)你有所幫助2021-10-10
C++?STL標(biāo)準(zhǔn)庫之std::list使用介紹及用法詳解
std::list是支持常數(shù)時(shí)間從容器任何位置插入和移除元素的容器,下面這篇文章主要給大家介紹了關(guān)于C++?STL標(biāo)準(zhǔn)庫之std::list使用介紹及用法詳解的相關(guān)資料,文中通過實(shí)例代碼介紹的非常詳細(xì),需要的朋友可以參考下2022-11-11
這篇文章主要介紹了C++中生成隨機(jī)數(shù)的方法總結(jié),文中通過示例代碼介紹的非常詳細(xì),對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2024-05-05
C++中回調(diào)函數(shù)及函數(shù)指針的實(shí)例詳解
這篇文章主要介紹了C++中回調(diào)函數(shù)及函數(shù)指針的實(shí)例詳解的相關(guān)資料,希望通過本文能幫助到大家，讓大家理解掌握這部分內(nèi)容，需要的朋友可以參考下2017-10-10
這篇文章主要介紹了C++成員函數(shù)后面加override問題，具有很好的參考價(jià)值，希望對(duì)大家有所幫助。如有錯(cuò)誤或未考慮完全的地方，望不吝賜教2022-11-11
本文主要介紹了Qt?QString的使用實(shí)現(xiàn)，文中通過示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2022-05-05
這篇文章主要為大家詳細(xì)介紹了C++中多態(tài)的機(jī)制以及使用，文中的示例代碼講解詳細(xì)，對(duì)我們學(xué)習(xí)C++有一定的幫助，感興趣的可以了解一下2022-06-06
C++ const 和 constexpr 的區(qū)別呢，constexpr表示這玩意兒在編譯期就可以算出來（前提是為了算出它所依賴的東西也是在編譯期可以算出來的）。而const只保證了運(yùn)行時(shí)不直接被修改（但這個(gè)東西仍然可能是個(gè)動(dòng)態(tài)變量）。下面我們來詳細(xì)講解下。2016-01-01
Qt使用QCamera實(shí)現(xiàn)切換相機(jī),分辨率和圖像捕獲功能
這篇文章主要為大家介紹了如何利用Qt中的相機(jī)類QCamera，取景器類QCameraViewfinder，圖像捕獲類QCameraImageCapture實(shí)現(xiàn)切換相機(jī)、分辨率和圖像捕獲功能，需要的可以了解一下2023-04-04
這篇文章主要介紹了C語言 掃雷程序的實(shí)現(xiàn)的相關(guān)資料,需要的朋友可以參考下2017-03-03