目錄
1、stack
1.1、stack的使用
1.2、stack的OJ題
1.2.1、最小棧
1.2.2、棧的壓入彈出序列
1.2.3、逆波蘭表達式求值
1.3、stack的模擬實現
2、queue
2.1、queue的使用
2.2、queue的OJ題
2.2.1、二叉樹的層序遍歷
2.3、queue的模擬實現
3、priority_queue
3.1、priority_queue的使用
3.2、priority_queue的OJ題
3.2.1、數組中第k大的元素
3.3、仿函數
3.3.1、仿函數的概念
3.3.2、less以及greater模擬實現
3.4、priority_queue的模擬實現
4、deque
4.1、deque的結構
4.2、deque的使用
4.2.1、構造及賦值重載
4.2.2、迭代器
4.2.3、容量
4.2.4、訪問
4.2.5、修改
適配器是一種設計模式(設計模式是一套被反復使用的、多數人知曉的、經過分類編目的、代碼設計經驗的總結),該種模式是將一個類的接口轉換成客戶希望的另外一個接口。
雖然stack和queue中也可以存放元素,但在STL中并沒有將其劃分在容器的行列,而是將其稱為容器適配器,這是因為stack和queue以及priority_queue只是對其他容器的接口進行了包裝,STL中stack和queue默認使用deque作為容器,priority_queue默認以vector作為容器。
1、stack
template <class T, class Container = deque<T> > class stack;
stack的文檔介紹
stack是一種容器適配器,專門用在具有后進先出操作的上下文環境中,其刪除只能從容器的一端進行元素的插入與提取操作。stack是作為容器適配器被實現的,容器適配器即是對特定類封裝作為其底層的容器,并提供一組特定的成員函數來訪問其元素。其結構如圖所示:
stack的底層容器應該支持以下操作:
empty:判空操作。
back:獲取尾部元素操作。
push_back:尾部插入元素操作。
pop_back:尾部刪除元素操作。
size:獲取有效元素的個數。
標準容器vector、deque、list均符合這些需求,默認情況下,如果沒有為stack指定特定的底層容器, 默認情況下使用deque。
1.1、stack的使用
bool empty() const;size_type size() const;reference top();
const_reference top() const;void push (const value_type& val);void pop();
例如:
int main()
{ stack<int> st;st.push(1);st.push(2);st.push(3);st.push(4);st.push(5);while (!st.empty()){cout << st.top() << ' ';st.pop();}cout << endl;return 0;
}
1.2、stack的OJ題
1.2.1、最小棧
最小棧
參考:
1.2.2、棧的壓入彈出序列
棧的壓入彈出序列
參考:
1.2.3、逆波蘭表達式求值
逆波蘭表達式求值
?參考:
1.3、stack的模擬實現
template<class T,class Container=deque<T>>
class stack
{
public:void push(const T& x){_con.push_back(x);}void pop(){_con.pop_back();}const T& top(){return _con.back();}bool empty(){return _con.empty();}size_t size(){return _con.size();}private:Container _con;
};
2、queue
template < class T, class Alloc = allocator<T> > class deque;
queue的文檔介紹
隊列是一種容器適配器,專門用于先進先出的操作,其中從容器一端插入元素,另一端提取元素。 隊列作為容器適配器實現,容器適配器即將特定容器類封裝作為其底層容器類,元素從隊尾入隊列,從隊頭出隊列。結構如圖所示:
該底層容器應至少支持以下操作:
empty:隊列是否為空
size:有效元素的個數
front:返回隊頭元素
back:返回隊尾元素
push_back:在隊列尾部入隊列
pop_front:在隊列頭部出隊列
標準容器類deque和list滿足了這些要求。默認情況下,如果沒有為queue實例化指定容器類,則使用標準容器deque。
2.1、queue的使用
bool empty() const;size_type size() const;value_type& front();
const value_type& front() const;value_type& back();
const value_type& back() const;void push (const value_type& val);void pop();
例如:
int main()
{ queue<int> q;q.push(1);q.push(2);q.push(3);q.push(4);q.push(5);while (!q.empty()){cout << q.front() << ' ';q.pop();}cout << endl;return 0;
}
2.2、queue的OJ題
2.2.1、二叉樹的層序遍歷
二叉樹的層序遍歷
參考:
2.3、queue的模擬實現
template<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(){return _con.front();}const T& back(){return _con.back();}bool empty(){return _con.empty();}size_t size(){return _con.size();}
private:Container _con;
};
3、priority_queue
template <class T, class Container = vector<T>, class Compare = less<typename Container::value_type> >
class priority_queue;
priority_queue文檔介紹
優先隊列是一種容器適配器,邏輯結構就是堆。 優先隊列被實現為容器適配器,容器適配器即將特定容器類封裝作為其底層容器類,提供一組特定的成員函數來訪問其元素。需要支持隨機訪問迭代器,以便始終在內部保持堆結構。
容器應該可以通過隨機訪問迭代器進行訪問,并支持以下操作:
empty():檢測容器是否為空
size():返回容器中有效元素個數
front():返回容器中第一個元素的引用
push_back():在容器尾部插入元素
pop_back():刪除容器尾部元素
標準容器類vector和deque滿足這些需求。默認情況下,如果沒有為特定的priority_queue類實例化指定容器類,則使用vector。
3.1、priority_queue的使用
bool empty() const;size_type size() const;const value_type& top() const;void push (const value_type& val);void pop();
例如:
int main()
{ priority_queue<int> q;q.push(3);q.push(1);q.push(5);q.push(4);while (!q.empty()){cout << q.top() << ' ';q.pop();}cout << endl;return 0;
}
默認是大堆,如果想要小堆,可以像下面這樣寫:
int main()
{ priority_queue<int, vector<int>, greater<int>> q;q.push(3);q.push(1);q.push(5);q.push(4);while (!q.empty()){cout << q.top() << ' ';q.pop();}cout << endl;return 0;
}
注意:如果在priority_queue中放自定義類型的數據,用戶需要在自定義類型中提供> 或者< 的重載。例如:
class Date
{
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);}friend ostream& operator<<(ostream& _cout, const Date& d);private:int _year;int _month;int _day;
};ostream& operator<<(ostream& _cout, const Date& d)
{_cout << d._year << "-" << d._month << "-" << d._day;return _cout;
}struct PDateCompare
{bool operator()(Date* p1, Date* p2){return *p1 > *p2;}
};int main()
{priority_queue<Date> q1;q1.push(Date(2018, 10, 29));q1.push(Date(2018, 10, 28));q1.push(Date(2018, 10, 30));cout << q1.top() << endl;priority_queue<Date*, vector<Date*>, PDateCompare> 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;return 0;
}
3.2、priority_queue的OJ題
3.2.1、數組中第k大的元素
數組中第k大的元素
參考:
3.3、仿函數
3.3.1、仿函數的概念
在C++中,仿函數是指一個可以像函數一樣被調用的對象。通常通過定義一個類,并在該類中重載函數調用運算符 operator() 來實現。比如:在functional中的less和greater用來比較大小
template <class T> struct less;template <class T> struct greater;
例如:
int main()
{ less<int> ls;cout << ls(2, 3) << endl;greater<int> gt;cout << gt(2, 3) << endl;return 0;
}
3.3.2、less以及greater模擬實現
//仿函數
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;}
};
3.4、priority_queue的模擬實現
template<class T, class Container = vector<T>, class Compare = Less<T>>
class Priority_queue
{
public:Priority_queue(){}template<class InputIterator> //構造函數Priority_queue(InputIterator first, InputIterator last):_con(first,last){//建堆for (int i = (_con.size() - 2) / 2; i >= 0; --i){adjust_down(i);}}void adjust_up(int child){Compare com;int parent = (child - 1) / 2;while (child > 0){if(com(_con[parent],_con[child]))//if (_con[parent] < _con[child]){swap(_con[child], _con[parent]);child = parent;parent = (parent - 1) / 2;}elsebreak;}}void adjust_down(int parent){Compare com;size_t child = parent * 2 + 1;while (child < _con.size())//vector的size()的返回值都是size_t。{if (child + 1 < _con.size() && com(_con[child], _con[child+1]))//if (child + 1 < _con.size() && _con[child] < _con[child+1]){++child;}if (com(_con[parent],_con[child]))//if (_con[parent] < _con[child]){swap(_con[child], _con[parent]);parent = child;child = parent * 2 + 1;}elsebreak;}}void push(const T& x){_con.push_back(x);adjust_up(_con.size() - 1);}void pop(){swap(_con[0], _con.size() - 1);_con.pop_back();adjust_down(0);}const T& top(){return _con[0];}bool empty(){return _con.empty();}size_t size(){return _con.size();}private:Container _con;
};
4、deque
template < class T, class Alloc = allocator<T> >
class deque;
deque又稱為雙端隊列(是容器):是一種雙開口的“連續”空間的數據結構,雙開口的含義是可以在頭尾兩端進行插入和刪除操作,且時間復雜度為O(1),與vector比較,頭插效率高,不需要搬移元素;與list比較,空間利用率比較高。
連續物理空間,優點:極致高效的下標隨機訪問;缺點:擴容以及中間或者頭部插入刪除效率低(因為要挪動數據),比如以vector為代表。非連續物理空間,優點:任意位置的插入刪除效率高,按需申請釋放;缺點:不支持下標隨機訪問,比如以list為代表。
4.1、deque的結構
Deque是由一段段的定長的連續空間構成以及中控器構成,Deque的最大的工作就是維護這些分段連續的內存空間的整體性的假象,而維持這種假象的就是中控器,中控器的本質就是指針數組,其中每個元素都是一個指針,指向一段定長的連續的空間(本質也是數組),稱為緩沖區,緩沖區才是deque的存儲空間的主體。如下圖所示:
deque并不是真正連續的空間,而是由一段段連續的小空間拼接而成的,實際是分段連續的,為了維護其“整體連續”以及隨機訪問的假象,deque的迭代器設計的就比較復雜,如下圖所示:
與vector比較,deque的優勢是頭部插入和刪除時,不需要搬移元素,效率特別高,而且在擴容時,也不需要搬移大量的元素,因此其效率是必vector高的。 與list比較,其底層是連續空間,空間利用率比較高,不需要存儲額外字段。
但是,deque有一個致命缺陷就是不適合遍歷,因為在遍歷時,deque的迭代器要頻繁的去檢測其是否移動到某段小空間的邊界,導致效率低下,而在有些場景中,可能需要經常遍歷,因此在實際中,需要線性結構時,大多數情況下優先考慮vector和list,deque的應用并不多,而目前能看到的一個應用就是,STL用其作為stack和queue的底層數據結構。
stack是一種后進先出的特殊線性數據結構,因此只要具有push_back()和pop_back()操作的線性結構,都可以作為stack的底層容器,比如vector和list都可以;queue是先進先出的特殊線性數據結構,只要具有 push_back和pop_front操作的線性結構,都可以作為queue的底層容器,比如list。但是STL中stack和queue默認選擇deque作為其底層容器,主要是因為:
1、stack和queue不需要遍歷,只需要在固定的一端或者兩端進行操作。
2、在stack中元素增長時,deque比vector的效率高(擴容時不需要搬移大量數據);queue中的元素增長時,deque不僅效率高,而且內存使用率高。
4.2、deque的使用
4.2.1、構造及賦值重載
explicit deque (const allocator_type& alloc = allocator_type());explicit deque (size_type n, const value_type& val = value_type(),const allocator_type& alloc = allocator_type());template <class InputIterator>
deque (InputIterator first, InputIterator last,const allocator_type& alloc = allocator_type());deque (const deque& x);deque& operator= (const deque& x);
4.2.2、迭代器
iterator begin();
iterator end();const_iterator begin() const;
const_iterator end() const;reverse_iterator rbegin();
reverse_iterator rend();const_reverse_iterator rbegin() const;
const_reverse_iterator rend() const;
例如:?
int main()
{ deque<int> dq1;deque<int> dq2(5, 3);deque<int> dq3(dq2.begin(), dq2.end());deque<int> dq4(dq3);dq1 = dq4;deque<int>::iterator it1 = dq1.begin();while (it1 != dq1.end()){cout << *it1 << ' ';++it1;}cout << endl;return 0;
}
4.2.3、容量
size_type size() const;void resize (size_type n, value_type val = value_type());bool empty() const;
4.2.4、訪問
reference operator[] (size_type n);
const_reference operator[] (size_type n) const;reference front();
const_reference front() const;reference back();
const_reference back() const;
例如:?
int main()
{ deque<int> dq(5, 2);cout << dq.size() << endl;cout << dq.empty() << endl;dq.resize(10, 3);cout << dq.size() << endl;for (auto e : dq){cout << e << ' ';}cout << endl;cout << --dq.front() << endl;cout << ++dq.back() << endl;for (int i = 0; i < dq.size(); ++i){cout << dq[i] << ' ';}cout << endl;deque<int>::reverse_iterator it = dq.rbegin();while (it != dq.rend()){cout << *it << ' ';++it;}cout << endl;return 0;
}
4.2.5、修改
void push_back (const value_type& val);void push_front (const value_type& val);void pop_back();void pop_front();iterator insert (iterator position, const value_type& val);iterator erase (iterator position);void swap (deque& x);void clear();
例如:
int main()
{ deque<int> dq;dq.push_back(1);dq.push_back(2);dq.push_back(3);dq.push_back(4);dq.push_back(5);dq.erase(dq.begin() + 2);dq.insert(dq.end(), 9);for (auto e : dq){cout << e << ' ';}cout << endl;deque<int> dq2;dq2.swap(dq);for (auto e : dq2){cout << e << ' ';}cout << endl;dq2.clear();cout << dq.size() << endl;cout << dq2.size() << endl;return 0;
}