容器適配器

容器適配器（Container Adapter） 是一種基于現有容器類（如 vector、deque、list 等）構建的 包裝器（Wrapper）。

1.容器適配器本身不直接管理數據存儲，而是依賴底層容器（稱為 底層容器 或 基礎容器）實現存儲和訪問操作。例如：

stack 默認基于 deque 實現。
queue 默認基于 deque 實現。
priority_queue 默認基于 vector 實現。

2.適配器會屏蔽底層容器的部分接口，僅暴露特定操作所需的接口。

棧（stack） 只允許在棧頂進行插入（push）和刪除（pop）操作，屏蔽了隨機訪問等功能。
隊列（queue） 只允許在隊尾插入（push）、隊頭刪除（pop），屏蔽了中間元素的操作。

3.底層容器可定制。

#include <stack>
#include <vector>
#include <list>// 使用 vector 作為底層容器
std::stack<int, std::vector<int>> stack1;// 使用 list 作為底層容器
std::stack<int, std::list<int>> stack2;

priority_queue(優先級隊列）

priority_queue的使用

int main()
{priority_queue<int> pq;//默認是大的優先級高(大堆）//變小堆//priority_queue<int,vector<int>,greater<int>> pq;pq.push(4);pq.push(1);pq.push(5);pq.push(7);pq.push(9);while (!pq.empty()){cout << pq.top() << " ";pq.pop();}cout << endl;return 0;
}

大堆調試：

小堆調試：

priority_queue的模擬實現：

#include<vector>template<class T>
class Less
{
public:bool operator()(const T& x, const T& y){return x < y;}
};template<class T>
class Greater
{
public:bool operator()(const T& x, const T& y){return x > y;}
};namespace bit
{// 默認是大堆template<class T, class Container = vector<T>, class Compare = Less<T>>class priority_queue{public:void AdjustUp(int child){Compare com;int parent = (child - 1) / 2;while (child > 0){//if (_con[parent] < _con[child])if (com(_con[parent], _con[child])){swap(_con[child], _con[parent]);child = parent;parent = (child - 1) / 2;}else{break;}}}void push(const T& x){_con.push_back(x);AdjustUp(_con.size() - 1);}void AdjustDown(int parent){// 先假設左孩子小size_t child = parent * 2 + 1;Compare com;while (child < _con.size())  // child >= n說明孩子不存在，調整到葉子了{// 找出小的那個孩子//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[child], _con[parent]);parent = child;child = parent * 2 + 1;}else{break;}}}void pop(){swap(_con[0], _con[_con.size() - 1]);_con.pop_back();AdjustDown(0);}const T& top(){return _con[0];}size_t size() const{return _con.size();}bool empty() const{return _con.empty();}private:Container _con;};
}

仿函數

什么叫仿函數？

仿函數：本質是一個類，這個類重載operator(),他的對象可以像函數一樣使用

template<class T>
class Less
{
public:bool operator()(const T& x, const T& y){return x < y;}
};template<class T>
class Greater
{
public:bool operator()(const T& x, const T& y){return x > y;}
};// < 升序
// > 降序
template<class Compare>
void BubbleSort(int* a, int n, Compare com)
{for (int j = 0; j < n; j++){// 單趟int flag = 0;for (int i = 1; i < n - j; i++){//if (a[i] < a[i - 1])if (com(a[i], a[i - 1])){swap(a[i - 1], a[i]);flag = 1;}}if (flag == 0){break;}}
}int main()
{Less<int> LessFunc;Greater<int> GreaterFunc;// 函數對象（仿函數）本質是一個對象cout << LessFunc(1, 2) << endl;cout << LessFunc.operator()(1, 2) << endl;int a[] = { 9,1,2,5,7,4,6,3 };BubbleSort(a, 8, LessFunc);BubbleSort(a, 8, GreaterFunc);BubbleSort(a, 8, Less<int>());BubbleSort(a, 8, Greater<int>());return 0;
}

需要自己實現仿函數的情況：

1.類類型不支持比較大小。
2.支持比較大小，但是比較的邏輯不是你想要的。

class Date
{friend ostream& operator<<(ostream& _cout, const Date& d);
public:Date(int year = 1900, int month = 1, int day = 1): _year(year), _month(month), _day(day){}bool operator<(const Date& d)const{return (_year < d._year) ||(_year == d._year && _month < d._month) ||(_year == d._year && _month == d._month && _day < d._day);}bool operator>(const Date& d)const{return (_year > d._year) ||(_year == d._year && _month > d._month) ||(_year == d._year && _month == d._month && _day > d._day);}
private:int _year;int _month;int _day;
};ostream& operator<<(ostream& _cout, const Date& d)
{_cout << d._year << "-" << d._month << "-" << d._day;return _cout;
}class DateLess
{
public:bool operator()(Date* p1, Date* p2){return *p1 < *p2;}
};
//測試
priority_queue<Date*, vector<Date*>, DateLess> q2;priority_queue<Date*> q2;q2.push(new Date(2018, 10, 29));q2.push(new Date(2018, 10, 28));q2.push(new Date(2018, 10, 30));cout << *q2.top() << endl;q2.pop();cout << *q2.top() << endl;q2.pop();cout << *q2.top() << endl;q2.pop();

棧的模擬實現

#include<deque>namespace bit
{// Container適配轉換出stacktemplate<class T, class Container = deque<T>>//deque:vector和list的縫合怪class stack{public:void push(const T& x){_con.push_back(x);}void pop(){_con.pop_back();}const T& top() const{return _con.back();}size_t size() const{return _con.size();}bool empty() const{return _con.empty();}private:Container _con;};}

隊列的模擬實現

#include<deque>namespace bit
{// Container適配轉換出queuetemplate<class T, class Container = deque<T>>class queue{public:void push(const T& x){_con.push_back(x);}void pop(){_con.pop_front();}const T& front() const{return _con.front();}const T& back() const{return _con.back();}size_t size() const{return _con.size();}bool empty() const{return _con.empty();}private:Container _con;};
}

deque（vector和list的縫合怪）

為什么選擇deque作為stack和queue的底層默認容器？

stack是一種后進先出的特殊線性數據結構，因此只要具有push_back()和pop_back()操作的線性結構，都可以作為stack的底層容器，比如vector和list都可以；queue是先進先出的特殊線性數據結構，只要具有push_back和pop_front操作的線性結構，都可以作為queue的底層容器，比如list。但是STL中對stack和queue默認選擇deque作為其底層容器，主要是因為：

1. stack和queue不需要遍歷(因此stack和queue沒有迭代器)，只需要在固定的一端或者兩端進行操作。
2. 在stack中元素增長時，deque比vector的效率高(擴容時不需要搬移大量數據)；queue中的元素增長時，deque不僅效率高，而且內存使用率高。結合了deque的優點，而完美的避開了其缺陷。

deque的優缺點

vector和list的優缺點