deque 雙端數組，可以對頭端進行插入删除操作 deque 與 vector 差別：

vector 對于頭部的插入删除效率低，資料量越大，效率越低

deque 相對而言，對頭部的插入删除速度回比vector快

vector 通路元素時的速度會比deque快,這和兩者内部實作有關

deque 容器的疊代器也是支援随機通路的

deque 内部工作原理：

deque 内部有個中控器，維護每段緩沖區中的内容，緩沖區中存放真實資料

中控器維護的是每個緩沖區的位址，使得使用deque時像一片連續的記憶體空間

構造函數

功能描述：

deque容器構造（用法與 vector 基本一緻）

函數原型：

deque<T> deqT; //預設構造形式
deque(beg, end); //構造函數将[beg, end)區間中的元素拷貝給本身。
deque(n, elem); //構造函數将n個elem拷貝給本身。
deque(const deque &deq); //拷貝構造函數

#include<iostream>
#include<string>
#include<deque>

using namespace std;

// 列印 deque
template<class T>
void print_deque(const deque<T>& d) {
	for (size_t i = 0; i < d.size(); i++) {
		cout << d[i] << " ";
	}
	cout << endl;
}

int main() {
	// 無參構造函數
	deque<int> d;
	// 向容器尾部添加元素
	for (int i = 0; i < 10; i++){
		d.push_back(i);
	}
	print_deque(d); // 0 1 2 3 4 5 6 7 8 9

	// 拷貝 d 容器中的元素進行構造容器
	deque<int> d2(d.begin(), d.end());
	print_deque(d2); // 0 1 2 3 4 5 6 7 8 9

	// 以 5 個 9 作為容器中的資料元素，進行構造容器
	deque<int> d3(5, 9);
	print_deque(d3); // 9 9 9 9 9

	// 拷貝構造函數
	deque<int> d4(d3);
	print_deque(d3); // 9 9 9 9 9

	return 0;
}

指派操作

功能描述：

給deque容器進行指派（用法與 vector 基本一緻）

函數原型：

deque& operator=(const deque &deq); //重載等号操作符
assign(beg, end); //将[beg, end)區間中的資料拷貝指派給本身。
assign(n, elem); //将n個elem拷貝指派給本身。

#include<iostream>
#include<string>
#include<deque>

using namespace std;

// 列印 deque
template<class T>
void print_deque(const deque<T>& d) {
	for (size_t i = 0; i < d.size(); i++) {
		cout << d[i] << " ";
	}
	cout << endl;
}

int main() {

	// 無參構造函數
	deque<int> d;
	// 向容器尾部添加元素
	for (int i = 0; i < 10; i++) {
		d.push_back(i);
	}
	print_deque(d); // 0 1 2 3 4 5 6 7 8 9

	// 直接等号指派
	deque<int> d2;
	d2 = d;
	print_deque(d2); // 0 1 2 3 4 5 6 7 8 9

	// 将 d 容器的 [begin(),end()) 區間内的資料元素指派給 d3 容器
	deque<int> d3;
	d3.assign(d.begin(),d.end());
	print_deque(d3); // 0 1 2 3 4 5 6 7 8 9


	// 将 5 個 9 指派給容器元素
	deque<int> d4;
	d4.assign(5, 9);
	print_deque(d4); // 9 9 9 9 9

	return 0;
}

容量大小

功能描述：

對deque容器的大小進行操作（用法與 vector 基本一緻）
由于内部實作不同，deque 沒有容量概念

函數原型：

deque.empty(); //判斷容器是否為空
deque.size(); //傳回容器中元素的個數
deque.resize(num);
//重新指定容器的長度為num,若容器變長，則以預設值填充新位置。

//如果容器變短，則末尾超出容器長度的元素被删除。
deque.resize(num, elem);
//重新指定容器的長度為num,若容器變長，則以elem值填充新位置。

//如果容器變短，則末尾超出容器長度的元素被删除。

#include<iostream>
#include<string>
#include<deque>

using namespace std;

// 列印 deque
template<class T>
void print_deque(const deque<T>& d) {
   for (size_t i = 0; i < d.size(); i++) {
   	cout << d[i] << " ";
   }
   cout << endl;
}

int main() {

   // 無參構造函數
   deque<int> d;
   // 判斷容器是否為空
   cout << (d.empty() ? "容器為空" : "容器不為空") << endl; // 容器為空
   // 擷取容器大小
   cout << "容器的大小為：" << d.size() << endl; // 容器的大小為：0

   // 向容器尾部添加元素
   for (int i = 0; i < 10; i++) {
   	d.push_back(i);
   }
   print_deque(d); // 0 1 2 3 4 5 6 7 8 9

   // 重新指定大小，剩餘部分預設以0填充
   d.resize(15);
   print_deque(d); // 0 1 2 3 4 5 6 7 8 9 0 0 0 0 0

   // 重新指定大小，剩餘部分預設以1填充
   d.resize(20,1);
   print_deque(d); // 0 1 2 3 4 5 6 7 8 9 0 0 0 0 0 1 1 1 1 1

   // 重新指定大小，若長度變短，超出的元素直接舍棄
   d.resize(5);
   print_deque(d); // 0 1 2 3 4



   return 0;
}

插入删除

功能描述：

向deque容器中插入和删除資料

函數原型：

兩端插入操作：

push_back(elem); //在容器尾部添加一個資料
push_front(elem); //在容器頭部插入一個資料
pop_back(); //删除容器最後一個資料
pop_front(); //删除容器第一個資料

指定位置操作：

insert(pos,elem); //在pos位置插入一個elem元素的拷貝，傳回新資料的位置。
insert(pos,n,elem); //在pos位置插入n個elem資料，無傳回值。
insert(pos,beg,end); //在pos位置插入[beg,end)區間的資料，無傳回值。
clear(); //清空容器的所有資料
erase(beg,end); //删除[beg,end)區間的資料，傳回下一個資料的位置。
erase(pos); //删除pos位置的資料，傳回下一個資料的位置。

#include<iostream>
#include<string>
#include<deque>

using namespace std;

// 列印 deque
template<class T>
void print_deque(const deque<T>& d) {
	for (size_t i = 0; i < d.size(); i++) {
		cout << d[i] << " ";
	}
	cout << endl;
}

int main() {
	deque<int> d;
	deque<int> d1;
	/*從容器兩端插入元素*/
	d.push_back(1); // 從尾部插入一個元素
	d.push_back(2);// 從尾部插入一個元素
	d.push_front(3); // 從頭部插入一個元素
	d.push_front(4); // 從頭部插入一個元素
	d.push_front(5); // 從頭部插入一個元素
	print_deque(d); // 5 4 3 1 2

	d1.push_back(111);
	d1.push_back(222);
	d1.push_back(333);

	/*從容器兩端删除元素*/
	d.pop_back(); // 從容器尾部删除一個元素
	d.pop_back(); // 從容器尾部删除一個元素
	d.pop_front(); // 從容器頭部删除一個元素
	print_deque(d); // 4 3

	/*在疊代器所指位置插入元素*/
	d.insert(d.begin(), 999); // 在第一個元素位置處插入 999
	print_deque(d); // 999 4 3
	d.insert(d.end(), 3, 888); // 在最後一個元素的下一個位置插入3個888
	print_deque(d); // 999 4 3 888 888 888

	// 擷取疊代器
	deque<int>::iterator ite = d.begin(); // 疊代器執向第一個位置
	ite++; // 疊代器往後移動一個位置
	d.insert(ite, 555); // 在目前執向位置插入一個 555
	print_deque(d); // 999 555 4 3 888 888 888
	
	d.insert(d.begin(),d1.begin(), d1.end()); // 在d的第一個位置處插入 d1 的[egin(),end()) 區間元素
	print_deque(d); // 111 222 333 999 555 4 3 888 888 888

	/* 删除疊代器指向區間内的元素 */
	deque<int>::iterator ite_1 = d.begin(); // 指向第一個元素位置的疊代器
	deque<int>::iterator ite_2 = d.end(); // 指向最後一個元素的下一個位置的疊代器
	ite_2-=3; // 疊代器指向 前移3個位置
	d.erase(ite_1, ite_2); // 删除指定區間内的元素
	print_deque(d); // 888 888 888

	/* 清空整個容器 */
	d.clear();
	d1.clear();
	cout << d.size() << endl; // 0
	cout << d1.size() << endl; // 0

	return 0;
}

資料存取

功能描述：

對deque 中的資料的存取操作

函數原型：

at(int idx); //傳回索引idx所指的資料
operator[]; //傳回索引idx所指的資料
front(); //傳回容器中第一個資料元素
back(); //傳回容器中最後一個資料元素

#include<iostream>
#include<string>
#include<deque>

using namespace std;

int main() {

	deque<int> d;
	d.push_back(1);
	d.push_back(2);
	d.push_back(3);

	// 擷取第一個位置的元素
	int e1 = d[0];
	cout << e1 << endl; // 1
	// 擷取第一個位置的元素
	int e2 = d.at(1); // 2
	cout << e2 << endl;

	// 設定第三個位置的元素
	d[2] = 888;
	d.at(1) = 999;

	// 周遊容器
	for (int i = 0; i < d.size(); i++){
		cout << d[i] << " ";
	}
	cout << endl;

	return 0;
}

排序

功能描述：

利用算法實作對deque容器進行排序

算法：

sort(iterator beg, iterator end) //對beg和end區間内元素進行排序
sort 排序算法使用需要導入一頭檔案 algorithm

#include<iostream>
#include<string>
#include<deque>
#include<algorithm>

using namespace std;

// 列印 deque
template<class T>
void print_deque(const deque<T>& d) {
	for (size_t i = 0; i < d.size(); i++) {
		cout << d[i] << " ";
	}
	cout << endl;
}

int main() {

	deque<int> d;
	d.push_back(2);
	d.push_back(4);
	d.push_back(1);
	d.push_front(3);
	d.push_front(7);
	d.push_front(5);
	d.push_front(6);
	print_deque(d); // 6 5 7 3 2 4 1
	
	// 擷取疊代器
	deque<int>::iterator begin = d.begin(); // 指向第一個元素位置
	deque<int>::iterator end = d.end(); // 指向最後一個元素的下一個位置
	
	// 對指定區間内的元素進行排序
	sort(begin, end);
	print_deque(d); // 1 2 3 4 5 6 7


	return 0;
}

案例：給選手評分

需求：有5名選手：選手ABCDE，10個評委分别對每一名選手打分，去除最高分，去除評委中最低分，取平均分。

建立五名選手，放到vector中
周遊vector容器，取出來每一個選手，執行for循環，可以把10個評分打分存到deque容器中
sort算法對deque容器中分數排序（升序），去除最高（從尾部删除）和去除最低（從頭部删除）分
deque容器周遊一遍，累加總分
計算平均分

#include<iostream>
#include<string>
#include<deque>
#include<vector>
#include<algorithm>

using namespace std;

const string NAME_PREFIX = "選手";
const string NAME_SUFFIX = "ABCDE";

// 周遊輸出容器
template<class T>
void print_container(const T& container) {
	for (int i = 0; i < container.size(); i++){
		cout << container[i] << endl;;
	}
}
class Player {
	friend ostream& operator<<(ostream& out,const Player& p);
private:
	string name; // 姓名
	int score_avg; // 平均分
public:
	Player(string name,int score_avg) {
		this->name = name;
		this->score_avg = score_avg;
	}
	void set_score_avg(int score) {
		this->score_avg = score;
	}
	
};
ostream& operator<<(ostream& out, const Player& p) {
	out << "姓名:"  << p.name << ",平均分:"  << p.score_avg;
	return out;
}

// 把選手裝入vector容器
void set_player(vector<Player>& players) {
	for (int i = 0; i < 5; i++) {
		Player p(NAME_PREFIX + NAME_SUFFIX[i], 0);
		players.push_back(p);
	}
}
// 循環10次給選手打分，計算出平均分
void set_score(vector<Player>& players) {
	deque<int> scores; // 存儲分數的容器
	int sum_score = 0; // 總分
	int avg_score = 0; // 平均分
	// 循環給每個選手打分
	for (int i = 0; i < players.size(); i++) {
		int score = 0; // 分數
		// 每個選手有十個得分
		for (int j = 0; j < 10; j++) {
			// 擷取到 [60,100]内的一個随機整數作為評分
			score = rand() % (100 - 60 + 1) + 60;
			// 将分數放入deque容器
			scores.push_back(score);
		}
		// 分數從小到大排序
		sort(scores.begin(), scores.end());
		// print_container(scores);
		// 去掉最高分
		scores.pop_back();
		// 去掉最低分
		scores.pop_front();
		// 計算總分
		for (int k = 0; k < scores.size(); k++) {
			sum_score += scores[k];
		}
		// 計算平均分
		avg_score = sum_score / scores.size();
		players.at(i).set_score_avg(avg_score);
		// 清空存儲分數的容器
		scores.clear();
		sum_score = 0;
	}
}

void test_rand() {

	/*
	通過rand() % n的方式，擷取到[0, n)的随機數,因為任何一個數除以n得到的餘數0到n-1。
	那麼我們就可以通過改變n的值就可以去指定截止數，再将取到的範圍加上一個值就可以改變起始數：
		要取得 [a,b) 的随機整數，使用 (rand () % (b-a))+ a;
		要取得 [a,b] 的随機整數，使用 (rand () % (b-a+1))+ a;
		要取得 (a,b] 的随機整數，使用 (rand () % (b-a))+ a + 1;
	*/
	// 取得[60-100]直接的随機數
	cout << rand() % (100 - 60 + 1) + 60 << endl;
}

int main() {
	/*
	void srand(unsigned int seed)初始化随機數發生器:随機數種子

	unsigned：無符号
	表示抛棄資料類型的負數部分，将更多的存儲空間用來存放非負數
	例如：int類型原本占用4位元組空間，即隻能存儲[-2^16,2^16 - 1]範圍内的資料
	加unsigned後存儲資料的範圍就是[0,2^32 - 1]

	unsigned int表示[0,2^32 - 1]範圍内的整型

	使用time()作為随機數種子.時間戳，傳回從1970年1月1月零點零分零秒到目前時間的秒數
	可以将time傳回的時間作為參數傳遞給srand()，因為程式每一次運作時，我們的時間都是不一樣的，即每次運作時的随機數種子都不一樣。
	*/
	srand((unsigned int)time(NULL));


	// 存儲選手的vector容器
	vector<Player> players;

	// 選手裝進容器
	set_player(players);

	print_container(players);

	// 打分
	set_score(players);

	print_container(players);

	return 0;
}

C++學習筆記——STL【容器：deque】構造函數指派操作容量大小插入删除資料存取排序案例：給選手評分

構造函數

指派操作

容量大小

插入删除

資料存取

排序

案例：給選手評分

繼續閱讀

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++驅動概述