STL容器

STL容器
順序容器
- vector（向量）
- list（清單）
- deque（雙端隊列）
關聯容器
- set（集合）
- map（映射）
容器擴充卡
- stack（棧）
- queue（隊列）
- priority_queue（優先隊列）
總結

STL容器

在現實生活中，容器是用來裝其他東西的器具。在C++中，容器就是能容納其他對象的對象。STL中提供了豐富的容器，并且它們都是泛型容器，可以容納不同的資料類型。

STL中定義的容器可分為三類：

類别	容器
順序容器	vector（向量）、list（清單）、deque（隊列）
關聯容器	map（集合）、set（映射）、multimap（多重集合）、multiset（多重映射）
容器擴充卡	stack（棧）、queue（隊列）、priority_queue（優先隊列）

順序容器

順序容器中各元素之間有順序關系，順序容器中每個元素均有固定的位置，位置的先後關系由添加進容器的先後順序決定。STL中有三個順序容器，它們分别是vector、list和deque。

vector（向量）

vectors是一種線性順序結構，與數組很類似，但不用預先指定其大小。當資料所需的存儲空間大于目前配置設定的空間時，vector會自動申請一塊更大的記憶體，然後将原來的資料拷貝到新的記憶體中并銷毀原記憶體中的資料，最後将原來的記憶體空間釋放掉。是以，當資料量變化較大時，vector的性能就不是很好。

vector的特點如下：

1.不用預先指定大小，可動态配置設定記憶體

2.由于是線性結構，可對元素進行随機通路

3.插入和删除的效率非常低

4.當動态添加的資料超過預設配置設定的大小時，進行動态記憶體配置設定，資料拷貝等操作非常消耗性能。

建立

vector的操作定義于<vector>頭檔案中。vector提供了很多的構造函數重載，是以可以很靈活的定義并初始化一個vector。此外，vector還是一個模闆容器，是以适用于不同的資料類型。下面是一個建立vector的簡單例子。

#include <iostream>
#include <iterator>
#include <vector>
using namespace std;
int main() {
	vector<int> vec;
	vector<int> vec1 = vec;
	vector<int> vec2(vec);
	vector<int> vec3(vec.begin(), vec.end());
	vector<int> vec4(10);
	vector<int> vec5(10, 1);
	vector<char> vec6(10, 'X');
	vector<string> vec7(10, "Hello World");
	cout << vec.size() << endl;
	cout << vec1.size() << endl;
	cout << vec5.size() << endl;
	return 0;
}

0
0
10

增删插入

上面說到，由于vector在記憶體中的存儲特性，是以vector在插入與删除性能很差。是以盡量需要頻繁的在資料中間進行插入和删除操作時，不宜使用vector容器。vector提供了一個在末尾增删元素的方法，當資料長度在目前配置設定資料大小以内時，效果還是不錯的。

#include <iostream>
#include <iterator>
#include <vector>
using namespace std;
void print_vec(const vector<int> &vec);
int main() {
	vector<int> vec;
	for (int i = 0; i < 10; ++i) 
		vec.push_back(i);//添加10個元素{0, 1, ..., 9}
	print_vec(vec);
	vec.pop_back();//删除最後一個元素
	print_vec(vec);
	vec.pop_back();//删除最後一個元素
	print_vec(vec);
	vec.insert(vec.begin(), 2, 0);//效率很低
	print_vec(vec);
	vec.erase(vec.begin(), vec.end());
	//vec.clear();
	print_vec(vec);
	cout <<  "sizeof vec: " << vec.size() << endl;
	return 0;
}

vec: 0 1 2 3 4 5 6 7 8 9
vec: 0 1 2 3 4 5 6 7 8
vec: 0 1 2 3 4 5 6 7
vec: 0 0 0 1 2 3 4 5 6 7
vec:
sizeof vec: 0

周遊

通路vector中元素的方法一般有三種：

1.由于vector的随機通路特性，是以它可以和數組一樣使用下标通路。

2.使用疊代器通路，疊代器也是STL一個非常重要的内容，這裡先給出周遊方法，後面會詳細讨論。

3.使用range_based for(後面簡稱rangefor)，這是C++11新增的，類似于python中的 for in等，不需要指出開始和結束的條件。

void print_vec(const vector<int> &vec) {
	int length = vec.size();
	for (int i=0; i<length; i++)
		cout << vec[i] << " ";
	cout << endl;
}

void print_vec(const vector<int> &vec) {
	for (vector<int>::const_iterator it = vec.begin(); it != vec.end(); it++)
		cout << *it << " ";
	cout << endl;
}

void print_vec(const vector<int> &vec) {
	for(auto& i:vec)
		cout << i << " ";
	cout << endl;
}

相關函數

函數	作用
size()	傳回容器中元素個數
max_size()	傳回容器的最大容量
resize()	改變容器的容量
at()	通路某個下标的元素
capacity()	傳回目前配置設定的空間大小（元素個數）
empty()	判斷容器是否為空
reserve()	改變capacity大小
shrink_to_fit()	減少capacoty,使之與size大小相同
front()	傳回首元素
back()	傳回尾元素
data()	傳回指向容器中數組的指針
assign	給容器指派（完全替換掉以前的内容）
push_back()	在容器末尾增加一個元素
pop_back()	在容器末尾移出一個元素
insert()	在某個位置插入元素
erase()	删除某個位置的元素
swap()	交化兩個容器的内容
clear()	清除容器内容
emplace()	insert的優化版本
emplace_back()	push_back的優化版本
emplace_back()	在最後插入一個元素
get_allocator()	給容器配置設定空間
(c)(r)begin()	傳回指向第一個元素的（常）（反）疊代器
(c)(r)end()	傳回指向最後一個元素後面的（常）（反）疊代器

list（清單）

list是一種線性連結清單結構，學過資料結構的都知道，連結清單由若幹個結點組成，每個節點包含資料域和指針域。而list就相當于一個雙向連結清單，它的每個結點包含一個指向前驅的指針和一個指向後驅的指針。list在記憶體中不是連續的，是以無法像vector那樣随機存取。但由于list的鍊式結構，其插入和删除的效率很高。

vector的特點如下：

1.不用預先指定大小，可動态配置設定記憶體

2.不能随機通路，查找效率低

3.插入和删除的效率高

4.由于存在指針域，是以比vector占用更多空間

建立

list的操作定義于<list>頭檔案中。list的定義和初始化與vector非常相似，

#include <iostream>
#include <iterator>
#include <list>
using namespace std;
int main() {
	list<int> list0;
	list<int> list1 = list0;
	list<int> list2(list0);
	list<int> list3(list0.begin(), list0.end());
	list<int> list4(10);
	list<int> list5(10, 1);
	list<char> list6(10, 'X');
	list<string> list7(10, "Hello World");
	cout << list0.size() << endl;
	cout << list2.size() << endl;
	cout << list6.size() << endl;
	return 0;
}

0
0
10

增删插入

list的增删插入操作和vector的也十分類似，不過list中一些操作的效率要高很多。

#include <iostream>
#include <iterator>
#include <list>
using namespace std;
int main() {
	list<int> list1;
	for (int i = 0; i < 10; ++i)
		list1.push_back(i);//添加10個元素{0, 1, ..., 9}
	print_list(list1);
	list1.pop_back();//删除最後一個元素
	print_list(list1);
	list1.pop_back();//删除最後一個元素
	print_list(list1);
	list1.insert(list1.begin(), 2, 0);
	print_list(list1);
	list1.erase(list1.begin(), list1.end());
	//vec.clear();
	print_list(list1);
	cout << "sizeof vec: " << list1.size() << endl;
	return 0;
}

周遊

list容器無法用下标進行周遊，是以隻能用疊代器和rangefor對list進行周遊：

void print_list(const list<int> &contain) {
	for (list<int>::const_iterator it = contain.begin(); it != contain.end(); it++)
		cout << *it << " ";
	cout << endl;
}

void print_list(const list<int> &contain) {
	for(auto& it:contain)
		cout << *it << "";
}

相關函數

list容器有關的函數大多數都和vector容器的類似，不過其中也有一些不同，少了關于capacity相關的函數，另外還多了幾個特殊的函數。

函數	作用
size()	傳回容器中元素個數
max_size()	傳回容器的最大容量
resize()	改變容器的容量
at()	通路某個下标的元素
capacity()	傳回目前配置設定的空間大小（元素個數）
empty()	判斷容器是否為空
reserve()	改變capacity大小
shrink_to_fit()	減少capacoty,使之與size大小相同
front()	傳回首元素
back()	傳回尾元素
data()	傳回指向容器中數組的指針
assign	給容器指派（完全替換掉以前的内容）
push_back()	在容器末尾增加一個元素
pop_back()	在容器末尾移出一個元素
insert()	在某個位置插入元素
erase()	删除某個位置的元素
swap()	交化兩個容器的内容
clear()	清除容器内容
emplace()	insert的優化版本
emplace_back()	push_back的優化版本
emplace_back()	在最後插入一個元素
get_allocator()	給容器配置設定空間
(c)(r)begin()	傳回指向第一個元素的（常）（反）疊代器
(c)(r)end()	傳回指向最後一個元素後面的（常）（反）疊代器
push_front()	容器最前面插入一個元素
pop_front()	容器最前面移除一個元素
merge()	合并兩個容器
splice()	合并兩個容器
reverse()	将容器中的元素進行反轉
sort()	排序
unique()	删除重複元素
remove()	移除某些特定元素
remove_if()	移除某些滿足條件的元素

deque（雙端隊列）

從上面的讨論可以看出，vector的查找效率高，插入和删除的效率低；而list的插入和删除效率低，但查找效率卻很低。而deque則是一種結合了vector和list各自有點的容器，它有着較高的查找效率和插入删除效率。當然，deque在查找上肯定不如vector，插入删除上不如list，但它兼顧了兩者的優點，在很多情況下是很好的選擇。

是以，deque的特點如下：

1.支援随機通路，但性能不如vector

2.支援在内部進行插入和删除，但性能不如list

3.它也支援雙端push和pop

建立

deque的定義和初始化與二者類似：

#include <iostream>
#include <iterator>
#include <deque>
using namespace std;
int main() {
	deque<int> deque0;
	deque<int> deque1 = deque0;
	deque<int> deque2(deque0);
	deque<int> deque3(deque0.begin(), deque0.end());
	deque<int> deque4(10);
	deque<int> deque5(10, 1);
	deque<char> deque6(10, 'X');
	deque<string> deque7(10, "Hello World");
	cout << deque0.size() << endl;
	cout << deque2.size() << endl;
	cout << deque6.size() << endl;
	return 0;
}

增删插入

list的插入與删除與list差不太多，不過在效率上稍低，它同樣支援在容器頭進行push和pop。

#include <iostream>
#include <iterator>
#include <deque>
using namespace std;
int main() {
	deque<int> deque1;
	for (int i = 0; i < 10; ++i)
		deque1.push_front(i);//從deque頭添加10個元素{0, 1, ..., 9}
	print_deque(deque1);
	deque1.pop_back();//删除最後一個元素
	print_deque(deque1);
	deque1.pop_front();//删除第一個元素
	print_deque(deque1);
	deque1.insert(deque1.begin(), 2, 0);
	print_deque(deque1);
	deque1.erase(deque1.begin(), deque1.end());
	//vec.clear();
	print_deque(deque1);
	cout << "sizeof vec: " << deque1.size() << endl;
	return 0;
}

周遊

由于deque支援下标通路，是以deque也支援下标周遊、疊代器周遊以及rangefor三種方式，此處省略，可參考vector的周遊。

相關函數

deque大多數函數和vector一緻，不過删除了兩個與capacity有關的函數，增加了幾個操作首元素的函數，詳細變動如下：

函數	作用
size()	傳回容器中元素個數
max_size()	傳回容器的最大容量
resize()	改變容器的容量
at()	通路某個下标的元素
capacity()	傳回目前配置設定的空間大小（元素個數）
empty()	判斷容器是否為空
reserve()	改變capacity大小
shrink_to_fit()	減少capacoty,使之與size大小相同
front()	傳回首元素
back()	傳回尾元素
data()	傳回指向容器中數組的指針
assign	給容器指派（完全替換掉以前的内容）
push_back()	在容器末尾增加一個元素
pop_back()	在容器末尾移出一個元素
insert()	在某個位置插入元素
erase()	删除某個位置的元素
swap()	交化兩個容器的内容
clear()	清除容器内容
emplace()	insert的優化版本
emplace_back()	push_back的優化版本
get_allocator()	給容器配置設定空間
(c)(r)begin()	傳回指向第一個元素的（常）（反）疊代器
(c)(r)end()	傳回指向最後一個元素後面的（常）（反）疊代器
push_front()	容器最前面插入一個元素
emplace_front()	push_front的優化版本
pop_front()	容器最前面移除一個元素

關聯容器

關聯容器内部是一種非線性的樹形結構，具體來說是采用的一種高效的平衡檢索二叉樹-紅黑樹。關聯容器分為兩類，集合（set）和映射（map）。

set（集合）

set是一種非線性結構，是以它不具有随機通路的特性。set中的元素是唯一的，是以一個set中不允許有重複的元素，并且set會根據元素的值進行自動排序，是以set中的元素是有序的。multiset和set非常相似，不過取消元素值唯一這個限制。

set的特點如下：

1.非線性結構，不能随機通路

2.内部元素是唯一的

3.内部元素自動排序

4.具有優秀的檢索以及插入删除特性

建立

#include <iostream>
#include <iterator>
#include <set>
using namespace std;
void print_set(const set<int> &s) {
	for (set<int>::const_iterator it = s.begin(); it != s.end(); it++)
		cout << *it << " " ;
	cout << endl;
}
int main() {
	set<int> set1;
	set<int> set2 = { 3,2,2,4,5,6,1,9,2,2,3,4 };
	set<int> set3 = set2;
	set<int> set4(set2);
	cout << "set1: "; print_set(set1);
	cout << "set2: "; print_set(set2);
	cout << "set3: "; print_set(set3);
	cout << "set4: "; print_set(set4);
	return 0;
}

set1:
set2: 1 2 3 4 5 6 9
set3: 1 2 3 4 5 6 9
set4: 1 2 3 4 5 6 9

從結果可以看出，set中元素是唯一的且預設按升序排序。這裡讀者不妨試試multiset的效果，結果應該如下：

set1:
set2: 1 2 2 2 2 3 3 4 4 5 6 9
set3: 1 2 2 2 2 3 3 4 4 5 6 9
set4: 1 2 2 2 2 3 3 4 4 5 6 9

增删插入

由于set的樹形結構，沒有樹尾的說法，是以未提供push、pop等方法進行插入删除。下面是利用insert\emplace和erase進行插入删除的例子：

int main() {
	set<int> set1 = { 3,2,2,4,5,6,1,9,2,2,3,4 };
	cout << "origin:     "; print_set(set1);
	set1.insert(10);
	cout << "inset(10):  "; print_set(set1);
	set1.emplace(8);
	cout << "emplace(8): "; print_set(set1);
	set1.erase(2);
	cout << "erase(2):   "; print_set(set1);
	return 0;
}

origin:     1 2 3 4 5 6 9
inset(10):  1 2 3 4 5 6 9 10
emplace(8): 1 2 3 4 5 6 8 9 10
erase(2):   1 3 4 5 6 8 9 10

注意這裡插入和删除可能不成功，因為set中的元素唯一，如果該元素已經存在，就會插入失敗。是以insert和emplace其實是有傳回值的，它的類型為：pair<set::iterator, bool>，代表傳回一個pair,分别是指向該元素的疊代器和插入成功與否的bool值，用.first和.second來擷取二者，如下例：

int main() {
	set<int> set1 = { 3,2,2,4,5,6,1,9,2,2,3,4 };
	cout << *set1.insert(4).first << endl;
	cout << set1.insert(5).second << endl;
	cout << set1.insert(8).second << endl;
	return 0;
}

4
0
1

運作結果中，4代表傳回的疊代器指向的是4，0代表插入5失敗，因為5已經存在于set中了，1代表插入8成功。

周遊

set隻能通過疊代器和rangefor進行周遊，疊代器方法在上面的例子中其實已經給出，下面給出rangefor方法的示例。

for(auto& it:set)
		cout << *it << " " ;
	cout << endl;

相關函數

函數	作用
(c/r)begin()	傳回指向第一個元素的（常/反）疊代器
(c/r)end()	傳回指向最後一個元素後面的（常/反）疊代器
clear()	清空容器
count()	對某個元素進行計數
empty()	判斷容器是否為空
emplace()	insert的優化版本
emplace_hint()	依據提示插入（提示可以是eplace()傳回的疊代器）
erase()	删除元素
equal_range()	傳回pair<lower_bound, upper_bound>
find()	查找元素傳回指向該元素的疊代器
get_allocator()	擷取配置設定器
insert()	插入元素傳回pair<set<type>::iter, bool>
key_comp()	傳回比較準則
value_comp()	傳回對value的比較準則
size()	傳回容器中元素個數
max_size()	傳回可能的最大容量
swap()	交換兩個容器
lower_bound()	傳回lower_bound
upper_bound()	傳回upper_bound

map（映射）

map和set一樣是非線性樹形結構，其内部實作為紅黑樹，與set不同的是，map以pair<key/value>作為元素進行管理。map以key的排序準則将元素進行排序。此外，map的元素也是唯一的，當然，這個限制也可以靠multimap來取消。

map的特點如下：

1.非線性結構，不能随機通路

2.内部元素有序排列

3.key-value一一映射

建立

容器的建立方法其實大多相似，不過map由于是以key-value的方式存儲元素，是以在建立map時需要以<key/value>pair進行初始化。

#include <iostream>
#include <iterator>
#include <string>
#include <map>
using namespace std;
void print_map(const map<int, string> &map1);
int main() {
	map<int, string> map1 = {{1, "Hello"},{2, "World" }};
	map<int, string> map2 = map1;
	map<int, string> map3(map1);
	cout << "map1: "; print_map(map1);
	cout << "map2: "; print_map(map2);
	cout << "map3: "; print_map(map3);
	return 0;
}

增删插入

map提供了和set類似的插入與删除的方法，不同的是map的操作元素和set不同。

#include <iostream>
#include <iterator>
#include <string>
#include <map>
using namespace std;
int main() {
	map<int, string> map1 = { {1, "Hello"},{2, "World" } };
	map1.insert({ 2, "C++" });//用insert插入{ 2, "C++" }
	print_map(map1);
	map1.insert({ 3, "!" });//用insert插入{ 3, "!" }
	print_map(map1);
	map1.emplace(2, "C++");//用emplace插入{ 2, "C++" }
	print_map(map1);
	map1.emplace(3, "!");//用emplace插入{ 3, "!" }
	print_map(map1);	
	map1.erase(2);//移除{2, "World"}
	print_map(map1);
	return 0;
}

{1:Hello} {2:World}
{1:Hello} {2:World} {3:!}
{1:Hello} {2:World} {3:!}
{1:Hello} {2:World} {3:!}
{1:Hello} {3:!}

從結果可以看出，當用insert/emplace進行插入時，如果key不存在，則插入成功，否則插入失敗。是以map1中的{2:World}沒變為{2:C++}，而{3:!}則成功插入。注意map中insert()和emplace()傳入參數的方式不同。

STL提供了另一個函數來解決這個問題：insert_or_assign(）從名字可以看出它的作用是在map中要插入的key已經存在時，直接将value的值指派為要插入的值。

int main() {
	map<int,string> map1 = {{ 1,"Hello"},{ 2,"World" }};
	print_map(map1);
	map1.insert_or_assign(2, "C++");
	print_map(map1);
	return 0;
}

{1:Hello} {2:World}
{1:Hello} {2:C++}

另外，由于map中key的唯一性，是以C++提供了下标的方式來索引元素，并且這種方式可以更改value的值。示例如下：

int main() {
	map<int, string> map1 = { {1, "Hello"},{2, "World" } };
	print_map(map1);
	map1.insert({ 2, "C++" });//用insert插入{ 2, "C++" }
	print_map(map1);
	map1[2] = "C++";
	print_map(map1);
	return 0;
}

{1:Hello} {2:World}
{1:Hello} {2:World}
{1:Hello} {2:C++}

這裡利用insert插入改變不了key=2對應的value=“World”，而利用下标的方式成功改變value=“C++”。值得提及的是key的類型不是int時也可以作為下标來索引元素，讀者可以嘗試驗證。

周遊

雖然map可以用下标來索引元素，但在不知道key的取值範圍的時候是無法用下标來周遊map的，是以常用的周遊map的方式是疊代器方式和rangefor的方式。

//for (map<int, string>::const_iterator it = map1.begin(); it != map1.end(); it++)
for (auto it = map1.begin(); it != map1.end(); it++)
		cout << "{" << it->first << ":" << it->second << "}" << " ";
	cout << endl;

for(auto& it:map1)
		cout << "{" << it.first << ":"<< it.second << "}" << " " ;
	cout << endl;

相關函數

函數	作用
(c)(r)begin()	傳回指向第一個元素的（常）（反）疊代器
(c)(r)end()	傳回指向最後一個元素後面的（常）（反）疊代器
clear()	清空容器
count()	對某個元素進行計數
empty()	判斷容器是否為空
emplace()	insert的優化版本
emplace_hint()	依據提示插入（提示可以是eplace()傳回的疊代器）
try_emplace()
erase()	删除元素
equal_range()	傳回pair<lower_bound, upper_bound>
find()	查找元素傳回指向該元素的疊代器
get_allocator()	擷取配置設定器
insert()	插入元素傳回pair<set<type>::iter, bool>
inset_or_assign()	key已經存在的時候直接給value指派
key_comp()	傳回比較準則
value_comp()	傳回對value的比較準則
size()	傳回容器中元素個數
max_size()	傳回可能的最大容量
swap()	交換兩個容器
lower_bound()	傳回lower_bound
upper_bound()	傳回upper_bound
at()	下标通路，傳回value

容器擴充卡

容器擴充卡的英文全稱為container adapter，它們本身不是容器，通過改造标準的STL容器來适應特定的場合。其中stack（棧）和queue（隊列）是基于deque，而priority_queue（優先隊列）則是基于vector實作的。

stack（棧）

stack（棧）的特點是後進先出（LIFO）,是以所有的順序容器都滿足它的操作要求，而stack預設是建立在deque容器上的。

建立

stack的初始化非常的簡單。

#include <iostream>
#include <iterator>
#include <stack>
using namespace std;
int main() {
	stack<int> stack1;
	stack<int> stack2(stack1);
	stack<int> stack3 = stack1;
	return 0;
}

相關函數

stack的函數也很簡單。

函數	作用
push()	壓棧
emplace()	壓棧
pop()	彈棧
top()	傳回棧頂元素
size()	棧中元素個數
empty()	判斷棧是否為空
swap()	交換兩個棧的内容

#include <iostream>
#include <iterator>
#include <stack>
using namespace std;
int main() {
	stack<int> stack1;
	stack<int> stack2(stack1);
	stack1.push(1);
	stack1.emplace(2);
	stack1.push(3);
	stack1.emplace(4);
	while (stack1.size())//或者while(!stack1.empty())
	{
		cout << stack1.top() << " ";//通路棧頂元素
		stack1.pop();//出棧
	}
	stack1.swap(stack2);
	return 0;
}

黑人問号臉

queue（隊列）

queue（隊列）的特點是先進先出（FIFO）,需要操作首元素，順序容器中vector不能滿足它的操作要求，而queue預設是建立在deque容器上的。

建立

queue的初始化與stack類似。

#include <iostream>
#include <iterator>
#include <queue>
using namespace std;
int main() {
	queue<int> queue1;
	queue<int> queue2(queue1);
	queue<int> queue3 = queue1;
	return 0;
}

相關函數

quque的函數和stack也很類似，不過把top()換成了front()和back()。

函數	作用
push()	入隊
emplace()	入隊
pop()	出隊
front()	傳回隊首元素
back()	傳回隊尾元素
size()	隊列中元素個數
empty()	判斷隊列是否為空
swap()	交換兩個隊列的内容

#include <iostream>
#include <iterator>
#include <queue>
using namespace std;
int main() {
	queue<int> queue1;
	queue<int> queue2(queue1);
	queue1.push(1);
	queue1.emplace(2);
	queue1.push(3);
	queue1.emplace(4);
	while (queue1.size())//或者while(!stack1.empty())
	{
		cout << queue1.front() << " ";//通路隊首元素
		queue1.pop();//出隊
	}
	queue1.swap(queue2);
	return 0;
}

priority_queue（優先隊列）

priority_queue（優先隊列）中元素并不像queue那樣元素先進先出，而是具有最高優先級的元素最先出隊。其中元素的大小可按預設大小關系，也可以通過重載"<"來規定大小關系。優先隊列需要隊元素進行随機通路，是以list不能滿足要求，隻能通過vector和deque來實作，實際上優先隊列預設是靠vector來實作的。

建立

priority_queue的初始化比stack和queue要靈活一些，因為其涉及到元素的優先級，是以需要元素能夠提供優先級的概念。實際上，就是需要元素能夠進行大小比較。C++内置資料結構都有預設的大小比較方法，而自定義資料結構需要通過重載"<“來提供優先級。下面是具體的例子：

#include <iostream>
#include <iterator>
#include <queue>
using namespace std;
struct Point{
	int x, y;
	Point(int a, int b) :x(a), y(b) {};//構造函數
};
bool operator<(const Point &A,const Point &B) {//重載操作符<
	return A.x < B.x;
}
ostream& operator<<(ostream &out, const Point &A) {//重載操作符<<
	out << "(" << A.x << "," << A.y << ")" << " ";
	return out;
}
template<typename T>
void pop_queue(T &q) {//資料出隊
	while (q.size())
	{
		cout << q.top() << " ";//通路隊首元素
		q.pop();//出隊
	}
	cout << endl;
}
int main() {
	Point p1(5, 1), p2(1, 4), p3(2, 2), p4(3, 2);

	priority_queue<int, vector<int>> queue1;//使用預設優先級less<int>
	priority_queue<int, vector<int>, greater<int>> queue2;//更改優先級為greater<int>
	priority_queue<int, deque<int>> queue3;//使用deque<int>
	priority_queue<Point> queue4;//使用自定義資料結構

	//資料入隊
	queue1.push(3); queue1.push(2); queue1.push(1); queue1.push(4);
	queue2.push(3); queue2.push(2); queue2.push(1); queue2.push(4);
	queue3.push(3); queue3.push(2); queue3.push(1); queue3.push(4);
	queue4.push(p1); queue4.push(p2); queue4.push(p3); queue4.push(p4);

	//資料出隊
	cout << "pop_queue1: "; pop_queue(queue1);
	cout << "pop_queue2: "; pop_queue(queue2);
	cout << "pop_queue3: "; pop_queue(queue3);
	cout << "pop_queue4: "; pop_queue(queue4);
	
	return 0;
}

上面的例子初始化了四個不同的優先隊列：

priority_queue<int, vector<int> > queue1;//使用預設優先級less

priority_queue<int, vector<int>, greater<int> > queue2;//更改優先級為greater

priority_queue<int, deque<int> > queue3;//使用deque

priority_queue<Point> queue4;//使用自定義資料結構

其中，第一個優先隊列采用vector作為容器，優先規則為預設的less（從大到小）。第二個隊列也采用vector作為容器，但配置優先規則為greater（從小到大）。第三個隊列采用deque作為容器，優先規則采用預設的less。最後一個隊列的元素為自定義資料結構Point，采用預設優先級less，但仍需要對”<"進行操作符重載。

從程式中對"<"進行重載的函數裡面可以看到，程式采用的x的值作為優先級的判據，是以x的值越大，優先級越高。下面是運作的結果：

pop_queue1: 4 3 2 1
pop_queue2: 1 2 3 4
pop_queue3: 4 3 2 1
pop_queue4: (5,1)  (3,2)  (2,2)  (1,4)

從結果可以看到，當優先級規則為less時，元素的值越大優先級越高，是以出隊列的順序時從大到小。反之，則按從小到大的順序出隊。從queue4的出隊順序可以看出，出隊的順序是按照x值的大小進行排列的。

相關操作

priority_quque的相關函數和stack是一樣的，它不像queue那樣提供通路隊首和隊尾的方法，隻提供了top()一個方法來讀取隊首的元素。具體的函數清單如下，函數的用法也不給出執行個體了。

函數	作用
push()	入隊
emplace()	入隊
pop()	出隊
top()	傳回隊首元素
size()	隊列中元素個數
empty()	判斷隊列是否為空
swap()	交換兩個隊列的内容

總結

至此，我們一共讨論了約5種容器：vector、list、deque、set（multiset）、map（multimap）。以及3種容器擴充卡：stack、queue、priority_queue。

容器按照在記憶體中的存儲形式分為線性和非線性兩類，線性的包括：vector、list、deque;非線性的包括set（multiset）和map（multimap）。

從通路機制上來看，vector和deque支援随機通路，可通過數字下标來通路容器中的元素；map雖然不支援随機通路，卻可以通過key作為下表來通路容器中的元素；其他的，list和map不支援随機通路，是以隻能通過疊代器對容器中的元素進行通路。當然，所有的容器提供了對應的疊代器來進行元素通路。
從資料結構上來看，vector是利用線性順序表來實作的，是以在記憶體中的存儲是連續的；list是通過線性連結清單實作，在記憶體中的間斷的；而deque是介于vector和list之間，在記憶體中是多個連續的片段組成；map和set和上述三種線性結構的容器不同，它是通過紅黑樹結構來實作的，紅黑樹是一種搞笑高效的的自平衡查找二叉樹，是以在記憶體中顯然是間斷的。從這裡我們也可以看出，為什麼隻有vector和deque支援随機通路，因為它們在記憶體中的存儲形式是連續的。
從應用上來看，vector支援随機通路，但進行插入和删除的效率很低，是以多适用于隻在末尾進行添加和删除的場合。list不支援随機通路，但由于其鍊式結構在插入和删除上效率很高，是以适用于經常進行插入和删除的場合。deque既支援随機通路，也有較高的插入删除效率，是以在複雜的情況下，deque作為一種折中也是不錯的選擇，但大多數情況下，為了追求極緻的性能，我們會選擇vector或list兩種極端的資料結構。而set和map是兩個有着特殊功能的關聯容器，set是有序集合，其中的元素唯一且有序排列；map是有序映射，它的key/value特性使得我們可以通過鍵（key）來擷取對應的值（value）。

容器擴充卡實質上就是容器的一種接口轉換器，它通過一定的轉換機理，将STL中的上述5類容易轉換為有特定用途的資料結構提供給開發者更友善的使用。換句話說，容器擴充卡本身不是容器，它是對容器的一種改造，使之滿足我們的特殊要求。

容器擴充卡為我們提供了三種非常重要的資料結構：stack（棧）、quque（隊列）、優先隊列（priority_queue），它們都是以依托于現成的容器來實作。

棧是一種先進後出的資料結構，是以隻需要在容器的一端進行增加和删除，由上面的分析可知，vector、deque、list三種線性容器都能滿足這個要求。由于vector在記憶體中線性存儲，相對于dque和list更加節省空間，是以大多數情況下将vector作為是實作棧的基本容器。
隊列是一種先進先出的資料結構，需要在容器的兩端進行增加和删除，隻有list和deque滿足這個要求，但由于不需要在容器中間進行插入和删除，是以選擇deque在空間的利用上更加合理，是以隊列經常選擇deque來實作。
優先隊列中元素出隊的順序是依據優先級來定的，是以需要一種排序算法來計算出各個元素的優先級。在C++中利用堆排序來對優先隊列中的元素進行排序。堆排序在這裡不展開闡述，但堆排序的實作的依據線性順序序列，許多基本容器能夠提供随機通路的功能，是以使用vector來實作是最好的。當然，也可以利用deque來實作優先隊列，但效率上肯定不如vector實作的優先隊列好。

綜上，我們預設情況下，利用vector來實作stack和priority_quque，而利用deque來實作queue。

STL之容器STL容器順序容器關聯容器容器擴充卡總結

STL容器

STL容器

順序容器

vector（向量）

list（清單）

deque（雙端隊列）

關聯容器

set（集合）

map（映射）

容器擴充卡

stack（棧）

queue（隊列）

priority_queue（優先隊列）

總結

繼續閱讀

C語言第四章自述2第四章選擇結構程式設計

面試題:vector和map的差別，異同。空間分布，100萬資料存哪個比較合适。一、疊代器差別二、vector三、Map、Set四、vector_map 為什麼比map效率高五、如何選擇六、容器選擇原則七、效率對比

C++ 多線程用條件變量确定線程的執行順序而不是使用 sleep(1)

POJ 1284 Primitive Roots (歐拉函數&原根定理)

CQ V1.0分詞bates(基于雙數組tire樹)—應該是目前最快的中文分詞算法

成員函數初始化清單

2021-08-13c++——類之操作符重載

swmm與lisflood-fp源碼如何一起編譯 CMake指令

Windows下VS開發環境環境安裝工程項目設定關于Debug和Release的提示

一文看懂字元串的加減乘除

C++ 第十五周報告1--《冒泡法排序》

C++實作簡單順序表

C經典書籍筆記——C陷阱與缺陷②(文法陷阱之優先級)一、錯誤案列二、優先級規律

線性表之順序表的實作

C++判斷素數、求最大公約數代碼判斷一個數是否為素數求兩個數的最大公約數

SequoiaDB巨杉資料庫C++驅動概述