配套視頻：https://www.bilibili.com/video/BV1et411b73Z

文章目錄：

一、C++核心編程
二、C++提高編程

1 模板

• 本階段主要針對C++泛型編程和STL技術做詳細講解，探討C++更深層的使用

1.1 模板的概念

模板就是建立通用的模具，大大提高復用性

模板的特點：

• 模板不可以直接使用，它只是一個框架
• 模板的通用并不是萬能的

1.2 函式模板

• C++另一種編程思想稱為泛型編程 ，主要利用的技術就是模板
• C++提供兩種模板機制:函式模板和類模板

1.2.1 函式模板語法

函式模板作用：建立一個通用函式，其函式回傳值型別和形參型別可以不具體指定，用一個虛擬的型別來代表，

語法：

template<typename T>
函式宣告或定義

解釋：
template — 宣告創建模板
typename — 表面其后面的符號是一種資料型別，可以用class代替
T — 通用的資料型別，名稱可以替換，通常為大寫字母

示例：

#include<iostream>
using namespace std;
//函式模板
//兩個整型交換函式
void swapInt(int& a, int& b) {
	int temp = a;
	a = b;
	b = temp;
}
//兩個浮點型交換函式
void swapDouble(double& a, double& b) {
	double temp = a;
	a = b;
	b = temp;
}
//函式模板
template<typename T>//宣告一個模板，告訴編譯器后面代碼中緊跟著的T不要報錯，T是一個通用資料型別
void mySwap(T& a, T& b) {
	T temp = a;
	a = b;
	b = temp;
}


void test() {
	int a = 1;
	int b = 2;
	//兩種方式使用模板函式
	//1.自動型別推導
	mySwap(a, b);
	cout << "a=" << a << ",b=" << b << endl;
	//2.顯示指定型別
	mySwap<int>(a, b);//告訴編譯器，T是int型別
}

int main() {
	test();
	return 0;
}

1.2.2 函式模板注意事項

注意事項：

• 自動型別推導，必須推匯出一致的資料型別T,才可以使用
• 模板必須要確定出T的資料型別，才可以使用

示例

//利用模板提供通用的交換函式
template<class T>
void mySwap(T& a, T& b)
{
	T temp = a;
	a = b;
	b = temp;
}


// 1、自動型別推導，必須推匯出一致的資料型別T,才可以使用
void test01()
{
	int a = 10;
	int b = 20;
	char c = 'c';

	mySwap(a, b); // 正確，可以推匯出一致的T
	//mySwap(a, c); // 錯誤，推導不出一致的T型別
}


// 2、模板必須要確定出T的資料型別，才可以使用
template<class T>
void func()
{
	cout << "func 呼叫" << endl;
}

void test02()
{
	//func(); //錯誤，模板不能獨立使用，必須確定出T的型別
	func<int>(); //利用顯示指定型別的方式，給T一個型別，才可以使用該模板
}

int main() {

	test01();
	test02();

	system("pause");

	return 0;
}

1.2.3 函式模板案例

案例描述：
利用函式模板封裝一個排序的函式，可以對不同資料型別陣列進行排序
排序規則從大到小，排序演算法為選擇排序
分別利用char陣列和int陣列進行測驗
示例：

//交換的函式模板
template<typename T>
void mySwap(T &a, T&b)
{
	T temp = a;
	a = b;
	b = temp;
}


template<class T> // 也可以替換成typename
//利用選擇排序，進行對陣列從大到小的排序
void mySort(T arr[], int len)
{
	for (int i = 0; i < len; i++)
	{
		int max = i; //最大數的下標
		for (int j = i + 1; j < len; j++)
		{
			if (arr[max] < arr[j])
			{
				max = j;
			}
		}
		if (max != i) //如果最大數的下標不是i，交換兩者
		{
			mySwap(arr[max], arr[i]);
		}
	}
}
template<typename T>
void printArray(T arr[], int len) {

	for (int i = 0; i < len; i++) {
		cout << arr[i] << " ";
	}
	cout << endl;
}
void test01()
{
	//測驗char陣列
	char charArr[] = "bdcfeagh";
	int num = sizeof(charArr) / sizeof(char);
	mySort(charArr, num);
	printArray(charArr, num);
}

void test02()
{
	//測驗int陣列
	int intArr[] = { 7, 5, 8, 1, 3, 9, 2, 4, 6 };
	int num = sizeof(intArr) / sizeof(int);
	mySort(intArr, num);
	printArray(intArr, num);
}

int main() {

	test01();
	test02();

	system("pause");

	return 0;
}

總結：模板可以提高代碼復用，需要熟練掌握

1.2.4 普通函式與函式模板的區別

普通函式與函式模板區別：

• 普通函式呼叫時可以發生自動型別轉換（隱式型別轉換）
• 函式模板呼叫時，如果利用自動型別推導，不會發生隱式型別轉換
• 如果利用顯示指定型別的方式，可以發生隱式型別轉換
  示例：

//普通函式
int myAdd01(int a, int b)
{
	return a + b;
}

//函式模板
template<class T>
T myAdd02(T a, T b)  
{
	return a + b;
}

//使用函式模板時，如果用自動型別推導，不會發生自動型別轉換,即隱式型別轉換
void test01()
{
	int a = 10;
	int b = 20;
	char c = 'c';
	
	cout << myAdd01(a, c) << endl; //正確，將char型別的'c'隱式轉換為int型別  'c' 對應 ASCII碼 99

	//myAdd02(a, c); // 報錯，使用自動型別推導時，不會發生隱式型別轉換

	myAdd02<int>(a, c); //正確，如果用顯示指定型別，可以發生隱式型別轉換
}

int main() {

	test01();

	system("pause");

	return 0;
}

總結：建議使用顯示指定型別的方式，呼叫函式模板，因為可以自己確定通用型別T

1.2.5 普通函式與函式模板的呼叫規則

呼叫規則如下：

1. 如果函式模板和普通函式都可以實作，優先呼叫普通函式
2. 可以通過空模板引數串列來強制呼叫函式模板
3. 函式模板也可以發生多載
4. 如果函式模板可以產生更好的匹配,優先呼叫函式模板

示例：

//普通函式與函式模板呼叫規則
void myPrint(int a, int b)
{
	cout << "呼叫的普通函式" << endl;
}

template<typename T>
void myPrint(T a, T b) 
{ 
	cout << "呼叫的模板" << endl;
}

template<typename T>
void myPrint(T a, T b, T c) 
{ 
	cout << "呼叫多載的模板" << endl; 
}

void test01()
{
	//1、如果函式模板和普通函式都可以實作，優先呼叫普通函式
	// 注意 如果告訴編譯器  普通函式是有的，但只是宣告沒有實作，或者不在當前檔案內實作，就會報錯找不到
	int a = 10;
	int b = 20;
	myPrint(a, b); //呼叫普通函式

	//2、可以通過空模板引數串列來強制呼叫函式模板
	myPrint<>(a, b); //呼叫函式模板

	//3、函式模板也可以發生多載
	int c = 30;
	myPrint(a, b, c); //呼叫多載的函式模板

	//4、 如果函式模板可以產生更好的匹配,優先呼叫函式模板
	char c1 = 'a';
	char c2 = 'b';
	myPrint(c1, c2); //呼叫函式模板
}

int main() {

	test01();

	system("pause");

	return 0;
}

總結：既然提供了函式模板，最好就不要提供普通函式，否則容易出現二義性

1.2.6 模板的局限性

局限性：模板的通用性并不是萬能的
例如：

	template<class T>
	void f(T a, T b)
	{ 
    	a = b;
    }

在上述代碼中提供的賦值操作，如果傳入的a和b是一個陣列，就無法實作了

再例如：

	template<class T>
	void f(T a, T b)
	{ 
    	if(a > b) { ... }
    }

在上述代碼中，如果T的資料型別傳入的是像Person這樣的自定義資料型別，也無法正常運行

因此C++為了解決這種問題，提供模板的多載，可以為這些特定的型別提供具體化的模板

示例：

#include<iostream>
using namespace std;

#include <string>

class Person
{
public:
	Person(string name, int age)
	{
		this->m_Name = name;
		this->m_Age = age;
	}
	string m_Name;
	int m_Age;
};

//普通函式模板
template<class T>
bool myCompare(T& a, T& b)
{
	if (a == b)
	{
		return true;
	}
	else
	{
		return false;
	}
}


//具體化，顯示具體化的原型和定意思以template<>開頭，并通過名稱來指出型別
//具體化優先于常規模板
template<> bool myCompare(Person &p1, Person &p2)
{
	if ( p1.m_Name  == p2.m_Name && p1.m_Age == p2.m_Age)
	{
		return true;
	}
	else
	{
		return false;
	}
}

void test01()
{
	int a = 10;
	int b = 20;
	//內置資料型別可以直接使用通用的函式模板
	bool ret = myCompare(a, b);
	if (ret)
	{
		cout << "a == b " << endl;
	}
	else
	{
		cout << "a != b " << endl;
	}
}

void test02()
{
	Person p1("Tom", 10);
	Person p2("Tom", 10);
	//自定義資料型別，不會呼叫普通的函式模板
	//可以創建具體化的Person資料型別的模板，用于特殊處理這個型別
	bool ret = myCompare(p1, p2);
	if (ret)
	{
		cout << "p1 == p2 " << endl;
	}
	else
	{
		cout << "p1 != p2 " << endl;
	}
}

int main() {

	test01();

	test02();

	system("pause");

	return 0;
}

總結：

• 利用具體化的模板，可以解決自定義型別的通用化
• 學習模板并不是為了寫模板，而是在STL能夠運用系統提供的模板

1.3 類模板

1.3.1 類模板語法

類模板作用：建立一個通用類，類中的成員的資料型別可以不具體制定，用一個虛擬的型別來代表，
語法：

template<typename T>
類

解釋：
template — 宣告創建模板
typename — 表面其后面的符號是一種資料型別，可以用class代替
T — 通用的資料型別，名稱可以替換，通常為大寫字母

示例：

#include <string>
//類模板
template<class NameType, class AgeType> 
class Person
{
public:
	Person(NameType name, AgeType age)
	{
		this->mName = name;
		this->mAge = age;
	}
	void showPerson()
	{
		cout << "name: " << this->mName << " age: " << this->mAge << endl;
	}
public:
	NameType mName;
	AgeType mAge;
};

void test01()
{
	// 指定NameType 為string型別，AgeType 為 int型別
	Person<string, int>P1("孫悟空", 999);
	P1.showPerson();
}

int main() {

	test01();

	system("pause");

	return 0;
}

總結：類模板和函式模板語法相似，在宣告模板template后面加類，此類稱為類模板

1.3.2 類模板與函式模板區別

類模板與函式模板區別主要有兩點：

• 類模板沒有自動型別推導的使用方式
• 類模板在模板引數串列中可以有默認引數
  示例：

#include <string>
//類模板
template<class NameType, class AgeType = int> 
class Person
{
public:
	Person(NameType name, AgeType age)
	{
		this->mName = name;
		this->mAge = age;
	}
	void showPerson()
	{
		cout << "name: " << this->mName << " age: " << this->mAge << endl;
	}
public:
	NameType mName;
	AgeType mAge;
};

//1、類模板沒有自動型別推導的使用方式
void test01()
{
	// Person p("孫悟空", 1000); // 錯誤 類模板使用時候，不可以用自動型別推導
	Person <string ,int>p("孫悟空", 1000); //必須使用顯示指定型別的方式，使用類模板
	p.showPerson();
}

//2、類模板在模板引數串列中可以有默認引數
void test02()
{
	Person <string> p("豬八戒", 999); //類模板中的模板引數串列 可以指定默認引數
	p.showPerson();
}

int main() {

	test01();

	test02();

	system("pause");

	return 0;
}

總結：

• 類模板使用只能用顯示指定型別方式
• 類模板中的模板引數串列可以有默認引數

1.3.3 類模板中成員函式創建時機

類模板中成員函式和普通類中成員函式創建時機是有區別的：

• 普通類中的成員函式一開始就可以創建
• 類模板中的成員函式在呼叫時才創建

示例：

class Person1
{
public:
	void showPerson1()
	{
		cout << "Person1 show" << endl;
	}
};

class Person2
{
public:
	void showPerson2()
	{
		cout << "Person2 show" << endl;
	}
};

template<class T>
class MyClass
{
public:
	T obj;

	//類模板中的成員函式，并不是一開始就創建的，而是在模板呼叫時再生成

	void fun1() { obj.showPerson1(); }
	void fun2() { obj.showPerson2(); }

};

void test01()
{
	MyClass<Person1> m;
	
	m.fun1();

	//m.fun2();//編譯會出錯，說明函式呼叫才會去創建成員函式
}

int main() {

	test01();

	system("pause");

	return 0;
}

總結：類中的模板函式一開始創建不出來是因為無法確定模板的資料型別，直到呼叫的時候才能確定模板的資料型別，才能呼叫模板函式

1.3.4 類模板物件做函式引數

學習目標：

• 類模板實體化出的物件，向函式傳參的方式

一共有三種傳入方式：

1. 指定傳入的型別 — 直接顯示物件的資料型別
2. 引數模板化 — 將物件中的引數變為模板進行傳遞
3. 整個類模板化 — 將這個物件型別 模板化進行傳遞

示例：

#include <string>
//類模板
template<class NameType, class AgeType = int> 
class Person
{
public:
	Person(NameType name, AgeType age)
	{
		this->mName = name;
		this->mAge = age;
	}
	void showPerson()
	{
		cout << "name: " << this->mName << " age: " << this->mAge << endl;
	}
public:
	NameType mName;
	AgeType mAge;
};

//1、指定傳入的型別 - 用得比較廣泛
void printPerson1(Person<string, int> &p) 
{
	p.showPerson();
}
void test01()
{
	Person <string, int >p("孫悟空", 100);
	printPerson1(p);
}

//2、引數模板化
template <class T1, class T2>
void printPerson2(Person<T1, T2>&p)//將法一中的指定傳入型別改為T1，T2
{
	p.showPerson();
	//如果想看模板中到底推匯出的是什么樣的資料型別
	cout << "T1的型別為： " << typeid(T1).name() << endl;
	cout << "T2的型別為： " << typeid(T2).name() << endl;
}
void test02()
{
	Person <string, int >p("豬八戒", 90);
	printPerson2(p);
}

//3、整個類模板化 - 和法二類似，模板化的范圍擴大到整個類
template<class T>
void printPerson3(T & p)
{
	cout << "T的型別為： " << typeid(T).name() << endl;
	p.showPerson();

}
void test03()
{
	Person <string, int >p("唐僧", 30);
	printPerson3(p);
}

int main() {

	test01();
	test02();
	test03();

	system("pause");

	return 0;
}

總結：如果想看模板中到底推匯出的是什么樣的資料型別：typeid(T1).name()

1.3.5 類模板與繼承

當類模板碰到繼承時，需要注意一下幾點：

• 當子類繼承的父類是一個類模板時，子類在宣告的時候，要指定出父類中T的型別
• 如果不指定，編譯器無法給子類分配記憶體
• 如果想靈活指定出父類中T的型別，子類也需變為類模板

示例：（太抽象了，，）

template<class T>
class Base
{
	T m;
};

//class Son:public Base  //錯誤，c++編譯需要給子類分配記憶體，必須知道父類中T的型別才可以向下繼承
class Son :public Base<int> //必須指定一個型別
{
};
void test01()
{
	Son c;
}

//類模板繼承類模板 ,可以用T2指定父類中的T型別
template<class T1, class T2>
class Son2 :public Base<T2>
{
public:
	Son2()
	{
		cout << typeid(T1).name() << endl;
		cout << typeid(T2).name() << endl;
	}
};

void test02()
{
	Son2<int, char> child1;
}


int main() {

	test01();

	test02();

	system("pause");

	return 0;
}

1.3.6 類模板成員函式類外實作

學習目標：能夠掌握類模板中的成員函式類外實作

示例：

#include <string>

//類模板中成員函式類外實作
template<class T1, class T2>
class Person {
public:
	//成員函式類內宣告
	Person(T1 name, T2 age);
	void showPerson();

public:
	T1 m_Name;
	T2 m_Age;
};

//建構式 類外實作：1.添加作用域2.在前面添加模板宣告3.作用域后面加上T，表明是個類模板的類外實作
template<class T1, class T2>
Person<T1, T2>::Person(T1 name, T2 age) {
	this->m_Name = name;
	this->m_Age = age;
}

//成員函式 類外實作
template<class T1, class T2>
void Person<T1, T2>::showPerson() {
	cout << "姓名: " << this->m_Name << " 年齡:" << this->m_Age << endl;
}

void test01()
{
	Person<string, int> p("Tom", 20);
	p.showPerson();
}

int main() {

	test01();

	system("pause");

	return 0;
}

總結：類外實作：1.添加作用域2.在前面添加模板宣告3.作用域后面加上T，表明是個類模板的類外實作

1.3.7 類模板分檔案撰寫

學習目標：掌握類模板成員函式分檔案撰寫產生的問題以及解決方式
問題：類模板中成員函式創建時機是在呼叫階段，導致分檔案撰寫時鏈接不到
解決：

• 解決方式1：直接包含.cpp源檔案
• 解決方式2：將宣告和實作寫到同一個檔案中，并更改后綴名為.hpp，hpp是約定的名稱，并不是強制 - 主流解決方式

示例：

person.hpp中代碼：

#pragma once
#include <iostream>
using namespace std;
#include <string>

template<class T1, class T2>
class Person {
public:
	Person(T1 name, T2 age);
	void showPerson();
public:
	T1 m_Name;
	T2 m_Age;
};

//建構式 類外實作
template<class T1, class T2>
Person<T1, T2>::Person(T1 name, T2 age) {
	this->m_Name = name;
	this->m_Age = age;
}

//成員函式 類外實作
template<class T1, class T2>
void Person<T1, T2>::showPerson() {
	cout << "姓名: " << this->m_Name << " 年齡:" << this->m_Age << endl;
}

類模板分檔案撰寫.cpp中代碼

#include<iostream>
using namespace std;

//#include "person.h"
#include "person.cpp" //解決方式1，包含cpp源檔案

//解決方式2，將宣告和實作寫到一起，檔案后綴名改為.hpp
#include "person.hpp"
void test01()
{
	Person<string, int> p("Tom", 10);
	p.showPerson();
}

int main() {

	test01();

	system("pause");

	return 0;
}

1.3.8 類模板與友元

學習目標：掌握類模板配合友元函式的類內和類外實作
全域函式類內實作 - 直接在類內宣告友元即可
全域函式類外實作 - 需要提前讓編譯器知道全域函式的存在

示例：

#include <string>

//2、全域函式配合友元  類外實作 - 先做函式模板宣告，下方在做函式模板定義，在做友元
template<class T1, class T2> class Person;

//如果宣告了函式模板，可以將實作寫到后面，否則需要將實作體寫到類的前面讓編譯器提前看到
//template<class T1, class T2> void printPerson2(Person<T1, T2> & p); 

template<class T1, class T2>
void printPerson2(Person<T1, T2> & p)
{
	cout << "類外實作 ---- 姓名： " << p.m_Name << " 年齡：" << p.m_Age << endl;
}

template<class T1, class T2>
class Person
{
	//1、全域函式配合友元   類內實作	（此處：如果不加friend，就是類內函式（默認為private），如果加了friend，就是全域友元函式的類內實作）
	friend void printPerson(Person<T1, T2> & p)
	{
		cout << "姓名： " << p.m_Name << " 年齡：" << p.m_Age << endl;
	}


	//全域函式配合友元  類外實作
	//1.要加空模板的引數串列<>
	//2.如果全域函式是類外實作，需要讓編譯器提前知道這個函式的存在
	friend void printPerson2<>(Person<T1, T2> & p);

public:

	Person(T1 name, T2 age)
	{
		this->m_Name = name;
		this->m_Age = age;
	}


private:
	T1 m_Name;
	T2 m_Age;

};

//1、全域函式在類內實作
void test01()
{
	Person <string, int >p("Tom", 20);
	printPerson(p);
}


//2、全域函式在類外實作
void test02()
{
	Person <string, int >p("Jerry", 30);
	printPerson2(p);
}

int main() {

	//test01();

	test02();

	system("pause");

	return 0;
}

總結：類外實作太麻煩，建議全域函式做類內實作，用法簡單，而且編譯器可以直接識別

1.3.9 類模板案例

案例描述: 實作一個通用的陣列類，要求如下：

• 可以對內置資料型別以及自定義資料型別的資料進行存盤
• 將陣列中的資料存盤到堆區
• 建構式中可以傳入陣列的容量
• 提供對應的拷貝建構式以及operator=防止淺拷貝問題
• 提供尾插法和尾刪法對陣列中的資料進行增加和洗掉
• 可以通過下標的方式訪問陣列中的元素
• 可以獲取陣列中當前元素個數和陣列的容量

示例：
myArray.hpp中代碼

#pragma once
#include <iostream>
using namespace std;

template<class T>
class MyArray
{
public:
    
	//建構式
	MyArray(int capacity)
	{
		this->m_Capacity = capacity;
		this->m_Size = 0;
		pAddress = new T[this->m_Capacity];
	}

	//拷貝構造
	MyArray(const MyArray & arr)
	{
		this->m_Capacity = arr.m_Capacity;
		this->m_Size = arr.m_Size;
		this->pAddress = new T[this->m_Capacity];
		for (int i = 0; i < this->m_Size; i++)
		{
			//如果T為物件，而且還包含指標，必須需要多載 = 運算子，因為這個等號不是 構造 而是賦值，
			// 普通型別可以直接= 但是指標型別需要深拷貝
			this->pAddress[i] = arr.pAddress[i];
		}
	}

	//多載= 運算子  防止淺拷貝問題
	MyArray& operator=(const MyArray& myarray) {

		if (this->pAddress != NULL) {
			delete[] this->pAddress;
			this->m_Capacity = 0;
			this->m_Size = 0;
		}

		this->m_Capacity = myarray.m_Capacity;
		this->m_Size = myarray.m_Size;
		this->pAddress = new T[this->m_Capacity];
		for (int i = 0; i < this->m_Size; i++) {
			this->pAddress[i] = myarray[i];
		}
		return *this;
	}

	//多載[] 運算子  arr[0]
	T& operator [](int index)
	{
		return this->pAddress[index]; //不考慮越界，用戶自己去處理
	}

	//尾插法
	void Push_back(const T & val)
	{
		if (this->m_Capacity == this->m_Size)
		{
			return;
		}
		this->pAddress[this->m_Size] = val;
		this->m_Size++;
	}

	//尾刪法
	void Pop_back()
	{
		if (this->m_Size == 0)
		{
			return;
		}
		this->m_Size--;
	}

	//獲取陣列容量
	int getCapacity()
	{
		return this->m_Capacity;
	}

	//獲取陣列大小
	int	getSize()
	{
		return this->m_Size;
	}


	//析構
	~MyArray()
	{
		if (this->pAddress != NULL)
		{
			delete[] this->pAddress;
			this->pAddress = NULL;
			this->m_Capacity = 0;
			this->m_Size = 0;
		}
	}

private:
	T * pAddress;  //指向一個堆空間，這個空間存盤真正的資料
	int m_Capacity; //容量
	int m_Size;   // 大小
};

類模板案例—陣列類封裝.cpp中

#include "myArray.hpp"
#include <string>

void printIntArray(MyArray<int>& arr) {
	for (int i = 0; i < arr.getSize(); i++) {
		cout << arr[i] << " ";
	}
	cout << endl;
}

//測驗內置資料型別
void test01()
{
	MyArray<int> array1(10);
	for (int i = 0; i < 10; i++)
	{
		array1.Push_back(i);
	}
	cout << "array1列印輸出：" << endl;
	printIntArray(array1);
	cout << "array1的大小：" << array1.getSize() << endl;
	cout << "array1的容量：" << array1.getCapacity() << endl;

	cout << "--------------------------" << endl;

	MyArray<int> array2(array1);
	array2.Pop_back();
	cout << "array2列印輸出：" << endl;
	printIntArray(array2);
	cout << "array2的大小：" << array2.getSize() << endl;
	cout << "array2的容量：" << array2.getCapacity() << endl;
}

//測驗自定義資料型別
class Person {
public:
	Person() {} 
		Person(string name, int age) {
		this->m_Name = name;
		this->m_Age = age;
	}
public:
	string m_Name;
	int m_Age;
};

void printPersonArray(MyArray<Person>& personArr)
{
	for (int i = 0; i < personArr.getSize(); i++) {
		cout << "姓名：" << personArr[i].m_Name << " 年齡： " << personArr[i].m_Age << endl;
	}

}

void test02()
{
	//創建陣列
	MyArray<Person> pArray(10);
	Person p1("孫悟空", 30);
	Person p2("韓信", 20);
	Person p3("妲己", 18);
	Person p4("王昭君", 15);
	Person p5("趙云", 24);

	//插入資料
	pArray.Push_back(p1);
	pArray.Push_back(p2);
	pArray.Push_back(p3);
	pArray.Push_back(p4);
	pArray.Push_back(p5);

	printPersonArray(pArray);

	cout << "pArray的大小：" << pArray.getSize() << endl;
	cout << "pArray的容量：" << pArray.getCapacity() << endl;

}

int main() {

	//test01();

	test02();

	system("pause");

	return 0;
}

2 STL初識

2.1 STL的誕生

長久以來，軟體界一直希望建立一種可重復利用的東西
C++的面向物件和泛型編程思想，目的就是復用性的提升
大多情況下，資料結構和演算法都未能有一套標準,導致被迫從事大量重復作業
為了建立資料結構和演算法的一套標準,誕生了STL
?

2.2 STL基本概念

STL(Standard Template Library,標準模板庫)
STL 從廣義上分為: 容器(container)、 演算法(algorithm) 、迭代器(iterator)
容器和演算法之間通過迭代器進行無縫連接，
STL 幾乎所有的代碼都采用了模板類或者模板函式

2.3 STL六大組件

STL大體分為六大組件，分別是：容器、演算法、迭代器、仿函式、配接器（配接器）、空間配置器

1. 容器：各種資料結構，如vector、list、deque、set、map等,用來存放資料，
2. 演算法：各種常用的演算法，如sort、find、copy、for_each等
3. 迭代器：扮演了容器與演算法之間的膠合劑，
4. 仿函式：行為類似函式，可作為演算法的某種策略，（多載小括號()）
5. 配接器：一種用來修飾容器或者仿函式或迭代器介面的東西，
6. 空間配置器：負責空間的配置與管理，

2.4 STL中容器、演算法、迭代器

1.容器： 置物之所也

STL容器就是將運用最廣泛的一些資料結構實作出來
常用的資料結構：陣列, 鏈表,樹, 堆疊, 佇列, 集合, 映射表 等
這些容器分為序列式容器和關聯式容器兩種:

• 序列式容器:強調值的排序，序列式容器中的每個元素均有固定的位置，
• 關聯式容器:二叉樹結構，各元素之間沒有嚴格的物理上的順序關系

2.演算法： 問題之解法也

有限的步驟，解決邏輯或數學上的問題，這一門學科我們叫做演算法(Algorithms)
演算法分為:質變演算法和非質變演算法，

• 質變演算法：是指運算程序中會更改區間內的元素的內容，例如拷貝，替換，洗掉等等
• 非質變演算法：是指運算程序中不會更改區間內的元素內容，例如查找、計數、遍歷、尋找極值等等

3.迭代器： 容器和演算法之間粘合劑

提供一種方法，使之能夠依序尋訪某個容器所含的各個元素，而又無需暴露該容器的內部表示方式，
每個容器都有自己專屬的迭代器
迭代器使用非常類似于指標，初學階段我們可以先理解迭代器為指標

迭代器種類：

種類	功能	支持運算
輸入迭代器	對資料的只讀訪問	只讀，支持++、==、！=
輸出迭代器	對資料的只寫訪問	只寫，支持++
前向迭代器	讀寫操作，并能向前推進迭代器	讀寫，支持++、==、！=
雙向迭代器	讀寫操作，并能向前和向后操作	讀寫，支持++、–
隨機訪問迭代器	讀寫操作，可以以跳躍的方式訪問任意資料，功能最強的迭代器	讀寫，支持++、–、[n]、-n、<、<=、>、>=

常用的容器中迭代器種類為雙向迭代器，和隨機訪問迭代器

2.5 容器演算法迭代器初識

了解STL中容器、演算法、迭代器概念之后，我們利用代碼感受STL的魅力

STL中最常用的容器為Vector，可以理解為陣列，下面我們將學習如何向這個容器中插入資料、并遍歷這個容器

2.5.1 vector存放內置資料型別

容器： vector
演算法： for_each
迭代器： vector<int>::iterator
示例：

#include<iostream>
using namespace std;
#include <vector>
#include <algorithm>
//vector容器存放內置資料型別

void myPrint(int val) {
	cout << val << endl;
}
void test01() {
	//創建一個vector容器，陣列
	vector<int> v;
	//向容器中插入資料
	v.push_back(10);//尾插
	v.push_back(20);
	v.push_back(30);
	//通過迭代器訪問容器中的資料
	vector<int>::iterator itBegin = v.begin();//起始迭代器，指向容器中第一個元素
	vector<int>::iterator itEnd = v.end();//結束迭代器，指向容器中最后一個元素的下一個位置

	//第一種遍歷方式
	//while (itBegin != itEnd) {
	//	cout << *itBegin << endl;//迭代器使用非常類似于指標，初學階段我們可以先理解迭代器為指標
	//	itBegin++;
	//}

	//第二種遍歷方式
	//for (vector<int>::iterator it = v.begin(); it != v.end(); it++) {
	//	cout << *it << endl;
	//}

	//第三種遍歷方式：利用STL中提供的遍歷演算法
	for_each(v.begin(), v.end(), myPrint);
}

int main() {

	test01();

	system("pause");

	return 0;
}

2.5.2 Vector存放自定義資料型別

學習目標：vector中存放自定義資料型別，并列印輸出

示例：

#include <vector>
#include <string>

//自定義資料型別
class Person {
public:
	Person(string name, int age) {
		mName = name;
		mAge = age;
	}
public:
	string mName;
	int mAge;
};
//存放物件
void test01() {

	vector<Person> v;

	//創建資料
	Person p1("aaa", 10);
	Person p2("bbb", 20);
	Person p3("ccc", 30);
	Person p4("ddd", 40);
	Person p5("eee", 50);

	v.push_back(p1);
	v.push_back(p2);
	v.push_back(p3);
	v.push_back(p4);
	v.push_back(p5);

	for (vector<Person>::iterator it = v.begin(); it != v.end(); it++) {
		cout << "Name:" << (*it).mName << " Age:" << (*it).mAge << endl;

	}
}


//放物件指標
void test02() {

	vector<Person*> v;

	//創建資料
	Person p1("aaa", 10);
	Person p2("bbb", 20);
	Person p3("ccc", 30);
	Person p4("ddd", 40);
	Person p5("eee", 50);

	v.push_back(&p1);
	v.push_back(&p2);
	v.push_back(&p3);
	v.push_back(&p4);
	v.push_back(&p5);

	for (vector<Person*>::iterator it = v.begin(); it != v.end(); it++) {
		Person * p = (*it);
		cout << "Name:" << p->mName << " Age:" << (*it)->mAge << endl;
	}
}


int main() {

	test01();
    
	test02();

	system("pause");

	return 0;
}

2.5.3 Vector容器嵌套容器

學習目標：容器中嵌套容器，我們將所有資料進行遍歷輸出

示例：

#include <vector>

//容器嵌套容器
void test01() {

	vector< vector<int> >  v;

	vector<int> v1;
	vector<int> v2;
	vector<int> v3;
	vector<int> v4;

	for (int i = 0; i < 4; i++) {
		v1.push_back(i + 1);
		v2.push_back(i + 2);
		v3.push_back(i + 3);
		v4.push_back(i + 4);
	}

	//將容器元素插入到vector v中
	v.push_back(v1);
	v.push_back(v2);
	v.push_back(v3);
	v.push_back(v4);


	for (vector<vector<int>>::iterator it = v.begin(); it != v.end(); it++) {

		for (vector<int>::iterator vit = (*it).begin(); vit != (*it).end(); vit++) {
			cout << *vit << " ";
		}
		cout << endl;
	}

}

int main() {

	test01();

	system("pause");

	return 0;
}

3 STL - 常用容器

3.1 string容器

3.1.1 string基本概念

本質：string是C++風格的字串，而string本質上是一個類
string和char * 區別：

• char * 是一個指標
• string是一個類，類內部封裝了char*，管理這個字串，是一個char*型的容器，

特點：

• string 類內部封裝了很多成員方法，例如：查找find，拷貝copy，洗掉delete 替換replace，插入insert
• string管理char*所分配的記憶體，不用擔心復制越界和取值越界等，由類內部進行負責

3.1.2 string建構式

建構式原型：

• string(); //創建一個空的字串 例如: string str;
• string(const char* s); //使用字串s初始化
• string(const string& str); //使用一個string物件初始化另一個string物件
• string(int n, char c); //使用n個字符c初始化

示例：

#include <string>
//string構造
void test01()
{
	string s1; //創建空字串，呼叫無參建構式
	cout << "str1 = " << s1 << endl;

	const char* str = "hello world";
	string s2(str); //把c_string轉換成了string

	cout << "str2 = " << s2 << endl;

	string s3(s2); //呼叫拷貝建構式
	cout << "str3 = " << s3 << endl;

	string s4(10, 'a');
	cout << "str4 = " << s4 << endl;
}

int main() {

	test01();

	system("pause");

	return 0;
}

總結：string的多種構造方式沒有可比性，靈活使用即可

3.1.3 string賦值操作

功能描述：給string字串進行賦值

賦值的函式原型：

• string& operator=(const char* s); //char*型別字串 賦值給當前的字串
• string& operator=(const string &s); //把字串s賦給當前的字串
• string& operator=(char c); //字符賦值給當前的字串
• string& assign(const char *s); //把字串s賦給當前的字串
• string& assign(const char *s, int n); //把字串s的前n個字符賦給當前的字串
• string& assign(const string &s); //把字串s賦給當前字串
• string& assign(int n, char c); //用n個字符c賦給當前字串

示例：

//賦值
void test01()
{
	string str1;
	str1 = "hello world";
	cout << "str1 = " << str1 << endl;

	string str2;
	str2 = str1;
	cout << "str2 = " << str2 << endl;

	string str3;
	str3 = 'a';
	cout << "str3 = " << str3 << endl;

	string str4;
	str4.assign("hello c++");
	cout << "str4 = " << str4 << endl;

	string str5;
	str5.assign("hello c++",5);
	cout << "str5 = " << str5 << endl;


	string str6;
	str6.assign(str5);
	cout << "str6 = " << str6 << endl;

	string str7;
	str7.assign(5, 'x');
	cout << "str7 = " << str7 << endl;
}

int main() {

	test01();

	system("pause");

	return 0;
}

總結：string的賦值方式很多，operator= 這種方式是比較實用的

3.1.4 string字串拼接

功能描述：實作在字串末尾拼接字串
函式原型：

• string& operator+=(const char* str); //多載+=運算子
• string& operator+=(const char c); //多載+=運算子
• string& operator+=(const string& str); //多載+=運算子
• string& append(const char *s); //把字串s連接到當前字串結尾
• string& append(const char *s, int n); //把字串s的前n個字符連接到當前字串結尾
• string& append(const string &s); //同operator+=(const string& str)
• string& append(const string &s, int pos, int n);//字串s中從pos開始的n個字符連接到字串結尾

示例：

//字串拼接
void test01()
{
	string str1 = "我";

	str1 += "愛玩游戲";

	cout << "str1 = " << str1 << endl;
	
	str1 += ':';

	cout << "str1 = " << str1 << endl;

	string str2 = "LOL DNF";

	str1 += str2;

	cout << "str1 = " << str1 << endl;

	string str3 = "I";
	str3.append(" love ");
	str3.append("game abcde", 4);
	//str3.append(str2);
	str3.append(str2, 4, 3); // 從下標4位置開始 ，截取3個字符，拼接到字串末尾
	cout << "str3 = " << str3 << endl;
}
int main() {

	test01();

	system("pause");

	return 0;
}

總結：字串拼接的多載版本很多，初學階段記住幾種即可

3.1.5 string查找和替換

功能描述：

• 查找：查找指定字串是否存在
• 替換：在指定的位置替換字串

函式原型：

• int find(const string& str, int pos = 0) const; //查找str第一次出現位置,從pos開始查找
• int find(const char* s, int pos = 0) const; //查找s第一次出現位置,從pos開始查找
• int find(const char* s, int pos, int n) const; //從pos位置查找s的前n個字符第一次位置
• int find(const char c, int pos = 0) const; //查找字符c第一次出現位置
• int rfind(const string& str, int pos = npos) const; //查找str最后一次位置,從pos開始查找
• int rfind(const char* s, int pos = npos) const; //查找s最后一次出現位置,從pos開始查找
• int rfind(const char* s, int pos, int n) const; //從pos查找s的前n個字符最后一次位置
• int rfind(const char c, int pos = 0) const; //查找字符c最后一次出現位置
• string& replace(int pos, int n, const string& str); //替換從pos開始n個字符為字串str
• string& replace(int pos, int n,const char* s); //替換從pos開始的n個字符為字串s

示例：

//查找和替換
void test01()
{
	//查找
	string str1 = "abcdefgde";

	int pos = str1.find("de");

	if (pos == -1)
	{
		cout << "未找到" << endl;
	}
	else
	{
		cout << "pos = " << pos << endl;
	}
	

	pos = str1.rfind("de");

	cout << "pos = " << pos << endl;

}

void test02()
{
	//替換
	string str1 = "abcdefgde";
	str1.replace(1, 3, "1111");

	cout << "str1 = " << str1 << endl;
}

int main() {

	//test01();
	//test02();

	system("pause");

	return 0;
}

總結：

• find查找是從左往后，rfind從右往左
• find找到字串后回傳查找的第一個字符位置，找不到回傳-1
• replace在替換時，要指定從哪個位置起，多少個字符，替換成什么樣的字串

3.1.6 string字串比較

功能描述：字串之間的比較
比較方式：字串比較是按字符的ASCII碼進行對比
= 回傳 0，>回傳 1，< 回傳 -1

函式原型：

• int compare(const string &s) const; //與字串s比較
• int compare(const char *s) const; //與字串s比較

示例：

//字串比較
void test01()
{

	string s1 = "hello";
	string s2 = "aello";

	int ret = s1.compare(s2);

	if (ret == 0) {
		cout << "s1 等于 s2" << endl;
	}
	else if (ret > 0)
	{
		cout << "s1 大于 s2" << endl;
	}
	else
	{
		cout << "s1 小于 s2" << endl;
	}

}

int main() {

	test01();

	system("pause");

	return 0;
}

總結：字串對比主要是用于比較兩個字串是否相等，判斷誰大誰小的意義并不是很大

3.1.7 string字符存取

string中單個字符存取方式有兩種

• char& operator[](int n); //通過[]方式取字符
• char& at(int n); //通過at方法獲取字符

示例：

void test01()
{
	string str = "hello world";

	for (int i = 0; i < str.size(); i++)
	{
		cout << str[i] << " ";
	}
	cout << endl;

	for (int i = 0; i < str.size(); i++)
	{
		cout << str.at(i) << " ";
	}
	cout << endl;


	//字符修改
	str[0] = 'x';
	str.at(1) = 'x';
	cout << str << endl;
	
}

int main() {

	test01();

	system("pause");

	return 0;
}

3.1.8 string插入和洗掉

功能描述：對string字串進行插入和洗掉字符操作
函式原型：

• string& insert(int pos, const char* s); //插入字串
• string& insert(int pos, const string& str); //插入字串
• string& insert(int pos, int n, char c); //在指定位置插入n個字符c
• string& erase(int pos, int n = npos); //洗掉從Pos開始的n個字符

示例：

//字串插入和洗掉
void test01()
{
	string str = "hello";
	str.insert(1, "111");
	cout << str << endl;

	str.erase(1, 3);  //從1號位置開始3個字符
	cout << str << endl;
}

int main() {

	test01();

	system("pause");

	return 0;
}

總結： 插入和洗掉的起始下標都是從0開始

3.1.9 string子串

功能描述：從字串中獲取想要的子串
函式原型：

• string substr(int pos = 0, int n = npos) const; //回傳由pos開始的n個字符組成的字串

示例：

//子串
void test01()
{

	string str = "abcdefg";
	string subStr = str.substr(1, 3);
	cout << "subStr = " << subStr << endl;

	string email = "hello@sina.com";
	int pos = email.find("@");
	string username = email.substr(0, pos);
	cout << "username: " << username << endl;

}

int main() {

	test01();

	system("pause");

	return 0;
}

總結： 靈活的運用求子串功能，可以在實際開發中獲取有效的資訊

3.2 vector容器

3.2.1 vector基本概念

功能：vector資料結構和陣列非常相似，也稱為單端陣列

vector與普通陣列區別：不同之處在于陣列是靜態空間，而vector可以動態擴展

動態擴展：

• 并不是在原空間之后續接新空間，而是找更大的記憶體空間，然后將原資料拷貝新空間，釋放原空間
  
• vector容器的迭代器是支持隨機訪問的迭代器

3.2.2 vector建構式

功能描述：創建vector容器
函式原型：

• vector<T> v; //采用模板實作類實作，默認建構式
• vector(v.begin(), v.end()); //將v[begin(), end()）區間中的元素拷貝給本身，
• vector(n, elem); //建構式將n個elem拷貝給本身，
• vector(const vector &vec); //拷貝建構式，

示例：

#include <vector>

void printVector(vector<int>& v) {

	for (vector<int>::iterator it = v.begin(); it != v.end(); it++) {
		cout << *it << " ";
	}
	cout << endl;
}

void test01()
{
	vector<int> v1; //無參構造
	for (int i = 0; i < 10; i++)
	{
		v1.push_back(i);
	}
	printVector(v1);

	vector<int> v2(v1.begin(), v1.end());
	printVector(v2);

	vector<int> v3(10, 100);
	printVector(v3);
	
	vector<int> v4(v3);
	printVector(v4);
}

int main() {

	test01();

	system("pause");

	return 0;
}

總結： vector的多種構造方式沒有可比性，靈活使用即可

3.2.3 vector賦值操作

功能描述：給vector容器進行賦值
函式原型：

• vector& operator=(const vector &vec);//多載等號運算子
• assign(beg, end); //將[beg, end)區間中的資料拷貝賦值給本身，
• assign(n, elem); //將n個elem拷貝賦值給本身，

示例：

#include <vector>

void printVector(vector<int>& v) {

	for (vector<int>::iterator it = v.begin(); it != v.end(); it++) {
		cout << *it << " ";
	}
	cout << endl;
}

//賦值操作
void test01()
{
	vector<int> v1; //無參構造
	for (int i = 0; i < 10; i++)
	{
		v1.push_back(i);
	}
	printVector(v1);

	vector<int>v2;
	v2 = v1;//1.多載等號運算子
	printVector(v2);

	vector<int>v3;
	v3.assign(v1.begin(), v1.end());
	printVector(v3);

	vector<int>v4;
	v4.assign(10, 100);
	printVector(v4);
}

int main() {

	test01();

	system("pause");

	return 0;
}

3.2.4 vector容量和大小

功能描述：對vector容器的容量和大小操作
函式原型：

• empty(); //判斷容器是否為空
• capacity(); //容器的容量
• size(); //回傳容器中元素的個數
• resize(int num); //重新指定容器的長度為num，若容器變長，則以默認值填充新位置，
  ? //如果容器變短，則末尾超出容器長度的元素被洗掉，
• resize(int num, elem); //重新指定容器的長度為num，若容器變長，則以elem值填充新位置，
  ? //如果容器變短，則末尾超出容器長度的元素被洗掉

示例：

#include <vector>

void printVector(vector<int>& v) {

	for (vector<int>::iterator it = v.begin(); it != v.end(); it++) {
		cout << *it << " ";
	}
	cout << endl;
}

void test01()
{
	vector<int> v1;
	for (int i = 0; i < 10; i++)
	{
		v1.push_back(i);
	}
	printVector(v1);
	if (v1.empty())
	{
		cout << "v1為空" << endl;
	}
	else
	{
		cout << "v1不為空" << endl;
		cout << "v1的容量 = " << v1.capacity() << endl;//vector會多預留出來一部分空間
		cout << "v1的大小 = " << v1.size() << endl;
	}

	//resize 重新指定大小 ，若指定的更大，默認用0填充新位置，可以利用多載版本替換默認填充
	v1.resize(15,10);
	printVector(v1);

	//resize 重新指定大小 ，若指定的更小，超出部分元素被洗掉
	v1.resize(5);
	printVector(v1);
}

int main() {

	test01();

	system("pause");

	return 0;
}

總結： vector會多預留出來一部分空間，使capacity大于size

3.2.5 vector插入和洗掉

功能描述：對vector容器進行插入、洗掉操作
函式原型：

• push_back(ele); //尾部插入元素ele
• pop_back(); //洗掉最后一個元素
• insert(const_iterator pos, ele); //迭代器指向位置pos插入元素ele
• insert(const_iterator pos, int count,ele);//迭代器指向位置pos插入count個元素ele
• erase(const_iterator pos); //洗掉迭代器指向的元素
• erase(const_iterator start, const_iterator end);//洗掉迭代器從start到end之間的元素
• clear(); //洗掉容器中所有元素

示例：

#include <vector>

void printVector(vector<int>& v) {

	for (vector<int>::iterator it = v.begin(); it != v.end(); it++) {
		cout << *it << " ";
	}
	cout << endl;
}

//插入和洗掉
void test01()
{
	vector<int> v1;
	//尾插
	v1.push_back(10);
	v1.push_back(20);
	v1.push_back(30);
	v1.push_back(40);
	v1.push_back(50);
	printVector(v1);
	//尾刪
	v1.pop_back();
	printVector(v1);
	//插入
	v1.insert(v1.begin(), 100);
	printVector(v1);

	v1.insert(v1.begin(), 2, 1000);
	printVector(v1);

	//洗掉
	v1.erase(v1.begin());
	printVector(v1);

	//清空
	v1.erase(v1.begin(), v1.end());
	v1.clear();
	printVector(v1);
}

int main() {

	test01();

	system("pause");

	return 0;
}

3.2.6 vector資料存取

功能描述：對vector中的資料的存取操作
函式原型：

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

示例：

#include <vector>

void test01()
{
	vector<int>v1;
	for (int i = 0; i < 10; i++)
	{
		v1.push_back(i);
	}

	for (int i = 0; i < v1.size(); i++)
	{
		cout << v1[i] << " ";
	}
	cout << endl;

	for (int i = 0; i < v1.size(); i++)
	{
		cout << v1.at(i) << " ";
	}
	cout << endl;

	cout << "v1的第一個元素為： " << v1.front() << endl;
	cout << "v1的最后一個元素為： " << v1.back() << endl;
}

int main() {

	test01();

	system("pause");

	return 0;
}

3.2.7 vector互換容器

功能描述：實作兩個容器內元素進行互換
函式原型：

• swap(vec); // 將vec與本身的元素互換

示例：

#include <vector>

void printVector(vector<int>& v) {

	for (vector<int>::iterator it = v.begin(); it != v.end(); it++) {
		cout << *it << " ";
	}
	cout << endl;
}

void test01()
{
	vector<int>v1;
	for (int i = 0; i < 10; i++)
	{
		v1.push_back(i);
	}
	printVector(v1);

	vector<int>v2;
	for (int i = 10; i > 0; i--)
	{
		v2.push_back(i);
	}
	printVector(v2);

	//互換容器
	cout << "互換后" << endl;
	v1.swap(v2);
	printVector(v1);
	printVector(v2);
}

void test02()
{
	vector<int> v;
	for (int i = 0; i < 100000; i++) {
		v.push_back(i);
	}

	cout << "v的容量為：" << v.capacity() << endl;//vector會多預留出來一部分空間
	cout << "v的大小為：" << v.size() << endl;

	v.resize(3);//resize只改變大小不改變容量

	cout << "v的容量為：" << v.capacity() << endl;
	cout << "v的大小為：" << v.size() << endl;

	//收縮記憶體
	vector<int>(v).swap(v); //vector<int>(v)：利用拷貝建構式創建匿名物件，會按照v目前所用大小來初始化匿名函式容量大小

	cout << "v的容量為：" << v.capacity() << endl;
	cout << "v的大小為：" << v.size() << endl;
}

int main() {

	test01();

	test02();

	system("pause");

	return 0;
}

總結： swap可以使兩個容器互換，可以達到實用的收縮記憶體效果

3.2.8 vector預留空間

功能描述：減少vector在動態擴展容量時的擴展次數
函式原型：

• reserve(int len);//容器預留len個元素長度，預留位置不初始化，元素不可訪問，

示例：

#include <vector>

void test01()
{
	vector<int> v;

	//預留空間
	v.reserve(100000);

	int num = 0;//統計vector因為空間不夠而開辟新空間的次數
	int* p = NULL;
	for (int i = 0; i < 100000; i++) {
		v.push_back(i);
		if (p != &v[0]) {//每次擴容會開辟一個新空間，原來的p不再指向v[0]
			p = &v[0];
			num++;
		}
	}

	cout << "num:" << num << endl;//一共開辟了30次，如果預留空間，就只開辟一次
}

int main() {

	test01();
    
	system("pause");

	return 0;
}

總結： 如果資料量較大，可以一開始利用reserve預留空間

3.3 deque容器

3.3.1 deque容器基本概念

功能：雙端陣列，可以對頭端進行插入洗掉操作

deque與vector區別：

• vector對于頭部的插入洗掉效率低，資料量越大，效率越低
• deque相對而言，對頭部的插入洗掉速度比vector快
• vector訪問元素時的速度會比deque快,這和兩者內部實作有關

deque內部作業原理：deque內部有個中控器，維護每段緩沖區中的內容，緩沖區中存放真實資料
中控器維護的是每個緩沖區的地址，使得使用deque時像一片連續的記憶體空間

為什么vector訪問元素時的速度會比deque快呢？因為deque在訪問元素時需要在中控器查找對應地址

deque容器的迭代器也是支持隨機訪問的

3.3.2 deque建構式

功能描述：deque容器構造
函式原型：

• deque<T> deqT; //默認構造形式
• deque(beg, end); //建構式將[beg, end)區間中的元素拷貝給本身，
• deque(n, elem); //建構式將n個elem拷貝給本身，
• deque(const deque &deq); //拷貝建構式

示例：

#include <deque>

void printDeque(const deque<int>& d) 
{
	for (deque<int>::const_iterator it = d.begin(); it != d.end(); it++) {
		cout << *it << " ";

	}
	cout << endl;
}
//deque構造
void test01() {

	deque<int> d1; //無參建構式
	for (int i = 0; i < 10; i++)
	{
		d1.push_back(i);
	}
	printDeque(d1);
	deque<int> d2(d1.begin(),d1.end());
	printDeque(d2);

	deque<int>d3(10,100);
	printDeque(d3);

	deque<int>d4 = d3;
	printDeque(d4);
}

int main() {

	test01();

	system("pause");

	return 0;
}

總結： deque容器和vector容器的構造方式幾乎一致，靈活使用即可

3.3.3 deque賦值操作

功能描述：給deque容器進行賦值
函式原型：

• deque& operator=(const deque &deq); //多載等號運算子
• assign(beg, end); //將[beg, end)區間中的資料拷貝賦值給本身，
• assign(n, elem); //將n個elem拷貝賦值給本身，

示例：

#include <deque>

void printDeque(const deque<int>& d) 
{
	for (deque<int>::const_iterator it = d.begin(); it != d.end(); it++) {
		cout << *it << " ";

	}
	cout << endl;
}
//賦值操作
void test01()
{
	deque<int> d1;
	for (int i = 0; i < 10; i++)
	{
		d1.push_back(i);
	}
	printDeque(d1);

	deque<int>d2;
	d2 = d1;
	printDeque(d2);

	deque<int>d3;
	d3.assign(d1.begin(), d1.end());
	printDeque(d3);

	deque<int>d4;
	d4.assign(10, 100);
	printDeque(d4);

}

int main() {

	test01();

	system("pause");

	return 0;
}

3.3.4 deque大小操作

功能描述：對deque容器的大小進行操作

函式原型：

• deque.empty(); //判斷容器是否為空
• deque.size(); //回傳容器中元素的個數
• deque.resize(num); //重新指定容器的長度為num,若容器變長，則以默認值填充新位置，
  ? //如果容器變短，則末尾超出容器長度的元素被洗掉，
• deque.resize(num, elem); //重新指定容器的長度為num,若容器變長，則以elem值填充新位置，
  ? //如果容器變短，則末尾超出容器長度的元素被洗掉，

示例：

#include <deque>

void printDeque(const deque<int>& d) 
{
	for (deque<int>::const_iterator it = d.begin(); it != d.end(); it++) {
		cout << *it << " ";

	}
	cout << endl;
}

//大小操作
void test01()
{
	deque<int> d1;
	for (int i = 0; i < 10; i++)
	{
		d1.push_back(i);
	}
	printDeque(d1);

	//判斷容器是否為空
	if (d1.empty()) {
		cout << "d1為空!" << endl;
	}
	else {
		cout << "d1不為空!" << endl;
		//統計大小
		cout << "d1的大小為：" << d1.size() << endl;
	}

	//重新指定大小
	d1.resize(15, 1);
	printDeque(d1);

	d1.resize(5);
	printDeque(d1);
}

int main() {

	test01();

	system("pause");

	return 0;
}

總結： deque沒有容量概念

3.3.5 deque 插入和洗掉

功能描述：向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 <deque>

void printDeque(const deque<int>& d) 
{
	for (deque<int>::const_iterator it = d.begin(); it != d.end(); it++) {
		cout << *it << " ";

	}
	cout << endl;
}
//兩端操作
void test01()
{
	deque<int> d;
	//尾插
	d.push_back(10);
	d.push_back(20);
	//頭插
	d.push_front(100);
	d.push_front(200);

	printDeque(d);

	//尾刪
	d.pop_back();
	//頭刪
	d.pop_front();
	printDeque(d);
}

//插入
void test02()
{
	deque<int> d;
	d.push_back(10);
	d.push_back(20);
	d.push_front(100);
	d.push_front(200);
	printDeque(d);

	d.insert(d.begin(), 1000);
	printDeque(d);

	d.insert(d.begin(), 2,10000);
	printDeque(d);

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

	d.insert(d.begin(), d2.begin(), d2.end());
	printDeque(d);

}

//洗掉
void test03()
{
	deque<int> d;
	d.push_back(10);
	d.push_back(20);
	d.push_front(100);
	d.push_front(200);
	printDeque(d);

	d.erase(d.begin());
	printDeque(d);

	d.erase(d.begin(), d.end());
	d.clear();
	printDeque(d);
}

int main() {

	//test01();

	//test02();

    test03();
    
	system("pause");

	return 0;
}

3.3.6 deque 資料存取

功能描述：對deque 中的資料的存取操作

函式原型：

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

示例：

#include <deque>

void printDeque(const deque<int>& d) 
{
	for (deque<int>::const_iterator it = d.begin(); it != d.end(); it++) {
		cout << *it << " ";

	}
	cout << endl;
}

//資料存取
void test01()
{

	deque<int> d;
	d.push_back(10);
	d.push_back(20);
	d.push_front(100);
	d.push_front(200);

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


	for (int i = 0; i < d.size(); i++) {
		cout << d.at(i) << " ";
	}
	cout << endl;

	cout << "front:" << d.front() << endl;

	cout << "back:" << d.back() << endl;

}

int main() {

	test01();

	system("pause");

	return 0;
}

3.3.7 deque 排序

功能描述：利用演算法實作對deque容器進行排序
演算法：

• sort(iterator beg, iterator end) //對beg和end區間內元素進行排序

示例：

#include <deque>
#include <algorithm>

void printDeque(const deque<int>& d) 
{
	for (deque<int>::const_iterator it = d.begin(); it != d.end(); it++) {
		cout << *it << " ";

	}
	cout << endl;
}

void test01()
{

	deque<int> d;
	d.push_back(10);
	d.push_back(20);
	d.push_front(100);
	d.push_front(200);

	printDeque(d);
	sort(d.begin(), d.end());
	printDeque(d);

}

int main() {

	test01();

	system("pause");

	return 0;
}

總結：sort演算法非常實用，使用時包含頭檔案 algorithm即可

3.4 案例-評委打分

3.4.1 案例描述

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

3.4.2 實作步驟

思考：需要去掉最高分去掉最低分，可以將每個選手的十個分數用deque存盤，方便去頭去尾，再將每個選手用vector存盤，
步驟：

1. 創建五名選手，放到vector中
2. 遍歷vector容器，取出來每一個選手，執行for回圈，可以把10個評分打分存到deque容器中
3. sort演算法對deque容器中分數排序，去除最高和最低分
4. deque容器遍歷一遍，累加總分
5. 獲取平均分

示例代碼：

//選手類
class Person
{
public:
	Person(string name, int score)
	{
		this->m_Name = name;
		this->m_Score = score;
	}

	string m_Name; //姓名
	int m_Score;  //平均分
};

void createPerson(vector<Person>&v)
{
	string nameSeed = "ABCDE";
	for (int i = 0; i < 5; i++)
	{
		string name = "選手";
		name += nameSeed[i];

		int score = 0;

		Person p(name, score);

		//將創建的person物件 放入到容器中
		v.push_back(p);
	}
}

//打分
void setScore(vector<Person>&v)
{
	for (vector<Person>::iterator it = v.begin(); it != v.end(); it++)
	{
		//將評委的分數 放入到deque容器中
		deque<int>d;
		for (int i = 0; i < 10; i++)
		{
			int score = rand() % 41 + 60;  // 60 ~ 100
			d.push_back(score);
		}

		//cout << "選手： " << it->m_Name << " 打分： " << endl;
		//for (deque<int>::iterator dit = d.begin(); dit != d.end(); dit++)
		//{
		//	cout << *dit << " ";
		//}
		//cout << endl;

		//排序
		sort(d.begin(), d.end());

		//去除最高和最低分
		d.pop_back();
		d.pop_front();

		//取平均分
		int sum = 0;
		for (deque<int>::iterator dit = d.begin(); dit != d.end(); dit++)
		{
			sum += *dit; //累加每個評委的分數
		}

		int avg = sum / d.size();

		//將平均分 賦值給選手身上
		it->m_Score = avg;
	}

}

void showScore(vector<Person>&v)
{
	for (vector<Person>::iterator it = v.begin(); it != v.end(); it++)
	{
		cout << "姓名： " << it->m_Name << " 平均分： " << it->m_Score << endl;
	}
}

int main() {

	//亂數種子
	srand((unsigned int)time(NULL));

	//1、創建5名選手
	vector<Person>v;  //存放選手容器
	createPerson(v);

	//測驗
	//for (vector<Person>::iterator it = v.begin(); it != v.end(); it++)
	//{
	//	cout << "姓名： " << (*it).m_Name << " 分數： " << (*it).m_Score << endl;
	//}

	//2、給5名選手打分
	setScore(v);

	//3、顯示最后得分
	showScore(v);

	system("pause");

	return 0;
}

我自己寫的代碼：

#include<iostream>
using namespace std;
//有5名選手：選手ABCDE，10個評委分別對每一名選手打分，去除最高分，去除評委中最低分，取平均分，
//思考：需要去掉最高分去掉最低分，可以將每個選手的十個分數用deque存盤，方便去頭去尾，再將每個選手用vector存盤，
//步驟：
//1.創建vector存盤五個選手
//2.每個選手的十個評委打分用deque存盤
//3.sort，去頭去尾，累加之后計算平均成績
#include <string>
#include <deque>
#include <vector>
#include <algorithm>
//選手類
class Person {
public:
	string m_Name;
	double m_AvgScore;
	deque<double> m_score;

	Person(string name, deque<double> score) {
		m_Name = name;
		m_score = score;
	}
};

//實體化選手物件
Person creatPerson(string name, double score[5]) {
	deque<double> dScore;
	for (int i = 0; i < 5; i++) {
		dScore.push_back(score[i]);
	}
	Person p = Person(name, dScore);
	return p;
}

//處理分數
void calAvg(vector<Person>& v) {//傳進來的是參考，就不需要回傳v了
	for (int i = 0; i < v.size(); i++) {
		deque<double> score = v[i].m_score;
		sort(score.begin(), score.end());
		
		score.pop_back();
		score.pop_front();
		
		double allScore = 0;
		int size = score.size();
		for (int j = 0; j < size; j++) {
			allScore += score[j];
		}
		
		v[i].m_AvgScore = allScore / size;
	}
}

//輸出結果
void print(vector<Person>& v) {
	for (int i = 0; i < v.size(); i++) {
		cout << "選手" << v[i].m_Name << "的平均分數為" << v[i].m_AvgScore << endl;
	}
}

int main() {
	//創建2個選手
	double score1[5] = { 9.0,8.6,8.8,8.5,8.2 };
	Person p1 = creatPerson("Marry", score1);

	double score2[5] = { 8.8,8.7,9.1,9.0 ,8.4};
	Person p2 = creatPerson("June", score2);

	//vector存盤選手
	vector<Person> v;
	v.push_back(p1);
	v.push_back(p2);

	//處理分數
	calAvg(v);
	//輸出結果
	print(v);

	system("pause");

	return 0;
}

學到的知識：
1.傳入的引數是參考型別，就不用再回傳該型別了，因為參考是直接在原資料上修改，（相反，如果不希望原資料被修改，就不要傳入參考型別）
2.代碼大致框架和老師一樣，即：專門的函式實作專門的功能，在main里只需要呼叫就好了， 這是個很好的編程習慣，要保持
3.涉及到容器的遍歷老師用的都是迭代器，而我用的還是普通的for回圈，要多用新學到的知識！
4.每寫一個模塊要有輸出測驗一下代碼是否正確，這點我偷懶了做得不是很好，

修改后的代碼：

#include<iostream>
using namespace std;
//有5名選手：選手ABCDE，10個評委分別對每一名選手打分，去除最高分，去除評委中最低分，取平均分，
//思考：需要去掉最高分去掉最低分，可以將每個選手的十個分數用deque存盤，方便去頭去尾，再將每個選手用vector存盤，
//步驟：
//1.創建vector存盤五個選手
//2.每個選手的十個評委打分用deque存盤
//3.sort，去頭去尾，累加之后計算平均成績
#include <string>
#include <deque>
#include <vector>
#include <algorithm>
//選手類
class Person {
public:
	string m_Name;
	double m_AvgScore;
	deque<double> m_score;

	Person(string name, deque<double> score) {
		m_Name = name;
		m_score = score;
	}
};

//實體化選手物件
Person creatPerson(string name, double score[5]) {
	deque<double> dScore;
	for (int i = 0; i < 5; i++) {
		dScore.push_back(score[i]);
	}
	Person p = Person(name, dScore);
	return p;
}

//處理分數
void calAvg(vector<Person>& v) {//傳進來的是參考，就不需要回傳v了
	for (vector<Person>::iterator it = v.begin(); it != v.end();it++) {
		deque<double> score = it->m_score;
		sort(score.begin(), score.end());
		
		score.pop_back();
		score.pop_front();
		
		double allScore = 0;

		for (deque<double>::iterator dit = score.begin(); dit != score.end();dit++) {
			allScore += *dit;
		}
		
		it->m_AvgScore = allScore / score.size();
	}
}

//輸出結果
void print(vector<Person>& v) {
	for (vector<Person>::iterator it = v.begin(); it != v.end(); it++) {
		cout << "選手" << it->m_Name << "的平均分數為" << it->m_AvgScore << endl;
	}
}

int main() {
	//創建2個選手
	double score1[5] = { 9.0,8.6,8.8,8.5,8.2 };
	Person p1 = creatPerson("Marry", score1);

	double score2[5] = { 8.8,8.7,9.1,9.0 ,8.4};
	Person p2 = creatPerson("June", score2);

	//vector存盤選手
	vector<Person> v;
	v.push_back(p1);
	v.push_back(p2);

	//處理分數
	calAvg(v);
	print(v);

	system("pause");

	return 0;
}

3.5 stack容器

3.5.1 stack 基本概念

概念：stack是一種先進后出(First In Last Out,FILO)的資料結構，它只有一個出口，堆疊中只有頂端的元素才可以被外界使用，因此堆疊不允許有遍歷行為

堆疊中進入資料稱為 — 入堆疊 push
堆疊中彈出資料稱為 — 出堆疊 pop

3.5.2 stack 常用介面

功能描述：堆疊容器常用的對外介面

建構式：

• stack<T> stk; //stack采用模板類實作， stack物件的默認構造形式
• stack(const stack &stk); //拷貝建構式

賦值操作：

• stack& operator=(const stack &stk); //多載等號運算子

資料存取：

• push(elem); //向堆疊頂添加元素
• pop(); //從堆疊頂移除第一個元素
• top(); //回傳堆疊頂元素

大小操作：

• empty(); //判斷堆疊是否為空
• size(); //回傳堆疊的大小

示例：

#include <stack>

//堆疊容器常用介面
void test01()
{
	//創建堆疊容器 堆疊容器必須符合先進后出
	stack<int> s;

	//向堆疊中添加元素，叫做 壓堆疊 入堆疊
	s.push(10);
	s.push(20);
	s.push(30);

	while (!s.empty()) {
		//輸出堆疊頂元素
		cout << "堆疊頂元素為： " << s.top() << endl;
		//彈出堆疊頂元素
		s.pop();
	}
	cout << "堆疊的大小為：" << s.size() << endl;

}

int main() {

	test01();

	system("pause");

	return 0;
}

3.6 queue 容器

3.6.1 queue 基本概念

概念：Queue是一種先進先出(First In First Out,FIFO)的資料結構，它有兩個出口，佇列容器允許從一端新增元素，從另一端移除元素，佇列中只有隊頭和隊尾才可以被外界使用，因此佇列不允許有遍歷行為

佇列中進資料稱為 — 入隊 push
佇列中出資料稱為 — 出隊 pop

3.6.2 queue 常用介面

功能描述：堆疊容器常用的對外介面

建構式：

• queue<T> que; //queue采用模板類實作，queue物件的默認構造形式
• queue(const queue &que); //拷貝建構式

賦值操作：

• queue& operator=(const queue &que); //多載等號運算子

資料存取：

• push(elem); //往隊尾添加元素
• pop(); //從隊頭移除第一個元素
• back(); //回傳最后一個元素
• front(); //回傳第一個元素

大小操作：

• empty(); //判斷堆疊是否為空
• size(); //回傳堆疊的大小

示例：

#include <queue>
#include <string>
class Person
{
public:
	Person(string name, int age)
	{
		this->m_Name = name;
		this->m_Age = age;
	}

	string m_Name;
	int m_Age;
};

void test01() {

	//創建佇列
	queue<Person> q;

	//準備資料
	Person p1("唐僧", 30);
	Person p2("孫悟空", 1000);
	Person p3("豬八戒", 900);
	Person p4("沙僧", 800);

	//向佇列中添加元素  入隊操作
	q.push(p1);
	q.push(p2);
	q.push(p3);
	q.push(p4);

	//佇列不提供迭代器，更不支持隨機訪問	
	while (!q.empty()) {
		//輸出隊頭元素
		cout << "隊頭元素-- 姓名： " << q.front().m_Name 
              << " 年齡： "<< q.front().m_Age << endl;
        
		cout << "隊尾元素-- 姓名： " << q.back().m_Name  
              << " 年齡： " << q.back().m_Age << endl;
        
		cout << endl;
		//彈出隊頭元素
		q.pop();
	}

	cout << "佇列大小為：" << q.size() << endl;
}

int main() {

	test01();

	system("pause");

	return 0;
}

3.7 list容器

3.7.1 list基本概念

功能： 將資料進行鏈式存盤

鏈表（list） 是一種物理存盤單元上非連續的存盤結構，資料元素的邏輯順序是通過鏈表中的指標鏈接實作的

鏈表的組成：鏈表由一系列結點組成

結點的組成：一個是存盤資料元素的資料域，另一個是存盤下一個結點地址的指標域

STL中的鏈表是一個雙向回圈鏈表（圖中并沒有畫出回圈）

由于鏈表的存盤方式并不是連續的記憶體空間，因此鏈表list中的迭代器只支持前移和后移，屬于雙向迭代器

list的優點：

• 采用動態存盤分配，不會造成記憶體浪費和溢位
• 鏈表執行插入和洗掉操作十分方便，修改指標即可，不需要移動大量元素

list的缺點：

• 鏈表靈活，但是空間(指標域) 和 時間（遍歷）額外耗費較大

List有一個重要的性質，插入操作和洗掉操作都不會造成原有list迭代器的失效，這在vector是不成立的，（因此后文中list的迭代器都是const_iterator只讀迭代器？這里不太懂）

總結：STL中List和vector是兩個最常被使用的容器，各有優缺點

3.7.2 list建構式

功能描述：創建list容器

函式原型：

• list<T> lst; //list采用采用模板類實作,物件的默認構造形式：
• list(beg,end); //建構式將[beg, end)區間中的元素拷貝給本身，
• list(n,elem); //建構式將n個elem拷貝給本身，
• list(const list &lst); //拷貝建構式，

示例：

#include <list>

void printList(const list<int>& L) {

	for (list<int>::const_iterator it = L.begin(); it != L.end(); it++) {
		cout << *it << " ";
	}
	cout << endl;
}

void test01()
{
	list<int>L1;
	L1.push_back(10);
	L1.push_back(20);
	L1.push_back(30);
	L1.push_back(40);

	printList(L1);

	list<int>L2(L1.begin(),L1.end());
	printList(L2);

	list<int>L3(L2);
	printList(L3);

	list<int>L4(10, 1000);
	printList(L4);
}

int main() {

	test01();

	system("pause");

	return 0;
}

3.7.3 list 賦值和交換

功能描述：給list容器進行賦值，以及交換list容器

函式原型：

• assign(beg, end); //將[beg, end)區間中的資料拷貝賦值給本身，
• assign(n, elem); //將n個elem拷貝賦值給本身，
• list& operator=(const list &lst); //多載等號運算子
• swap(lst); //將lst與本身的元素互換，

示例：

#include <list>

void printList(const list<int>& L) {

	for (list<int>::const_iterator it = L.begin(); it != L.end(); it++) {
		cout << *it << " ";
	}
	cout << endl;
}

//賦值和交換
void test01()
{
	list<int>L1;
	L1.push_back(10);
	L1.push_back(20);
	L1.push_back(30);
	L1.push_back(40);
	printList(L1);

	//賦值
	list<int>L2;
	L2 = L1;
	printList(L2);

	list<int>L3;
	L3.assign(L2.begin(), L2.end());
	printList(L3);

	list<int>L4;
	L4.assign(10, 100);
	printList(L4);

}

//交換
void test02()
{

	list<int>L1;
	L1.push_back(10);
	L1.push_back(20);
	L1.push_back(30);
	L1.push_back(40);

	list<int>L2;
	L2.assign(10, 100);

	cout << "交換前： " << endl;
	printList(L1);
	printList(L2);

	cout << endl;

	L1.swap(L2);

	cout << "交換后： " << endl;
	printList(L1);
	printList(L2);

}

int main() {

	//test01();

	test02();

	system("pause");

	return 0;
}

3.7.4 list 大小操作

功能描述：對list容器的大小進行操作
函式原型：

• size(); //回傳容器中元素的個數
• empty(); //判斷容器是否為空
• resize(num); //重新指定容器的長度為num，若容器變長，則以默認值填充新位置，
  ? //如果容器變短，則末尾超出容器長度的元素被洗掉，
• resize(num, elem); //重新指定容器的長度為num，若容器變長，則以elem值填充新位置，
  //如果容器變短，則末尾超出容器長度的元素被洗掉，

示例：

#include <list>

void printList(const list<int>& L) {

	for (list<int>::const_iterator it = L.begin(); it != L.end(); it++) {
		cout << *it << " ";
	}
	cout << endl;
}

//大小操作
void test01()
{
	list<int>L1;
	L1.push_back(10);
	L1.push_back(20);
	L1.push_back(30);
	L1.push_back(40);

	if (L1.empty())
	{
		cout << "L1為空" << endl;
	}
	else
	{
		cout << "L1不為空" << endl;
		cout << "L1的大小為： " << L1.size() << endl;
	}

	//重新指定大小
	L1.resize(10);
	printList(L1);

	L1.resize(2);
	printList(L1);
}

int main() {

	test01();

	system("pause");

	return 0;
}

3.7.5 list 插入和洗掉
功能描述：

對list容器進行資料的插入和洗掉
函式原型：

• push_back(elem);//在容器尾部加入一個元素
• pop_back();//洗掉容器中最后一個元素
• push_front(elem);//在容器開頭插入一個元素
• 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位置的資料，回傳下一個資料的位置，
• remove(elem);//洗掉容器中所有與elem值匹配的元素，

示例：

#include <list>

void printList(const list<int>& L) {

	for (list<int>::const_iterator it = L.begin(); it != L.end(); it++) {
		cout << *it << " ";
	}
	cout << endl;
}

//插入和洗掉
void test01()
{
	list<int> L;
	//尾插
	L.push_back(10);
	L.push_back(20);
	L.push_back(30);
	//頭插
	L.push_front(100);
	L.push_front(200);
	L.push_front(300);

	printList(L);

	//尾刪
	L.pop_back();
	printList(L);

	//頭刪
	L.pop_front();
	printList(L);

	//插入
	list<int>::iterator it = L.begin();
	L.insert(++it, 1000);
	printList(L);

	//洗掉
	it = L.begin();
	L.erase(++it);
	printList(L);

	//移除
	L.push_back(10000);
	L.push_back(10000);
	L.push_back(10000);
	printList(L);
	L.remove(10000);
	printList(L);
    
    //清空
	L.clear();
	printList(L);
}

int main() {

	test01();

	system("pause");

	return 0;
}

3.7.6 list 資料存取

功能描述：對list容器中資料進行存取

函式原型：

• front(); //回傳第一個元素，
• back(); //回傳最后一個元素，

示例：

#include <list>

//資料存取
void test01()
{
	list<int>L1;
	L1.push_back(10);
	L1.push_back(20);
	L1.push_back(30);
	L1.push_back(40);

	
	//cout << L1.at(0) << endl;//錯誤 不支持at訪問資料
	//cout << L1[0] << endl; //錯誤  不支持[]方式訪問資料
	cout << "第一個元素為： " << L1.front() << endl;
	cout << "最后一個元素為： " << L1.back() << endl;

	//list容器的迭代器是雙向迭代器，不支持隨機訪問
	list<int>::iterator it = L1.begin();
	//it = it + 1;//錯誤，不可以跳躍訪問，即使是+1
}

int main() {

	test01();

	system("pause");

	return 0;
}

總結：list容器中不可以通過[]或者at方式訪問資料

3.7.7 list 反轉和排序

功能描述：將容器中的元素反轉，以及將容器中的資料進行排序

函式原型：

reverse(); //反轉鏈表
sort(); //鏈表排序

示例：

void printList(const list<int>& L) {

	for (list<int>::const_iterator it = L.begin(); it != L.end(); it++) {
		cout << *it << " ";
	}
	cout << endl;
}

bool myCompare(int val1 , int val2)
{
	return val1 > val2;
}

//反轉和排序
void test01()
{
	list<int> L;
	L.push_back(90);
	L.push_back(30);
	L.push_back(20);
	L.push_back(70);
	printList(L);

	//反轉容器的元素
	L.reverse();
	printList(L);

	//排序
	L.sort(); //默認的排序規則 從小到大
	printList(L);

	L.sort(myCompare); //指定規則，從大到小
	printList(L);
}

int main() {

	test01();

	system("pause");

	return 0;
}

3.7.8 排序案例

案例描述：將Person自定義資料型別進行排序，Person中屬性有姓名、年齡、身高

排序規則：按照年齡進行升序，如果年齡相同按照身高進行降序

示例：

#include <list>
#include <string>
class Person {
public:
	Person(string name, int age , int height) {
		m_Name = name;
		m_Age = age;
		m_Height = height;
	}

public:
	string m_Name;  //姓名
	int m_Age;      //年齡
	int m_Height;   //身高
};


bool ComparePerson(Person& p1, Person& p2) {

	if (p1.m_Age == p2.m_Age) {
		return p1.m_Height  > p2.m_Height;
	}
	else
	{
		return  p1.m_Age < p2.m_Age;
	}

}

void test01() {

	list<Person> L;

	Person p1("劉備", 35 , 175);
	Person p2("曹操", 45 , 180);
	Person p3("孫權", 40 , 170);
	Person p4("趙云", 25 , 190);
	Person p5("張飛", 35 , 160);
	Person p6("關羽", 35 , 200);

	L.push_back(p1);
	L.push_back(p2);
	L.push_back(p3);
	L.push_back(p4);
	L.push_back(p5);
	L.push_back(p6);

	for (list<Person>::iterator it = L.begin(); it != L.end(); it++) {
		cout << "姓名： " << it->m_Name << " 年齡： " << it->m_Age 
              << " 身高： " << it->m_Height << endl;
	}

	cout << "---------------------------------" << endl;
	L.sort(ComparePerson); //排序

	for (list<Person>::iterator it = L.begin(); it != L.end(); it++) {
		cout << "姓名： " << it->m_Name << " 年齡： " << it->m_Age 
              << " 身高： " << it->m_Height << endl;
	}
}

int main() {

	test01();

	system("pause");

	return 0;
}

總結：

• 對于自定義資料型別，必須要指定排序規則，否則編譯器不知道如何進行排序
• 高級排序只是在排序規則上再進行一次邏輯規則制定，并不復雜

3.8 set/ multiset 容器

3.8.1 set基本概念

簡介：所有元素都會在插入時自動被排序

本質：set/multiset屬于關聯式容器，底層結構是用二叉樹實作，

set和multiset區別：

• set不允許容器中有重復的元素
• multiset允許容器中有重復的元素

3.8.2 set構造和賦值

功能描述：創建set容器以及賦值

構造：

• set<T> st; //默認建構式：
• set(const set &st); //拷貝建構式

賦值：

• set& operator=(const set &st); //多載等號操作

示例：

#include <set>

void printSet(set<int> & s)
{
	for (set<int>::iterator it = s.begin(); it != s.end(); it++)
	{
		cout << *it << " ";
	}
	cout << endl;
}

//構造和賦值
void test01()
{
	set<int> s1;

	s1.insert(10);
	s1.insert(30);
	s1.insert(20);
	s1.insert(40);
	printSet(s1);

	//拷貝構造
	set<int>s2(s1);
	printSet(s2);

	//賦值
	set<int>s3;
	s3 = s2;
	printSet(s3);
}

int main() {

	test01();

	system("pause");

	return 0;
}

總結：

• set容器插入資料時用insert
• set容器插入資料的資料會自動排序

3.8.3 set大小和交換

功能描述：統計set容器大小以及交換set容器

函式原型：

• size(); //回傳容器中元素的數目
• empty(); //判斷容器是否為空
• swap(st); //交換兩個集合容器

示例：

#include <set>

void printSet(set<int> & s)
{
	for (set<int>::iterator it = s.begin(); it != s.end(); it++)
	{
		cout << *it << " ";
	}
	cout << endl;
}

//大小
void test01()
{

	set<int> s1;
	
	s1.insert(10);
	s1.insert(30);
	s1.insert(20);
	s1.insert(40);

	if (s1.empty())
	{
		cout << "s1為空" << endl;
	}
	else
	{
		cout << "s1不為空" << endl;
		cout << "s1的大小為： " << s1.size() << endl;
	}

}

//交換
void test02()
{
	set<int> s1;

	s1.insert(10);
	s1.insert(30);
	s1.insert(20);
	s1.insert(40);

	set<int> s2;

	s2.insert(100);
	s2.insert(300);
	s2.insert(200);
	s2.insert(400);

	cout << "交換前" << endl;
	printSet(s1);
	printSet(s2);
	cout << endl;

	cout << "交換后" << endl;
	s1.swap(s2);
	printSet(s1);
	printSet(s2);
}

int main() {

	//test01();

	test02();

	system("pause");

	return 0;
}

3.8.4 set插入和洗掉

功能描述：set容器進行插入資料和洗掉資料
函式原型：

• insert(elem); //在容器中插入元素，
• clear(); //清除所有元素
• erase(pos); //洗掉pos迭代器所指的元素，回傳下一個元素的迭代器，
• erase(beg, end); //洗掉區間[beg,end)的所有元素 ，回傳下一個元素的迭代器，
• erase(elem); //洗掉容器中值為elem的元素，

示例：

#include <set>

void printSet(set<int> & s)
{
	for (set<int>::iterator it = s.begin(); it != s.end(); it++)
	{
		cout << *it << " ";
	}
	cout << endl;
}

//插入和洗掉
void test01()
{
	set<int> s1;
	//插入
	s1.insert(10);
	s1.insert(30);
	s1.insert(20);
	s1.insert(40);
	printSet(s1);

	//洗掉
	s1.erase(s1.begin());
	printSet(s1);

	s1.erase(30);
	printSet(s1);

	//清空
	//s1.erase(s1.begin(), s1.end());
	s1.clear();
	printSet(s1);
}

int main() {

	test01();

	system("pause");

	return 0;
}

3.8.5 set查找和統計

功能描述：對set容器進行查找資料以及統計資料
函式原型：

• find(key); //查找key是否存在,若存在，回傳該鍵的元素的迭代器；若不存在，回傳set.end();
• count(key); //統計key的元素個數

示例：

#include <set>

//查找和統計
void test01()
{
	set<int> s1;
	//插入
	s1.insert(10);
	s1.insert(30);
	s1.insert(20);
	s1.insert(40);
	
	//查找
	set<int>::iterator pos = s1.find(30);

	if (pos != s1.end())
	{
		cout << "找到了元素 ： " << *pos << endl;
	}
	else
	{
		cout << "未找到元素" << endl;
	}

	//統計
	int num = s1.count(30);
	cout << "num = " << num << endl;
}

int main() {

	test01();

	system("pause");

	return 0;
}

3.8.6 set和multiset區別

學習目標：掌握set和multiset的區別
區別：

• set不可以插入重復資料，而multiset可以
• set插入資料的同時會回傳插入結果，表示插入是否成功
• multiset不會檢測資料，因此可以插入重復資料

示例：

#include <set>

//set和multiset區別
void test01()
{
	set<int> s;
	pair<set<int>::iterator, bool>  ret = s.insert(10);
	if (ret.second) {
		cout << "第一次插入成功!" << endl;
	}
	else {
		cout << "第一次插入失敗!" << endl;
	}

	ret = s.insert(10);
	if (ret.second) {
		cout << "第二次插入成功!" << endl;
	}
	else {
		cout << "第二次插入失敗!" << endl;
	}
    
	//multiset
	multiset<int> ms;
	ms.insert(10);
	ms.insert(10);

	for (multiset<int>::iterator it = ms.begin(); it != ms.end(); it++) {
		cout << *it << " ";
	}
	cout << endl;
}

int main() {

	test01();

	system("pause");

	return 0;
}

3.8.7 pair對組創建

功能描述：成對出現的資料，利用對組可以回傳兩個資料

兩種創建方式：

• pair<type, type> p ( value1, value2 );
• pair<type, type> p = make_pair( value1, value2 );

示例：

#include <string>

//對組創建
void test01()
{
	pair<string, int> p(string("Tom"), 20);
	cout << "姓名： " <<  p.first << " 年齡： " << p.second << endl;

	pair<string, int> p2 = make_pair("Jerry", 10);
	cout << "姓名： " << p2.first << " 年齡： " << p2.second << endl;
}

int main() {

	test01();

	system("pause");

	return 0;
}

3.8.8 set容器排序

學習目標：set容器默認排序規則為從小到大，掌握如何改變排序規則

主要技術點：利用仿函式，可以改變排序規則

示例一 set存放內置資料型別

#include <set>

class MyCompare 
{
public:
	bool operator()(int v1, int v2) {
		return v1 > v2;
	}
};
void test01() 
{    
	set<int> s1;
	s1.insert(10);
	s1.insert(40);
	s1.insert(20);
	s1.insert(30);
	s1.insert(50);

	//默認從小到大
	for (set<int>::iterator it = s1.begin(); it != s1.end(); it++) {
		cout << *it << " ";
	}
	cout << endl;

	//指定排序規則
	set<int,MyCompare> s2;
	s2.insert(10);
	s2.insert(40);
	s2.insert(20);
	s2.insert(30);
	s2.insert(50);

	for (set<int, MyCompare>::iterator it = s2.begin(); it != s2.end(); it++) {
		cout << *it << " ";
	}
	cout << endl;
}

int main() {

	test01();

	system("pause");

	return 0;
}

示例二 set存放自定義資料型別

#include <set>
#include <string>

class Person
{
public:
	Person(string name, int age)
	{
		this->m_Name = name;
		this->m_Age = age;
	}

	string m_Name;
	int m_Age;

};
class comparePerson
{
public:
	bool operator()(const Person& p1, const Person &p2)
	{
		//按照年齡進行排序  降序
		return p1.m_Age > p2.m_Age;
	}
};

void test01()
{
	set<Person, comparePerson> s;

	Person p1("劉備", 23);
	Person p2("關羽", 27);
	Person p3("張飛", 25);
	Person p4("趙云", 21);

	s.insert(p1);
	s.insert(p2);
	s.insert(p3);
	s.insert(p4);

	for (set<Person, comparePerson>::iterator it = s.begin(); it != s.end(); it++)
	{
		cout << "姓名： " << it->m_Name << " 年齡： " << it->m_Age << endl;
	}
}
int main() {

	test01();

	system("pause");

	return 0;
}

總結：對于自定義資料型別，set必須指定排序規則才可以插入資料

3.9 map/ multimap容器

3.9.1 map基本概念

簡介：

• map中所有元素都是pair
• pair中第一個元素為key（鍵值），起到索引作用，第二個元素為value（實值）
• 所有元素都會根據元素的鍵值自動排序

本質：map/multimap屬于關聯式容器，底層結構是用二叉樹實作，

優點：可以根據key值快速找到value值

map和multimap區別：

• map不允許容器中有重復key值元素
• multimap允許容器中有重復key值元素

3.9.2 map構造和賦值

功能描述：對map容器進行構造和賦值操作

函式原型：

構造：

• map<T1, T2> mp; //map默認建構式:
• map(const map &mp); //拷貝建構式

賦值：

• map& operator=(const map &mp); //多載等號運算子

示例：

#include <map>

void printMap(map<int,int>&m)
{
	for (map<int, int>::iterator it = m.begin(); it != m.end(); it++)
	{
		cout << "key = " << it->first << " value = " << it->second << endl;
	}
	cout << endl;
}

void test01()
{
	map<int,int>m; //默認構造
	m.insert(pair<int, int>(1, 10));
	m.insert(pair<int, int>(2, 20));
	m.insert(pair<int, int>(3, 30));
	printMap(m);

	map<int, int>m2(m); //拷貝構造
	printMap(m2);

	map<int, int>m3;
	m3 = m2; //賦值
	printMap(m3);
}

int main() {

	test01();

	system("pause");

	return 0;
}

總結：map中所有元素都是成對出現，插入資料時候要使用對組

3.9.3 map大小和交換

功能描述：統計map容器大小以及交換map容器

函式原型：

• size(); //回傳容器中元素的數目
• empty(); //判斷容器是否為空
• swap(st); //交換兩個集合容器

示例：

#include <map>

void printMap(map<int,int>&m)
{
	for (map<int, int>::iterator it = m.begin(); it != m.end(); it++)
	{
		cout << "key = " << it->first << " value = " << it->second << endl;
	}
	cout << endl;
}

void test01()
{
	map<int, int>m;
	m.insert(pair<int, int>(1, 10));
	m.insert(pair<int, int>(2, 20));
	m.insert(pair<int, int>(3, 30));

	if (m.empty())
	{
		cout << "m為空" << endl;
	}
	else
	{
		cout << "m不為空" << endl;
		cout << "m的大小為： " << m.size() << endl;
	}
}


//交換
void test02()
{
	map<int, int>m;
	m.insert(pair<int, int>(1, 10));
	m.insert(pair<int, int>(2, 20));
	m.insert(pair<int, int>(3, 30));

	map<int, int>m2;
	m2.insert(pair<int, int>(4, 100));
	m2.insert(pair<int, int>(5, 200));
	m2.insert(pair<int, int>(6, 300));

	cout << "交換前" << endl;
	printMap(m);
	printMap(m2);

	cout << "交換后" << endl;
	m.swap(m2);
	printMap(m);
	printMap(m2);
}

int main() {

	test01();

	test02();

	system("pause");

	return 0;
}

3.9.4 map插入和洗掉

功能描述：map容器進行插入資料和洗掉資料

函式原型：

• insert(elem); //在容器中插入元素，
• clear(); //清除所有元素
• erase(pos); //洗掉pos迭代器所指的元素，回傳下一個元素的迭代器，
• erase(beg, end); //洗掉區間[beg,end)的所有元素 ，回傳下一個元素的迭代器，
• erase(key); //洗掉容器中值為key的元素，

示例：

#include <map>

void printMap(map<int,int>&m)
{
	for (map<int, int>::iterator it = m.begin(); it != m.end(); it++)
	{
		cout << "key = " << it->first << " value = " << it->second << endl;
	}
	cout << endl;
}

void test01()
{
	//插入
	map<int, int> m;
	//第一種插入方式
	m.insert(pair<int, int>(1, 10));
	//第二種插入方式
	m.insert(make_pair(2, 20));
	//第三種插入方式
	m.insert(map<int, int>::value_type(3, 30));
	//第四種插入方式
	m[4] = 40; 
	printMap(m);

	//洗掉
	m.erase(m.begin());
	printMap(m);

	m.erase(3);
	printMap(m);

	//清空
	m.erase(m.begin(),m.end());
	m.clear();
	printMap(m);
}

int main() {

	test01();

	system("pause");

	return 0;
}

3.9.5 map查找和統計

功能描述：對map容器進行查找資料以及統計資料

函式原型：

• find(key); //查找key是否存在,若存在，回傳該鍵的元素的迭代器；若不存在，回傳set.end();
• count(key); //統計key的元素個數

示例：

#include <map>

//查找和統計
void test01()
{
	map<int, int>m; 
	m.insert(pair<int, int>(1, 10));
	m.insert(pair<int, int>(2, 20));
	m.insert(pair<int, int>(3, 30));

	//查找
	map<int, int>::iterator pos = m.find(3);

	if (pos != m.end())
	{
		cout << "找到了元素 key = " << (*pos).first << " value = " << (*pos).second << endl;
	}
	else
	{
		cout << "未找到元素" << endl;
	}

	//統計
	int num = m.count(3);
	cout << "num = " << num << endl;
}

int main() {

	test01();

	system("pause");

	return 0;
}

3.9.6 map容器排序

學習目標：map容器默認排序規則為 按照key值進行 從小到大排序，掌握如何改變排序規則

主要技術點：利用仿函式，可以改變排序規則

示例：

#include <map>

class MyCompare {
public:
	bool operator()(int v1, int v2) {
		return v1 > v2;
	}
};

void test01() 
{
	//默認從小到大排序
	//利用仿函式實作從大到小排序
	map<int, int, MyCompare> m;

	m.insert(make_pair(1, 10));
	m.insert(make_pair(2, 20));
	m.insert(make_pair(3, 30));
	m.insert(make_pair(4, 40));
	m.insert(make_pair(5, 50));

	for (map<int, int, MyCompare>::iterator it = m.begin(); it != m.end(); it++) {
		cout << "key:" << it->first << " value:" << it->second << endl;
	}
}
int main() {

	test01();

	system("pause");

	return 0;
}

總結：

• 利用仿函式可以指定map容器的排序規則
• 對于自定義資料型別，map必須要指定排序規則,同set容器

3.10 案例-員工分組

3.10.1 案例描述

• 公司今天招聘了10個員工（ABCDEFGHIJ），10名員工進入公司之后，需要指派員工在哪個部門作業
• 員工資訊有: 姓名 工資組成；部門分為：策劃、美術、研發
• 隨機給10名員工分配部門和工資
• 通過multimap進行資訊的插入 key(部門編號) value(員工)
• 分部門顯示員工資訊

3.10.2 實作步驟

• 創建10名員工，放到vector中
• 遍歷vector容器，取出每個員工，進行隨機分組
• 分組后，將員工部門編號作為key，具體員作業為value，放入到multimap容器中
• 分部門顯示員工資訊

案例代碼：

#include<iostream>
using namespace std;
#include <vector>
#include <string>
#include <map>
#include <ctime>

/*
- 公司今天招聘了10個員工（ABCDEFGHIJ），10名員工進入公司之后，需要指派員工在那個部門作業
- 員工資訊有: 姓名  工資組成；部門分為：策劃、美術、研發
- 隨機給10名員工分配部門和工資
- 通過multimap進行資訊的插入  key(部門編號) value(員工)
- 分部門顯示員工資訊
*/

#define CEHUA  0
#define MEISHU 1
#define YANFA  2

class Worker
{
public:
	string m_Name;
	int m_Salary;
};

void createWorker(vector<Worker>&v)
{
	string nameSeed = "ABCDEFGHIJ";
	for (int i = 0; i < 10; i++)
	{
		Worker worker;
		worker.m_Name = "員工";
		worker.m_Name += nameSeed[i];

		worker.m_Salary = rand() % 10000 + 10000; // 10000 ~ 19999
		//將員工放入到容器中
		v.push_back(worker);
	}
}

//員工分組
void setGroup(vector<Worker>&v,multimap<int,Worker>&m)
{
	for (vector<Worker>::iterator it = v.begin(); it != v.end(); it++)
	{
		//產生隨機部門編號
		int deptId = rand() % 3; // 0 1 2 

		//將員工插入到分組中
		//key部門編號，value具體員工
		m.insert(make_pair(deptId, *it));
	}
}

void showWorkerByGourp(multimap<int,Worker>&m)
{
	// 0  A  B  C   1  D  E   2  F G ...
	cout << "策劃部門：" << endl;

	multimap<int,Worker>::iterator pos = m.find(CEHUA);
	int count = m.count(CEHUA); // 統計具體人數
	int index = 0;
	for (; pos != m.end() && index < count; pos++ , index++)
	{
		cout << "姓名： " << pos->second.m_Name << " 工資： " << pos->second.m_Salary << endl;
	}

	cout << "----------------------" << endl;
	cout << "美術部門： " << endl;
	pos = m.find(MEISHU);
	count = m.count(MEISHU); // 統計具體人數
	index = 0;
	for (; pos != m.end() && index < count; pos++, index++)
	{
		cout << "姓名： " << pos->second.m_Name << " 工資： " << pos->second.m_Salary << endl;
	}

	cout << "----------------------" << endl;
	cout << "研發部門： " << endl;
	pos = m.find(YANFA);
	count = m.count(YANFA); // 統計具體人數
	index = 0;
	for (; pos != m.end() && index < count; pos++, index++)
	{
		cout << "姓名： " << pos->second.m_Name << " 工資： " << pos->second.m_Salary << endl;
	}

}

int main() {

	srand((unsigned int)time(NULL));

	//1、創建員工
	vector<Worker>vWorker;
	createWorker(vWorker);

	//2、員工分組
	multimap<int, Worker>mWorker;
	setGroup(vWorker, mWorker);


	//3、分組顯示員工
	showWorkerByGourp(mWorker);

	測驗
	//for (vector<Worker>::iterator it = vWorker.begin(); it != vWorker.end(); it++)
	//{
	//	cout << "姓名： " << it->m_Name << " 工資： " << it->m_Salary << endl;
	//}

	system("pause");

	return 0;
}

我的代碼：

#include<iostream>
using namespace std;
/*公司今天招聘了10個員工（ABCDEFGHIJ），10名員工進入公司之后，需要指派員工在哪個部門作業
員工資訊有 : 姓名 工資組成；部門分為：策劃、美術、研發
隨機給10名員工分配部門和工資
通過multimap進行資訊的插入 key(部門編號) value(員工)
分部門顯示員工資訊*/
/*
思路：
創建10名員工用vector存盤
遍歷vector，給每個員工隨機分配部門和工資
通過multimap進行資訊的插入 key(部門編號) value(員工)
分部門顯示員工資訊
*/
#include<string>
#include <vector>
#include <stdlib.h>
#include <ctime>
#include <map>

#define CHEHUA 0
#define MEISHU 1
#define YANFA 2
//員工類
class Employee {
public:
	string m_name;
	int m_salary;
};
//創建員工
void creatEmployee(vector<Employee>& v) {
	string name = "ABCDEFGHIJ";
	for (int i = 0; i < 10 ; i ++) {
		Employee employee;
		employee.m_name = name[i];
		employee.m_salary = rand() % 1000 + 1000;
		v.push_back(employee);
	}
	//測驗員工是否添加成功
	//for (vector<Employee>::iterator it = v.begin(); it != v.end(); it++) {
	//	cout << "員工姓名：" << it->m_name << ",員工工資：" << it->m_salary<< endl;
	//}
}

//給員工分配部門
void setDeptno(vector<Employee>& v, multimap<int, Employee>& m) {
	int deptno;
	for (vector<Employee>::iterator it = v.begin(); it != v.end(); it++) {
		deptno = rand() % 3;
		m.insert(make_pair(deptno, *it));
	}
	//測驗部門是否分配成功
	//for (multimap<int, Employee>::iterator it = m.begin(); it != m.end(); it++) {
	//	cout << "key=" << it->first << ",value=" << (it->second).m_name << endl;
	//}
}

//分部門顯示員工資訊
void showInfo(multimap<int, Employee> m) {
	cout << "策劃部門：" << endl;
	multimap<int, Employee>::iterator pos = m.find(CHEHUA);//查找函式回傳的是迭代器
	int count = m.count(CHEHUA);
	for (; pos != m.end(), count > 0; pos++, count--) {
		cout << "員工姓名：" << (pos->second).m_name << ",員工工資：" << (pos->second).m_salary << endl;
	}
	cout << "----------------------------" << endl;

	cout << "美術部門：" << endl;
	pos = m.find(MEISHU);
	count = m.count(MEISHU);
	for (; pos != m.end(), count > 0; pos++, count--) {
		cout << "員工姓名：" << (pos->second).m_name << ",員工工資：" << (pos->second).m_salary << endl;
	}
	cout << "----------------------------" << endl;

	cout << "研發部門：" << endl;
	pos = m.find(YANFA);
	count = m.count(YANFA);
	for (; pos != m.end(), count > 0; pos++, count--) {
		cout << "員工姓名：" << (pos->second).m_name << ",員工工資：" << (pos->second).m_salary << endl;
	}
}
int main() {
	//亂數種子
	//rand的亂數種子默認為1，如果不用srand來初始化亂數種子，每次隨機出來的數都是一樣的
	srand((unsigned int)time(NULL));
	//創建員工vector
	vector<Employee> v;
	creatEmployee(v);
	//分配部門
	multimap<int, Employee> m;
	setDeptno(v, m);
	
	showInfo(m);
	return 0;
}

學到的知識：
1.不同的功能用不同的函式實作，代碼間耦合度低；每寫完一個功能要測驗一下
2.rand()和srand()要一起使用，其中srand()用來初始化亂數種子,rand()用來產生亂數， 參考鏈接
3.find函式回傳的是指向該元素的迭代器

4 STL - 函式物件

4.1 函式物件

4.1.1 函式物件概念

概念：

• 多載函式呼叫運算子的類，其物件常稱為函式物件
• 函式物件使用多載的()時，行為類似函式呼叫，也叫仿函式

本質：函式物件(仿函式)是一個類，不是一個函式

4.1.2 函式物件使用

特點：

• 函式物件在使用時，可以像普通函式那樣呼叫, 可以有引數，可以有回傳值
• 函式物件超出普通函式的概念，函式物件可以有自己的狀態
• 函式物件可以作為引數傳遞

示例:

#include <string>

//1、函式物件在使用時，可以像普通函式那樣呼叫, 可以有引數，可以有回傳值
class MyAdd
{
public :
	int operator()(int v1,int v2)
	{
		return v1 + v2;
	}
};

void test01()
{
	MyAdd myAdd;
	cout << myAdd(10, 10) << endl;
}

//2、函式物件可以有自己的狀態
class MyPrint
{
public:
	MyPrint()
	{
		count = 0;
	}
	void operator()(string test)
	{
		cout << test << endl;
		count++; //統計使用次數
	}

	int count; //內部自己的狀態
};
void test02()
{
	MyPrint myPrint;
	myPrint("hello world");
	myPrint("hello world");
	myPrint("hello world");
	cout << "myPrint呼叫次數為： " << myPrint.count << endl;
}

//3、函式物件可以作為引數傳遞
void doPrint(MyPrint &mp , string test)
{
	mp(test);
}

void test03()
{
	MyPrint myPrint;
	doPrint(myPrint, "Hello C++");
}

int main() {

	//test01();
	//test02();
	test03();

	system("pause");

	return 0;
}

總結：創建一個類，在類里面多載小括號回傳型別 operator()(引數串列)，該類的實體化物件稱為函式物件，函式物件可以有引數和回傳值，可以有自己的狀態，可以作為引數傳遞，

4.2 謂詞

4.2.1 謂詞概念

概念：

• 回傳bool型別的仿函式稱為謂詞
• 如果operator()接受一個引數，那么叫做一元謂詞
• 如果operator()接受兩個引數，那么叫做二元謂詞

4.2.2 一元謂詞

示例：

#include <vector>
#include <algorithm>

//1.一元謂詞
class GreaterFive{
	bool operator()(int val) {
		return val > 5;
	}
};

void test01() {

	vector<int> v;
	for (int i = 0; i < 10; i++)
	{
		v.push_back(i);
	}
	//GreaterFive():匿名函式物件（實體化的右半部分：GreaterFive a = GreaterFive()
	vector<int>::iterator it = find_if(v.begin(), v.end(), GreaterFive());//第三個引數是謂詞
	if (it == v.end()) {
		cout << "沒找到!" << endl;
	}
	else {
		cout << "找到:" << *it << endl;
	}

}

int main() {

	test01();

	system("pause");

	return 0;
}

4.2.3 二元謂詞

示例：

#include <vector>
#include <algorithm>
//二元謂詞
class MyCompare
{
public:
	bool operator()(int num1, int num2)
	{
		return num1 > num2;
	}
};

void test01()
{
	vector<int> v;
	v.push_back(10);
	v.push_back(40);
	v.push_back(20);
	v.push_back(30);
	v.push_back(50);

	//默認從小到大
	sort(v.begin(), v.end());
	for (vector<int>::iterator it = v.begin(); it != v.end(); it++)
	{
		cout << *it << " ";
	}
	cout << endl;
	cout << "----------------------------" << endl;

	//使用函式物件改變演算法策略，排序從大到小
	sort(v.begin(), v.end(), MyCompare());
	for (vector<int>::iterator it = v.begin(); it != v.end(); it++)
	{
		cout << *it << " ";
	}
	cout << endl;
}

int main() {

	test01();

	system("pause");

	return 0;
}

4.3 內建函式物件

4.3.1 內建函式物件意義

概念：STL內建了一些函式物件

分類:

• 算術仿函式
• 關系仿函式
• 邏輯仿函式

用法：

• 這些仿函式所產生的物件，用法和一般函式完全相同
• 使用內建函式物件，需要引入頭檔案 #include<functional>

4.3.2 算術仿函式

功能描述：實作四則運算，其中negate是一元運算，其他都是二元運算

仿函式原型：

• template<class T> T plus<T> //加法仿函式
• template<class T> T minus<T> //減法仿函式
• template<class T> T multiplies<T> //乘法仿函式
• template<class T> T divides<T> //除法仿函式
• template<class T> T modulus<T> //取模仿函式
• template<class T> T negate<T> //取反仿函式

示例：

#include <functional>
//negate
void test01()
{
	negate<int> n;
	cout << n(50) << endl;
}

//plus
void test02()
{
	plus<int> p;
	cout << p(10, 20) << endl;
}

int main() {

	test01();
	test02();

	system("pause");

	return 0;
}

4.3.3 關系仿函式

功能描述：實作關系對比

仿函式原型：

• template<class T> bool equal_to<T> //等于
• template<class T> bool not_equal_to<T> //不等于
• template<class T> bool greater<T> //大于 - 最常用
• template<class T> bool greater_equal<T> //大于等于
• template<class T> bool less<T> //小于
• template<class T> bool less_equal<T> //小于等于

示例：

#include <functional>
#include <vector>
#include <algorithm>

class MyCompare
{
public:
	bool operator()(int v1,int v2)
	{
		return v1 > v2;
	}
};
void test01()
{
	vector<int> v;

	v.push_back(10);
	v.push_back(30);
	v.push_back(50);
	v.push_back(40);
	v.push_back(20);

	for (vector<int>::iterator it = v.begin(); it != v.end(); it++) {
		cout << *it << " ";
	}
	cout << endl;

	//自己實作仿函式
	//sort(v.begin(), v.end(), MyCompare());
	//STL內建仿函式  大于仿函式
	sort(v.begin(), v.end(), greater<int>());

	for (vector<int>::iterator it = v.begin(); it != v.end(); it++) {
		cout << *it << " ";
	}
	cout << endl;
}

int main() {

	test01();

	system("pause");

	return 0;
}

4.3.4 邏輯仿函式

功能描述：實作邏輯運算

函式原型：

• template<class T> bool logical_and<T> //邏輯與
• template<class T> bool logical_or<T> //邏輯或
• template<class T> bool logical_not<T> //邏輯非

示例：

#include <vector>
#include <functional>
#include <algorithm>
void test01()
{
	vector<bool> v;
	v.push_back(true);
	v.push_back(false);
	v.push_back(true);
	v.push_back(false);

	for (vector<bool>::iterator it = v.begin();it!= v.end();it++)
	{
		cout << *it << " ";
	}
	cout << endl;

	//邏輯非  將v容器搬運到v2中，并執行邏輯非運算
	vector<bool> v2;
	v2.resize(v.size());
	transform(v.begin(), v.end(),  v2.begin(), logical_not<bool>());
	for (vector<bool>::iterator it = v2.begin(); it != v2.end(); it++)
	{
		cout << *it << " ";
	}
	cout << endl;
}

int main() {

	test01();

	system("pause");

	return 0;
}

5 STL - 常用演算法

概述：

• 演算法主要是由頭檔案<algorithm> <functional> <numeric>組成，
• <algorithm>是所有STL頭檔案中最大的一個，范圍涉及到比較、 交換、查找、遍歷操作、復制、修改等等
• <numeric>體積很小，只包括幾個在序列上面進行簡單數學運算的模板函式
• <functional>定義了一些模板類,用以宣告函式物件，

5.1 常用遍歷演算法

學習目標：掌握常用的遍歷演算法

演算法簡介：

• for_each //遍歷容器
• transform //搬運容器到另一個容器中

5.1.1 for_each

功能描述：實作遍歷容器

函式原型：

• for_each(iterator beg, iterator end, _func);
  // 遍歷演算法 遍歷容器元素
  // beg 開始迭代器
  // end 結束迭代器
  // _func 函式或者函式物件

示例：

#include <algorithm>
#include <vector>

//普通函式
void print01(int val) 
{
	cout << val << " ";
}
//函式物件
class print02 
{
 public:
	void operator()(int val) 
	{
		cout << val << " ";
	}
};

//for_each演算法基本用法
void test01() {

	vector<int> v;
	for (int i = 0; i < 10; i++) 
	{
		v.push_back(i);
	}

	//遍歷演算法
	for_each(v.begin(), v.end(), print01);
	cout << endl;

	for_each(v.begin(), v.end(), print02());
	cout << endl;
}

int main() {

	test01();

	system("pause");

	return 0;
}

總結： for_each：傳入起始迭代器、終止迭代器和函式，遍歷一個元素就執行一次函式，在實際開發中是最常用遍歷演算法，需要熟練掌握

5.1.2 transform

功能描述：搬運容器到另一個容器中

函式原型：

• transform(iterator beg1, iterator end1, iterator beg2, _func);
  //beg1 源容器開始迭代器
  //end1 源容器結束迭代器
  //beg2 目標容器開始迭代器
  //_func 函式或者函式物件

示例：

#include<vector>
#include<algorithm>

//常用遍歷演算法  搬運 transform

class TransForm
{
public:
	int operator()(int val)
	{
		return val;
	}

};

class MyPrint
{
public:
	void operator()(int val)
	{
		cout << val << " ";
	}
};

void test01()
{
	vector<int>v;
	for (int i = 0; i < 10; i++)
	{
		v.push_back(i);
	}

	vector<int>vTarget; //目標容器

	vTarget.resize(v.size()); // 目標容器需要提前開辟空間

	transform(v.begin(), v.end(), vTarget.begin(), TransForm());

	for_each(vTarget.begin(), vTarget.end(), MyPrint());
}

int main() {

	test01();

	system("pause");

	return 0;
}

總結： 搬運的目標容器必須要提前開辟空間，否則無法正常搬運

5.2 常用查找演算法

學習目標：掌握常用的查找演算法

演算法簡介：

• find //查找元素
• find_if //按條件查找元素
• adjacent_find //查找相鄰重復元素
• binary_search //二分查找法
• count //統計元素個數
• count_if //按條件統計元素個數

5.2.1 find

功能描述：查找指定元素，找到回傳指定元素的迭代器，找不到回傳結束迭代器end()

函式原型：

• find(iterator beg, iterator end, value);
  // 按值查找元素，找到回傳指定位置迭代器，找不到回傳結束迭代器位置
  // beg 開始迭代器
  // end 結束迭代器
  // value 查找的元素

示例：

#include <algorithm>
#include <vector>
#include <string>
void test01() {

	vector<int> v;
	for (int i = 0; i < 10; i++) {
		v.push_back(i + 1);
	}
	//查找容器中是否有 5 這個元素
	vector<int>::iterator it = find(v.begin(), v.end(), 5);
	if (it == v.end()) 
	{
		cout << "沒有找到!" << endl;
	}
	else 
	{
		cout << "找到:" << *it << endl;
	}
}

class Person {
public:
	Person(string name, int age) 
	{
		this->m_Name = name;
		this->m_Age = age;
	}
	//多載==
	bool operator==(const Person& p) 
	{
		if (this->m_Name == p.m_Name && this->m_Age == p.m_Age) 
		{
			return true;
		}
		return false;
	}

public:
	string m_Name;
	int m_Age;
};

void test02() {

	vector<Person> v;

	//創建資料
	Person p1("aaa", 10);
	Person p2("bbb", 20);
	Person p3("ccc", 30);
	Person p4("ddd", 40);

	v.push_back(p1);
	v.push_back(p2);
	v.push_back(p3);
	v.push_back(p4);

	vector<Person>::iterator it = find(v.begin(), v.end(), p2);
	if (it == v.end()) 
	{
		cout << "沒有找到!" << endl;
	}
	else 
	{
		cout << "找到姓名:" << it->m_Name << " 年齡: " << it->m_Age << endl;
	}
}

總結： 利用find可以在容器中找指定的元素，回傳值是迭代器

5.2.2 find_if

功能描述：按條件查找元素

函式原型：

• find_if(iterator beg, iterator end, _Pred);
  // 按值查找元素，找到回傳指定位置迭代器，找不到回傳結束迭代器位置
  // beg 開始迭代器
  // end 結束迭代器
  // _Pred 函式或者謂詞（回傳bool型別的仿函式）

示例：

#include <algorithm>
#include <vector>
#include <string>

//內置資料型別
class GreaterFive
{
public:
	bool operator()(int val)
	{
		return val > 5;
	}
};

void test01() {

	vector<int> v;
	for (int i = 0; i < 10; i++) {
		v.push_back(i + 1);
	}

	vector<int>::iterator it = find_if(v.begin(), v.end(), GreaterFive());
	if (it == v.end()) {
		cout << "沒有找到!" << endl;
	}
	else {
		cout << "找到大于5的數字:" << *it << endl;
	}
}

//自定義資料型別
class Person {
public:
	Person(string name, int age)
	{
		this->m_Name = name;
		this->m_Age = age;
	}
public:
	string m_Name;
	int m_Age;
};

class Greater20
{
public:
	bool operator()(Person &p)
	{
		return p.m_Age > 20;
	}

};

void test02() {

	vector<Person> v;

	//創建資料
	Person p1("aaa", 10);
	Person p2("bbb", 20);
	Person p3("ccc", 30);
	Person p4("ddd", 40);

	v.push_back(p1);
	v.push_back(p2);
	v.push_back(p3);
	v.push_back(p4);

	vector<Person>::iterator it = find_if(v.begin(), v.end(), Greater20());
	if (it == v.end())
	{
		cout << "沒有找到!" << endl;
	}
	else
	{
		cout << "找到姓名:" << it->m_Name << " 年齡: " << it->m_Age << endl;
	}
}

int main() {

	//test01();

	test02();

	system("pause");

	return 0;
}

總結：find_if按條件查找使查找更加靈活，提供的仿函式可以改變不同的策略

5.2.3 adjacent_find

功能描述：查找相鄰重復元素

函式原型：

• adjacent_find(iterator beg, iterator end);
  // 查找相鄰重復元素,回傳相鄰元素的第一個位置的迭代器
  // beg 開始迭代器
  // end 結束迭代器

示例：

#include <algorithm>
#include <vector>

void test01()
{
	vector<int> v;
	v.push_back(1);
	v.push_back(2);
	v.push_back(5);
	v.push_back(2);
	v.push_back(4);
	v.push_back(4);
	v.push_back(3);

	//查找相鄰重復元素
	vector<int>::iterator it = adjacent_find(v.begin(), v.end());
	if (it == v.end()) {
		cout << "找不到!" << endl;
	}
	else {
		cout << "找到相鄰重復元素為:" << *it << endl;
	}
}

總結：面試題中如果出現查找相鄰重復元素，記得用STL中的adjacent_find演算法

5.2.4 binary_search

功能描述：查找指定元素是否存在

函式原型：

• bool binary_search(iterator beg, iterator end, value);
  // 查找指定的元素，查到 回傳true 否則false
  // 注意: 在無序序列中不可用
  // beg 開始迭代器
  // end 結束迭代器
  // value 查找的元素

示例：

#include <algorithm>
#include <vector>

void test01()
{
	vector<int>v;

	for (int i = 0; i < 10; i++)
	{
		v.push_back(i);
	}
	//二分查找
	bool ret = binary_search(v.begin(), v.end(),2);
	if (ret)
	{
		cout << "找到了" << endl;
	}
	else
	{
		cout << "未找到" << endl;
	}
}

int main() {

	test01();

	system("pause");

	return 0;
}

總結： 二分查找法查找效率很高，值得注意的是查找的容器中元素必須的有序序列

5.2.5 count

功能描述：統計元素個數

函式原型：

• count(iterator beg, iterator end, value);
  // 統計元素出現次數
  // beg 開始迭代器
  // end 結束迭代器
  // value 統計的元素

示例：

#include <algorithm>
#include <vector>

//內置資料型別
void test01()
{
	vector<int> v;
	v.push_back(1);
	v.push_back(2);
	v.push_back(4);
	v.push_back(5);
	v.push_back(3);
	v.push_back(4);
	v.push_back(4);

	int num = count(v.begin(), v.end(), 4);

	cout << "4的個數為： " << num << endl;
}

//自定義資料型別
class Person
{
public:
	Person(string name, int age)
	{
		this->m_Name = name;
		this->m_Age = age;
	}
	bool operator==(const Person & p)
	{
		if (this->m_Age == p.m_Age)
		{
			return true;
		}
		else
		{
			return false;
		}
	}
	string m_Name;
	int m_Age;
};

void test02()
{
	vector<Person> v;

	Person p1("劉備", 35);
	Person p2("關羽", 35);
	Person p3("張飛", 35);
	Person p4("趙云", 30);
	Person p5("曹操", 25);

	v.push_back(p1);
	v.push_back(p2);
	v.push_back(p3);
	v.push_back(p4);
	v.push_back(p5);
    
    Person p("諸葛亮",35);

	int num = count(v.begin(), v.end(), p);
	cout << "num = " << num << endl;
}
int main() {

	//test01();

	test02();

	system("pause");

	return 0;
}

總結： 統計自定義資料型別時候，需要配合多載 operator==

5.2.6 count_if

功能描述：按條件統計元素個數

函式原型：

• count_if(iterator beg, iterator end, _Pred);
  // 按條件統計元素出現次數
  // beg 開始迭代器
  // end 結束迭代器
  // _Pred 謂詞

示例：

#include <algorithm>
#include <vector>

class Greater4
{
public:
	bool operator()(int val)
	{
		return val >= 4;
	}
};

//內置資料型別
void test01()
{
	vector<int> v;
	v.push_back(1);
	v.push_back(2);
	v.push_back(4);
	v.push_back(5);
	v.push_back(3);
	v.push_back(4);
	v.push_back(4);

	int num = count_if(v.begin(), v.end(), Greater4());

	cout << "大于4的個數為： " << num << endl;
}

//自定義資料型別
class Person
{
public:
	Person(string name, int age)
	{
		this->m_Name = name;
		this->m_Age = age;
	}

	string m_Name;
	int m_Age;
};

class AgeLess35
{
public:
	bool operator()(const Person &p)
	{
		return p.m_Age < 35;
	}
};
void test02()
{
	vector<Person> v;

	Person p1("劉備", 35);
	Person p2("關羽", 35);
	Person p3("張飛", 35);
	Person p4("趙云", 30);
	Person p5("曹操", 25);

	v.push_back(p1);
	v.push_back(p2);
	v.push_back(p3);
	v.push_back(p4);
	v.push_back(p5);

	int num = count_if(v.begin(), v.end(), AgeLess35());
	cout << "小于35歲的個數：" << num << endl;
}


int main() {

	//test01();

	test02();

	system("pause");

	return 0;
}

總結： 按值統計用count，按條件統計用count_if

5.3 常用排序演算法

學習目標：掌握常用的排序演算法

演算法簡介：

• sort //對容器內元素進行排序
• random_shuffle //洗牌 指定范圍內的元素隨機調整次序
• merge // 容器元素合并，并存盤到另一容器中
• reverse // 反轉指定范圍的元素

5.3.1 sort

功能描述：對容器內元素進行排序

函式原型：

• sort(iterator beg, iterator end, _Pred);
  // 按值查找元素，找到回傳指定位置迭代器，找不到回傳結束迭代器位置
  // beg 開始迭代器
  // end 結束迭代器
  // _Pred 謂詞

示例：

#include <algorithm>
#include <vector>

void myPrint(int val)
{
	cout << val << " ";
}

void test01() {
	vector<int> v;
	v.push_back(10);
	v.push_back(30);
	v.push_back(50);
	v.push_back(20);
	v.push_back(40);

	//sort默認從小到大排序
	sort(v.begin(), v.end());
	for_each(v.begin(), v.end(), myPrint);
	cout << endl;

	//從大到小排序
	sort(v.begin(), v.end(), greater<int>());
	for_each(v.begin(), v.end(), myPrint);
	cout << endl;
}

int main() {

	test01();

	system("pause");

	return 0;
}

總結： sort屬于開發中最常用的演算法之一，需熟練掌握

5.3.2 random_shuffle

功能描述：洗牌 指定范圍內的元素隨機調整次序

函式原型：

• random_shuffle(iterator beg, iterator end);
  // 指定范圍內的元素隨機調整次序
  // beg 開始迭代器
  // end 結束迭代器

示例：

#include <algorithm>
#include <vector>
#include <ctime>

class myPrint
{
public:
	void operator()(int val)
	{
		cout << val << " ";
	}
};

void test01()
{
	srand((unsigned int)time(NULL));
	vector<int> v;
	for(int i = 0 ; i < 10;i++)
	{
		v.push_back(i);
	}
	for_each(v.begin(), v.end(), myPrint());
	cout << endl;

	//打亂順序
	random_shuffle(v.begin(), v.end());
	for_each(v.begin(), v.end(), myPrint());
	cout << endl;
}

int main() {

	test01();

	system("pause");

	return 0;
}

總結： random_shuffle洗牌演算法比較實用，使用時記得加亂數種子

5.3.3 merge

功能描述：兩個容器元素合并，并存盤到另一容器中

函式原型：

• merge(iterator beg1, iterator end1, iterator beg2, iterator end2, iterator dest);
  // 容器元素合并，并存盤到另一容器中
  // 注意: 兩個容器必須是有序的
  // beg1 容器1開始迭代器
  // end1 容器1結束迭代器
  // beg2 容器2開始迭代器
  // end2 容器2結束迭代器
  // dest 目標容器開始迭代器

示例：

#include <algorithm>
#include <vector>

class myPrint
{
public:
	void operator()(int val)
	{
		cout << val << " ";
	}
};

void test01()
{
	vector<int> v1;
	vector<int> v2;
	for (int i = 0; i < 10 ; i++) 
    {
		v1.push_back(i);
		v2.push_back(i + 1);
	}

	vector<int> vtarget;
	//目標容器需要提前開辟空間
	vtarget.resize(v1.size() + v2.size());
	//合并  需要兩個有序序列
	merge(v1.begin(), v1.end(), v2.begin(), v2.end(), vtarget.begin());
	for_each(vtarget.begin(), vtarget.end(), myPrint());
	cout << endl;
}

int main() {

	test01();

	system("pause");

	return 0;
}

總結： merge合并的兩個容器必須的有序序列

5.3.4 reverse

功能描述：將容器內元素進行反轉

函式原型：

• reverse(iterator beg, iterator end);
  // 反轉指定范圍的元素
  // beg 開始迭代器
  // end 結束迭代器

示例：

#include <algorithm>
#include <vector>

class myPrint
{
public:
	void operator()(int val)
	{
		cout << val << " ";
	}
};

void test01()
{
	vector<int> v;
	v.push_back(10);
	v.push_back(30);
	v.push_back(50);
	v.push_back(20);
	v.push_back(40);

	cout << "反轉前： " << endl;
	for_each(v.begin(), v.end(), myPrint());
	cout << endl;

	cout << "反轉后： " << endl;

	reverse(v.begin(), v.end());
	for_each(v.begin(), v.end(), myPrint());
	cout << endl;
}

int main() {

	test01();

	system("pause");

	return 0;
}

總結： reverse反轉區間內元素，面試題可能涉及到

5.4 常用拷貝和替換演算法

學習目標：掌握常用的拷貝和替換演算法

演算法簡介：

• copy // 容器內指定范圍的元素拷貝到另一容器中
• replace // 將容器內指定范圍的舊元素修改為新元素
• replace_if // 容器內指定范圍滿足條件的元素替換為新元素
• swap // 互換兩個容器的元素

5.4.1 copy

功能描述：容器內指定范圍的元素拷貝到另一容器中

函式原型：

• copy(iterator beg, iterator end, iterator dest);
  // 按值查找元素，找到回傳指定位置迭代器，找不到回傳結束迭代器位置
  // beg 開始迭代器
  // end 結束迭代器
  // dest 目標起始迭代器

示例：

#include <algorithm>
#include <vector>

class myPrint
{
public:
	void operator()(int val)
	{
		cout << val << " ";
	}
};

void test01()
{
	vector<int> v1;
	for (int i = 0; i < 10; i++) {
		v1.push_back(i + 1);
	}
	vector<int> v2;
	v2.resize(v1.size());
	copy(v1.begin(), v1.end(), v2.begin());

	for_each(v2.begin(), v2.end(), myPrint());
	cout << endl;
}

int main() {

	test01();

	system("pause");

	return 0;
}

總結： 利用copy演算法在拷貝時，目標容器記得提前開辟空間

5.4.2 replace

功能描述：將容器內指定范圍的舊元素修改為新元素

函式原型：

• replace(iterator beg, iterator end, oldvalue, newvalue);
  // 將區間內舊元素 替換成 新元素
  // beg 開始迭代器
  // end 結束迭代器
  // oldvalue 舊元素
  // newvalue 新元素

示例：

#include <algorithm>
#include <vector>

class myPrint
{
public:
	void operator()(int val)
	{
		cout << val << " ";
	}
};

void test01()
{
	vector<int> v;
	v.push_back(20);
	v.push_back(30);
	v.push_back(20);
	v.push_back(40);
	v.push_back(50);
	v.push_back(10);
	v.push_back(20);

	cout << "替換前：" << endl;
	for_each(v.begin(), v.end(), myPrint());
	cout << endl;

	//將容器中的20 替換成 2000
	cout << "替換后：" << endl;
	replace(v.begin(), v.end(), 20,2000);
	for_each(v.begin(), v.end(), myPrint());
	cout << endl;
}

int main() {

	test01();

	system("pause");

	return 0;
}

總結： replace會替換區間內滿足條件的元素

5.4.3 replace_if

功能描述:將區間內滿足條件的元素，替換成指定元素

函式原型：

• replace_if(iterator beg, iterator end, _pred, newvalue);
  // 按條件替換元素，滿足條件的替換成指定元素
  // beg 開始迭代器
  // end 結束迭代器
  // _pred 謂詞
  // newvalue 替換的新元素

示例：

#include <algorithm>
#include <vector>

class myPrint
{
public:
	void operator()(int val)
	{
		cout << val << " ";
	}
};

class ReplaceGreater30
{
public:
	bool operator()(int val)
	{
		return val >= 30;
	}

};

void test01()
{
	vector<int> v;
	v.push_back(20);
	v.push_back(30);
	v.push_back(20);
	v.push_back(40);
	v.push_back(50);
	v.push_back(10);
	v.push_back(20);

	cout << "替換前：" << endl;
	for_each(v.begin(), v.end(), myPrint());
	cout << endl;

	//將容器中大于等于的30 替換成 3000
	cout << "替換后：" << endl;
	replace_if(v.begin(), v.end(), ReplaceGreater30(), 3000);
	for_each(v.begin(), v.end(), myPrint());
	cout << endl;
}

int main() {

	test01();

	system("pause");

	return 0;
}

總結： replace_if按條件查找，可以利用仿函式靈活篩選滿足的條件

5.4.4 swap

功能描述：互換兩個容器的元素

函式原型：

• swap(container c1, container c2);
  // 互換兩個容器的元素
  // c1容器1
  // c2容器2

示例：

#include <algorithm>
#include <vector>

class myPrint
{
public:
	void operator()(int val)
	{
		cout << val << " ";
	}
};

void test01()
{
	vector<int> v1;
	vector<int> v2;
	for (int i = 0; i < 10; i++) {
		v1.push_back(i);
		v2.push_back(i+100);
	}

	cout << "交換前： " << endl;
	for_each(v1.begin(), v1.end(), myPrint());
	cout << endl;
	for_each(v2.begin(), v2.end(), myPrint());
	cout << endl;

	cout << "交換后： " << endl;
	swap(v1, v2);
	for_each(v1.begin(), v1.end(), myPrint());
	cout << endl;
	for_each(v2.begin(), v2.end(), myPrint());
	cout << endl;
}

int main() {

	test01();

	system("pause");

	return 0;
}

總結： swap交換容器時，注意交換的容器要同種型別

5.5 常用算術生成演算法

學習目標：掌握常用的算術生成演算法

注意：算術生成演算法屬于小型演算法，使用時包含的頭檔案為 #include <numeric>

演算法簡介：

• accumulate // 計算容器元素累計總和
• fill // 向容器中添加元素

5.5.1 accumulate

功能描述：計算區間內 容器元素累計總和

函式原型：

• accumulate(iterator beg, iterator end, value);
  // 計算容器元素累計總和
  // beg 開始迭代器
  // end 結束迭代器
  // value 起始值

示例：

#include <numeric>
#include <vector>
void test01()
{
	vector<int> v;
	for (int i = 0; i <= 100; i++) {
		v.push_back(i);
	}

	int total = accumulate(v.begin(), v.end(), 0);

	cout << "total = " << total << endl;
}

int main() {

	test01();

	system("pause");

	return 0;
}

總結： accumulate使用時頭檔案注意是 numeric，這個演算法很實用

5.5.2 fill

功能描述：向容器中填充指定的元素

函式原型：

• fill(iterator beg, iterator end, value);
  // 向容器中填充元素
  // beg 開始迭代器
  // end 結束迭代器
  // value 填充的值

示例：

#include <numeric>
#include <vector>
#include <algorithm>

class myPrint
{
public:
	void operator()(int val)
	{
		cout << val << " ";
	}
};

void test01()
{

	vector<int> v;
	v.resize(10);
	//填充
	fill(v.begin(), v.end(), 100);

	for_each(v.begin(), v.end(), myPrint());
	cout << endl;
}

int main() {

	test01();

	system("pause");

	return 0;
}

總結： 利用fill可以將容器區間內元素填充為 指定的值

5.6 常用集合演算法

學習目標：掌握常用的集合演算法

演算法簡介：

• set_intersection // 求兩個容器的交集
• set_union // 求兩個容器的并集
• set_difference // 求兩個容器的差集

5.6.1 set_intersection

功能描述：求兩個容器的交集
函式原型：

• set_intersection(iterator beg1, iterator end1, iterator beg2, iterator end2, iterator dest);
  // 求兩個集合的交集
  // 注意:兩個集合必須是有序序列
  // beg1 容器1開始迭代器
  // end1 容器1結束迭代器
  // beg2 容器2開始迭代器
  // end2 容器2結束迭代器
  // dest 目標容器開始迭代器

示例：

#include <vector>
#include <algorithm>

class myPrint
{
public:
	void operator()(int val)
	{
		cout << val << " ";
	}
};

void test01()
{
	vector<int> v1;
	vector<int> v2;
	for (int i = 0; i < 10; i++)
    {
		v1.push_back(i);
		v2.push_back(i+5);
	}

	vector<int> vTarget;
	//取兩個里面較小的值給目標容器開辟空間
	vTarget.resize(min(v1.size(), v2.size()));

	//回傳目標容器的最后一個元素的迭代器地址
	vector<int>::iterator itEnd = 
        set_intersection(v1.begin(), v1.end(), v2.begin(), v2.end(), vTarget.begin());

	for_each(vTarget.begin(), itEnd, myPrint());
	cout << endl;
}

int main() {

	test01();

	system("pause");

	return 0;
}

總結：

• 求交集的兩個集合必須的有序序列
• 目標容器開辟空間需要從兩個容器中取小值
• set_intersection回傳值既是交集中最后一個元素的位置

5.6.2 set_union

功能描述：求兩個集合的并集

函式原型：

• set_union(iterator beg1, iterator end1, iterator beg2, iterator end2, iterator dest);
  // 求兩個集合的并集
  // 注意:兩個集合必須是有序序列
  // beg1 容器1開始迭代器
  // end1 容器1結束迭代器
  // beg2 容器2開始迭代器
  // end2 容器2結束迭代器
  // dest 目標容器開始迭代器

示例：

#include <vector>
#include <algorithm>

class myPrint
{
public:
	void operator()(int val)
	{
		cout << val << " ";
	}
};

void test01()
{
	vector<int> v1;
	vector<int> v2;
	for (int i = 0; i < 10; i++) {
		v1.push_back(i);
		v2.push_back(i+5);
	}

	vector<int> vTarget;
	//取兩個容器的和給目標容器開辟空間
	vTarget.resize(v1.size() + v2.size());

	//回傳目標容器的最后一個元素的迭代器地址
	vector<int>::iterator itEnd = 
        set_union(v1.begin(), v1.end(), v2.begin(), v2.end(), vTarget.begin());

	for_each(vTarget.begin(), itEnd, myPrint());
	cout << endl;
}

int main() {

	test01();

	system("pause");

	return 0;
}

總結：

• 求并集的兩個集合必須的有序序列
• 目標容器開辟空間需要兩個容器相加
• set_union回傳值既是并集中最后一個元素的位置

5.6.3 set_difference

功能描述：求兩個集合的差集

函式原型：

• set_difference(iterator beg1, iterator end1, iterator beg2, iterator end2, iterator dest);
  // 求兩個集合的差集
  // 注意:兩個集合必須是有序序列
  // beg1 容器1開始迭代器
  // end1 容器1結束迭代器
  // beg2 容器2開始迭代器
  // end2 容器2結束迭代器
  // dest 目標容器開始迭代器

示例：

#include <vector>
#include <algorithm>

class myPrint
{
public:
	void operator()(int val)
	{
		cout << val << " ";
	}
};

void test01()
{
	vector<int> v1;
	vector<int> v2;
	for (int i = 0; i < 10; i++) {
		v1.push_back(i);
		v2.push_back(i+5);
	}

	vector<int> vTarget;
	//取兩個里面較大的值給目標容器開辟空間
	vTarget.resize( max(v1.size() , v2.size()));

	//回傳目標容器的最后一個元素的迭代器地址
	cout << "v1與v2的差集為： " << endl;
	vector<int>::iterator itEnd = 
        set_difference(v1.begin(), v1.end(), v2.begin(), v2.end(), vTarget.begin());
	for_each(vTarget.begin(), itEnd, myPrint());
	cout << endl;


	cout << "v2與v1的差集為： " << endl;
	itEnd = set_difference(v2.begin(), v2.end(), v1.begin(), v1.end(), vTarget.begin());
	for_each(vTarget.begin(), itEnd, myPrint());
	cout << endl;
}

int main() {

	test01();

	system("pause");

	return 0;
}

總結：

• 求差集的兩個集合必須的有序序列
• 目標容器開辟空間需要從兩個容器取較大值