STL學習筆記5 —— Container Adaptor

一、容器介面卡

接下來介紹 3 種容器介面卡，分別是 stack、queue、priority_queue：

• stack：是一個封裝了 deque 容器的介面卡類別範本，預設實現的是一個後入先出（Last-In-First-Out，LIFO）的壓入棧。stack 模板定義在標頭檔案 stack 中。
• queue：是一個封裝了 deque 容器的介面卡類別範本，預設實現的是一個先入先出（First-In-First-Out，LIFO）的佇列。可以為它指定一個符合確定條件的基礎容器。queue 模板定義在標頭檔案 queue 中。
• priority_queue：是一個封裝了 vector 容器的介面卡類別範本，預設實現的是一個會對元素排序，從而保證最大元素總在佇列最前面的佇列。priority_queue 模板定義在標頭檔案 queue 中。

簡單的理解容器介面卡：將不適用的序列式容器（包括 vector、deque 和 list）變得適用

功能如下：

container addaptor	characteristic	functions
stack	LIFO	push()、pop()、top()
queue	FIFO	push()、pop()、front()、back()
priority_queue	first item is the greatest priority	push()、pop()、top()

三類容器介面卡均無迭代器，因此存取元素的唯一方式是遍歷容器，通過不斷移除存取過的元素，去存取下一個元素

---

二、stack容器

1. stack的特點與使用

棧中儲存的元素滿足「後進先出（簡稱LIFO）」的準則，stack 介面卡也同樣遵循這一準則。

由於 stack 介面卡以模板類 stack<T,Container=deque<T>>（其中 T 為儲存元素的型別，Container 表示底層容器的型別）的形式位於標頭檔案中，並定義在 std 名稱空間裡。第二個引數預設為 deque，可以指定第二個引數的型別，只要該容器支援 empty()、size()、back()、push_back()、pop_back() 這 5 個成員函數即可，如：vector、deque 和 list：

std::stack<std::string, std::list<int>> values;

2. stack的成員函數

函數	功能
size()	返回元素個數
empty()	若stack為空則返回true
top()	返回棧頂元素的參照&，棧空則報錯
push(const T& val)	將val壓棧，利用了push_back()來實現
pop()	彈棧操作

舉例：

#include <iostream>
#include <stack>
#include <list> 
using namespace std;

int main()
{
	stack<int> s;
	stack<int, std::list<int>> s1;
	s.push(2);
	s.push(5);
	s.push(1);
	s.push(8);
	
	cout << s.size() << endl;
	while(!s.empty()){
		cout << s.top() << " ";
		s.pop();
	}
	return 0;
}

結果：

4
8 1 5 2

---

三、queue容器

1. queue的特點與使用

這種儲存結構最大的特點是，最先進入 queue 的元素，也可以最先從 queue 中出來，即用此容器介面卡儲存資料具有「先進先出（簡稱 「FIFO」 ）」的特點，因此 queue 又稱為佇列介面卡。

queue容器包含在 <queue> 庫中，定義一個queue容器可以指定基礎容器（deque或list），底層使用的基礎容器選擇預設為 deque 容器

#include <queue>
#include <iostream>
using namespace std;

queue<int, deque<int>> q;
queue<int, std::list<int>> q1;

2. queue的成員函數

函數	功能
size()	返回元素個數
empty()	若stack為空則返回true
front()	返回 queue 中第一個元素的參照。如果 queue 是常數，就返回一個常參照；如果 queue 為空，返回值是未定義的
back()	返回 queue 中最後一個元素的參照。如果 queue 是常數，就返回一個常參照；如果 queue 為空，返回值是未定義的
push(const T& val)	在 queue 的尾部新增一個元素的副本。這是通過呼叫底層容器的成員函數 push_back() 來完成的。
pop()	刪除 queue 中的第一個元素。
swap(queue &other_queue)	交換兩個容器（要求底層基礎容器相同

3. queue的使用

#include <queue>
#include <iostream>
using namespace std;

int main()
{
	queue<int> myque;
	myque.push(5);
	myque.push(2);
	myque.push(2);
	myque.push(3);
	myque.push(6);
	
	cout << "size: " << myque.size() << endl;
	while (!myque.empty()){
		cout << myque.front() << " ";
		myque.pop();
	}
	return 0;
}

---

四、priority_queue容器

1. 特點

priority_queue容器遵循 「First in，Largest out」原則。直白的翻譯，指的就是先進佇列的元素並不一定先出佇列，而是優先順序最大的元素最先出佇列。每個 priority_queue 容器介面卡在建立時，都制定了一種排序規則。根據此規則，該容器介面卡中儲存的元素就有了優先順序高低之分。

2. 使用

STL 中，priority_queue 容器介面卡的定義如下：

template <typename T,
        typename Container=std::vector<T>,
        typename Compare=std::less<T> >
class priority_queue{
    //......
}

• priority_queue定義在 <queue> 標頭檔案中
• typename T：指定儲存元素的具體型別；
• typename Container：指定 priority_queue 底層使用的基礎容器，預設使用 vector 容器。
• typename Compare：指定容器中評定元素優先順序所遵循的排序規則，預設使用std::less按照元素值從大到小進行排序，還可以使用std::greater按照元素值從小到大排序，但更多情況下是使用自定義的排序規則。

作為 priority_queue 容器介面卡的底層容器，其必須包含 empty()、size()、front()、push_back()、pop_back() 這幾個成員函數，STL 序列式容器中只有 vector 和 deque 容器符合條件。

priority_queue的操作函數和stack的類似，包含了push()、pop()、top()、empty() 和 size() 等函數。

#include <iostream>
#include <queue>
using namespace std;

class Student{
	public:
		string name;
		int number;
		Student(string str, int n):name(str), number(n){}
};

struct mycmp{
	bool operator() (const Student &s1, const Student &s2){
		return s1.number < s2.number;	// 從大到小 
	}
};

int main()
{
	priority_queue<Student, deque<Student>, mycmp> pq;
	pq.push(Student("L", 12));
	pq.push(Student("Y", 3));
	pq.push(Student("U", 8));
	pq.push(Student("C", 5));
	
	cout << "Size = " << pq.size() << endl;
	cout << "name" << "t" << "number" << endl;
	while(!pq.empty()){
		Student stud = pq.top();
		cout << stud.name << "\t" << stud.number << endl;
		pq.pop();
	}
	return 0;
}

輸出結果為：

Size = 4
nametnumber
L       12
U       8
C       5
Y       3

---

參考內容：容器介面卡的使用