C++ 提高編程

2022 年 2 月 18 日
筆記
C++

C++ 提高編程

C++ 提高編程

主要針對C++泛型編程和STL技術

一、模板

1、概念

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

模板特點

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

2、函數模板

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

2.1 函數模板語法

函數模板的作用：建立一個通用函數，其函數返回值類型和形參類型可以不具體確定，用一個虛擬的類型來代表

語法

template<typename T>
函數聲明或定義

參數

template：聲明創建模板
typename：表明其後面的符號是一種數據類型，可以用class來代替
T：通用的數據類型，名稱可以替換，通常為大寫字母

// 兩個整型交換函數
void swap(int& a, int& b)
{
	int temp = a;
	a = b; 
	b = temp;
}
// 交換浮點型的函數
void swap(double& a, double& b)
{
	double temp = a;
	a = b;
	b = temp;
}
// 函數模板
template <typename T>  // 聲明模板，告訴編譯器後面程式碼緊跟著T，不要報錯，T是一個通用的數據類型
void m_swap(T& a, T& b)
{
	T temp = a;
	a = b;
	b = temp;
}
void test()
{
	int a = 1;
	int b = 3;
	double a1 = 4;
	double b1 = 5;
	/* swap(a, b);
	cout << a << b << endl;
	swap(a1, b1);
	cout << a1 << b1 << endl; */
	// 使用函數模板
	// 1、 自動推導
	m_swap(a, b);
	cout << a << b << endl;
	// 2、 顯示指定類型
	m_swap<int>(a, b);
	cout << a << b << endl;
}

模板可以將數據類型參數化

模板的使用方法

自動推導

顯示指定類型

2.2 注意事項

注意事項

自動推導數據類型，必須推導出一致的數據類型 T，才可以使用
模板必須要確定出 T 的數據類型，才可以使用

2.3 普通函數和函數模板的區別

普通函數調用時可以發生自動類型轉換（隱式類型裝換）
函數模板調用時，如果利用自動類型推導，不會發生隱式類型裝換
如果利用顯示指定類型的方法，可以發生隱式類型轉換

2.4 普通函數和函數模板的調用規則

調用規則如下

如果函數模板和普通函數都可以實現，優先調用普通函數

可以通過空模板參數列表強制調用函數模板

void myPrint(int a, int b)
{
	cout << a << b << endl;
	cout << "普通函數" << endl;
}
template<typename T>
void myPrint(T a, T b)
{
	cout << a << b << endl;
	cout << "模板函數" << endl;
}

void test()
{
	int a = 10;
	int b = 20;
	myPrint<>(a, b);  // 空模板參數列表調用模板函數
}

函數模板也可以發生重載

如果函數模板可以產生更好的匹配模式，優先調用函數模板

void myPrint(int a, int b)
{
	cout << a << b << endl;
	cout << "普通函數" << endl;
}
template<typename T>
void myPrint(T a, T b)
{
	cout << a << b << endl;
	cout << "模板函數" << endl;
}

void test()
{
	char a = 'a';
	char b = 'b';
	myPrint(a, b);  // 函數模板可以產生更好的匹配 
}

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

2.5 模板的局限性

模板的通用性並不是萬能的

如果傳入的是一個元組以及自定義數據類型，就無法實現了

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

// 模板重載
// 對比兩個數據是否相等
class Person
{
public:
	Person(string name, int age)
	{
		m_Age = age;
		m_Name = name;
	}
	string m_Name;
	int m_Age;
};
template<class T>
bool myCompare(T& a, T& b)  // 如果傳入的是一個自定義數據類型呢
{
	if (a == b)
	{
		return true;
	}
	else
	{
		return false;
	}
}
// 利用具體化Person的版本實現程式碼，具體化優先調用
// 也可以使用運算符重載
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 test()
{
	Person p1("Tom", 10);
	Person p2("Tom", 10);
	cout << myCompare(p1, p2) << endl;
}

學習模板並不是為了寫模板，而是在STL中能夠運用系統提供的模板

3、類模板

3.1 類模板語法

類模板作用

建立一個通用類，類中成員數據類型可以不具體制定，用一個虛擬的類型代表

語法

template<typename T>
類

參數

template：聲明創建模板
typename：表明其後面的符號是一種數據類型，可以用class來代替
T：通用的數據類型，名稱可以替換，通常為大寫字母

template<typename NameT, typename AgeT>
class Person
{
public:
	Person(NameT name, AgeT age)
	{
		m_Age = age;
		m_Name = name;
	}
	NameT m_Name;
	AgeT m_Age;
};
void test()
{
	Person<string, int>("Tom", 30);  // 調用-只有一種調用方式
}

3.2 類模板和函數模板的區別

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

類模板沒有自動類型推導的使用方式

類模板在模板參數列表中可以有默認參數

template<typename NameT, typename AgeT = int>  // 默認參數
class Person
{
public:
	Person(NameT name, AgeT age)
	{
		m_Age = age;
		m_Name = name;
	}
	NameT m_Name;
	AgeT m_Age;
};
void test()
{
	Person<string>("Tom", 30);
}

3.3 使用時機

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

普通類中的成員函數一開始就可以創建
類模板中的成員函數在調用時才創建

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

};

template<typename T>
class Person
{
public:
    // 沒調用，其不會編譯，因為無法確定T的數據類型
	T p1;
	void func1()
	{
		p1.show();
	}
	
};
void test()
{
	Person<Person1> p;
	p.func1();
}

3.4 類模板對象函數做參數

類模板實例出的對象，向函數傳參

一共有三種傳入方式

指定傳入的數據類型：直接顯示對象的數據類型

// 指定傳入類型
void printPerson1(Person<string, int> &p);

參數模板化：將對象中的參數變為模板進行傳遞

// 參數模板化
template<class T1, class T2>
void printPerson2(Person<T1, T2>& p);

整個類模板化：將這個對象類型模板化進行傳遞

// 整個類模板化
template<class T>
void printPerson3(T &p);

// 類模板做函數的參數
template<class T1, class T2>
class Person
{
public:
	Person(T1 name, T2 age)
	{
		m_Name = name;
		m_Age = age;
	}
	T1 m_Name;
	T2 m_Age;
	void showPerson()
	{
		cout << "name:" << m_Name << " age:" << m_Age << endl;
	}
};
// 指定傳入類型
void printPerson1(Person<string, int> &p)  
{
	p.showPerson();
}
// 參數模板化
template<class T1, class T2>
void printPerson2(Person<T1, T2>& p)
{
	p.showPerson();
	cout << "T1的類型為：" << typeid(T1).name() << endl;
	cout << "T2的類型為：" << typeid(T2).name() << endl;
}
// 整個類模板化
template<class T>
void printPerson3(T &p)
{
	p.showPerson();
}
void test()
{
	Person<string, int> p("Tom", 12);
	printPerson1(p);
	printPerson2(p);
	printPerson3(p);
}

查看數據類型的方式
typeid(T2).name()

3.5 類模板與繼承

當類模板碰到繼承是，需要注意以下幾點

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

// 類模板與繼承
template<class T>
class Base
{
public:
	T m_M;
};
// 當子類繼承的父類是一個類模板時，子類在聲明的時候，要指定出父類中 T 的數據類型
class Son : public Base<string> {};
// 如果想靈活使用父類中的 T 類型，子類也需要變為類模板
template<class T1, class T2>
class Son1 : public Base<T2> {};

3.6 類模板成員函數類外實現

能夠掌握類模板中的成員函數類外實現

// 類外實現
template<class T1, class T2>
class Person
{
public:
	Person(T1 age, T2 name);
	void shouPerson();
	T1 m_Age;
	T2 m_Name;
};
template <class T1, class T2>
Person<T1, T2>::Person(T1 age, T2 name)
{
	this->m_Name = name;
	m_Age = age;
}
// 要體現其為類模板的類函數，沒有參數也要添加
template <class T1, class T2>
void Person<T1, T2>::shouPerson()
{
	cout << "name:" << m_Name << " age:" << m_Age << endl;
}

3.7 類模板文件編寫

掌握類模板成員函數分文件編寫產生的問題以及解決方式

問題

類模板中成員函數創建時機是在調用階段，導致文件編寫是鏈接不到

解決

直接包含 .cpp 源文件
將聲明和實現寫到同一個文件中，並更改後綴名為 .hpp，hpp 是約定的名稱，並不是強制

person.hpp 中程式碼

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


template<class T1, class T2>
class Person
{
public:
	Person(T1 age, T2 name);
	void shouPerson();
	T1 m_Age;
	T2 m_Name;
};
template <class T1, class T2>
Person<T1, T2>::Person(T1 age, T2 name)
{
	this->m_Name = name;
	m_Age = age;
}
template <class T1, class T2>
void Person<T1, T2>::shouPerson()
{
	cout << "name:" << m_Name << " age:" << m_Age << endl;
}

程式入口程式碼

#include <iostream>
using namespace std;
#include <fstream>
// 第一中解決方式，包含 .cpp源文件
// #include"Person.cpp"

// 第二種解決方式，將 .h 和 .cpp 中的內容寫到 .hpp 文件中
#include "Person.hpp"

void test()
{
	Person<string, int> p("Tom", 132);
	p.shouPerson();
}
int main() {
	test();

	system("pause");
	return 0;
}

主要解決方式是第二種，將類模板成員函數寫到一起，並將後綴名改為 .hpp

3.8 類模板和友元

掌握類模板配合友元函數的類內和類外實現

全局函數類內實現：直接在類內聲明友元即可
全局函數類外實現：需要提前讓編譯器知道全局函數的存在

// 通過全局函數列印全局資訊
 // 提前讓編譯器知道Person類的存在
template<class T1, class T2>
class Person;

// 如果是類外實現的話需要讓編譯器提前知道該函數存在
template<class T1, class T2>
void printPerson1(Person<T1, T2>& p);

template<class T1, class T2>
class Person
{
	// 全局函數，類內實現
	friend void printPerson(Person<T1, T2>& p)
	{
		cout << "姓名：" << p.m_Name << " 年齡：" << p.m_Age << endl;
 	}
	// 全局函數，類外實現
	friend void printPerson1<>(Person<T1, T2>& p);  // <> 其為函數模板聲明
public:
	Person(T1 name, T2 age)
	{
		m_Name = name;
		m_Age = age;
	}
private:
	T1 m_Name;
	T2 m_Age;
};
template<class T1, class T2>
void printPerson1(Person<T1, T2>& p)
{
	cout << "姓名：" << p.m_Name << " 年齡：" << p.m_Age << endl;
	cout << "類外實現" << endl;
}

建議全局函數做類內實現，用法簡單，而且編譯器可以直接識別

3.9 數組類封裝

案例描述：實現一個通用的數組類，要求如下

可以對內置數據類型以及自定義數據類型的數據進行存儲
將數組中的數據存儲到堆區
構造函數中可以傳入數組的容量
提供對應的拷貝構造函數以及opertator=防止出現淺拷貝的問題
可以通過下標方式訪問數組中的元素
可以獲取數組中當前元素個數和數組數量

myArray.hpp 中程式碼

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

template<class T1>  // 輸出函數
void printArray();
template<class T1>
class MyArray
{
public:
	MyArray(int capacity);  // 有參構造
	MyArray(const MyArray& arr);  // 拷貝構造
	MyArray& operator=(const MyArray& arr);  // 賦值運算符重載，防止淺拷貝問題
	void pushBack(const T1& val);  //  尾插法插入數據
	void delBack();  // 尾刪法刪除數據
	T1& operator[](int index);  // 重載[]，使得可以使用索引訪問數組，同時可以賦值
	int getCapacity();// 返回數組的容量
	int getSize();// 返回數組的大小
	~MyArray();  // 清空堆區數據
private:
	T1* pAddress;  // 指針指向開闢到堆區的真實數組
	int m_Capacity; // 數組容量
	int m_Size;  // 數組大小
};

template<class T1>
MyArray<T1>::MyArray(int capacity)
{
	this->m_Capacity = capacity;
	this->m_Size = 0;
	this->pAddress = new T1[this->m_Capacity];  // 開闢數組空間
}
template<class T1>
MyArray<T1>::~MyArray()
{
	if (this->pAddress)
	{
		delete[] pAddress;
		pAddress = NULL;
	}
}
template<class T1>
MyArray<T1>::MyArray(const MyArray& arr)
{
	this->m_Capacity = arr.m_Capacity;
	this->m_Size = arr.m_Size;
	// this->pAddress = arr.pAddress  // 淺拷貝
	this->pAddress = new T1[arr.m_Capacity];  // 深拷貝
	// arr中的數據都拷貝過去
	for (int i = 0; i < this->m_Size; i++)
	{
		this->pAddress[i] = arr.pAddress[i];
	}
}
template<class T1>
MyArray<T1>& MyArray<T1>::operator=(const MyArray& arr)
{
	// 先判斷原來堆區是否有數據，如果有先釋放
	if (this->pAddress)
	{
		delete[] pAddress;
		this->pAddress = NULL;
		this->m_Size = 0;
		this->m_Capacity = 0;
	}
	// 深拷貝
	this->m_Capacity = arr.m_Capacity;
	this->m_Size = arr.m_Size;
	this->pAddress = new T1[this->m_Capacity];
	for (int i = 0; i < this->m_Size; i++)
	{
		this->pAddress[i] = arr.pAddress[i];
	}
	return *this;
}
template<class T1>
void MyArray<T1>::pushBack(const T1& val)
{
	// 判斷容量是否等於大小
	if (this->m_Capacity == this->m_Size)
	{
		cout << "達到數組容量，無法插入" << endl;
		return;
	}
	this->pAddress[this->m_Size] = val;
	this->m_Size++;  // 更新數組大小
}
template<class T1>
void MyArray<T1>::delBack()
{
	// 讓用戶訪問不到最後一個元素，即為尾刪，邏輯刪除
	if (!this->m_Size)
	{
		cout << "數組中沒有元素" << endl;
		return;
	}
	this->m_Size--;  // 訪問不到那個元素
}
template<class T1>
T1& MyArray<T1>::operator[](int index)
{
	return this->pAddress[index];
}
template<class T1>
int MyArray<T1>::getCapacity()
{
	return this->m_Capacity;
}
template<class T1>
int MyArray<T1>::getSize()
{
	return this->m_Size;
}
template<class T1>
void printArray(MyArray<T1>& arr)
{
	for (int i = 0; i < arr.getSize(); i++)
	{
		cout << arr[i] << endl;
	}
}

主函數調用

#include <iostream>
using namespace std;
#include <fstream>
#include "Person.hpp"

void test()
{
	MyArray<int> arr(5);
	for (int i = 0; i < 5; i++)
	{
		arr.pushBack(i);
	}
	cout << "開始輸出數組" << endl;
	printArray(arr);
}
int main() {
	test();

	system("pause");
	return 0;
}

該數組也可以存儲自定義數據類型

二、 STL 初識

1、基本概念

STL 基本模板庫
STL 從廣義上分為容器、演算法和迭代器
容器和演算法事件通過迭代器無縫連接
STL 幾乎所有的程式碼都採用了模板類或模板函數

2、 STL 六大組件

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

容器：各種數據結構：vector、list、deque、set、map等，用來存放數據
演算法：各種常用的演算法，如sort、find、copy、for_each等
迭代器：扮演了容器和演算法之間的膠合劑
仿函數：行為類似的函數，可作為演算法的某種策略
適配器：一種用來修飾容器或者仿函數或迭代器介面的東西
空間配置器：負責空間的配置和管理

2.1 容器、演算法、迭代器

容器：置物之所也

STL 容器就是將運用最廣泛的一些數據結構實現出來

常用的數據結構：數組、列表、樹、棧、隊列、集合、映射表等

這些容器分為序列式容器和關聯式容器兩種

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

演算法：問題之解也

有限的步驟，解決邏輯或數學上的問題，這叫做演算法

演算法分為：質變演算法和非質變演算法

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

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

提供一種方法，使之能夠依序尋訪某個容器所含有的各個元素，而又無需暴露該容器的內部表示方式

每個容器都有自己專屬的迭代器

迭代器使用非常類似於指針

迭代器種類

種類	許可權	支援運算
Input iterator(輸入迭代器)	只讀	++、==、!=
Output iterator(輸出迭代器)	只寫	++
Forward iterator(前向迭代器)	讀和寫，並且推進迭代器	++、==、!=
Bidirectional iterator(雙向迭代器)	讀和寫，可以向前或向後操作	++、–
Random access iterator(隨機訪問迭代器)	讀和寫。可以跳躍式訪問任意數據	++、–、[n]、-n、<、>

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

3、迭代器初始

3.1 vector 存放內置數據類型

容器：vector

演算法：for_each

迭代器：vector<int>::iterator

#include <vector>  // vector 頭文件
#include <algorithm>  // 標準演算法頭文件

void printVector(int value)
{
	cout << value << endl;
}
// vector 存放內置數據類型
void test()
{
	// 創建一個 vector 容器——數組
	vector<int> v;

	// 向容器中插入數據
	v.push_back(10);  // 尾插數據
	v.push_back(11);
	v.push_back(12);

	// 通過迭代器訪問容器中的數據
	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;
	}
	// 第三種遍歷方式
	for_each(v.begin(), v.end(), printVector);  // 回調函數
}

3.2 vector 存放自定義數據類型

vector 中存放自定義數據類型，並列印輸出

// 存放自定義數據類型
class Person
{
public:
	Person(string name, int age)
	{
		m_Name = name;
		m_Age = age;
	}
	int m_Age;
	string m_Name;
};

void test()
{
	vector<Person> v;
	Person p1("a", 20);
	Person p2("b", 34);
	Person p3("c", 20);
	v.push_back(p1);
	v.push_back(p2);
	v.push_back(p3);

	// 遍曆數據
	for (vector<Person>::iterator it = v.begin(); it != v.end(); it++)
	{
		cout << "name:" << it->m_Name  
			<< " age:" << it->m_Age << endl;  // it是一個指針
	}

	// 存放自定義數據類型的指針
	vector<Person*> v1;
	v1.push_back(&p1);
	v1.push_back(&p2);
	v1.push_back(&p3);
	// 遍曆數據
	for (vector<Person*>::iterator its = v1.begin(); its != v1.end(); its++)
	{
		cout << "name:" << (*its)->m_Name
			<< " age:" << (*its)->m_Age << endl;  // it是一個指針
	}
}

3.3 vector 中嵌套容器

容器中嵌套容器，我們將所有數據遍歷輸出

// 容器嵌套容器
void test()
{
	vector<vector<int>> V;
	// 創建小容器
	vector<int> v1;
	vector<int> v2;
	vector<int> v3;
	vector<int> v4;

	// 向小容器中添加數據
	for (int i = 0; i < 10; i++)
	{
		v1.push_back(i);
		v2.push_back(10 - i);
		v3.push_back(20 - i);
		v4.push_back(i + 10);
	}
	// 將小容器插入到大容器中
	V.push_back(v1);
	V.push_back(v2);
	V.push_back(v3);
	V.push_back(v4);

	// 遍歷大容器
	for (vector<vector<int>>::iterator i = V.begin(); i != V.end(); i++)
	{
		// *i 是一個容器
		for (vector<int>::iterator j = (*i).begin(); j != (*i).end(); j++)
		{
			cout << *j << "\t";
		}
		cout << endl;
	}
}

三、 STL 常用容器

每個容器都要添加頭文件

1、 string 容器

1.1 string 基本概念

本質

string 是 C++ 風格的字元串，而 string 本質是一個類

string 和 char* 的區別

char* 是一個指針
string 是一個類，類內部封裝了 char* ，管理這個字元串，是一個 char* 容器

特點

string 類內部封裝了很多成員方法
- 例如：find, copy, delete, replace, insert
string 管理 char* 所分配的記憶體，不用擔心複製和取值越界等，由類內進行負責

1.2 string 構造函數

構造函數原型

string(); 創建一個空字元串

string(const char* s); 使用字元串 s 初始化
string(const string& str); 使用一個 string 對象初始化另一個 string 對象
string(int, char c); 使用 n 個字元 c 初始化

/*
- string();							創建一個空字元串
  string(const char* s);			使用字元串 s 初始化
- string(const string& str);		使用一個 string 對象初始化另一個 string 對象
- string(int, char c);              使用 n 個字元 c 初始化
*/
void test()
{
	string s1;  // 默認構造
	const char* str = "hello world";
	string s2(str);  // 有參構造
	cout << "s2:" << s2 << endl;
	string s3(s2);  // 拷貝構造
	cout << "s3:" << s3 << endl;
	string s4(10, 'a');  // 10 個 a 構造
	cout << "s4:" << s4 << endl;
}

string 的多種構造方式沒有可比性，靈活性較高

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 賦值給當前字元串

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 個字元連接到字元串結尾

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

總結

find查找是從左往右，rfind是從右往左

find找到字元串後返回查找的第一個字元位置，找不到返回-1

replace在替換時，要指定從哪個位置起，多少個字元，替換成什麼樣的字元串

1.6 string 字元串比較

功能描述

字元串之間的比較

比較方式

字元串比較時按字元的ASCII碼進行對比
= 返回 0
< 返回 1
> 返回 -1

函數原型

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

主要比較兩個字元串是否相等

1.7 string 字元存取

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

char& operator[](int n);  // 通過 [] 方法獲取字元
char& at(int n);  // 通過 at 方法獲取字元
str.size();  // 返回字元串的長度

可以修改字元，str[int n] = 'c'

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 個字元

1.9 string 中的子串

功能描述

從字元串中獲取想要的子串

函數原理

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

2、 vector 容器

2.1 vector 基本概念

功能

vector 數據結構和數組非常相似，也稱為單端數組

vector 與普通數組的區別

不同之處在於數組是靜態空間，而 vector 可以動態擴展

動態擴展
- 並不是在原空間之後續接新空間，而是找更大的記憶體空間，然後將原數據拷貝到新空間，釋放原空間
- vector 容器的迭代是支援隨機訪問的迭代器

2.2 vector 構造函數

功能描述

創建 vector 容器

函數原型

vector<T> v;  // 採用模板實現類實現，默認構造函數
vector v2(v.begin(), v.end());  // 將 v[begin(), end()] 區間中的元素拷貝到自身，左閉右開
vector v3(n, elem);  // 構造函數將 n 個 elem 拷貝給本身
vector v4(const vector& vec);  // 拷貝構造函數

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

2.3 vector 賦值操作

功能描述

給 vector 容器進行賦值

函數原理

vector& operator=(const vector &vec);  // 重載賦值操作符
assign(v.begin(), v.end());  // 將v[begin, end]區間中的數據拷貝賦值給本身
assign(n, elem);  // 將 n 個 elem 拷貝賦值給本身

2.4 vector 大小操作

功能描述

對 vector 容器的容量和大小操作

函數原型

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

void printVector(vector<int>& v)
{
	for (vector<int>::iterator i = v.begin(); i != v.end(); i++)
	{
		cout << *i << " ";
	}
	cout << endl;
}
void test()
{
	vector<int> v;
	for (int i = 0; i < 10; i++)
	{
		v.push_back(i);
	}
	cout << v.capacity() << endl;
	cout << v.size() << endl;
	v.resize(20);  // 默認使用0填充
	cout << v.size() << endl;
	cout << v.capacity() << endl;
	printVector(v);
}

容量大於等於大小

2.5 vector 插入和刪除

功能描述

對 vector 容器進行插入、刪除操作

函數原型

push_back(elem);  // 尾部插入元素elem
pop_back();  // 刪除最後一個元素
insert(const_iterator pos, elem);  // 迭代器指向位置 pos 插入元素 elem
insert(const_iterator pos, int n, elem);  // 迭代器指向位置 pos 插入 n 個元素
erase(const_iterator pos);  // 刪除迭代器指向的長度
erase(const_iterator start, const_iterator end);  // 刪除迭代器從 start 到 end 之間的元素，左閉右開
clear();  // 刪除容器中所有元素

v1.insert(v1.begin(), 100); // 第一個參數是迭代器

2.6 vector 數據存取

功能描述

對 vector 中的數據的存取操作

數據原型

at(int idx);  // 返回索引 idx 所指的對象
operator[](int idx);  // 返回索引 idx 所指的數據
fornt();  // 返回容器中第一個數據元素
back();  // 返回容器中最後一個數據元素

2.7 vector 互換容器

功能描述

實現兩個容器內元素進行互換

函數原型

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

void test()
{
	vector<int> v;
	vector<int> v1;
	for (int i = 0; i < 10; i++)
	{
		v.insert(v.begin(), i);
		v1.push_back(i + 100);
	}
	cout << "交換前" << endl;
	printVector(v);
	printVector(v1);
	v.swap(v1);
	cout << "交換後" << endl;
	printVector(v);
	printVector(v1);
}

作用：巧用 swap 可以收縮記憶體空間vector<int> (v).swap(v); // 使用匿名對象

2.8 vector 預留空間

功能描述

減少 vector 在動態擴展容量時的擴展次數

函數原理

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

void test()
{
	vector<int> v;

	int num = 0;  // 統計開闢次數
	v.reserve(1000000);  // 當沒有添加此程式碼時，開闢了 35 次記憶體空間
	int* p = NULL;  
	for (int i = 0; i < 1000000; i++)
	{
		v.push_back(i);
		if (p != &v[0])  // 開闢一次記憶體，其首地址會發生改變
		{
			p = &v[0];
			num++;
		}
	}
	cout << num << endl;
}

如果數據量比較大，可以一開始利用 reserve 預留空間

3、 deque 容器

3.1 deque 基本概念

功能

雙端數組：可以對頭部進行插入刪除操作

deque 和 vector 區別

vector 對於頭部的插入和刪除的效率較低，數據量大，效率低
deque 相對而言，對頭部的插入刪除速度會比 vector 快
vector 訪問元素時的速度會比 deque 快，這和兩者實現有關

deque 內部工作原理

deque 內部有一個中控器，維護每段緩衝區中的內容，緩衝區中存放真實數據

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

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

3.2 deque 構造函數

功能描述

deque 容器構造

函數原理

deque<T> deq;  // 默認構造形式
deque d2(deq.begin(), deq.end());  // 構造函數將 [beg, end] 區間中的元素拷貝給本身
deque d3(n, elem);  // 構造函數將 n 個 elem 拷貝給本身
deque d4(const deque &deq);  // 拷貝構造函數

3.3 deque 賦值操作

功能描述

給 deque 容器進行賦值

函數原理

deque& operator=(const deque& d);  // 重載賦值運算符
assign(beg, end);  // 將 [beg, end] 區間中的數據拷貝賦值給本身
assign(n, elem);  // 將 n 個 elem 拷貝賦值給本身

3.4 deque 大小操作

功能描述

對 deque 容器的大小進行操作

函數原理

empty();  // 判斷容器是否為空
size();  // 返回容器中元素的個數
resize(int num);  // 重新指定容器的長度為 num，若容器變長，則以默認值填充新位置；如果容器變短，則末尾超出容器長度的元素被刪除（默認為0）
resize(int num, elem);  // 重新指定容器的長度為 num，若容器邊長，則以 elem 值填充新位置；如果容器變短，則末尾超出容器長度的元素被刪除

deque 沒有容量的概念

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 位置插入 (d1.begin(), d1.end()) 數據，無返回值
clear();  // 清空容器的所有數據
erase(beg, end);  // 刪除 [beg, end] 區間的數據，返回下一個數據的位置
erase(pos);  // 刪除 pos 位置的數據，返回下一個數據的位置

裡面的 pos 是迭代器指針的位置

3.6 deque 數據存取

功能描述

對 deque 中的數據的存取操作

函數原型

at(int idx);  // 返回索引 idx 所指的數據
operator[])(int idx);  // 返回索引 idx 所指的值
front();  // 返回容器第一個數據元素
back();  // 返回容器最後一個數據元素

3.7 deque 排序

功能描述

利用演算法對 deque 中的數據進行排序

函數原型

sort(iterator beg, iterator end);  // 對 [beg, end] 區間內元素進行排序

注意使用時，要包含頭文件#include <algorithm>

對於支援隨機訪問的迭代器的容器，都可以利用 sort 演算法直接對其進行排序

vector 也可以利用 sort 進行排序

4、案例-評委打分

4.1 案例描述

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

4.2 實現步驟

創建五名選手，放到 vector 容器中
遍歷 vector 容器，取出每名選手，執行 for 循環，可以把 10 個評分存到 deque 容器中
sort 演算法對 deque 容器中分數進行排序，去除最高分和最低分
deque 容器遍歷一遍，累加總分
獲取平均分

// 選手類
class Person
{
public:
	Person(string name, int score)
	{
		m_Name = name;
		m_Score = score;
	}
	string m_Name;
	int m_Score;  // 平均分
};
void createPerson(vector<Person>& v)
{
	// 創建五名選手
	for (int i = 0; i < 5; i++)
	{
		char nameSeed[] = { 'A', 'B', 'C', 'D', 'E' };
		string name = "選手";
		name += nameSeed[i];
		int score = 0;  // 默認為0分
		Person p(name, score);
		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);  // 將分數放入容器中
		}
		// 排序
		sort(d.begin(), d.end());

		// 去除最高分，和最低分
		d.pop_front();
		d.pop_back();
		// 取平均分
		int sum = 0;
		for (deque<int>::iterator dit = d.begin(); dit != d.end(); dit++)
		{
			sum += *dit;  // 累加分數
		}
		int avr = sum / d.size();
		it->m_Score = avr;
	}
}
void showScore(vector<Person> v)
{
	for (vector<Person>::iterator it = v.begin(); it != v.end(); it++)
	{
		cout << "名字為：" << it->m_Name << "  平均分為：" << it->m_Score << endl;
	}
}
void test()
{
	// 隨機數種子
	srand((unsigned int)time(NULL));

	vector<Person> v;  // 存放選手類
	v.reserve(5);

	createPerson(v);

	setScore(v);

	showScore(v);
}

5、 stack 容器

5.1 stack 基本概念

概念：stack 是一種先進後出的數據結構，它只有一個出口

棧中進入元素稱為入棧：push();

棧中彈出元素稱為出棧：pop();

5.2 stack 常用介面

功能描述：

棧容器常用的對外介面

5.2.1 構造函數

stack<T> stk;  // stack 採用模板實現，stack對象的默認構造形式
stack stk1(const stack& stk);  // 拷貝構造函數

5.2.2 賦值操作

stack& operator=(const stack& stk);  // 重載賦值運算符

5.2.3 大小操作

empty();  // 判斷堆棧是否為空
size();  // 返回棧的大小

5.2.4 數據存取

push(elem);  // 向棧頂添加元素
pop();  // 從棧頂移除第一個元素
top();  // 返回棧頂元素

6、 queue 容器

6.1 queue 基本概念

概念：

queue 是一種先進先出的數據結構，它有兩個出口

隊列容器允許從一端新增元素，從另一端移除元素

隊列中只有隊頭和隊尾才可以被外界使用，因此隊列不允許有遍歷行為

隊列中進數據稱為入隊：push();

隊列中出數據稱為出隊：pop();

6.2 queue 常用介面

功能描述

棧容器常用的對外介面

6.2.1 構造函數

queue<T> q;  // queue 採用模板類實現，queue 對象的默認構造函數
queue(const queue& que);  // 拷貝構造函數

6.2.2 賦值操作

queue& operator=(const queue& q);  // 重載賦值操作符

6.2.3 大小操作

empty();  // 判斷堆棧是否為空
size();  // 返回棧大小

6.2.4 數據存取

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

7、 list 容器

7.1 list 基本概念

功能：將數據進行鏈式存儲

鏈表是一種物理存儲單元上非連續的存儲結構，數據元素的邏輯順序是通過鏈表中的指針鏈接實現的

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

結點的組成：一個是存儲數據元素的數據域，另一個是存儲下一個結點地址的指針域

STL 中的鏈表是一個雙向循環鏈表

由於鏈表的存儲方式並不是連續的記憶體空間，因此鏈表 list 中的迭代器只支援前移或後移，屬於雙向迭代器

list 優點

採用動態分配記憶體，不會造成記憶體浪費和溢出
鏈表執行插入和刪除操作十分方便，修改指針即可，不需要移動大量數據

list 缺點

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

list 有一個重要的性質，插入操作和刪除操作都不會造成原有 list 迭代器的失效，這在 vector 是不成立的

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

7.2 list 構造函數

功能描述

創建 list 容器

函數原型

list<T> l;  // list 採用模板類實現，對象的默認構造形式
list(beg, end);  // 構造函數將 [beg, end]區間中的元素拷貝給本身
list(n, elem);  // 構造函數將 n 個 elem 拷貝給本身
list(const list& l);  // 拷貝構造函數

7.3 list 賦值和交換

功能描述

給 list 容器進行賦值，以及交換 list 容器

函數原型

assign(beg, end);  // 將 [beg, end] 區間中的數據拷貝賦值給本身
assign(n, elem);  // 將 n 個 elem 拷貝賦值給本身
list& operator=(const list& l);  // 重載賦值運算符
swap(l);  // 將 list 與本身的元素互換

7.4 list 大小操作

功能描述

對 list 容器的大小進行操作

函數原型

size();  // 返回容器中元素的個數
empty();  // 判斷容器是否為空
resize(int num);  // 重新指定容器的長度為 num，若容器變長，則以默認值填充新位置；如果容器變短，則末尾超出容器長度的元素被刪除（默認為0）
resize(int num, elem);  // 重新指定容器的長度為 num，若容器邊長，則以 elem 值填充新位置；如果容器變短，則末尾超出容器長度的元素被刪除

7.5 list 插入和刪除

功能描述

對 list 容器進行數據的插入和刪除

函數原型

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 位置插入 (l.begin(), l.end()) 數據，無返回值
clear();  // 清空容器的所有數據
erase(beg, end);  // 刪除 [beg, end] 區間的數據，返回下一個數據的位置
erase(pos);  // 刪除 pos 位置的數據，返回下一個數據的位置
remove(elem);  // 刪除容器中所有與 elem 值匹配的元素

7.6 list 數據存取

功能描述

對 list 容器中數據進行存取

函數原型

front();  // 返回第一個元素
back();  // 返回最後一個元素

注意不能使用 at 和 [] 的方式訪問容器中的元素

原因是 list 本質是鏈表，而不是使用連續線性空間存儲數據，迭代器也是不支援隨機訪問的

迭代器不支援隨機訪問，支援雙向訪問

7.7 list 反轉和排序

功能描述

將容器中的元素反轉，以及將容器中的數據進行排序

函數原型

reverse();  // 反轉鏈表
sort();  // 鏈表排序，其為成員函數

所有不支援隨機訪問迭代器容器，不可以使用標準演算法

不支援隨機訪問迭代器的容器，內部會提供對應一些演算法

對於自定義數據類型，sort() 括弧可以添加一個排序規則

高級排序只是在排序規則上再進行一次邏輯規則的制定，並不複雜
bool comparePerson(Person& p1, Person& p2)
{
    // 按照年齡升序
    if (p1.m_Age == p2.m_Name)
    {
        // 年齡相同，身高升序
        return p1.Height > p2.Height;
    }
    else
    {
        return p1.m_Age < p2.m_Age;
    }
}
l.sort(comparePerson);  // 排序演算法

8、 set / multiset 容器

8.1 set 基本概念

簡介：

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

本質

set 屬於關聯式容器，底層結構使用二叉樹實現

set 和 multiset 區別

set 不允許容器中有重複元素
multiset 允許容器中有重複元素

8.2 set 構造和賦值

功能描述

創建 set 容器以及賦值

函數原型

set<T> s;  // 默認構造函數
set(const set& s);  // 拷貝構造函數

set& operator=(const set& s);  // 重載賦值運算符
inset(elem);  // 插入數據

8.3 set 大小和交換

功能描述

統計 set 容器大小及交換 set 容器

函數原型

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

8.4 set 插入合刪除

功能描述

set 容器進行插入和刪除操作

函數原型

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

8.5 set 查找和統計

功能描述

對 set 容器進行查找數據以及進行數據統計

函數原型

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

8.6 set 和 multiset 區別

掌握 set 和 multiset 的區別

區別

set 不可以插入重複數據，而 multiset 可以
set插入數據的同時會返回插入結果，表示插入是否成功

ret.second用來查看是否插入成功
multiset 不會檢測數據，因此可以重複插入數據

8.7 pair 對組創建

功能描述

成功出現的數據，利用對組可以返回兩個數據

兩種創建方式

pair<type1, type2> p (value1, value2);  // 兩個 type 分別對應 value 的數據類型
pair<type1, type2> p = make_pair(value1, value2);

兩種創建方式，記住一種就可以了

使用方式

pair<string, int> p ("Tom", 20);
cout << "name:" << p.first << "  age:" << p.second;

8.8 set 排序

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

利用仿函數，可以改變排序規則

#include <set>
class MyCompare
{
public:
	bool operator()(int v1, int v2) const  
	{
		return v1 > v2;  // 降序排序
	}
};

void test()
{
	// 存放內置數據類型，改變排序規則
	set<int, MyCompare> s1;  // 仿函數的本質是一個類
	s1.insert(10);
	s1.insert(30);
	s1.insert(20);
	s1.insert(40);
	for (set<int, MyCompare>::iterator it = s1.begin(); it != s1.end(); it++)
	{
		cout << *it << endl;
	}
}

對於自定義的數據類型，要創建排序規則，必須要指定排序規則
class MyCompare
{
public:	  
    bool operator()(const Person& p1, const Person& p2)
    {
        // 按照年齡降序
        return p1.m_Age > p2.m_Age;
    }
};

9、 map / multimap 容器

9.1 map 基本概念

簡介：

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

本質：

map/ multimap 屬於關聯式容器，底層結構通過二叉樹實現

優點：

可以根據 key 值快速找到 value 值

map/ multimap 區別

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

9.2 map 構造和賦值

功能描述：

對 map 容器進行構造和賦值操作

函數原型

map<T1, T2> mp;  // map 默認構造函數
map (const map& mp);  // 拷貝構造

map& operator=(const map& mp);  // 重載賦值運算符

map 容器中所有元素都是成對出現的，插入數據的時候要使用對組

9.3 map 大小和交換

功能描述：

對 map 容器大小以及交換 map 值

函數原型

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

9.4 map 插入和刪除

功能描述：

map 容器進行插入和刪除數據

函數原型

insert(elem);  // 在容器中插入元素
clear();  // 清空所有元素
erase(pos);  // 刪除 pos 迭代器所指的元素，返回下一個元素的迭代器
erase(beg, end);  // 刪除區間 [beg, end] 的所有元素，返回下一個元素的迭代器
erase(key);  // 刪除容器鍵為 key 的元素

注意插入的是對組

// 第一種
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;  // 不建議使用，可以利用 [] 訪問值

9.5 map 查找和統計

功能描述：

對 map 容器進行查找數據和統計數據

函數原型

find();  // 查找 key 是否存在，返回改鍵的元素的迭代值；若不存在，返回 m.end();
count();  // 統計 key 的元素個數

9.6 map 排序

map 容器默認排序規則為按照鍵升序排序

利用仿函數可以改變排序規則

其和 [set 排序](#8.8 set 排序)類似

10、案例-員工分組

10.1 案例描述

公司每天招聘10個員工，10名員工進入公司後，需要指派員工在哪個部門工作
員工資訊：姓名、工資組成；部門分為：策劃、美術、研發
隨機給10名員工分配部門和工資
通過 multimap 進行資訊的插入 key：部門編號、value：員工
分部門顯示員工

10.2 實現步驟

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

10.3 程式碼演示

class Worker
{
	// 創建員工
public:
	string m_Name;
	int m_Salary;
};
void createWorker(vector<Worker>& v)
{
	// 創建10名員工
	for (int i = 0; i < 10; i++)
	{
		Worker worker;
		string nameSeed = "ABCDEFGHIJ";
		worker.m_Name = "員工";
		worker.m_Name += nameSeed[i];
		worker.m_Salary = rand() % 10000 + 10000;  // 10000~19999
		v.push_back(worker);  // 將員工放入分組中
	}
}
void printWorker(const vector<Worker>& v)
{
	for (vector<Worker>::const_iterator it = v.begin(); it != v.end(); it++)
	{
		cout << "name: " << it->m_Name << "   salary: " << it->m_Salary << endl;
	}
}
void printWorker(multimap<string, Worker>& mp, string* arr)
{
	string s0(20, '-');
	for (int i = 0; i < 3; i++)
	{
		string s = arr[i];
		s += "部門資訊";
		cout << s << endl;
		multimap<string, Worker>::iterator pos = mp.find(arr[i]);  // 返回迭代器對象
		int count = mp.count(arr[i]);
		for (int index = 0; pos != mp.end() && index < count; pos++, index++)
		{
			cout << "姓名：" << pos->second.m_Name << "   工資：" << pos->second.m_Salary << endl;
		}
		cout << s0 << endl;
	}
}
void setGroup(vector<Worker>& v, multimap<string, Worker>& mp, string* arr)
{
	for (vector<Worker>::iterator it = v.begin(); it != v.end(); it++)
	{
		// 產生隨機部門編號
		int depId = rand() % 3;  // 0 1 2 隨機數
		// 將員工插入到分組中，key編號，value員工
		mp.insert(pair<string, Worker>(arr[depId], *it));
	}
}
void test()
{
	// 添加隨機種子
	srand((unsigned int)time(NULL));
	string dep[] = { "策劃", "美術", "研發" };
	vector<Worker> v;
	createWorker(v);
	printWorker(v);

	// 員工分組
	multimap<string, Worker> mp;
	setGroup(v, mp, dep);
	printWorker(mp, dep);
}

四、 STL 函數對象

1、函數對象

1.1 基本概念

概念：

重載函數調用操作符的類，其對象常稱為函數對象
函數對象使用重載的 () 時，行為類似函數調用，也叫仿函數

本質：

函數對象（仿函數）是一個類，不是一個函數

1.2 使用方法

特點：

函數對象在使用時，可以像普通函數那樣調用，可以有參數，可以有返回值
函數對象超出普通函數的概念，函數對象可以有自己的狀態
函數對象可以作為參數傳遞

// 函數對象
class MyAdd
{
public:
	MyAdd()
	{
		this->count = 0;
	}
	int operator()(int v1, int v2)
	{
		this->count++;
		return v1 + v2;
	}
	int count;  // 函數對象可以有自己的內部狀態
};
void test()
{
	MyAdd ma;
	cout << ma(1, 2) << endl;
	cout << ma(1, 2) << endl;
	cout << ma(1, 2) << endl;
	cout << ma(1, 2) << endl;
	cout << "調用次數為：" << ma.count << endl;
}

2、謂詞

2.1 謂詞概念

概念

返回 bool 類型的仿函數稱為謂詞
如果 operator() 接受一個參數，那麼叫做一元謂詞
如果 operator() 接受兩個參數，那麼叫做二元謂詞

2.2 一元謂詞

class CreateFive
{
public:
	bool operator()(int val)
	{
		return val > 5 ? true : false;
	}  // 一元謂詞

};

void test()
{
	vector<int> v;
	for (int i = 0; i < 10; i++)
	{
		v.push_back(i);
	}
	// 查找容器中有么有大於5的數字
	vector<int>::iterator it = find_if(v.begin(), v.end(), CreateFive());  // 其為匿名函數對象，find_if 的返回值為一個迭代對象
	if (it == v.end())
	{
		cout << "沒有找到" << endl;
	}
	else
	{
		cout << "大於五的數字為：" << *it << endl;
	}
}

2.3 二元謂詞

// 二元謂詞
class MySort
{
public:
	bool operator()(int a, int b)
	{
		return a > b ? true : false;
	}
};
void test()
{
	vector<int> v;
	v.push_back(10);
	v.push_back(20);
	v.push_back(30);
	v.push_back(40);
	v.push_back(50);
	// sort(v.begin(), v.end());  // 升序排列
	// 使用函數對象，改變演算法策略，變為排序規則降序排列
	sort(v.begin(), v.end(), MySort());
	for (vector<int>::iterator it = v.begin(); it != v.end(); it++)
	{
		cout << *it << " ";
	}
	cout << endl;
}

3、內建函數對象

3.1 意義

概念：

STL 內建了一些函數對象

分類：

算術仿函數
關係仿函數
邏輯仿函數

用法：

這些仿函數所產生的對象，用法和一般函數完全相同
使用內建函數對象，需要引入頭文件#include <functional>

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>;  // 取反運算，10 取反為 -10

plus<int> p;
cout << p(10, 20) << endl;
negate<int> n;
cout << n(20) << endl;

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>;  // <=

3.4 邏輯仿函數

功能描述

實現邏輯運算

仿函數原理

template<typename T> bool logical_and<T>;  // 與
template<typename T> bool logical_or<T>;  // 或
template<typename T> bool logical_not<T>;  // 非

五、 STL 常用演算法

描述：

演算法主要是由頭文件<algorithm><functional><numeric>組成
<algorithm>是所有 STL 頭文件中最大的一個，範圍涉及到比較、交換、查找、遍歷、賦值等等
<numeric>體積很小，只包括幾個在序列上面進行簡單數學運算的模組函數
<functional>定義了一些模快類，用以聲明函數對象

1、常用遍歷演算法

學習目標：

掌握常用遍歷演算法

演算法簡介：

for_each();  // 遍歷容器
transform();  // 搬運容器到另一個容器中

1.1 for_each

功能描述：

實現遍歷容器

函數原型

for_each(iterator beg, iterator end, _func);

遍歷演算法：遍歷容器元素

參數：

beg：開始迭代器

end：結束迭代器

_func：函數或者函數對象，一般為輸出內容的函數，回調函數

1.2 transform

功能描述：

搬運容器到另一個容器中

函數原型

transform(iterator beg1, iterator end1, iterator beg2, _func);

目標容器要提前開闢空間，否則會報錯

參數：

beg1：源容器開始迭代器

end1：源容器結束迭代器

beg2：目標容器開始迭代器

_func：函數或函數對象

2、常用查找演算法

學習目標：

掌握常用的查找演算法

演算法簡介：

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

2.1 find

功能描述：

查找指定元素，找到返回指定元素的迭代器，找不到返回結束迭代器

函數原型

find(iterator beg, iterator end, value);

參數：

beg：開始迭代器

end：結束迭代器

value：查找的元素

如果是自定義數據類型，查找時要重載等號運算符

2.2 find_if

功能描述：

按條件查找元素

函數原型

find_if(iterator beg, iterator end, _Pred);

參數：

beg：起始迭代器

end：結束迭代器

_Pred：函數或者謂詞（返回 bool 類型的仿函數）

2.3 adjacent_find

功能描述：

查找相鄰重複元素

函數原型

adjacent_find(iterator beg, iterator end);

參數：

beg：開始迭代器

end：結束迭代器

2.4 binary_search

功能描述：

查找指定元素是否存在

函數原型

bool binary_search(iterator beg, iterator end, value);

注意：在無序序列中不可用

參數：

beg：開始迭代器

end：結束迭代器

value：查找的元素

2.5 count

功能描述：

統計元素個數

函數原型

count(iterator beg, iterator end, value);

beg：開始迭代器

end：結束迭代器

value：統計的元素

統計自定義數據類型時，要使用仿函數

class Person
{
public:
    Person(string name, int age)  
    {
        this->m_Name = name;
        this->m_Age = age;
    }
    bool operator==(const Person& p)  // 需要重載等號運算符，才可以統計
    {
        return this->m_Age == p.m_Age && this->m_Name = p.m_Name? true : flase;
    }
    int m_Age;
    string m_Name;
};

統計自定義數據類型的時候，需要配合重載operator==

2.6 count_if

功能描述：

按條件統計元素個數

函數原型

count_if(iterator beg, iterator end, _Pred);

參數：

beg：開始迭代器

end：結束迭代器

_Pred：謂詞

3、常用排序演算法

學習目標

掌握常用的排序演算法

演算法簡介：

sort();  // 對容器內元素進行排序
random_shuffle();  // 洗牌，指定範圍內的元素隨機調整次序
merge();  // 容器元素合併，並存儲到另一個容器中
reverse();  // 反轉指定範圍內的元素

3.1 sort

功能描述

對容器內元素進行排序

函數原型

sort(iterator beg, iterator end, _Pred);

參數：

beg：開始迭代器

end：結束迭代器

_Pred：謂詞

3.2 random_shuffle

功能描述

洗牌，指定範圍內的元素隨機調整次序

函數原型

random_shuffle(iterator beg, iterator end);

使用時記得添加隨機種子
srand((unsigned int)time(NULL));
參數：

beg：起始迭代器

end：結束迭代器

3.3 merge

功能描述：

兩個容器元素合併，並存儲到另一個容器中

函數原型

merge(iterator beg1, iterator end1, iterator beg2, iterator end2, iterator dest);

注意：

兩個容器必須是有序的

要提前給目標容器分配空間

參數：

beg1：容器1開始迭代器

end1：容器1結束迭代器

beg2：容器2開始迭代器

end2：容器2結束迭代器

dest：目標容器開始迭代器

3.4 reverse

功能描述

將容器內元素進行反轉

函數原型

reverse(iterator beg, iterator end);

參數：

beg：開始迭代器

end：結束迭代器

4、常用拷貝和替換演算法

學習目標

掌握常用的拷貝和替換演算法

演算法簡介

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

4.1 copy

功能描述：

容器內指定範圍的元素拷貝到另一個容器中

函數原型

copy(iterator beg, iterator end, iterator dest);

按值查找元素，找到返回指定位置迭代器，找不到返回結束迭代器位置

需要先預定目標容器的空間

參數：

beg：開始迭代器

end：結束迭代器

dest：目標容器起始迭代器

4.2 replace

功能描述

將容器內指定範圍內的舊元素修改為新元素

函數原型

replace(iterator beg, iterator end, oldvalue, newvalue);

它會替換區間內所有滿足條件的元素

參數：

beg：起始迭代器

end：結束迭代器

oldvalie：舊元素

newvalue：新元素

4.3 replace_if

功能用法

將區間內滿足條件的元素，替換成特定元素

函數原理

replace_if(iterator beg, iterator end, _Pred, newvalue);

它會替換區間內所有滿足條件的元素

參數：

beg：起始迭代器

end：結束迭代器

_Pred：謂詞

newvalue：替換的新元素

4.4 swap

功能描述：

互換兩個容器的元素

函數原型

swap(container c1, container c2);

同種數據類型的容器才能互換

參數：

c1：容器1

c2：容器2

5、常用算術生成演算法

學習目標

掌握常用的算術生成演算法

注意：

算術生成演算法屬於小型演算法，使用時需要包含的頭文件為#include <numeric>

演算法簡介

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

5.1 accumulate

功能描述：

計算區間內元素的總和

函數原型

accumulate(iterator beg, iterator end, firstValue);

參數：

beg：起始迭代器

end：結束迭代器

firstValue：起始累加值

5.2 fill

功能描述：

向容器中填充指定的元素

函數原型

fill(iterator beg, iterator end, value);

參數：

beg：開始迭代器

end：結束迭代器

value：填充的值

6、常用集合演算法

學習目標：

掌握常用的集合演算法

演算法簡介

set_insersection();  // 求兩個容器的交集
set_union();  // 求兩個容器的並集
set_different();  // 求兩個容器的差集

6.1 set_insersection

功能描述：

求兩個容器的交集，重複的元素

函數原型

iterator itEnd = set_insersection(iterator beg1, iterator end1, iterator beg2, iterator end2, iterator dest);  // 交集，返回最後一個值的迭代器

需要提前開闢空間，最特殊的情況：大容器包含小容器，開闢空間，取小容器的 size 即可
dest.resize(c1.size() > c2.size() ? c2.size() : c1.size());
參數：

beg1：容器1開始迭代器

end1：容器1結束迭代器

beg2：容器2開始迭代器

end2：容器2結束迭代器

dest：目標容器開始迭代器

6.2 set_union

功能描述：

求兩個容器的並集

函數原型

iterator itEnd = set_insersection(iterator beg1, iterator end1, iterator beg2, iterator end2, iterator dest);  // 並集，返回最後一個值的迭代器

目標容器要提前開闢空間，最特殊的情況是兩個容器沒有交集
dest.resize(c1.size() + c2.size());
參數：

beg1：容器1開始迭代器

end1：容器1結束迭代器

beg2：容器2開始迭代器

end2：容器2結束迭代器

dest：目標容器開始迭代器

6.3 set_difference

功能描述：

求兩個容器的差集

函數原型

iterator itEnd = set_insersection(iterator beg1, iterator end1, iterator beg2, iterator end2, iterator dest);  // c1 和 c2 的差集，返回最後一個值的迭代器，c1 - c2

目標容器要提前開闢空間，最特殊的情況是兩個容器沒有交集，取 size 大的作為容器的空間
dest.resize(c1.size() > c2.size() ? c1.size() : c2.size());  // 也可以使用 max(c1.size(), c2.size());
參數：

beg1：容器1開始迭代器

end1：容器1結束迭代器

beg2：容器2開始迭代器

end2：容器2結束迭代器

dest：目標容器開始迭代器

Tags: C++

C++ 提高編程

C++ 提高編程

一、 模板

1、 概念

2、 函數模板

2.1 函數模板語法

2.2 注意事項

2.3 普通函數和函數模板的區別

2.4 普通函數和函數模板的調用規則

2.5 模板的局限性

3、 類模板

3.1 類模板語法

3.2 類模板和函數模板的區別

3.3 使用時機

3.4 類模板對象函數做參數

3.5 類模板與繼承

3.6 類模板成員函數類外實現

3.7 類模板文件編寫

3.8 類模板和友元

3.9 數組類封裝

二、 STL 初識

1、 基本概念

2、 STL 六大組件

2.1 容器、演算法、迭代器

3、 迭代器初始

3.1 vector 存放內置數據類型

3.2 vector 存放自定義數據類型

3.3 vector 中嵌套容器

三、 STL 常用容器

1、 string 容器

1.1 string 基本概念

1.2 string 構造函數

1.3 string 賦值操作

1.4 string 字元串拼接

1.5 string 查找和替換

1.6 string 字元串比較

1.7 string 字元存取

1.8 string 插入和刪除

1.9 string 中的子串

2、 vector 容器

2.1 vector 基本概念

2.2 vector 構造函數

2.3 vector 賦值操作

2.4 vector 大小操作

2.5 vector 插入和刪除

2.6 vector 數據存取

2.7 vector 互換容器

2.8 vector 預留空間

3、 deque 容器

3.1 deque 基本概念

3.2 deque 構造函數

3.3 deque 賦值操作

3.4 deque 大小操作

3.5 deque 插入和刪除

3.6 deque 數據存取

3.7 deque 排序

4、 案例-評委打分

4.1 案例描述

4.2 實現步驟

5、 stack 容器

5.1 stack 基本概念

5.2 stack 常用介面

5.2.1 構造函數

5.2.2 賦值操作

5.2.3 大小操作

5.2.4 數據存取

6、 queue 容器

6.1 queue 基本概念

6.2 queue 常用介面

6.2.1 構造函數

6.2.2 賦值操作

6.2.3 大小操作

6.2.4 數據存取

7、 list 容器

7.1 list 基本概念

7.2 list 構造函數

7.3 list 賦值和交換

7.4 list 大小操作

7.5 list 插入和刪除

7.6 list 數據存取

一、模板

1、概念

2、函數模板

3、類模板

1、基本概念

3、迭代器初始

4、案例-評委打分

10、案例-員工分組

1、函數對象

2、謂詞

3、內建函數對象

1、常用遍歷演算法

2、常用查找演算法

3、常用排序演算法

4、常用拷貝和替換演算法

5、常用算術生成演算法

6、常用集合演算法

DM-i威力巨大比亞迪秦PLUS熱銷2.5萬台逼近宏光MINI EV！

《拳皇15》不知火舞被全形色頂點超殺美女被虐慘