目錄

1、Deque(了解)

1.1 起源

1.2 結構

1.3 優缺點

1.4 應用

2、Stack

3、Queue

4、Priority_Queue

---

注意：stack，queue，priority_queue是容器適配器(container adaptor) ，封裝一個容器，按照某種規則使用，一般不實現迭代器。

1、Deque(了解)

1.1 起源

vector和list優缺點，挺互補的，能不能實現一個容器，都具備他們的優點，就這樣，deque誕生了，但是從現在來看，deque，并不算成功?。

1.2 結構

中控數組(map)，是一個指針數組，指針指向一個buffer數組的地址，通過迭代器遍歷。

細節：

1. map中的指針，一開始放在中間位置，方便頭插數據。

2. 使用兩個迭代器，start，finish。

3. 通過，取模，除，找到是在第幾個buffer數組的第幾個位置。

1.3 優缺點

優點：

1. 頭插尾插效率高。

2. 隨機下標訪問也不錯。

缺點：

3. 中部位置插入刪除，需挪動數據，效率低。

4. 遍歷數據，需頻繁檢查，效率低。

1.4 應用

STL中對stack和queue默認選擇deque作為其底層容器，主要是因為：

1. stack和queue不需要遍歷(因此stack和queue沒有迭代器)，只需要在固定的一端或者兩端進行操作。

2. 在stack中元素增長時，deque比vector的效率高(擴容時不需要搬移大量數據)；

? ? 在queue中元素增長時，deque不僅效率高，而且內存使用率高。(一次開更多的空間，只存數據，不存節點)

2、Stack

#pragma once
#include <deque>using namespace std;namespace Lzc
{template<class T, class Container = deque<T>>class stack{public:void push(const T& val){_con.push_back(val);}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;};
}

3、Queue

#pragma once
#include <deque>using namespace std;namespace Lzc
{template<class T,class Container = deque<T>>class queue{public:void push(const T& val){_con.push_back(val);}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;};
}

4、Priority_Queue

容器適配器，封裝vector，采用堆的結構。堆+堆排序+topK問題_大頂堆小頂堆java-CSDN博客

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

如：Less le;? ? le.operator()(x,y) 等價于?le(x,y);

#include <algorithm>
#include <vector>using namespace std;// less(<) 升序
// greater(>) 降序
template<class T>
struct Less
{bool operator()(const T& x, const T& y){return x < y;}
};template<class T>
struct Greater
{bool operator()(const T& x, const T& y){return x > y;}
};int main()
{vector<int> v = {3,2,4,5,1,6,7,8,9};// void sort (RandomAccessIterator first, RandomAccessIterator last, Compare comp);sort(v.begin(),v.end(),Less<int>()); // 升序 函數模板，傳對象(匿名對象)sort(v.begin(),v.end(),Greater<int>()); // 降序return 0;
}

std::priority_queue，默認less，建大堆。

#pragma once
#include <vector>using namespace std;namespace Lzc
{template<class T, class Container = vector<T>, class Compare = less<T>> // 使用std中的less<T>和greater<T>class priority_queue{public:void AdjustUp(size_t child)//建大堆，child為插入元素的下標{size_t parent = (child - 1) / 2;Compare com;while (child > 0){//if (_con[parent] < _con[child])if (com(_con[parent], _con[child])) //建大堆{swap(_con[parent], _con[child]);child = parent;parent = (parent - 1) / 2;}elsebreak;//沒有交換，則就是在這個位置}}void AdjustDown(size_t parent)//建大堆,n為a的元素個數，parent為要向下調整的元素下標{size_t child = 2 * parent + 1;Compare com;while (child < size()){//if (_con[child] < _con[child + 1] && child + 1 < n) // 假設法，建大堆if (com(_con[child], _con[child + 1] && child + 1 < size()))child++;// if (_con[parent] < _con[child]) // 建大堆if (com(_con[parent], _con[child])){swap(_con[parent], _con[child]);parent = child;child = 2 * child + 1;}elsebreak;}}void push(const T& val){_con.push_back(val);AdjustUp(size() - 1);}void pop(){swap(_con[0], _con[size() - 1]);_con.pop_back();AdjustDown(0);}const T& top() const{return _con.front();}size_t size() const{return _con.size();}bool empty() const{return _con.empty();}private:Container _con;};
}