C++ STL中的容器適配器實(shí)現(xiàn)
1 stack
1.1 stack 介紹
- stack是一種容器適配器，專門用在具有后進(jìn)先出操作的上下文環(huán)境中，其刪除只能從容器的一端進(jìn)行元素的插入與提取操作。
- stack是作為容器適配器被實(shí)現(xiàn)的，容器適配器即是對(duì)特定類封裝作為其底層的容器，并提供一組特定的成員函數(shù)來訪問其元素，將特定類作為其底層的，元素特定容器的尾部(即棧頂)被壓入和彈出。
- stack的底層容器可以是任何標(biāo)準(zhǔn)的容器類模板或者一些其他特定的容器類，這些容器類應(yīng)該支持以下操作：empty：判空操作、back：獲取尾部元素操作、push_back：尾部插入元素操作、pop_back：尾部刪除元素操作
- 標(biāo)準(zhǔn)容器vector、deque、list均符合這些需求，默認(rèn)情況下，如果沒有為stack指定特定的底層容器，默認(rèn)情況下使用deque。
1.2 stack 使用
接口說明
1.3 stack 模擬實(shí)現(xiàn)
namespace czh
{
template<class T, class Container = deque<T>>
// template<class T, class Container = list<T>>
// template<class T, class Container = vector<T>>
class stack
{
public:
void push(const T& x)
{
_con.push_back(x);
}
void pop()
{
_con.pop_back();
}
T& top()
{
return _con.back();
}
const T& top() const
{
return _con.back();
}
size_t size() const
{
return _con.size();
}
bool empty() const
{
return _con.empty();
}
private:
Container _con;
};
}
1.4 deque 的簡(jiǎn)單介紹
原理
1、deque(雙端隊(duì)列)：是一種雙開口的"連續(xù)"空間的數(shù)據(jù)結(jié)構(gòu)，注意和 queue 沒有關(guān)系雙開口的含義是：可以在頭尾兩端進(jìn)行插入和刪除操作，且時(shí)間復(fù)雜度為O(1)，與vector比較，頭插效率高，不需要搬移元素；與list比較，空間利用率比較高。
2、deque并不是真正連續(xù)的空間，而是由一段段連續(xù)的小空間拼接而成的，實(shí)際deque類似于一個(gè)動(dòng)態(tài)的二維數(shù)組
3、雙端隊(duì)列底層是一段假象的連續(xù)空間，實(shí)際是分段連續(xù)的，為了維護(hù)其“整體連續(xù)”以及隨機(jī)訪問的假象，落在了deque的迭代器身上，因此deque的迭代器設(shè)計(jì)就比較復(fù)雜，如下圖所示：
缺陷
與vector比較，deque的優(yōu)勢(shì)是：頭部插入和刪除時(shí)，不需要搬移元素，效率特別高，而且在擴(kuò)容時(shí)，也不需要搬移大量的元素，因此其效率是比 vector 高的。
與list比較，其底層是連續(xù)空間，空間利用率比較高，不需要存儲(chǔ)額外字段。
但是，deque有一個(gè)致命缺陷：不適合遍歷，因?yàn)樵诒闅v時(shí)，deque的迭代器要頻繁的去檢測(cè)其是否移動(dòng)到某段小空間的邊界，導(dǎo)致效率低下，而序列式場(chǎng)景中，可能需要經(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)。
為何作為stack 和 queue的 默認(rèn) 實(shí)現(xiàn)
stack是一種后進(jìn)先出的特殊線性數(shù)據(jù)結(jié)構(gòu)，因此只要具有push_back()和pop_back()操作的線性結(jié)構(gòu)，都可以作為stack的底層容器，比如vector和list都可以；queue是先進(jìn)先出的特殊線性數(shù)據(jù)結(jié)構(gòu)，只要具有push_back和pop_front操作的線性結(jié)構(gòu)，都可以作為queue的底層容器，比如list。
但是STL中對(duì)stack和queue默認(rèn)選擇deque作為其底層容器，主要是因?yàn)椋?/p>
stack 和 queue 不需要遍歷（因此stack 和 queue沒有迭代器），只需要在固定的一段或者兩端進(jìn)行操作。
在 stack 中元素增長(zhǎng)時(shí)，deque 比 vector 的效率高（擴(kuò)容時(shí)候不需要搬移大量數(shù)據(jù)）；queue 中的元素增長(zhǎng)時(shí)，deque 不僅效率高，而且內(nèi)存使用率也高。
所以結(jié)合了deque的優(yōu)點(diǎn)，完美遞避開了其缺陷
2 queue
2.1 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。
2.2 queue 使用
接口介紹
2.3 queue 模擬實(shí)現(xiàn)
因?yàn)閝ueue的接口中存在頭刪和尾插，因此使用vector來封裝效率太低，故可以借助list 和 deque 來模擬實(shí)現(xiàn)queue
namespace czh
{
// 設(shè)計(jì)模式 -- 適配器模式(配接器)
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& front()
{
return _con.front();
}
const T& front() const
{
return _con.front();
}
T& back()
{
return _con.back();
}
const T& back() const
{
return _con.back();
}
size_t size() const
{
return _con.size();
}
bool empty() const
{
return _con.empty();
}
private:
Container _con;
};
}
3 priority_queue
3.1 priority_queue 介紹
優(yōu)先級(jí)隊(duì)列是一種容器適配器，根據(jù)嚴(yán)格的弱排序標(biāo)準(zhǔn)，它的第一個(gè)元素總是它所包含的元素中最大的那一個(gè)。
內(nèi)部實(shí)現(xiàn)其實(shí)是堆，在堆中可以隨時(shí)插入元素，并且只能檢索最大堆元素（優(yōu)先級(jí)隊(duì)列中位于頂部的元素）。
底層容器可以是任何標(biāo)準(zhǔn)容器類模板，也可以是其他特定設(shè)計(jì)的容器類。容器應(yīng)該可以通過隨機(jī)訪問迭代器訪問，并支持以下操作：empty()：檢測(cè)容器是否為空、size()：返回容器中有效元素個(gè)數(shù)、front()：返回容器中第一個(gè)元素的引用、push_back()：在容器尾部插入元素、pop_back()：刪除容器尾部元素
標(biāo)準(zhǔn)容器類vector和deque滿足這些需求。默認(rèn)情況下，如果沒有為特定的priority_queue類實(shí)例化指定容器類，則使用vector。
需要支持隨機(jī)訪問迭代器，以便始終在內(nèi)部保持堆結(jié)構(gòu)。容器適配器通過在需要時(shí)自動(dòng)調(diào)用算法函數(shù)，make_heap、push_heap和pop_heap來自動(dòng)完成此操作。
3.2 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 是大堆。通過仿函數(shù)可以改變其為小堆。
#include <iostream>
#include <vector>
#include <queue>
#include <functional> // greater算法的頭文件
void TestPriorityQueue()
{
// 默認(rèn)情況下，創(chuàng)建的是大堆，其底層按照小于號(hào)比較
vector<int> v{3,2,7,6,0,4,1,9,8,5};
priority_queue<int> q1;
for (auto& e : v)
q1.push(e);
cout << q1.top() << endl;
// 如果要?jiǎng)?chuàng)建小堆，將第三個(gè)模板參數(shù)換成greater比較方式
priority_queue<int, vector<int>, greater<int>> q2(v.begin(), v.end());
cout << q2.top() << endl;
}
3.3 仿函數(shù)的引入
仿函數(shù)準(zhǔn)確來說是一個(gè)類，這個(gè)類重載了operator()，這個(gè)類的對(duì)象調(diào)用 operator()，可以像函數(shù)一樣去使用，在優(yōu)先級(jí)隊(duì)列中的使用可以控制創(chuàng)建的優(yōu)先級(jí)隊(duì)列中是大堆還是小堆使其可以像水龍頭的開關(guān)一樣可以去控制熱水還是涼水。在 STL庫中中的兩個(gè)仿函數(shù)的實(shí)現(xiàn)如下：
STL 中的優(yōu)先級(jí)隊(duì)列
舉例說明仿函數(shù)的應(yīng)用
比如我們想買個(gè)手機(jī)，在京東上搜索手機(jī)，可以按照價(jià)格、銷量等標(biāo)簽排序，那么我們可以利用仿函數(shù)簡(jiǎn)單實(shí)現(xiàn)，寫一個(gè)商品類代表手機(jī)我們用排序算法 sort 對(duì)其排序，但是我們不可以在類的內(nèi)部重載 > < 運(yùn)算符，因?yàn)槲覀儾⒉恢廊绾闻判?，按照什么?biāo)準(zhǔn)排序，為了更好說明問題，來盤代碼。
#include <iostream>
#include "priority_queue.h"
#include <algorithm>
#include <vector>
using namespace std;
//仿函數(shù)的應(yīng)用
struct Phone{
int saleNum;
int price;
//.....
};
struct LessPhonePrice{
bool operator()(const Phone& p1, const Phone& p2)
{
return p1.price < p2.price;
}
};
struct LessPhoneSaleNum{
bool operator()(const Phone& p1, const Phone& p2)
{
return p1.saleNum < p2.saleNum;
}
};
void TestSort()
{
vector <Phone> gv = { { 1, 3 }, { 5, 2 }, { 2, 10 } };
sort(gv.begin(), gv.end(),LessPhoneSaleNum());//匿名對(duì)象會(huì)在STL中調(diào)用我自己寫的比較方法
sort(gv.begin(), gv.end(), LessPhonePrice());
}
int main()
{
TestSort();
return 0;
}
3.4 priority_queue 模擬實(shí)現(xiàn)
因?yàn)閮?yōu)先級(jí)隊(duì)列的底層結(jié)構(gòu)就是堆所以對(duì) vector 進(jìn)行適當(dāng)封裝就可以了，如果不知道堆的知識(shí)請(qǐng)參考我的另外一篇文章 http://www.dbjr.com.cn/article/210171.htm
#pragma once
//仿函數(shù)
template<class T>
class Less{
public:
bool operator()(const T& t1, const T& t2) const
{
return t1 < t2;
}
};
template<class T>
class Greater{
public:
bool operator()(const T& t1, const T& t2) const
{
return t1 > t2;
}
};
namespace czh{
template<class T, class Container = vector<T>, class Compare = Greater<T>>
class priority_queue {
public:
priority_queue() = default;
/*priority_queue()
{}*/
template<class InputIterator>
priority_queue(InputIterator first, InputIterator last)
:_con(first, last)
{
//利用向下調(diào)整算法，從下到上建堆
/*for (int i = (_con.size() - 2) / 2; i >= 0; i--)
{
AdjustDown(i);
}*/
利用向上調(diào)整算法，從上到下調(diào)整
for (size_t i = 1; i < _con.size(); i++)
{
AdjustUp(i);
}
}
void push(const T& data)
{
_con.push_back(data);
// 向上調(diào)整
AdjustUp(_con.size() - 1);
}
void pop()
{
if (empty()) return;
swap(_con.front(),_con.back());
_con.pop_back();
AdjustDown(0);
}
size_t size() const
{
return _con.size();
}
const T& top() const
{
return _con.front();
}
bool empty() const
{
return _con.empty();
}
private:
//向上調(diào)整算法
void AdjustUp(int child)
{
Compare com;
int parent = (child - 1) >> 1;
while (child > 0)
{
/*if (_con[child] > _con[parent])*/
if (com(_con[child], _con[parent]))
{
swap(_con[child], _con[parent]);
child = parent;
parent = (child - 1) >> 1;
}
else
{
break;
}
}
}
void AdjustDown(int parent)
{
Compare com;
size_t child = 2 * parent + 1;
while (child < _con.size())
{
/*if (child + 1 < _con.size() && _con[child + 1] < _con[child])*/
if (child + 1 < _con.size() && com(_con[child + 1], _con[child]))
{
child++;
}
/*if (_con[child] > _con[parent])*/
if (com(_con[child], _con[parent]))
{
swap(_con[child], _con[parent]);
parent = child;
child = 2 * parent + 1;
}
else
{
break;
}
}
}
//向下調(diào)整算法
Container _con;
};
}
4 容器適配器模式
適配器是一種設(shè)計(jì)模式(設(shè)計(jì)模式是一套被反復(fù)使用的、多數(shù)人知曉的、經(jīng)過分類編目的、代碼設(shè)計(jì)經(jīng)驗(yàn)的總結(jié))，該種模式是將一個(gè)類的接口轉(zhuǎn)換成客戶希望的另外一個(gè)接口。
上面介紹的3種數(shù)據(jù)結(jié)構(gòu)都是容器適配器（container adapter）。
到此這篇關(guān)于C++ STL中的容器適配器實(shí)現(xiàn)的文章就介紹到這了,更多相關(guān)C++ STL容器適配器內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！
相關(guān)文章
本文章主要為分享C/C++ INI文件操作實(shí)現(xiàn)代碼，增加注釋和修復(fù)了一些問題。這里給出完整的實(shí)現(xiàn)文件，在需要的地方包含該頭文件就好了2020-02-02
本篇文章對(duì)小編void以及void指針的含義進(jìn)行了詳細(xì)的分析和介紹。需要的朋友參考下2013-05-05
static_cast,dynamic_cast,reinterpret_cast和const_cast的區(qū)別詳解
以下是對(duì)static_cast,dynamic_cast,reinterpret_cast和const_cast之間的區(qū)別進(jìn)行了詳細(xì)的介紹，需要的朋友可以過來參考下2013-09-09
C++從文本文件讀取數(shù)據(jù)到vector中的方法
這篇文章主要給大家介紹了利用C++如何從文本文件讀取數(shù)據(jù)到vector中，文章通過實(shí)例給出示例代碼，相信會(huì)對(duì)大家的理解和學(xué)習(xí)很有幫助，有需要的朋友們下面來一起看看吧。2016-10-10
C/C++?Qt?選擇夾TabWidget組件實(shí)現(xiàn)導(dǎo)航欄切換
Tab切換在很多地方都可以使用的到，本文就使用TabWidget組件來實(shí)現(xiàn)一下，文中通過示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2021-11-11
C/C++?Qt?StringListModel?字符串列表映射組件詳解
StringListModel?字符串列表映射組件，該組件用于處理字符串與列表框組件中數(shù)據(jù)的轉(zhuǎn)換，通常該組件會(huì)配合ListView組件一起使用，本文給大家介紹了C/C++?Qt?StringListModel?字符串列表映射組件的相關(guān)知識(shí)，感興趣的朋友跟隨小編一起看看吧2021-12-12
最近正在閱讀關(guān)于C語言的庫,但是我還沒有find關(guān)于目標(biāo)文件的解釋,這篇文章主要給大家介紹了C語言目標(biāo)文件的詳細(xì)講解,文中介紹的非常詳細(xì),需要的朋友可以參考下2023-01-01
C++中指針的數(shù)據(jù)類型和運(yùn)算相關(guān)知識(shí)小結(jié)
這篇文章主要介紹了C++中指針的數(shù)據(jù)類型和運(yùn)算相關(guān)知識(shí)小結(jié),是C++入門學(xué)習(xí)中的基礎(chǔ)知識(shí),需要的朋友可以參考下2015-09-09
traits就是提取“被傳進(jìn)的對(duì)象”對(duì)應(yīng)的返回類型，讓同一個(gè)接口實(shí)現(xiàn)對(duì)應(yīng)的功能。因?yàn)镾TL的算法和容器是分離的，兩者通過迭代器鏈接，本文通過實(shí)例代碼給大家介紹C++ traits技術(shù)，感興趣的朋友一起看看吧2021-05-05
嵌入式項(xiàng)目使用C語言結(jié)構(gòu)體位段特性實(shí)現(xiàn)斷言宏校驗(yàn)數(shù)據(jù)范圍有效性的方法
今天小編就為大家分享一篇關(guān)于嵌入式項(xiàng)目使用C語言結(jié)構(gòu)體位段特性實(shí)現(xiàn)斷言宏校驗(yàn)數(shù)據(jù)范圍有效性的方法，小編覺得內(nèi)容挺不錯(cuò)的，現(xiàn)在分享給大家，具有很好的參考價(jià)值，需要的朋友一起跟隨小編來看看吧2018-12-12