note

C++提高编程

本阶段主要针对c++==泛型编程==和==STL==技术做详细讲解

一、STL初识

SIL基本概念：

STL大体分为六大组件，分别是：

容器、算法、迭代器、仿函数、适配器(配接器)、空间配置器

  1. 容器：各种数据结构，如vector、list、deque、set、map等，用来存放数据；
  2. 算法：各种常用的算法，如sort、find、copy、for_each(遍历)等；
  3. 迭代器：扮演了容器和算法之间的胶合剂；
  4. 仿函数：行为类似函数(小括号重载那个)，可作为算法的某种策略；
  5. 适配器：一种用来修饰容器或者仿函数或迭代器接口的东西
  6. 空间适配器：负责空间的配置与管理。

似乎只要导入了头文件 algorithm ，然后map，vector这些容器就可以直接用了，不用在导入相关头文件了。

1.1 STL中容器|算法|迭代器

二、STL-常用顺序容器

注意：

容器适配器

​ 除了顺序容器外，标准库还定义了三个顺序容器适配器：==stack==、==queue==、==priority_queue==。

​ 默认情况下，stack和queue是基于deque实现的，priority_queue是在vector之上实现的。

​ queue和priority_queue适配器定义在queue头文件中：标准库queue使用的是先进先出(first-in,first-out,FIFO)，==但是priority_queue允许为队列中的元素建立优先级，新加入的元素回排在所有优先级比它低的已有元素之前==。就好比饭店按照客人预定时间而不是来的时间早晚来为他们安排座位。

​ 还有一个 forward_list 顺序容器，表示一个单项链表，只能顺序访问，迭代器不支持–操作

a_vector.data() // 返回一个指向数组中第一个元素的指针，该指针在向量内部使用，是 int *pos; 也可以pos++

打印出来是一个地址，结果和 &(*a_vector.begin()) 一样

2.1 string容器

特别注意：string的一个字符的格式就是char, std::string str(“hello!”); ==typeid(str[0]).name() 的结果是 char==

本质：stringshiC++风格的字符串，但它本质上是一个类。

==string和char * 区别==：

特点：string内部封装了很多成员方法

​ 例如：查找find，拷贝copy，删除delete，替换replace，插入insert等； ​ string管理char * 所分配的内存，不用担心复制越界和取值越界等，由类内部进行负责。

创建字符串的时候还可以这样初始化：

std::string str1("this is (pee).");
std::string str2{"this is (pee)."};

这里第一次看到用花括号来初始化的，记录一下吧，感觉用起来是一样的,。

2.1.1 构造函数

构造函数原型：

这是string这个类的构造函数的各个重载版本，就很明了了。

void test01() {
	std::string str1;  // 默认构造，空的

	const char* s = "hello";  // C风格字符串
	std::string str2(s);  // C风格的字符串转成了string

	std::string str3(str2);  // 拷贝构造
	std::string str4 = str3;

	std::string str5(5, 'a');  // 后面只能是字符
}

补充：

int main(int argc, char **argv) {
	// 必须要有const
	const char *cp = "hello world!";    // 以空字符串结束的数组
	char cp1[] = { 'h', 'i'};  // 不是以空字符结束

	// 拷贝操作是遇到空字符时停止，所以：
	std::string str1(cp);
	std::string str2(cp1, 2);  // 给定个数是ok的
    // 因为没空字符，或给的数字大过数组的个数，则构造函数的行为(比如下面这)就是未定义的，
    std::string str3(cp1);  
	return 0;
}

2.1.2 赋值操作

赋值的函数原型：

除了重载的=号赋值，还有重载的成员函数assign

void test01() {
	std::string str1, str2, str3, str4, str5, str8;

	const char *s = "hello";
	str1 = s;  // 就普通赋值
	str2 = str1;
	str3 = 'd';  // 相当于把字符转成字符串了
	
	str4.assign(s);  // asign几乎类似
	str5.assign(str2);
	str8.assign(3, 'a');

	// 需要注意：
	const char* a = "hello world";
	std::string b;  // C风格得到的是前面的
	b.assign(a, 3);  // `hel`
	std::string e = "hello world";
	std::string f;  // C++风格得到的是后面的
	f.assign(e, 3);  // `lo world`
	std::cout << "这是b:" << f << std::endl;
}

2.1.3 字符串拼接

作用：实现在字符串末尾拼接字符串

函数原型：

​ 1、成员函数重载运算符+=:

void test01() {
	std::string str = "hello";
	const char* s = " world";
	str += s;
	char c = '!';
	str += c;

	std::string str1 = " how  ";
	str += str1;
	// 这两行是c风格
	str.append(s);
	str.append(s, 2);  // 直接是前2个
	// 这两行是c++风格
	str.append(str1);
	str.append(str1, 1, 2);  // 这里要指定开始位置
	std::cout << str << std::endl;
	// 注意，要是c++风格的只给了一个int,那就是此处索引到结尾的所有字符(跟上面截取赋值一样)
	str.append(str1, 1);
	std::cout << str << std::endl;
}

2.1.4 查找和替换

作用：查找字符串索引或是替换指定位置的字符串

函数原型：

void test01() {
	std::string str = "abcdefgde";
	int pos = str.find("de");  // 3
	 pos = str.rfind("de"); // 7
	 // 替换（从索引1往后的3个字符替换成`hello`）
	 str.replace(1, 3, "hello");   // 这就是在原来的字符串上修改
	 std::cout << str << std::endl;
    
    int new_pos = str.find("de", 5);  // 7，就是从str的第5个位置开始查找 de
}

总结：

2.1.5 字符串比较

作用：比较两个字符串是否相同

函数原型：(这是常函数)

void test01() {
	std::string str1 = "hello";
	std::string str2 = "aello";
	int ret = str1.compare(str2);
	if (ret == 0) {
		std::cout << "str1 等于 str2" << std::endl;
	}
	else if (ret == 1) {
		std::cout << "str1 大于 str2" << std::endl;
	}
	else if (ret == -1) {
		std::cout << "str1 小于 str2" << std::endl;
	}
}

​ 总结：字符串对比主要还是用来比较两个字符串是否相等，判断谁小谁大的意义并不是很大。

​ 这个还有一些重载版本，可以通过指定 pos1,n1,s2,pos2,n2的方式来对字符串s1和s2的部分进行对比。

2.1.6 字符修改|获取|判空|size()

string中单个字符存取方式有两种

void test01() {
	std::string str = "hello";
	// 可用`.size()`获取字符串长度
	for (int i = 0; i < str.size(); i++) {
		cout << str[i] << " ";
	}
	std::cout << std::endl;
	for (int i = 0; i < str.size(); i++) {
		std::cout << str.at(i) << ' ';
	}
	std::cout << std::endl;
	// 字符串修改
	str[0] = 'x';
	str.at(1) = 'x';
}

总结：

判断一个字符串是否为空，有如下三种方法：

std::string name = “”;

  1. if (name.empty()) {}
  2. if (name.size() == 0) {}
  3. if (name == “”) {}

​ 几种方法中，empty()函数是效率最高，也是最常用的一种。注意：不能使用name==NULL来判断，NULL一般只拿和指针做比较或者赋给指针，string是类，传参进函数时str调用默认的构造函数已经初始化了，并且str都已经是对象了，它不可能为NULL,也不能和NULL比较。

2.1.7 插入和删除

函数原型：

void test01() {
	std::string str = "hello";
	str.insert(2, " zhangsan ");  // 索引2处加字符串
	str.insert(1, 5, 'a');  // 在1处加5个a

	str.erase(2, 3);  // 从2处开始删除3个字符
    str.erase(0, str.find_first_not_of(" \t\n\r"));  // 把字符串最前面的空白删了
    
	str.erase(3);  // 从3处往后删掉所有
}

​ 总结：针对删除，若是没有给第2个参数(即删除几个字符)，那么看函数原型，是有默认参数的，是字符串最后的位置，所有就会从给的pos往后删完。

2.1.8 截取子串substr

作用：从字符串中截取想要的子字符串

函数原型：

void test01() {
	std::string str = "hello world";
	string substr = str.substr(3);
	std::cout << substr << std::endl;  // lo world

	std::string email = "songh@foxmail.com";
	int pos = email.find('@');  // 5,截取5个
	std::string name = email.substr(0, pos);  
	std::cout << name << std::endl;  // songh
}

​ Tips：使用substr是不会改变原来的string的，所以一定要用一个string去接收结果，不然就没有意义。

2.1.9 string注意事项

​ 直接的”nihao” “abcd”这些是字符串字面值(好像是C风格的字符串)，他们是不能直接相加的，如下：

std::string s1 = "hello";

std::string b = "niho" + "abcd";  // 非法，字符串字面值不能直接相加

std::string a = s1 + "niho" + "abcd";  // 正确，s1是string，加上nihao，会自动转换成string对象,然后再加abcd

std::string c = "niho" + "abcd" + s1;  // 非法，这里就是先nihao + abcd，都是字符串字面值，不能直接相加，就错了，里面至少要有一个string对象。

string类的输入运算符和getline函数分别是如何处理空白字符的：

别忘了这种输入：

std::string str1, str2;
while (std::cin >> str1 >> str2) { /*...*/ }
// 控制台输入 hello world   str1、str2就得到了这两个词

2.1.10 字符串常用处理函数

cctype头文件中的函数(可见c++小知识.md中关于头文件的说明)：

#include <cctype>

std::string s1 = "hello 123 world!!!";

decltype(s1.size()) count = 0;
for (auto &c : s1) {   // 注意这里是引用就会修改
	std::cout << typeid(c).name() << std::endl;   // 类型是char，所以如果要修改，一定是：
    c = 'X';   // 注意必须是单引号，
    
	if (std::ispunct(c)) {   // 上面一定有导入了<cctype> ，才能有std::ispunct()这些
		++count;
	}
	c = std::toupper(c);   // 好像不要<cctype>，也行，前面不加std::就行
}
std::cout << count << std::endl;  // 3 个标点符号
std::cout << s1 << std::endl;  // 把字母都变成大写了

​ 表3.3:cctype头文件中的函数（==c只能是字符==）

#inlcude <cctype> // 记得导入这个头文件，然后用 std::isdigit()这样的写法

2.2 vector容器

​ 功能：vector数据结构和数组非常相似，也称为==单端数组==，——数组左端是封闭的，一般都是通过右端添加删除。

​ vector与普通数组区别：数组是静态空间(定义好了多大就是多大)，而vector可以==动态扩展==。

Ps:

2.2.0 vector与指针的联系使用(书)

​ 再注意： std::begin(a_arr)、std::end(a_arr)这俩可以获取数组的首地址和尾地址后一位。

​ 注意：在早期c++标准中，如果vector元素还是vector或是其它模板类型，就需要右尖括号和元素类型之间添加一个空格，必须写成：vector<vector<int> > // 这里面必须有空格(可能一些老的编译器还需要) ​ 现在直接写成：vector<vector<int» 就行。

==vector 和 string 的迭代器支持的运算==（n为常数）：

但是特别注意：这个是不支持 iter1 + iter2 这种两个迭代器相加的， 所以迭代器的中间值的写法只能是:

auto begin = v.begin(), end = v.end(); auto mid = begin + (end - begin) / 2;

绝对不能是: auto mid = (begin + end) / 2; // 两个迭代器不能相加

std::vector<int> v1{ 1, 2, 3 };
std::vector<int> v2{ 11, 2, 3 };
if (v1 == v2) {
	std::cout << "一样" << std::endl;
}  // 两个vector之间是可以直接比较是否相等的，但还是两个数组是不能这样的，数组名代表的是各自的首地址，可能是不一样的，不能这样比

​ ==为什么两个迭代器之间不能相加==：将两个指针相减可以表示两个指针(在同一数组中)相距的距离，将指针加上一个整数也可以表示移动这个指针到某一位置。但是两个指针相加并没有逻辑上的意义，因此两个指针不能相加。

2.2.1 vector构造函数

后续遇到的补充：

函数原型：

#include <iostream>
#include <vector>  // 要导入这个

//template<typename T>  // 不知道这里为啥不让函数模板
void printVector(std::vector<float> &vec) {
	//for (vector<T>::iterator iter = vec.begin(); iter != vec.end(); iter++) {
	////  vector<T>::iterator 主要是这里不让用，一定得失具体的类型
	//	cout << *iter << ' ';
	//}
	//cout << endl;
	for (std::vector<float>::iterator iter = vec.begin(); iter != vec.end(); iter++) {
		std::cout << *iter << ' ';
	}
	std::cout << std::endl;
}
void test01() {
	std::vector<float> v;  // 无参构造
	for (float i = 0; i < 10; i++) {
		v.push_back(i);
	}
	printVector(v);

	// 这个`++`不能放在begin()后面
	std::vector<float> v1((++v.begin()), v.end());
	printVector(v1);

	std::vector<float> v2(10, 3.14);  // 10个3.14
	printVector(v2);

	std::vector<float> v3(v2);  // 拷贝构造
	printVector(v3);
}

一些初始化的注意：

std::vector<int> v1;         // size:0,  no values.
std::vector<int> v2(10);     // size:10, value:0
std::vector<int> v3(10, 42); // size:10, value:42
std::vector<int> v4{ 10 };     // size:1,  value:10
std::vector<int> v5{ 10, 42 }; // size:2,  value:10, 42
std::vector<string> v6{ 10 };  // size:10, value:""   // 10并不是string，所以就当做std::vsctor<string> v6(10)来处理了。
std::vector<string> v7{ 10, "hi" };  // size:10, value:"hi"  // 10并不是string，就当做v7(10, "hi")来处理了。

2.2.2 vector赋值操作

函数原型：

#include <vector>
#include <iostream>
void test01() {
	std::vector<float> v;  // 无参构造
	for (float i = 0; i < 10; i++) {
		v.push_back(i);
	}
	std::vector<float> v1;  // 先构造
	v1 = v;  // 在赋值，下面也一样

	std::vector<float> v2;
	v2.assign(v.begin(), v.end());

	std::vector<float> v3;
	v3.assign(10, 3.14);
}

2.2.3 vector容量和大小

函数原型：

void printVector(vector<float> &vec) {
	for (std::vector<float>::iterator iter = vec.begin(); iter != vec.end(); iter++) {
		std::cout << *iter << ' ';
	}
	std::cout << std::endl;
}
void test01() {
	std::vector<float> v;  // 无参构造
	for (float i = 0; i < 10; i++) {
		v.push_back(i);
	}
	std::cout << v.empty() << std::endl;  // 0
	std::cout << v.capacity() << std::endl;  // 13 != 10
	std::cout << v.size() << std::endl;  // 10
	v.resize(15);
	printVector(v);
	v.resize(5);
	printVector(v);
	v.resize(20, 5);
	printVector(v);
}

2.2.4 vector插入和删除

函数原型：

void printVector(vector<int> &vec) {
	for (std::vector<int>::iterator iter = vec.begin(); iter != vec.end(); iter++) {
		std::cout << *iter << ' ';
	}
	std::cout << std::endl;
}
void test01() {
	std::vector<int> v;
	for (int i = 1; i < 6; i++) {
		v.push_back(i * 10);  // 尾插
	}
	printVector(v);
	v.pop_back();   // 尾删
	printVector(v);

	std::vector<int>::iterator iter1 = v.begin();
	v.insert(iter1, 101);  // 尽量直接使用`v.begin()`
	v.insert(v.begin(), 3, 102);  // 插入3个102
	//v.insert(iter1, 3, 102);  // 这是错的
	//这里就一定不能再用`iter1`，动态库扩展的，再用就变了，就会
	printVector(v);

	v.erase(v.begin());  // 删掉一个数
	// 下面俩都是清空操作了
	v.erase(v.begin(), v.end());
	v.clear();
	printVector(v);
}

2.2.5 vector数据存取

函数原型：

void test01() {
	std::vector<int> v;
	for (int i = 1; i < 6; i++) {
		v.push_back(i * 10);  // 尾插
	}
	for (int i = 0; i < v.size(); i++) {
		// 两种访问方式
		cout << v[i] << '/' << v.at(i) << endl;
	}
	std::cout << "第一个元素：" << v.front() << std::endl;
	std::cout << "最后一个元素：" << v.back() << std::endl;
}

2.2.6 vector互换容器

功能：实现两个容器内元素的交换

函数原型：

// 简单的交互
void printVector(vector<int> &vec) {
	for (std::vector<int>::iterator iter = vec.begin(); iter != vec.end(); iter++) {
		std::cout << *iter << ' ';
	}
	std::cout << std::endl;
}
void test01() {
	std::vector<int> v, v1;
	for (int i = 1; i < 6; i++) {
		v.push_back(i * 10);  // 尾插
	}
	for (int i = 5; i > 0; i--) {
		v1.push_back(i * 10);
	}
	std::cout << "交换前：" << std::endl;
	printVector(v);
	printVector(v1);

	v.swap(v1);
	std::cout << "交换后：" << std::endl;
	printVector(v);
	printVector(v1);
}

// swap可以使两个容器互换，以达到使用的收缩内存效果

void test02() {
	std::vector<int> v;
	for (int i = 0; i < 100000; i++) {
		v.push_back(i);
	}
	std::cout << "v的容量：" << v.capacity() << std::endl;  // 13万多
	std::cout << "v的个数：" << v.size() << std::endl;  // 10万
	// 会发现容量比实际使用的个数多很多

	v.resize(5);

	std::cout << "v的容量：" << v.capacity() << std::endl;  // 13万多
	std::cout << "v的个数：" << v.size() << std::endl;  // 5
	// resize()后，容量却没减小，就浪费了很多空间

	// 收缩内存
	std::vector<int>(v).swap(v);  // 匿名对象，这行执行完就释放
	/*拆解：1、构建了一个匿名对象，是用v去构造的vector<int>(v)，v的个数现在是5个，所以这个匿名对象容量、个数都是5,；
	2、这个匿名对象和v交换了指针指向，然后现在的v容量个数都是5了，
	匿名对象是容量有13万多了，但是这行执行完就释放了。*/
	std::cout << "v的容量：" << v.capacity() << std::endl;  // 5
	std::cout << "v的个数：" << v.size() << std::endl;  // 5
}

2.2.7 vector预留空间

作用：减少vector在动态扩展容量是的扩展次数

函数原型：

void test01() {
	std::vector<int> v;
	// 预留空间
	v.reserve(100000);  // 要这就nums=1;不要nums=30

	int nums = 0;   // 记录扩展次数
	int *p = NULL;
	for (int i = 0; i < 100000; i++) {
		v.push_back(i);  // 这个放上面，一开始才有数
		//if (p != v.begin())  // 这是错的，不能这么写
        // 如果p不等于数组首地址了，就把首地址赋值给p
		if (p != &v[0]) {
			p = &v[0];  // 一定是v[0]，数组首地址来赋值
			nums++;
		}
	}
	std::cout << "nums：" << nums << std::endl;  // 30
	// 即数组首地址变了30次，需要30次动态扩展
}

总结：如果数据量较大，可以一开始利用reserve预留空间

2.2.8 书上内容补充(书)

拷贝构造的补充：

std::vector<int> vec(other_vec); // 拷贝 other_vec 的元素
std::vector<int> vec(other_vec.begin(), other_vec.end()); // 拷贝 other_vec 的元素

==特别注意==：向一个 vector、string 或deque 中insert插入元素会使所有指向容器的迭代器、引用和指针失效。而且插入任何位置都是合法的，但可能会很耗时。

​ 以下是一种写法操作，挺好的，可细看：从一个list中拷贝元素到deque中，值为偶数的放一个，为奇数的放另外一个：

int main() {	
	std::deque<int> deq1, deq2;
	std::list<int> li{ 1, 2, 3, 4, 5 };
	for (auto k : li) {
		(k % 2 == 0 ? deq1 : deq2).push_back(k);
        // 上面是我的写法，下面的写法等价，书上的
		// (k & 0X1 ? deq1 : deq2).push_back(k);
	}
	return 0;
}

还有一个操作后返回值的问题，也挺重要：

这俩最常用的就是这种，比如下面循环删除一个list中所有的奇数元素

int main() {	
	std::list<int> li{ 1, 2, 3, 4, 5 };
	auto iter = li.begin();
	while (iter != li.end()) {
		if (*iter % 2) 
            //  核心是下面这步(当然其它地方擦除可以不要返回值的)
			iter = li.erase(iter);
		else 
			++iter;
	}
	return 0;
}

2.2.9 vector存放不同数据类型及打印

1、内置数据类型：

注意：v.begin()是数组的第一个位置，然而v.end()是数组最后一个位置还要往后偏移一个。

#include <iostream>
#include <vector>  // 记得这头文件
#include <algorithm>  // 使用算法的头文件

void MyPrint(int val) {
	std::cout << val << std::endl;
}
void test01() {
	std::vector<int> v;  // 像类模板那样用
	v.push_back(10);  // 这是插入函数
	v.push_back(20);
	v.push_back(30);
	// 第1种遍历：
	// v.begin()是一个函数，返回值要定义一个数据类型去接收
	std::vector<int>::iterator itBegin = v.begin();
	// std::vector<int>::iterator 就是拿到vector<int>这种容器的迭代器类型
	std::vector<int>::iterator itEnd = v.end();
	while (itBegin != itEnd) {
		std::cout << *itBegin++ << std::endl;  // 当做指针去用(解引用加++的偏移)
	}
	// 第2种遍历：for循环
	for (std::vector<int>::iterator it = v.begin(); it != v.end(); it++) {
		// 注意下面这行写法是错的，这里不能再用 v.begin() != ，不能再v.begin()，必须用初始化的it
	//for (vector<int>::iterator it = v.begin(); v.begin() != v.end(); it++) {
		std::cout << *it << std::endl;
	}
	// 第3种遍历：算法`for_each`,记得头文件
	std::for_each(v.begin(), v.end(), MyPrint);
	// 第三个参数是一个自定义函数，那个参数还不是很明确
}

2、自定义数据类型：

​ 目标：vector中存放自定义数据类型，并打印输出

#include <vector>
#include <string>

class Person {
public:
	Person(std::string name, int age) {
		this->m_Name = name;
		this->m_Age = age;
	}
	std::string m_Name;
	int m_Age;
};
void test01() {
	Person p1("aaa", 10);
	Person p2("bbb", 20);
	Person p3("ccc", 30);
	vector<Person> v;  // 是什么类型就给什么
	v.push_back(p1);
	v.push_back(p2);
	v.push_back(p3);
	// 遍历
	for (std::vector<Person>::iterator it = v.begin(); it != v.end(); it++) {
		// (*it)这解引用出来的数据类型就是`<>`里面的类型，即Person
		std::cout << (*it).m_Name << it->m_Age << std::endl;  // 也可当指针使用
	}
}
void test02() {
	Person p1("eee", 10);
	Person p2("fff", 20);
	Person p3("ggg", 30);
	std::vector<Person *> v;  // 存放的数据是指针
	v.push_back(&p1);  // 指针不非得是new，可以是取址符
	v.push_back(&p2);
	v.push_back(&p3);
	std::vector<Person *>::iterator it = v.begin();
	while (it != v.end()) {
		// 解引用一次拿到的是一个数据的地址指针
		std::cout << (*it)->m_Name << (**it).m_Age << std::endl;
		it++;
	}
}

3、容器嵌套容器：

​ 目标：容器中嵌套容器，将所有数据进行遍历输出。

void test01() {
	std::vector<int> v1, v2, v3;
	for (int i = 0; i < 5; i++) {
		v1.push_back(i * 10);
		v2.push_back(i * 100);
		v3.push_back(i * 1000);
	}
	// 大容器:容器里面的数据类型是容器
	std::vector<vector<int>> v;
	v.push_back(v1);
	v.push_back(v2);
	v.push_back(v3);
	// 遍历；再次注意，这种`*iter`解引用得到的数据类型就是`<>`括号里的
	for (std::vector<vector<int>>::iterator iter = v.begin(); iter != v.end(); iter++) {
		// 太多的时候，这种解引用一定要加`括号`哦
		for (std::vector<int>::iterator it = (*iter).begin(); it != (*iter).end(); it++) {
			std::cout << *it << "\t";
		}
		// 或者用个中间变量
		//vector<int> temp = *iter;
		//for (vector<int>::iterator it = temp.begin(); it != temp.end(); it++) {
		//	cout << *it << "\t";
		//}
		std::cout << std::endl;
	}
}

2.3 deque容器

功能：==双端数组==，可以对头端进行插入删除操作

deque与vector区别：

deque内部工作原理：

​ deque内部有个==中控器==，维护每段缓冲区的内容，缓冲区存放真实数据

​ 换言之：中控器维护的是每个缓冲区的地址，使得使用deque时像一片连续的内存空间，不上图了，记不起来时点击这里

2.3.1 deque构造函数

和vector基本就是一模一样了

#include <iostream>
#include <deque>

void printDeque(const std::deque<int> d) {
	// 加个const保证只读，防止值被修改，对应的下面也要改
	//for (deque<int>::iterator iter = d.begin(); iter != d.end(); iter++) {
	for (std::deque<int>::const_iterator iter = d.begin(); iter != d.end(); iter++) {
		// 这里要对应的改成 `const_iterator`
		std::cout << *iter << ' ';
	}
	std::cout << std::endl;
}
void test01() {
	std::deque<int> d1;
	for (int i = 0; i < 10; i++) {
		d1.push_back(i);
	}
	printDeque(d1);
	// 其他的就不演示了，跟vector一模一样
}

注意：在打印时，要是加了const，让只读，那么对应的iterator也要改成const_iterator

2.3.2 deque赋值操作

跟vector一模一样，就不写了，看vector

2.3.3 deque大小操作

​ 和vector类似，但是是没有容量的概念的，在硬件支持的情况下理论上是可以无限扩容的。

2.3.4 deque插入和删除

函数原型： 两端插入操作：

指定位置操作：

2.4 案例-评委打分

​ 描述：有5名选手：选手ABCDE，10个评委分别对每一名选手打分，去除最高分，去除评委中最低分，取平均分。

实现步骤：

  1. 创建五名选手，放到vector中；
  2. 创建了一个用于存放评分的vector,里面的每一个元素都是一个deque，里面是10个评委的打分；
  3. sort算法对deque容器中分数排序，去除最高和最低分；
  4. deque容器遍历一遍，累加总分；
  5. 获取平均分。
#include <iostream>
#include <string>
#include <vector>
#include <deque>
#include <algorithm>  // sort算法要的
#include <ctime>  // 设置随机种子要的


class Person {
public:
	std::string m_Name;
	float m_Score;
	Person(std::string name, float score): m_Name(name), m_Score(score) {}
};
// 初始化选手
void createPerson(std::vector<Person> &v) {
	std::string name_id = "ABCDE";

	float score = 0;  // 初始化分数0
	for (int i = 0; i < 5; i++) {
		// 统一都是`选手`开头(必须循环里，每次重置)
		std::string name = "选手";  
		name += name_id[i];  // string可以直接加等，用索引去取
		Person p(name, score);
		v.push_back(p);
	}
}
// 给每个选手打分(假设打分随机在60~100)
void score(std::vector<Person> &v, std::vector<deque<int>> &v_score) {
	for (std::vector<Person>::iterator it = v.begin(); it != v.end(); it++) {
		std::deque<int> d;  // 记录每个人的打分
		for (int i = 0; i < 10; i++) {
			// c++中随机数的写法`rand() % 41`得到的就是0~40的随机数
			int score = rand() % 41 + 60;  // 0~40 + 60 = 60~100
			d.push_back(score);
		}
		v_score.push_back(d);  // 那5个人的乘积也放到队列
	}
}
void mySort(std::vector<deque<int>> &v_score) {
	/*千万别像这样临时起个变量，这样修改的就不是v_score了*/
	//deque<int> temp;
	//for (int i = 0; i < v_score.size(); i++) {
	//	temp = v_score[i];
	//	sort(temp.begin(), temp.end());  // 排序
	//	temp.pop_front(); 
	//	temp.pop_back();  // 去掉最高分和最低分
	//}  // 错误的写法(语法没问题，但是没有对传进来的排序)

	for (int i = 0; i < v_score.size(); i++) {
		// sort排序里面给的也是迭代器
		sort(v_score[i].begin(), v_score[i].end());  // 排序
		v_score[i].pop_front();
		v_score[i].pop_back();  // 去掉最高分和最低分
	}
}
// 传入存选手信息的数组及存选手得分的数组
void cal(std::vector<Person> &v, std::vector<deque<int>> &v_score) {
	if (v.size() != v_score.size()) {
		cout << "错误，选手信息与选手得分不符！" << endl;
		return;
	}
	float avg = 0;
	for (int i = 0; i < v.size(); i++) {
		int sum = 0;
		for (std::deque<int>::iterator it = v_score[i].begin(); it != v_score[i].end(); it++) {
			sum += *it;
		}
		avg = float(sum) / v_score[i].size();  // 平均分
		v[i].m_Score = avg;
	}
}

int main() {
	// 随机数种子(根据系统时间算随机种子)
	std::srand((unsigned int)time(NULL));
	// 这跟Python不同，有随机种子，每次才不一样，没有的话，每次都不一样

	// 存放存放人的数组
	std::vector<Person> v;
	createPerson(v);  // 去初始化赋值
	// 存放打分的数组
	std::vector<deque<int>> v_score;
	// 去随机打分
	score(v, v_score);
	// sort对deque中排序，去掉最高分和最低分；
	mySort(v_score);
	// 这就看下效果
	for (std::vector<deque<int>>::iterator it = v_score.begin(); it != v_score.end(); it++) {
		for (std::deque<int>::iterator iter = (*it).begin(); iter != (*it).end(); iter++) {
			std::cout << *iter << '\t';
		}
		std::cout << std::endl;
	}
	std::cout << "************************" << std::endl;
	// 开始累加，计算平均分，并赋值给成员
	cal(v, v_score);
	for (std::vector<Person>::iterator it = v.begin(); it != v.end(); it++) {
		std::cout << "姓名：" << it->m_Name << "\t平均分：" << it->m_Score << std::endl;
	}
    system("pause");
    return 0;
}

生成随机数技巧

小技巧：c++中生成随机小数的技巧

双波浪线中间就是加一条删除线

~单对波浪线，就是中间的字体变小，做下标时可以考虑~

2.5 stack容器

​ 概念：栈，stack是一种==先进后出==(FILO, First In Last Out)的数据结构，它只有一个出口

栈中只有顶端(栈顶)的元素才可以被外界使用，因此==栈不允许有遍历行为==

栈中进入数据称为 — ==入栈== push

栈中弹出数据称为 — ==出栈== pop

2.5.1 stack常用接口

构造函数：

赋值操作：

数据存取：

大小操作：

#include <iostream>
#include <stack>

void test01() {
	std::stack<int> stk;
	for (int i = 1; i < 6; i++) {
		stk.push(i * 10);
	}
	// 不可以遍历，不能这样去打印
	//for (int i = 0; i < stk.size(); i++)

	std::cout << stk.size() << std::endl;  // 5
	int elem = 0;
	// 这不是遍历，一直在删除栈顶元素
	while (!stk.empty()) {  // `!`取反
		elem = stk.top();  // 栈顶元素
		// 先进先出，第一个是50
		std::cout << elem << std::endl;
		stk.pop();  // 删除栈顶元素
	}
	std::cout << stk.size() << std::endl;  // 0
}

2.6 queue容器

概念：队列，Queue是一种==先进先出==FIFO，First In First Out)的数据结构，它有两个口。

队列容器允许从一端新增元素，从另一段移除元素

队列中只有队头和队尾才可以被外界使用，因此==队列不允许有遍历行为==

队列中进数据称为 — ==入队== push

队列中出数据称为 — ==出队== pop

队列是单向的，只能从队尾进(push)，队头出(pop)

2.6.1 queue常用接口

构造函数：

赋值操作：

数据存取：

大小操作：

#include <iostream>
#include <string>
#include <queue>

void test01() {
	Person p1("唐僧", 500);
	Person p2("孙悟空", 1000);
	Person p3("猪八戒", 900);
	Person p4("沙僧", 800);
	// 创建队列
	std::queue<Person> que;
	que.push(p1);
	que.push(p2);
	que.push(p3);
	que.push(p4);

	while (!que.empty()) {
		std::cout << "队头元素：" << que.front().m_Name << std::endl;
		std::cout << "队尾元素：" << que.back().m_Name << "\n" << std::endl;
		que.pop();  // 移除队头的第一个元素
	}
}

2.7 list容器

功能：将数据进行链式存储

​ ==链表==(list)是一种物理存储单元上非连续的存储结构，数据元素的逻辑顺序是通过链表中的指针链接实现的。

链表的组成：链表有一系列==节点==组成，一个列表10个元素就是10个节点；

节点的组成：一个节点由两部分组成：

​

​ STL中的链表是一个==双向循环链表==(简单来说就是最好一个节点的指针域并不指向NULL，而是指向第一个元素，且一个节点即指向后一个节点，也指向了前一个节点)

list的优点：

list的缺点：

​ 总结：链表(list)的优点就是数组(vector)的缺点；它的缺点就是数组的优点。

特别注意：

​ List有一个重要的性质，插入和删除操作都不会造成原有list迭代器(可以理解为那个指针)都不会失效，但是这在vector种是绝对不行的(迭代器也像是一个指针，记录着位置，数组的插入删除会另外开辟一个新的空间，原先的迭代器也就失效了，前面有例子)

2.7.1 list构造函数

函数原型：

#include <iostream>
#include <list>

void printList(const std::list<int> &lst) {
	// 上面用了const,那么下面一定要是const_iterator
	for (std::list<int>::const_iterator it = lst.begin(); it != lst.end(); it++) {
		cout << *it << ' ';
	}
	std::cout << std::endl;
}
void test01() {
	std::list<int> lst;
	lst.push_back(10);
	lst.push_back(20);
	lst.push_back(30);
	printList(lst);
	
	std::list<int> lst1(lst.begin(), lst.end());
	printList(lst1);

	std::list<int> lst2(10, 5);
	printList(lst2);

	std::list<int> lst3(lst2);
	printList(lst3);
}

2.7.2 list赋值和交换

功能描述：给list容器进行赋值，以及交换list容器

函数原型：

void printList(const std::list<int> &lst) {
	// 上面用了const,那么下面一定要是const_iterator
	for (std::list<int>::const_iterator it = lst.begin(); it != lst.end(); it++) {
		std::cout << *it << ' ';
	}
	std::cout << std::endl;
}
void test01() {
	std::list<int> lst;
	lst.push_back(10);
	lst.push_back(20);
	lst.push_back(30);

	std::list<int> lst1, lst2, lst3;
	lst1.assign(lst.begin(), lst.end());

	lst2.assign(10, 5);

	lst3 = lst1;

	std::cout << "交换前：" << std::endl;
	printList(lst1);
	printList(lst2);
	std::cout << "交换后：" << std::endl;
	lst1.swap(lst2);  // 交换
	printList(lst1);
	printList(lst2);
}

2.7.3 list大小操作

函数原型：算是成员函数吧，要用实例化对象去调用

void test01() {
	std::list<int> lst;
	lst.push_back(10);
	lst.push_back(20);
	lst.push_back(30);

	std::cout << lst.size() << std::endl;  // 3
	std::cout << lst.empty() << std::endl;  // 0
	lst.resize(2);  //  10 20
	lst.resize(5, 3);  // 10 20 3 3 3
}

2.7.4 list插入删除

函数原型：

​ 注意：这上面的pos、begin、end均是指的迭代器，也要主要巧用有返回值的函数。remove也是list特有的。

void printList(const std::list<int> &lst) {
	// 上面用了const,那么下面一定要是const_iterator
	for (std::list<int>::const_iterator it = lst.begin(); it != lst.end(); it++) {
		std::cout << *it << ' ';
	}
	std::cout << std::endl;
}
void test01() {
	std::list<int> lst;
	lst.push_back(10);
	lst.push_back(20);
	lst.push_front(30);
	lst.push_front(40);  // 40 30 10 20

	// 这个会返回新插入数据的位置，记得要用迭代器去接收
	std::list<int>::iterator it = lst.insert(lst.begin(), 5);  // 5 40 30 10 20
	std::cout << *it << std::endl;  // 5

	lst.insert(lst.end(), 3, 100);  // 尾部插了3个100

	// erase后都会返回下一个元素的地址，可以不去接收的
	//lst.erase(lst.begin());   // 这也是可以的
	std::list<int>::iterator it1 = lst.erase(lst.begin());
	std::cout << *it1 << std::endl;  // 40 可以不要这个

	// 会删除所有的 100
	lst.remove(100);

	printList(lst);
}

2.7.5 list数据存取

​ list容器不可以通过[]或者at()方式访问数据，是不支持随机访问的，因为list本质是链表，不是用连续线性空间存储数据，迭代器也是不支持随机访问的。

函数原型：

void test01() {
	std::list<int> lst;
	lst.push_back(10);
	lst.push_back(20);
	lst.push_front(30);
	lst.push_front(40);  // 40 30 10 20

	std::cout << lst.front() << std::endl;  // 40
	std::cout << lst.back() << std::endl;  // 20

	// 验证迭代器是不支持随机访问的
	std::list<int>::iterator it = lst.begin();
	it++;
	it--;  // 这俩是可以的，就说明是支持双向的
	
		   // 下面可验证是不是支持随机访问
	//it = it + 1;  // 这里是错误的
	//it = it + 5;  // 或者其他int
	// 这就说明list是不支持随机访问的，其它的如vector支持随机访问的，这就没问题
}

2.7.6 list反转和排序

功能：将容器中的元素反转，以及将容器中的数据进行排序

函数原型：注意这里的sort是成员函数，不是全局的那个sort

void printList(const std::list<int> &lst) {
	// 上面用了const,那么下面一定要是const_iterator
	for (std::list<int>::const_iterator it = lst.begin(); it != lst.end(); it++) {
		std::cout << *it << ' ';
	}
	std::cout << std::endl;
}
bool myCompare(int num1, int num2) {
	return num1 > num2;  // 这就是升序
}
void test01() {
	std::list<int> lst;
	lst.push_back(10);
	lst.push_back(20);
	lst.push_front(30);
	lst.push_front(40);  // 40 30 10 20
	// 反转
	lst.reverse();
	printList(lst);  // 20 10 30 40
	// 排序(默认升序排列)
	lst.sort();
	printList(lst);  // 10 20 30 40
	// 若想要升序，就要仿函数
	lst.sort(myCompare);
	printList(lst);  // 40 30 20 10
}

​ Ps：所有不支持随机访问迭代器的容器，不可以使用标准算法(即中的算法)；所以不支持随机访问迭代器的容器，内部会提供对应一些算法。

2.7.7 排序案例

​ 案例描述：将Person自定义数据类型进行排序，Person中属性有姓名、年龄、身高

​ 排序规则：按照年龄进行升序，如果年龄相同按照身高进行降序

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

void printList(const std::list<Person> &L) {
	for (std::list<Person>::const_iterator it = L.begin(); it != L.end(); it++) {
		std::cout << "姓名：" << it->m_Name << "\t年龄：" << it->m_Age
			<< "\t身高：" << it->m_Height << std::endl;
	}
}
// 自己写的排序函数
bool desc(Person p1, Person p2) {
	if (p1.m_Age == p2.m_Age) {
		return p1.m_Height > p2.m_Height;
	}
	return p1.m_Age < p2.m_Age;
}
void test01() {
	Person p7("钱五", 12, 150);
	Person p1("张三", 18, 175);
	Person p2("李四", 23, 165);
	Person p6("钱六", 12, 199);
	Person p3("王五", 15, 190);
	Person p4("赵六", 30, 155);
	Person p5("钱七", 12, 168);

	std::list<Person> L;
	L.push_back(p7);
	L.push_back(p1);
	L.push_back(p2);
	L.push_back(p6);
	L.push_back(p3);
	L.push_back(p4);
	L.push_back(p5);

	std::cout << "排序前：" << std::endl;
	printList(L);
	std::cout << "***********\n" << std::endl;

	std::cout << "排序后：" << std::endl;
	L.sort(desc);
	printList(L);
	std::cout << "***********\n" << std::endl;
}

总结：对于自定数据类型，必须指定排序规则，否则编译器不知道如何进行排序。

2.8 array容器

​ 还有这个容器，了解即可，定义后的空间是固定的，明确知道多少个可以试着用array，元素个数经常变，vector比较好。

#include <array>    // 同名头文件
int main() {
 	std::array<int, 3> arr1;  // 10个默认初始化的int
	std::array<int, 3> arr2 = { 1, 2, 3 };  // 列表初始化
	std::array<int, 3> arr3 = { 12 };  // arr3[0]=12,剩余为0 
}

三、STL-常用关联容器

​ set和list的区别：set是有序不重复集合，底层实现是红黑树；而list是无序可重复集合，底层实现是链表。

标准库一共定义了8个关联容器：（无序容器则定义在头文件==unordered_map==和==unordered_set==中。）

   
按关键字有序保存元素  
map 关联数组：保存关键字-值对
set 关键字即值，即只保存关键字的容器
multimap 关键字可重复出现的map
multiset 关键字可重复出现的set
无序集合 (不保持关键字顺序的容器都以==unordered==开头)
unordered_map 用哈希函数组织的map
unordered_set 用哈希函数组织的set
unordered_multimap 哈希组织的map：关键字可重复出现
unordered_multiset 哈希组织的set：关键字可重复出现

==无序容器==的一点补充：

unordered_set unordered_map 这些

新标准定义了4个无序关联容器，这些容器不是使用比较运算符来组织元素，而是使用一个==哈希函数==和关键字类型的==运算符。。map、set这些是有序的(会自动排序的)，在某些关键字元素类型无明显的序关系下，无序容器也很有用，，因为维护元素的序代价非常高昂。可以不使用默认的hash,可以自己重载定义，也不想说了，了解。

无序容器，有一个==管理桶==的概念，管理操作————==桶接口==、==桶迭代==、==哈希策略==放这里吧，就不详说了，以后用到再讲吧。

总结：==无序容器拥有更好的性能，有序容器使得元素始终有序==。

3.1 set/multiset容器

set和multiset定义在头文件set中；

本质：set/multiset属于==关联式容器==，底层结构是用==二叉树==实现

set和multiset区别：

==初始化==：

std::set<std::string> excl= {"the", "and", "The", "And", "and"};

3.1.1 set构造和赋值

构造：

赋值：

#include <iostream>
#include <set>

void printSet(const std::set<int> &s) {
	// 没想到在set里这iterator也是可以的，但还是统一使用
	//for (set<int>::iterator it = s.begin(); it != s.end(); it++) {
	for (set<int>::const_iterator it = s.begin(); it != s.end(); it++) {
		std::cout << *it << ' ';
	}
	std::cout << std::endl;
}
void test01() {
	std::set<int> s1;
	// 数据插入的方式 只有insert方式
	s1.insert(20);
	s1.insert(10);
	s1.insert(40);
	s1.insert(30);
	s1.insert(10);
	// 会自动插入，且重复插入的值无效
	printSet(s1);  // 10 20 30 40

	// 拷贝构造
	std::set<int> s2(s1);
	// 赋值
	std::set<int> s3;
	s3 = s2;
}

3.1.2 set大小和交换

​ 在set中是没有resize的，因为resize变长是要填充默认值的，都是重复的，而重复值在set中是不被允许的。

函数原型：

void test01() {
	std::set<int> s1;
	// 数据插入的方式 只有insert方式
	s1.insert(20);
	s1.insert(10);
	s1.insert(40);
	s1.insert(30);
	s1.insert(10);  // s1  // 10 20 30 40
	// 会自动插入，且重复插入的值无效

	std::cout << s1.size() << std::endl;  // 4
	std::cout << s1.empty() << std::endl;  // 0

	std::set<int> s2;
	s2.insert(50);
	s2.swap(s1);
	// s1和s2中元素的值就互相交换了
}

3.1.3 set插入和删除

注意：set在插入时会自动按照从小到大的顺序排序。

函数原型：

void printSet(const std::set<int> &s) {
	for (std::set<int>::const_iterator it = s.begin(); it != s.end(); it++) {
		std::cout << *it << std::endl;
	}
}
void test01() {
	std::set<int> s;
	s.insert(20);
	s.insert(40);
	s.insert(10);
	s.insert(50);
	s.insert(30);
	printSet(s);  // 10 20 30 40 50

	s.erase(s.begin());  // 删除的是10
	// 这个删除会返回下一个迭代所指的元素
	std::set<int>::iterator it = s.erase(s.begin());  // 删的20
	std::cout << *it << std::endl;  // 30

	// 直接删除指定元素，像list中的remove
	s.erase(40);
	printSet(s);  // 30 50

	// 清空,这都是清空
	s.erase(s.begin(), s.end());
	s.clear();  
}

3.1.4 set查找和统计

函数原型：

void  test01() {
	std::set<int> s;
	s.insert(20);
	s.insert(10);
	s.insert(30);
	s.insert(10);

	std::set<int>::iterator it = s.find(10);
	//it = s.find(100);  // 找不到就返回s.end()
	if (it != s.end()) {
		std::cout << "找到该元素了:" << *it << std::endl;
	}
	else {
		std::cout << "该元素不存在" << std::endl;
	}
	std::cout << s.count(10) << std::endl;  // 存在就是1
	std::cout << s.count(100) << std::endl;  // 不存在就是0
}

3.1.5 set和multiset区别

两个都是用的头文件#include <set>

区别：

// set
void  test01() {
	std::set<int> s;
	// 可以在定义里看到isnert返回的是一个对组
	std::pair<std::set<int>::iterator, bool> ret = s.insert(10);
	// 对组里面两个数，用first和second去取
	std::cout << *(ret.first) << std::endl;  // 10
	std::cout << ret.second << std::endl;  // 1
	// 再插入同一个值，返回的bool就是0了
	ret = s.insert(10);
	std::cout << *(ret.first) << std::endl;  // 10
	std::cout << ret.second << std::endl;  // 0
}
// multiset
void test02() {
	std::multiset<int> ms;
	ms.insert(10);  // 这是不会去检测的，也是没有返回值的
	ms.insert(10);
	ms.insert(10);
	for (std::multiset<int>::iterator it = ms.begin(); it != ms.end(); it++) {
		std::cout << *it << std::endl;
	}
}

3.1.7 set容器自定义排序

目标：

主要技术点：

示例一：set=放置内置数据类型

// 这个一定要写到函数printCompare前面
class MyCompare {
public:
	bool operator()(int val1, int val2) {
		return val1 > val2;
	}
};
void printSet(const std::set<int, MyCompare> &s) {
	for (std::set<int, MyCompare>::const_iterator it = s.begin(); it != s.end(); it++) {
		std::cout << *it << ' ';
	}
	std::cout << std::endl;
}
void  test01() {
	//set<int> s;  // 会默认从小到大排序
	// 这里改了模板类型，后面打印的时候全部类型都要改
	std::set<int, MyCompare> s;
	s.insert(20);
	s.insert(50);
	s.insert(10);
	s.insert(40);
	s.insert(30);  
	printSet(s);
}

​ 理解：set<int, MyCompare> s; MyCompare说是用的仿函数，我的理解，这是一个类，重载了()，正常使用是先实例化：MyCompare mc;再mc()就是仿函数，这里的参数本来是要一个函数名的，放个类名，可以理解为是匿名对象，再被后台调用()时就是仿函数。

实例二：

class Person {
public:
	std::string m_Name;
	int m_Age;
	Person(std::string name, int age) {
		this->m_Name = name;
		this->m_Agvoid  test01() {
	std::set<Person, MyCompare> s;
	Person p1("张三", 13);
	Person p2("李四", 14);
	Person p3("王五", 19);
	Person p4("赵六", 15);
	s.insert(p1);
	s.insert(p2);
	s.insert(p3);
	s.insert(p4);
	// 这么插入就不行，不能实例化；必须用匿名对象
	//s.insert(Person p7("钱七", 23));
	s.insert(Person("钱七", 23));  // 匿名对象是OK的

	std::set<Person, MyCompare>::iterator it = s.begin();
	for (; it != s.end(); it++) {
		std::cout << "姓名：" << it->m_Name
			<< " 年龄：" << (*it).m_Age << std::endl;
	}
}  自己写的，一定要有const,不然编译不过
	//bool operator()(Person &p1, Person &p2) {
	bool operator()(const Person &p1, const Person &p2) {
		return p1.m_Age > p2.m_Age;
	}
};
void  test01() {
	std::set<Person, MyCompare> s;
	Person p1("张三", 13);
	Person p2("李四", 14);
	Person p3("王五", 19);
	Person p4("赵六", 15);
	s.insert(p1);
	s.insert(p2);
	s.insert(p3);
	s.insert(p4);
	//set<Person, MyCompare>::iterator it = s.begin();
	for (std::set<Person, MyCompare>::iterator it = s.begin(); it != s.end(); it++) {
		std::cout << "姓名：" << it->m_Name
			<< " 年龄：" << (*it).m_Age << std::endl;
	}
}

注意：

3.2 map/multimap

类型map和multimap定义在头文件map中；有点像是Python中的字典 // 或许应该尽量使用 对应的 std::unordered_map 就不会去排序，可能会节省性能。

简介：

本质：

优点：

map和multimap区别：

==初始化==：

std::map<std::string, unsigned short> info = {
	{"zhangsan", 13},
	{"lisi", 14}
};

3.2.1 map构造和赋值

函数原型：

构造：

赋值：

#include <iostream>
#include <string>
#include <map>

void printMap(const std::map<int, int> &m) {
	for (std::map<int, int>::const_iterator it = m.begin(); it != m.end(); it++) {
		std::cout << "key:" << (*it).first << " value:" << it->second << endl;
	}
}
void test01() {
	std::map<int, int> m;
	// 放的元素都要是对组
	std::pair<int, int> p1(2, 20);
	std::pair<int, int> p2 = make_pair(3, 30);
	m.insert(p1);
	m.insert(p2);
	// 只能是这样匿名对象
	m.insert(pair<int, int>(5, 50));
	m.insert(pair<int, int>(1, 10));
	printMap(m);  // 会自动排序的

	std::map<int, int> m1(m);  // 拷贝构造

	std::map<int, int> m2;
	m2 = m1;   // 赋值
}

总结：map中所有的元素都是成对出现的，插入数据时要使用对组。

3.2.2 map大小和交换

函数原型：

void printMap(const std::map<int, int> &m) {
	for (std::map<int, int>::const_iterator it = m.begin(); it != m.end(); it++) {
		std::cout << "key:" << (*it).first << " value:" << it->second << endl;
	}
	cout << endl;
}
void test01() {
	std::map<int, int> m;
	std::pair<int, int> p1(2, 20);
	std::pair<int, int> p2 = make_pair(3, 30);
	m.insert(p1);
	m.insert(p2);
	m.insert(pair<int, int>(1, 10));
	std::map<int, int> m1;
	m1.insert(pair<int, int>(6, 60));
	m1.insert(pair<int, int>(5, 50));
	std::cout << "交换前：" << std::endl;
	printMap(m);  // 会自动排序的
	printMap(m1);
	std::cout << "\n交换后：" << std::endl;
	m.swap(m1);
	printMap(m);  
	printMap(m1);
}

3.2.3 map插入和删除

函数原型：

void printMap(const std::map<int, int> &m) {
	for (std::map<int, int>::const_iterator it = m.begin(); it != m.end(); it++) {
		std::cout << "key:" << (*it).first << " value:" << it->second << endl;
	}
	std::cout << std::endl;
}
void test01() {
	std::map<int, int> m;
	// 第一种
	m.insert(std::pair<int, int>(3, 30));
	// 第二种
	m.insert(std::make_pair(2, 20));
	// 第三种
	m.insert(std::map<int, int>::value_type(5, 50));
	// 第四种
	m[1] = 10;

	// 注意这里，key=9是不存在的，
	int a = m[9];
	std::cout << a << std::endl;  // 0
	// 怕那是这样，这个对组(11, 0)也会被加到m中去
	std::cout << m[11] << std::endl;
 	printMap(m);  // 会发现这里会被创建key=10,value=0的对组

	m.erase(m.begin());  // 单纯删除
	// 这会返回下一个元素的迭代器
	std::map<int, int>::iterator it = m.erase(m.begin());
	std::cout << it->first << it->second << std::endl;  // 330

	// 删除容器中元素key=5的对组；
	m.erase(5);
	m.erase(510);  // 删除一个不存在的key没有任何影响
	printMap(m);
}

​ 注意：在map中使用m[key]的时候，无论这出现在哪里，如果key不存在，就一定会向map容器中添加一个key=key，value=0的对组。

注意这种嵌套式写法：

	std::map<std::string, std::map<std::string, std::string>> m;
    m["1"]["1.1"] = "张三";
    m["1"]["1.2"] = "张四";
    m["2"]["2.5"] = "王五";
    m["2"]["2.6"] = "王六";
    for (const auto &fir : m) {
        std::cout << fir.first << std::endl;
        for (const auto &sec : fir.second) {
            std::cout << sec.first << " = " << sec.second << std::endl;
        }
    }

3.2.4 map查找和统计

函数原型：

void test01() {
	std::map<int, int> m;
	m.insert(std::pair<int, int>(1, 10));
	m.insert(std::pair<int, int>(3, 30));
	// 注意find返回的是迭代器
	std::map<int, int>::iterator it = m.find(1);
	if (it != m.end()) {
		std::cout << "找到该元素了" << std::endl;
		std::cout << it->first << ' ' << it->second << std::endl;
	}
	else {
		std::cout << "没找到到就会执行这里" << std::endl;
		// 没找到，返回的就是 m.end()
	}
	std::cout << m.count(2) << std::endl;  // 0
	std::cout << m.count(3) << std::endl;  // 1
}

3.2.5 map容器排序

class MyCompare {
public:
    // 如果是自定义数据类型，定义传参时都还是加上`const`
	bool operator()(int v1, int v2) {
		return v1 > v2;
	}
};
void test01() {
	// 不指定排序方式会自动排序
	// 降序
	std::map<int, int, MyCompare> m;
	m.insert(std::pair<int, int>(1, 10));
	m.insert(std::make_pair(3, 30));
	m.insert(std::map<int, int>::value_type(5, 50));
	m.insert(std::pair<int, int>(2, 20));
	// 下面这种方式在加了排序方式后就编译不通过，就尽量少用
	//m[2] = 20;

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

​ 注意：在有了自定义排序规则时，数据的插入一定不要用m[2] = 20这样的方式，编译通过不了，这种插入方式其它地方也慎用、少用。

3.2.7 下标操作(重要)

以下 c 都是一个map

map: std::map<std::string , size_t> word_count; // 空的map word_count[“hello”] = 2; 这里其实执行了如下操作：

所以说下标运算可能会插入一个新元素，只能对非const的map使用下标操作，即便是只写 word_count[“a_word”]; a_word这个key不存在，也会把这添加进去的，所以要谨慎

map和unordered_map的下标操作：

c[k] 返回关键字为k的元素，如果k不在c中，添加一个关键字为k的元素，并对其进行值初始化

c.at(k) 访问关键字为k的元素，带参数检查，若k不在c中，抛出一个out_of_range异常

所以不确定key是否在map中，且不想修改map时，一定不要去用下标操作。而是用find先查找一下,判断一下再做决定，if (word_count.find(“a_key”) == wor_count.end())

还有一些成员函数操作：lower_bound和upper_bound 这俩不适用于无序容器

于是：如果lowe_bound和upper_bound返回相同的迭代器，则说明给定的关键字不在容器中。一般如果要同时用到lower_bound和upper_bound的话，更好的选择就是用equal_range，就有头有尾，不会需要中间变量。

3.2.6 书上补充

==添加元素==：

a_map.insert({“age”, 13}); a_map.insert(std::make_pair(“age”, 13)); a_map.insert(std::pair<std::string, size_t>(“age”, 13)); a_map.insert(std::map<std::string, size_t>::value_type(“age”, 13));

a_map.emplace(“name”, 13); // 这里a_map的类型是<std::string, int> 这也是插入数据，C++11开始有的，这个成员可以直接传递用于生成对象的参数，对象的创建过程交给容器去执行(其它容器应该也有)。除了emplace_front以外，C++11还提供了emplace和emplace_back方法，分别对应insert和push_back方法

​ 关联性容器，除了有insert插入数据，还有一个a_map.emplace() 好像也是一样的，而且这个函数会返回一个pair数据类型，包含一个迭代器，指向具有指定关键字的元素，以及一个指示插入是否成功的bool值；对于map、set这种不能有重复key的，insert就可能会失败，得到的bool值就是0

std::map<int, int> p;
auto ret1 = p.insert({15, 16});  // ret是pair类型,里面一个迭代器，一个bool
std::pair<std::map<int, int>::iterator, bool> ret = p.insert({5, 10});
// 下面一定要注意括号，少了会因为解析顺序问题而失败
std::cout << (*(ret.first)).first << std::endl;   // 5
std::cout << ret.first->first << std::endl;   // 5
std::cout << (*(ret.first)).second << std::endl;  // 10
std::cout << ret.second << std::endl;   // 1  成功

像是解引用*，++一般都是最后执行的，所以想要让其先运行，就要加括号，好比第4行的，或者++result.first->second，在没有括号时这种就是最后执行++

比如下面这个（单词计数嘛）：

while (std::cin >> word)
	++word_count.insert({word, 0}).first->second;
// 上面的就等价于这：
while (std::cin >> word) {
	auto result = word_count.insert({word, 0});
	++(result.first->second);
}

说明： 若insert成功：先添加一个元素，然后返回一个 pair，pair 的 first元素是一个迭代器。这个迭代器指向刚刚添加的元素，这个元素是pair，然后递增pair的second成员。 若insert失败：递增已有指定关键字的元素的 second成员。

使用（注意返回类型怎么写）：

std::map<std::string, std::vector<int>> m;
	std::pair<std::map<std::string, std::vector<int>>::iterator, bool> ret = m.insert(std::pair<std::string, std::vector<int>>("age", {1, 2, 3}));  // 后面的{1, 2, 3}是vector的一个初始化列表，也可以写成 std::vector<int>{1, 2, 3}

像这种如果类型很长，且这种类型还会经常用到的话，就使用：using retrunType = std::pair<std::map<std::string, std::vector<int»::iterator, bool>

3.2.7 单词计数(以及remove_if使用)

​ 练习：编写一个单词计数程序(忽略大小写和标点符号，如Example、exam!p.le、eXa%mPle*都算作一个)

#include <iostream>
#include <map>
#include <string>
#include <algorithm>
#include <cctype>

int main(int argc, char*argv[]) {
	// 但是这里没导入 cstddef 头文件也能直接使用啊
	std::map <std::string, size_t > word_count;
	std::string word;
	while (std::cin >> word) {
        
        //[&word](char c) {std::tolower(c); };  // 不行
		for (auto &s : word)  // 这能这样变小写，用lambda表达式不行
			s = std::tolower(s);
	
		word.erase(std::remove_if(word.begin(), word.end(), [](char c) { return !std::isalnum(c); }), word.end());
        // remove_if中除了使用lambda外，还可直接使用std::ispunct，
		//word.erase(std::remove_if(word.begin(), word.end(), std::ispunct), word.end());  // 千万注意不能是std::ispunct(),绝对不能有这个括号

		++word_count[word];    // 最关键的统计
	
	}
	for (std::map<std::string, size_t>::const_iterator iter = word_count.begin(); iter != word_count.end(); ++iter) {
		std::cout << iter->first << " occurs " << iter->second << 
			(iter->second > 1 ? " tiems" : " time") << std::endl;
	}
    return 0;
}

说明：

3.2.8 map姓氏练习

一个练习：定义一个map，关键字是家庭的姓，值是一个vector，保存家中孩子（们）的名。编写代码，实现添加新的家庭以及向已有家庭中添加新的孩子。

我的实现:

std::map<std::string, std::vector<std::string>> ped;  // 值是一个vector
ped.insert(std::pair<std::string, std::vector<std::string>>("song", std::vector<std::string>{"hui"}));

std::pair<std::string, std::vector<std::string>> an{ "zhang", std::vector<std::string>{"3", "4"} };
ped.insert(an);  // 或者以这种方式添加

ped["song"].push_back("huang");
ped["chen"].push_back("chao");  // 重点是这样

for (auto &k : ped) {
	std::cout << "姓氏：" << k.first << std::endl;
	for (int i = 0; i < k.second.size(); ++i) {
		std::cout << k.first + k.second.at(i) << "   ";
	}
	std::cout << std::endl;
}

注意：map里一开始是没有’chen’这个key的，也不是通过insert插入进去，这样就会自动创建这个键值对；关联容器一般用insert插入数据，vector这些放数据的时候都是用push_back。

​ 可以定义 vector<int>::iterator 到 int 的map，但是不能定义 list<int>::iterator 到 int 的map。因为map的键必须实现 < 操作，list 的迭代器不支持比较运算。当然还可以自定义类的行为正常的<运算符。

3.3 pair类型

pair是标准库类型(把它看作一种数据类型)，它定义在头文件utility中（在vs中没导入也在直接使用）

功能：成对出现的数据，利用对组可以返回两个数据

两种创建方式：

void  test01() {
	std::pair<string, int> p1("张三", 13);
	std::pair<string, int> p2 = make_pair("李四", 14);
	std::cout << "姓名：" << p1.first << " 年龄：" << p1.second;
}

用first获取对组的第一个元素，second获取对组的第二个元素。

std::pair<T1, T2> P;
std::pair<T1, T2> P(V1, V2);   // 这里花括号也是可以的，但是早期c++是不让用花括号的
std::pair<T1, T2> P = {V1, V2};  // 等价于P(V1, V2)，注意这种写法
P = std::make_pair(V1, V2);
p1 == p2  当first和second成员分别相等时才等

假设vec是一个存放pair数据类型的vector,那么就可以有如下三种形式：

vec.push_back(std::pair<std::string, int>(str, num));
vec.push_back({str, num});
vec.push_back(std::make_pair(str, num));

注意：这个pair和map的数据类型是不一样的，，map使用insert(pair数据)

3.4 tuple类型(==放任意数据类型==)

类似于实现python的检测结果，[name, conf, position]：[[“YBKC”, 0.89, [11, 22, 33, 44]], [“XDSC”, 0.59, [77, 88, 99, 10]]]

#include <tuple>
#include <string>
#include <vector>
#include <iostream>

// 定义出来类型
using detectType = std::tuple<std::string, float, std::vector<int>>;

// 放入数据
std::vector<detectType> vec;
vec.push_back({ "YBKC", 0.5, {1, 2, 3, 4} });
vec.push_back({ "XDSC", 0.78, {4, 5, 6, 7} });

// 拿数据，方式一：（这里要不了那么多，还可以用std::ignore占位）
std::string name;
float conf;
std::vector<int> position;
for (detectType& item : vec) {
	std::tie(name, conf, position) = item;
	std::cout << name << ": " << conf << std::endl;
}
// 拿数据，方式二：
for (detectType& item : vec) {
	std::string name = std::get<0>(item);
	float conf = std::get<1>(item);
	std::vector<int> position = std::get<2>(item);
	std::cout << name << ": " << conf << std::endl;
}

下面有详细的解释。

​ tuple是类似pair的模板，它里面可以任意数量的不同数据类型,可以将其看作一个“快速而随意”的数据结构，定义在头文件#include <tuple>，

==定义==：当定义一个tuple时，需要指出每个成员的类型：

std::tuple<size_t, size_t, size_t> t1;    // 三个成员都设置为0
std::tuple<std::string, std::vector<double>, int, std::list<int>>
    someVal{"constants", {3.14, 2.718}, 42, {0, 1, 2, 3, 4, 5}};

注意：

当然除了以上定义，类似piar的make_pair函数，标准库定义了std::make_tuple函数，可用它来生成tuple对象：auto item = std::make_tuple("nihao", 42, 20.00);这个函数使用初始值类型来推断tuple的类型，这里的类型为tuple<const char*, int, double>。

==访问tuple的成员==： 使用一个名为==get==的标准库函数模板(业绩的tuple头文件)，必须指定一个显式模板参数，指出我们想要访问第几个成员，再传递给get一个tuple对象，它==返回指定成员的引用==：使用上面定义的someVal

auto name = std::get<0>(someVal);     // 返回第一个成员
auto li = std::get<1>(someVal);
auto res1 = std::get<2>(someVal) / 2;   // 返回第二成员的值除以2的结果
std::get<2>(someVal) *= 2;      
std::cout << std::get<2>(someVal) << std::endl;   // 84了

特别注意：

==获取成员类型即数量==： 如果不知道一个tuple准确的类型信息，可以用两个辅助类模板std::tuple_size、std::tuple_element来查询tuple成员的数量和类型：

std::tuple<std::string, std::vector<double>, int, std::list<int>, int> 
	someVal{ "constants", {3.14, 2.718}, 42, {0, 1, 2, 3, 4, 5}, 12 };

typedef decltype(someVal) trans;   // trans就是someVal的类型
size_t number = std::tuple_size<trans>::value;  // 5（注意结果是5，而不是4）

std::tuple_element<1, trans>::type cnt = std::get<1>(someVal);  // cnt是一个vector

解读：

​ 再来一点：tuple定义了<和==这样的比较运算符，可以将tuple序列传递给算法，并且可以在无序容器中将tuple作为关键字类型。两个tuple想要比较大小或等不等这些，那成员数量一定要先一致，成员的数据类型也要一样才能比较。

​ 以往有多个数据类型时，就是用struct结构体来进行封装，其实没那么灵活，现在就可以用tuple来装，然后再使用==typedef 一个tuple类型 另外一个别名==，或者==using my_name = std::tuple<int, float, bool>==,这两种方式来简单使用。

在图形学中学会的补充： 现在有这样一个函数：std::tuple<float, float, float> compute(){return {c1,c2,c3};}

bitset类型

​ ==bitset==类，使得位运算的使用更为容易，并且能够处理超过最长整数类型大小的位集合。bitset类定义在#include <bitset>中。

这里就不详写了，如果以后有用到，来看书自己右上标的==641页==。

3.5 关联容器删除点

假定c是关联容器：

3.6 获取关联容器数据类型

key_type value_type mapped_type (后面这个是map类型(unorder_map等等)特有的，是相当于set的value_type)

std::set<int>::key_type v1;   // int
std::set<int>::value_type v2;  //int

std::map<std::string, int>::key_type m1;   // string
std::map<std::string, int>::value_type m2;  // 注意：这个结果类型是 pair<const string, int>
std::map<std::string, int>::mapped_type m3;  // 值的类型，int

注意：map的value_type的类型是一个pair，第一个值是key的类型(是有const不可修改的)，第二个值是value的类型，是不同于set的。

set同时定义了iterator和const_iterator两种迭代器类型，但都是只读的，像map的key不能修改一样,set数据都是const的

3.7 案例-员工分组

案例描述：

实现步骤：

  1. 创建10名员工，放到vector中
  2. 遍历vector容器，取出每个员工，进行随机分组
  3. 分组后，将员工部门编号作为key，具体员工作为value，放入到multimap容器中
  4. 分部门显示员工信息
#include <iostream>
#include <string>
#include <vector>
#include <map>

class Person {
public:
	// 部门的枚举值
	enum Department { scheme = 10, arts = 11, develop = 12 };  

	std::string m_Name;  
	int m_Salary;   // 薪酬
	Department m_Depart;  // 部门
};

void insertPerson(std::vector<Person> &v) {
	std::string name_ids = "ABCDEFGHIJ";
	Person p;
	for (int i = 0; i < 10; i++) {
		p.m_Name = name_ids[i];
		p.m_Salary = std::rand() % 1001 + 1000;
		// 员工随机部门
		int sec = std::rand() % 3 + 10;
		switch (sec) {
		case 10:
			p.m_Depart = Person::scheme;
			break;
		case 11:
			p.m_Depart = Person::arts;
			break;
		case 12:
			p.m_Depart = Person::develop;
			break;
		default:
			break;
		}
		v.push_back(p);
	}
}

// 重载版本(1)
std::ostream& operator<<(std::ostream &cout, std::vector<Person>::const_iterator it) {
	std::cout << "员工编号：" << it->m_Name << "\t员工工资：" << it->m_Salary << "\t员工部门编号：" << (*it).m_Depart;
	return cout;
}
// 重载版本(2)
std::ostream& operator<<(std::ostream &cout, const Person &p) {
	std::cout << "员工编号：" << p.m_Name << "\t员工工资：" << p.m_Salary << "\t员工部门编号：" << p.m_Depart;
	return cout;
}
void printPerson(const std::vector<Person> &v) {
	// 打印方式1
	for (std::vector<Person>::const_iterator it = v.begin(); it != v.end(); it++) {
		// 这也是普通打印
		std::cout << "员工编号：" << it->m_Name << "\t员工工资：" << it->m_Salary << "\t员工部门编号：" << (*it).m_Depart << std::endl;
		// 重载版本(1)
		std::cout << it << std::endl;
	}
	std::cout << "*********************" << std::endl;
	// 打印方式2
	for (int i = 0; i < v.size(); i++) {
		// 这是普通打印
		std::cout << "员工编号：" << v[i].m_Name << "\t员工工资：" << v[i].m_Salary << "\t员工部门编号：" << v[i].m_Depart << std::endl;
		// 重载版本(2)
		std::cout << v[i];  
		// 注意这个重载，函数传进来的是const vector<Person> &v,是有const的；那么重载时一定要写const Person &p，不能少了const，不然类型不对
	}
}

// 1、简单排序
void test01() {
	std::vector<Person> v;
	// 插入10个员工
	insertPerson(v);  // 可以看看这
	// 打印信息(写的比较全，很多方法，重载版本)
	//printPerson(v);

	std::multimap<Person::Department, Person> mm;
	for (std::vector<Person>::iterator it = v.begin(); it != v.end(); it++) {
		mm.insert(pair<Person::Department, Person>(it->m_Depart, *it));
	}
	// count计数，multimap的key是可以重复的，
	std::cout << mm.count(Person::Department(Person::Department::develop)) << std::endl;  // 5

	// 再试用一下查找find
	std::multimap<Person::Department, Person>::iterator it = mm.find(Person::Department::arts);
	if (it != mm.end()) {
		// 这个find得到的是第一个key的位置，相同key肯定是连续的；这里不能用迭代器到mm.end()，会把后面所有的都遍历出来
		for (int i = 0; i < mm.count(Person::Department::arts); i++) {
			std::cout << "部门编号：" << it->first
				<< " 员工编号：" << it->second.m_Name
				<< " 薪酬：" << it->second.m_Salary << std::endl;
			it++;
		}
	}
}

class MyCompare {
public:
	bool operator()(const Person::Department &d1, const Person::Department &d2) {
		return d1 > d2;
	}
};
// 2、自定义排序
void test02() {
	std::vector<Person> v;
	// 插入10个员工
	insertPerson(v);
	// 自定义部门升序排列
	std::multimap<Person::Department, Person, MyCompare> mm;
	for (std::vector<Person>::iterator it = v.begin(); it != v.end(); it++) {
		mm.insert(pair<Person::Department, Person>(it->m_Depart, *it));
	}
	// 打印的时候也要跟上排序的仿函数(部门为key，排了序，算是分部门打印了吧)
	for (std::multimap<Person::Department, Person, MyCompare>::iterator it = mm.begin(); it != mm.end(); it++) {
		std::cout << it->first << ' ' << it->second.m_Name << ' ' << it->second.m_Salary << std::endl;
	}
	// 注意：用了自定义排序后，这count、find就编译不通过了，不知道咋解决
	//mm.count(Person::Department(Person::Department::develop));
	//multimap<Person::Department, Person, MyCompare>::iterator it = mm.find(Person::Department::develop);
}	

int main() {
	test01();
	std::cout << "*********" << std::endl;
	test02();
	system("pause");
	return 0;
}

四、STL-函数对象

4.1 函数对象

概念：

本质：函数对象(仿函数)是一个类，不是一个函数

函数对象使用，特点：

class MyAdd {
public:
	int operator()(int v1, int v2) {
		return v1 + v2;
	}
};
class MyPrint {
public:
	void operator()(std::string &s) {
		cout << s << endl;
	}
};

// 注意这里如果是引用string &s,那下面传参数时不能直接给"hello"
void doPrint(MyPrint &mp, string s) {
	mp(s);
}
void test01() {
	// 1、可以有参数、返回值
	MyAdd myadd;
	cout << myadd(10, 20) << endl;
	// 注意匿名对象是这样调用的
	cout << MyAdd()(10, 20) << endl;

	// 2、 可以自己的状态（解读就是因为这是类，可以有其它的属性值，记录自己的内部状态）

	// 3、 函数对象作为参数传递
	MyPrint myPrint;
	doPrint(myPrint, "hello");
}

4.2 谓词

谓词概念：返回bool类型的仿函数称为==谓词==

4.2.1 一元谓词

例：找数组中有没有大于5的数

// 一元谓词（5写死了不太好）
struct GtraterFive {
	bool operator()(int val) {
		return val > 5;
	}
};

// 这也是对函数对象，有自己内在属性的一个解释
class MyGreater {
public:
	// 构造函数
	explicit MyGreater(int value):point_value(value) {}
	// explicit关键字，启用显示转换，禁止隐式转换(更多的是针对一个参数)

	bool operator()(int val) {
		return val > this->point_value;
	}

	int point_value;
};

void test01() {
	std::vector<int> v;
	for (int i = 0; i < 10; i++) {
		v.push_back(i);
	}
	// GtraterFive()这是匿名对象，也可以先另起一行声明一个对象
	// find_if是算法<algorithm>中的，接收三个参数：开始、结束、谓词(参数名称是有Pred的，就是代表谓词);返回值也是迭代器；这个就是找有没有满足条件的
	//vector<int>::iterator it = find_if(v.begin(), v.end(), GtraterFive());  // 以前简单谓词的写法，把大于的值——5是写死了的
	std::vector<int>::iterator it = find_if(v.begin(), v.end(), MyGreater(6));  // 匿名对象，再`()`初始化，就等于普通函数名了，
	// 找到了返回找到的位置(看源码定义,一满足条件就会break退出不再找了)，没有找到就是返回v.end()
	if (it == v.end()) {
		std::cout << "未找到大于5的数" << std::endl;
	}
	else {
		std::cout << "找到了大于5的数：" << *it << std::endl;  // 6
	}
}
explicit关键字

​ 一般约定所有单参数的构造函数都必须是显示的，就用关键字explicit声明，只有极少数情况下拷贝构造函数可以不声明称explicit。参考。

前提，类Person的构造函数只有一个参数string的name，简单来说，显示就必须是Person p1(“张三”);而不能是隐式的Person p2 = “张三”; 而且传递的参数类型就必须直接是定义的数据类型，不能发生隐式转换，如：定义一个函数 void f(std::vector<int>); 那么

f(10); // 错误，不能用一个explicit的拷贝一个实参(我的理解就是不能隐式转换) f(std::vector<int>(10)); // 正确，从一个int直接构造一个临时的vector

4.2.2 二元谓词

给数组降序排列：

void printVector(const vector<int> &v) {
	for (std::vector<int>::const_iterator it = v.begin(); it != v.end(); it++) {
		std::cout << *it << std::endl;
	}
}
// 二元谓词
class MyCompare {
public:
	bool operator()(int v1, int v2) {
		return v1 > v2;
	}
};
void test01() {
	std::vector<int> v;
	v.push_back(20);
	v.push_back(50);
	v.push_back(10);
	v.push_back(30);
	v.push_back(40);
	printVector(v);
	std::cout << "升序排列：" << std::endl;
	sort(v.begin(), v.end());  // 注意都是要给区间的迭代器
	printVector(v);
	std::cout << "降序排列：" << std::endl;
	// 匿名对象
	std::sort(v.begin(), v.end(), MyCompare());  // 要头文件 <algorithm>
	printVector(v);
	// 这升序就是默认的版本，默认就是v1<v2；后再给二元谓词参数的sort就是系统重载的版本
}

4.3 内建函数对象

STL中内建了一些函数对象(即写了一些仿函数)

分类：

用法：

4.3.1 算数仿函数

功能描述：

仿函数原型：

#include <functional>
void test01() {
	// 要导入头文件<functional>
	negate<int> n;  
	// 直接当仿函数那样使用
	std::cout << n(15) << std::endl;  // -15

	// 两个参数，参数列表应该是两个，但是同为int才能加，所以就一个int就行了
	plus<int> p;
	std::cout << p(10, 20) << std::endl;  // 30
}

4.3.2 关系仿函数

功能描述：实现各种关系对比

仿函数原型：

实例greater，等同于我们自己用类实现的仿函数(重载`()`)的降序排序

void printVector(const vector<int> &v) {
	for (std::vector<int>::const_iterator it = v.begin(); it != v.end(); it++) {
		std::cout << *it << std::endl;
	}
}
class MyCompare {
public:
	bool operator()(int v1, int v2) {
		return v1 > v2;
	}
};
void test01() {
	std::vector<int> v;
	v.push_back(30);
	v.push_back(10);
	v.push_back(50);
	v.push_back(20);
	v.push_back(40);

	// 1、自己实现的仿函数降序排序
	//std::sort(v.begin(), v.end(), MyCompare());

	// 2、模板，头文件<algorithm>带的
	std::sort(v.begin(), v.end(), std::greater<int>());
	// 这里看定义，如果只传前两个参数，默认用了less<>()
	// 传三个参数，就是又一个重载版本

	printVector(v);
}

4.3.3 逻辑仿函数

功能描述：实现逻辑运算

函数原型：

简单示例一个非

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

void test01() {
	std::vector<bool> v;
	v.push_back(true);
	v.push_back(false);
	v.push_back(true);
	v.push_back(false);

	std::vector<bool> v2;
	v2.resize(v.size());
	// 逻辑非  将v容器搬运到v2中，并执行逻辑非运算
	std::transform(v.begin(), v.end(), v2.begin(), std::logical_not<bool>());
    // std::logical_not 需要头文件 <functional>
}

五、STL-常用算法

概述：

特定容器算法：

​ 链表类型list和forward_list，定义了独有的sort、merger、remove、reverse、unique，通用版本的sort要求随机访问迭代器，就不能用于list和forward_list。所以对于list和forward_list，应该优先使用成员函数版本的算法而不是通用算法(一些能用的通用算法代价会高很多)。

链表类型还定义了==splice==算法，是链表数据结构所特有的，因此不需要通用版。

5.0 一些命名规则

5.1 常用遍历算法

5.1.1 for_each

功能：实现遍历容器,需要头文件<algorithm>

函数原型：

// 1、函数：因为要去使用的地方就int的vector
void printVector(int val) {
	std::cout << val << ' ';
}
// 2、仿函数
class Print02 {
public:
	void operator()(int val) {
		std::cout << val << ' ';
	}
};
void test01() {
	std::vector<int> v;
	for (int i = 0; i < 10; i++) {
		v.push_back(i);
	}
	// 1、两个迭代器，自己写的对vector的操作的函数名
	std::for_each(v.begin(), v.end(), printVector);
	std::cout << std::endl;

	// 2、仿函数(放的是匿名对象)
	std::for_each(v.begin(), v.end(), Print02());
	cout << endl;
	// ，也可以先初始化一个对象再放进去
	Print02 p02;
	std::for_each(v.begin(), v.end(), p02);
}

5.1.2 transform

功能描述：搬运一个容器的数据到另外一个容器中,需要头文件<algorithm>

函数原型：

class Print02 {
public:
	void operator()(int val) {
		std::cout << val << ' ';
	}
};
class MyTransform {
public:
	int operator()(int val) {
		 // 这就是把原数据+100后再搬运，也可以原样搬运
		return val + 100;
	}
};
void test01() {
	std::vector<int> v;
	for (int i = 0; i < 10; i++) {
		v.push_back(i);
	}
	std::for_each(v.begin(), v.end(), Print02());
	std::cout << std::endl;  // 这是源容器

	std::vector<int> targetV;
	// 必须要先开辟一个空间才能搬运，不然直接报错 // 更新，或者直接使用std::back_inserter
	targetV.resize(v.size());
	// 使用自动填充后，记得自己加`()`啊，总不是忘记
	std::transform(v.begin(), v.end(), targetV.begin(), MyTransform());
    std::transform(v.begin(), v.end(), std::back_inserter(targetV), MyTransform());
    // 以上两行是一个效果，第二个就不用先去resize开辟空间了，所以推荐这个
	std::for_each(targetV.begin(), targetV.end(), Print02());
    
    // 更新。直接用它把string小写改大写(主要是第三个参数，目标容器就是它本身)
    std::string name = "zhangsan";       // 强推这个，直接变更本身，就不去创建新的容器了。
    std::transform(name.begin(), name.end(), name.begin(), 
                   [](const char c){return std::toupper(c);});
}

注意：

5.2 常用查找算法

5.2.1 find

​ 功能描述：查找指定元素，找到就返回指定元素的迭代器(就会退出，后面的就不找了)；找不到就返回迭代器end().,头文件<algorithm>

函数原型：

#include <algorithm>
// 1、内置数据类型
void test01() {
	std::vector<int> v;
	for (int i = 0; i < 10; i++) {
		v.push_back(i);
	}
	std::vector<int>::iterator it = std::find(v.begin(), v.end(), 50);
	if (it == v.end()) {
		std::cout << "这就是没找到该元素，或说该元素不存在于此容器" << endl;
	}
	else {
		std::cout << "找到该元素，为：" << *it << std::endl;
	}
}

// 2、 自定义数据类型
class Person {
public:
	std::string m_Name;
	int m_Age;
	Person(string name, int age) {
		this->m_Name = name;
		this->m_Age = age;
	}
	// 特别注意这里，因为是底层的`==`对比，不能修改值，一定要加const，不然就是错的
	bool operator==(const Person &p) {
		if (this->m_Age == p.m_Age && m_Name == p.m_Name) {
			return true;
		}
		return false;
	}
};
void test02() {
	std::vector<Person> v;
	Person p1("aa", 10);
	Person p2("bb", 20);
	Person p3("cc", 30);
	v.push_back(p1);
	v.push_back(p2);
	v.push_back(p3);
	Person p("cc", 30);
	// 底层也是用`==`去作对比的，自定义数据类型就需要重载`==`
	std::vector<Person>::iterator it = std::find(v.begin(), v.end(), p);
	if (it == v.end()) {
		std::cout << "没有找到该人" << std::endl;
	}
	else {
		std::cout << "找到该人，姓名：" << it->m_Name << " 年纪：" << (*it).m_Age << std::endl;
	}
}

注意：

除了作用于容器，还可以作用于数组,那它的返回值就是对应数组类型的指针：

#include <iostream>
#include <algorithm>
int main() {

	int arr[] = { 11, 22, 33, 44, 55 };
    // 不太确定类型是怎么写的时候，可用auto
	int *out = std::find(std::begin(arr), std::end(arr), 222);
	if (out == std::end(arr)) {
		std::cout << "无" << std::endl;
	}
	return 0;
}

甚至可以通过运算指定范围查找：

int arr[] = { 11, 22, 33, 44, 55 };
auto out = std::find(arr+1, arr+4, 222);  // 这里是右开的，是不包括arr[4]这个数据的

5.2.2 find_if

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

函数原型：

// 1、内置数据类型
class Greater5 {
public:
	bool operator()(int val) {
		return val > 5;
	}
};
void test01() {
	std::vector<int> v;
	for (int i = 0; i < 10; i++) {
		v.push_back(i);
	}
	std::vector<int>::iterator it = std::find_if(v.begin(), v.end(), Greater5());
	// 注意这里找到第一个就会退出了，得到的也是找到的第一个的位置
	if (it == v.end()) {
		std::cout << "这就是没找到该元素，或说该元素不存在于此容器" << std::endl;
	}
	else {
		std::cout << "找到该元素，为：" << *it << std::endl;
	}
}

// 2、 自定义数据类型
class Person {
public:
	std::string m_Name;
	int m_Age;
	Person(std::string name, int age) {
		this->m_Name = name;
		this->m_Age = age;
	}
};
// 查找年龄>10的
// (1)、一元谓词
class Greater10 {
public:
	bool operator()(const Person &p) {
		return p.m_Age > 10;
	}
};
// (2)、仿函数（上面才是仿函数啊，这就是一个普通函数啊）
bool myGreater10(const Person &p) {
	return p.m_Age > 10;
}
void test02() {
	std::vector<Person> v;
	Person p1("aa", 10);
	Person p2("bb", 20);
	Person p3("cc", 30);
	v.push_back(p1);
	v.push_back(p2);
	v.push_back(p3);
	// 看这个参数，第三个参数是要`谓词`
	//vector<Person>::iterator it = find_if(v.begin(), v.end(), Greater10());
	// 或者使用仿函数
	std::vector<Person>::iterator it = std::find_if(v.begin(), v.end(), myGreater10);
	if (it == v.end()) {
		std::cout << "没有找到该人" << std::endl;
	}
	else {
		std::cout << "找到该人，姓名：" << it->m_Name << " 年纪：" << (*it).m_Age << std::endl;
	}
}

​ 总结：find_if按条件查找使查找更加灵活，提供的仿函数可以改变不同的策略。

find_first_of

字符串中，其它的查找方法：

一个练习(挺重要，写法思想挺有意思，用来==查找字符串中是否包含或是不包含另一组字符串中任意一个字符==)： 首先查找字符串”ab2c3d7R4E6a”中的每个数字字符并打印，然后查找其中给的每个字母字符，两个版本，第一个用find_first_of,第二个用find_first_not_of：

#include <iostream>
#include <string>
int main(int argc, char **argv) {
	std::string number("0123456789");
	std::string str("ab2c3d7R4E6a");
	// 找数字
	for (int pos = 0; (pos = str.find_first_of(number, pos)) != std::string::npos; ++pos) {
		std::cout << str[pos] << " ";
	}
	// 找字母
	for (int pos = 0; (pos = str.find_first_not_of(number, pos)) != std::string::npos; ++pos) {
		std::cout << str[pos] << " ";
	}
	return 0;
}

特别重要的Tips：

std::string::npos

直接看上面，有说明，find也会经常用，可见leetcode的796题。

5.2.3 adjacent_find

功能描述：查找相邻重复元素

函数原型：

void test01() {
	std::vector<int> v;
	v.push_back(10);
	v.push_back(30);  // 输出的就是这个30
	v.push_back(30);
	v.push_back(10);
	v.push_back(30);
	std::vector<int>::iterator it = adjacent_find(v.begin(), v.end());
	if (it == v.end()) {
		std::cout << "没有" << std::endl;
	}
	else {
		std::cout << *it << std::endl;
	}
}

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

函数原型：

void test01() {
	std::vector<int> v;
	for (int i = 0; i < 10; i++) {
		v.push_back(i);
	}
	// 得到的是bool值
	bool ret = std::binary_search(v.begin(), v.end(), 5);
	if (ret) {
		std::cout << "找到了,容器中有该元素" << std::endl;
	}
	else {
		std::cout << "没找到" << std::endl;
	}
}

总结：

5.2.5 count

功能描述：统计元素个数(也可以说是出现次数)

函数原型：

对自定义数据类型，找指定年龄的有多少个

#include <algorithm>
// 1、内置数据类型
void test01() {
	std::vector<int> v;
	for (int i = 0; i < 10; i++) {
		v.push_back(5);
	}
	int nums = std::count(v.begin(), v.end(), 5);  // 10个
	std::cout << nums << std::endl;
}

// 2、 自定义数据类型
class Person {
public:
	std::string m_Name;
	int m_Age;
	Person(string name, int age) {
		this->m_Name = name;
		this->m_Age = age;
	}
	// 底层也是用的`==`来对比，一定要加const
	// 自定义数据类型一定要重载`==`，返回布尔值，说明怎么才是相等
	bool operator==(const Person &p) {
		if (this->m_Age == p.m_Age) {
			return true;
		}
		return false;
	}
};
void test02() {
	std::vector<Person> v;
	Person p1("aa", 10);
	Person p2("cc", 20);
	Person p3("aa", 10);
	Person p4("aa", 15);
	v.push_back(p1);
	v.push_back(p2);
	v.push_back(p3);
	v.push_back(p4);
	Person p("dd", 10);
    // 这就是查找跟p年龄相同的人的个数
	int nums = std::count(v.begin(), v.end(), p);
	std::cout << nums << std::endl;  // 2
}

​ 注意：自定义数据类型，内部一定要重载bool operator==() {},内部说明怎么才算是相等。

还有一个点注意：（std::find对string来说也是这样）

// a_str 是 std::string类型
int mun = std::count(a_Str.begin(), a_tarStr.end(), 'l');  // 这是ok的，因为a_Str的个体是char，所以查找char没问题，但是后面查找的内容不能是std::string，即以下是错的的
int mun = std::count(a_Str.begin(), a_tarStr.end(), "lol");

5.2.6 count_if

功能描述：获取满足条件的元素的个数

函数原型：

// 1、内置数据类型
bool greater20(int val) {
	return val > 5;  // 仿函数（这是普通函数）
}
void test01() {
	std::vector<int> v;
	for (int i = 0; i < 10; i++) {
		v.push_back(i);
	}
	// 用的仿函数（不是是不是当时理解错了，这就是普通函数啊），也可以放谓词，获取大于5个元素个数
	int nums = std::count_if(v.begin(), v.end(), greater20);  
	std::cout << nums << std::endl;
}

// 2、 自定义数据类型
class Person {
public:
	std::string m_Name;
	int m_Age;
	Person(string name, int age) {
		this->m_Name = name;
		this->m_Age = age;
	}
};
// 用的谓词(谓词是这样写的，要重载`bool operator()() {}`)
class Greater10 {
public:
	bool operator()(const Person &p) {
		return p.m_Age > 10;
	}
};
void test02() {
	std::vector<Person> v;
	Person p1("aa", 10);
	Person p2("cc", 20);
	Person p3("aa", 10);
	Person p4("aa", 15);
	v.push_back(p1);
	v.push_back(p2);
	v.push_back(p3);
	v.push_back(p4);
	// 查找年龄大于10的
	int nums = std::count_if(v.begin(), v.end(), Greater10());
	std::cout << nums << std::endl;  // 2
}

​ 总结：这种带if,按条件查询的，都要给一个谓词(写的类，重载的()，返回的是布尔值)，或是给仿函数。

5.3 常用排序算法

5.3.1 sort

函数原型：需要头文件<algorithm>

void myPrint(int val) {
	std::cout << val << ' ';
}
// 1、方法1，重载`()`来做谓词，仿函数
class Sort01 {
public:
	bool operator()(int v1, int v2) {
		return v1 > v2;
	}
};
// 2、方法2，直接写一个返回bool值的函数
bool Sort02(int v1, int v2) {
	return v1 > v2;
}
void test01() {
	std::vector<int> v;
	v.push_back(30);
	v.push_back(10);
	v.push_back(50);
	v.push_back(20);
	v.push_back(40);
	std::sort(v.begin(), v.end());  // 默认降序
	std::for_each(v.begin(), v.end(), myPrint);
	std::cout << std::endl;
	// 需要一个谓词，三种方法
	// 方法1
	//sort(v.begin(), v.end(), Sort01());

	// 方法2(注意函数千万不要给括号，上面是匿名对象)
	//sort(v.begin(), v.end(), Sort02);

	// 方法3（内建函数对象）(还是导入头文件<functional>，兼容低版本)
	std::sort(v.begin(), v.end(), std::greater<int>());
	std::for_each(v.begin(), v.end(), myPrint);
}

5.3.2 random_shuffle

功能描述：指定范围内的元素随机调整次序

函数原型：

void test01() {
	std::vector<int> v;
	for (int i = 0; i < 10; i++) {
		v.push_back(i);
	}
	// 设了随时间的随机种子，每次才不一样；记得头文件<ctime>
	std::srand((unsigned int)time(NULL));
	std::random_shuffle(v.begin(), v.end());
}

5.3.3 merge

功能描述：将两个容器元素合并，并存储到另一容器中

函数原型：

void test01() {
	std::vector<int> v1, v2;
	for (int i = 0; i < 10; i++) {
		v1.push_back(i);
		v2.push_back(i + 1);
	}
	std::vector<int> vTarget;
	// 目标容器必须要先开辟空间
	vTarget.resize(v1.size() + v2.size());
	std::merge(v1.begin(), v1.end(), v2.begin(), v2.end(), vTarget.begin());
}

​ 注意：v1、v2必须是两个有序的序列，且要么都是升序，要么都是降序；得到的目标容器也是有序的。

5.3.4 reverse

函数原型：

std::reverse(v.begin(), v.end());

5.4 常用拷贝和替换算法

5.4.1 copy

功能描述：容器内指定范围内的元素拷贝到另一容器中

函数原型：

void myPrint(int val) {
	std::cout << val << ' ';
}
class Print02 {
public:
	void operator()(int val) {
		std::cout << val << ' ';
	}
};
void test01() {
	std::vector<int> v1;
	for (int i = 0; i < 10; i++) {
		v1.push_back(i);
	}
	std::vector<int> v2;
	v2.resize(v1.size());  // 记得先给空间
	std::copy(v1.begin(), v1.end(), v2.begin());
	std::for_each(v2.begin(), v2.end(), myPrint);
	std::cout << std::endl;
	std::for_each(v2.begin(), v2.end(), Print02());
}

总结：

std::copy 这个是不需要什么头文件的

#include <iostream>
int main() {
	int a1[] = { 0, 1, 2, 3, 4, 5 };
	int a2[sizeof(a1) / sizeof(*a1)];
    // 核心是这行代码
	auto ret = std::copy(std::begin(a1), std::end(a1), std::begin(a2));
	return 0;
}

​ std::copy接受3个参数，前两个表示一个输入范围，第三个表示目的序列的起始位置(所以上面第6行代码的第3个参数可以直接写成 a2 也行)，copy返回的是其目的位置迭代器(递增后)的值，即ret恰好指向拷贝到a2的微博元素之后的位置。

5.4.2 replace

功能描述：将容器内指定范围内的旧元素改为新元素

函数原型：

void test01() {
	std::vector<int> v;
	v.push_back(10);
	v.push_back(20);
	v.push_back(20);
	v.push_back(30);
	std::for_each(v.begin(), v.end(), myPrint);
	std::cout << std::endl;
	// 核心是这行;将容器中所有20换成50
	std::replace(v.begin(), v.end(), 20, 50);

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

注：std::replace除了只能给iterator后，还可以给位置，特别是对string，非常友好：

例：a_str.replace(1, 2, std::string(5, ‘a’)); // 从索引为1开始往后2个字符被替换成5个a

std::replace(str.begin(), str.end(), ‘c’, ‘a’); // 传统的给迭代器，是把所有的c换成a，而且这里的值只能给char，不能是string

replace_copy

​ 使用replace时都是会改变原来的容器中的值，如果不想改变源容器中的值，想把提替代后的值重新放一个容器，那就是 std::replace_copy

#include <iostream>
#include <vector>
#include <list>
#include <algorithm>     // 需要这个头文件
int main() {
	std::list<int> li{0, 1, 2, 0, 1, 2};
	std::vector<int> vec;
    // 核心是下面这行代码
	std::replace_copy(li.cbegin(), li.cend(), std::back_inserter(vec), 0, 42);
	return 0;
}

​ 解释：这个就比replace多了一个参数，std::back_inserter(vec)，然后vec中的值就是li中的0改成42后的数据。li中的数据是保持不变的。

​ 这里一个注意点：书上提到过，标准库算法不会改变他们所操作容器的大小，为什么使用std::back_inserter不会使这一断言失效？ ​ 答：back_inserter是插入迭代器，在iterator.h头文件中(但试验下来好像vs、linux都不需要导入头文件就能用)，不是标准库的算法。

5.4.3 replace_if

功能描述：将区间内满足条件的元素，替换成指定元素

函数原型：

class Print02 {
public:
	void operator()(int val) {
		std::cout << val << ' ';
	}
};
class GreaterEqual20 {
public:
	bool operator()(int val) {
		return val >= 20;
	}
};
bool gre_equ20(int val) {
	return val >= 20;
}
void test01() {
	std::vector<int> v;
	v.push_back(10);
	v.push_back(20);
	v.push_back(20);
	v.push_back(30);
	std::for_each(v.begin(), v.end(), Print02());
	std::cout << std::endl;

	// 核心是这行,将大于等于20的元素置为50
	//replace_if(v.begin(), v.end(), GreaterEqual20(), 50);  // 1、（谓词）（仿函数）的实现
	std::replace_if(v.begin(), v.end(), gre_equ20, 50); // 两行的效果是一模一样的，2、这是是全局函数的实现
    std::replace_if(v.begin(), v.end(), [](int i) {return i >= 20; }, 50);  // 3、使用lambda函数的实现；；这里lambda表达式之所以是 int i ，是因为vector中的元素是 int 

	for (int i = 0; i < v.size(); i++) {
		std::cout << v[i] << ' ';
	}
}

​ 总结：谓词也是仿函数，现在就下定论了，凡是参数是_Pred(就是谓词(谓词又是类内重载()的))，其实也就是仿函数，都是可以用一个返回布尔值的全局函数来替代，反之亦然。

​ 这种带有if的都是可以自定义满足的条件的。

练习：结合上面replace_if中的代码查看，这里就只放了一点核心代码：

// v中元素 10 20 20 30
std::vector<int> v2;
// 方式一：dest直接使用v2.begin()
//v2.resize(v.size());   // 那一定需要这行，必须初始化，不然下面一定报错(这时v2中元素0 0 0 0)
//std::replace_copy_if(v.begin(), v.end(), v2.begin(), [](int i) {return i >= 20; }, 50);

// 方式二：直接使用std::back_inserter(v2),就不需要上面初始化resize
std::replace_copy_if(v.begin(), v.end(), std::back_inserter(v2), [](int i) {return i >= 20; }, 50);

replace(beg, end, old_val, new_val); // 直接把old_val替换掉 replace_if(beg, end, pred, new_val); // 使用谓词判断，慢足条件的替换掉 replace_copy(beg, end, dest, old_val, new_val); // 复制所有值到新容器，再在新容器内把old_val替换成new_val replace_copy_if(beg, end, dest, pred, new_val); // 上面只能是替换掉指定旧值，带if的就是自己写谓词条件

5.4.4 swap

功能描述：互换两个==相同类型==容器的元素

函数原型：

void test01() {
	std::vector<int> v1;
	v1.push_back(10);
	v1.push_back(20);
	std::vector<int> v2;
	v2.push_back(333);
	v2.push_back(555);

	std::swap(v1, v2);
}

5.5 常用算术生成算法

这属于小型算法，使用的时候记得包含头文件#include <numeric>

5.5.1 accumulate

功能描述：计算区间内，容器元素累计总和

函数原型：

#include <iostream>
#include <vector>
#include <numeric>     // 这个算法的头文件是这个

void test01() {
	std::vector<int> v;
	for (int i = 0; i <= 100; i++) {
		v.push_back(i);
	}
	// 这个算法一定要头文件`<numeric>`
	// 100是一个初始值，可根据需要设置成别的
	int total = std::accumulate(v.begin(), v.end(), 100);
	std::cout << total << std::endl;  // 5050 + 100 = 5150
}

注意：若容器v中数据是浮点型，那给的起始值一定也要是这样的浮点型

float total = std::accumulate(v.begin(), v.end(), 0.0f);

​ 起始累加值必须得是浮点型，若是给的0，那么容器内的浮点型数据的精度是要被丢失掉的。

它可以把一些字符串连接起来：

#include <iostream>
#include <list>
#include <string>
#include <numeric>

int main() {
	std::list<std::string> li{"aa", "bb", "aa", "cc"};
	std::string s = std::accumulate(li.begin(), li.end(), std::string(""));
	return 0;
}

​ 特别注意：默认加的空字符串能是==std::string(“”)==,绝对不能是==””==(编译会直接出错)，因为==””==的类型是const char*,而不是string，它是没定义+运算符，是不能字符串连接。

实现python中的 “_“.join(s_list) 效果。

#include <iostream>
#include <vector>
#include <string>
#include <numeric>

int main() {
    std::vector<std::string> vec{"aa", "bb", "aa", "cc"};
	std::string result = "";
    if (!vec.empty()) {
    	result = vec.at(0);  // 第一个
        // 如果直接用下划线拼接起来（那直接拼接最前面也会有一个下划线，所以下面是从第2个开始拼接）
        result += std::accumulate(vec.cbegin() + 1, vec.cend(), std::string(""), [](const std::string& str1, const std::string& str2) {return str1 + "_" + str2;});
        // 最后基本都是用lambda表达式，也可以用谓词去实现更复杂的写法
    }
    std::cout << result << std::endl;
	return 0;
}

5.5.2 fill

功能描述：向容器中所有元素变成指定的元素(相比resize,这个更多的是后期来重新填充元素)

函数原型：

#include <iostream>
#include <vector>
#include <numeric>   // 注意这个头文件

void test01() {
	std::vector<int> v;
	for (int i = 0; i <= 10; i++) {
		v.push_back(i);
	}
	// 把这十个元素全部变成5了
	// 一样记得头文件`<numeric>`
	std::fill(v.begin(), v.end(), 5);
	for (std::vector<int>::iterator it = v.begin(); it != v.end(); it++) {
		std::cout << *it << std::endl;
	}
}

5.5.3 fill_n

如下，它将给定值(100)赋予迭代器指向的元素开始(vec.begin() + 2)的指定个(3)元素。

#include <iostream>
#include <vector>
#include <numeric>   // 注意这个头文件
int main() {
	std::vector<int> vec{ 11, 22, 33, 44, 55 , 22, 33, 22 };
	// 核心在下面这行，将33、44、55这几个数全改为100
    std::fill_n(vec.begin() + 2, 3, 100);
	return 0;
}

5.6 常用集合算法

集合算法都要注意一下三个点

注意：

  1. 求交集的两个集合必须是==有序序列==
  2. 且要么都为升序，要么都为降序
  3. 目标容器需要提前开辟空间，空间的大小设置为两个原容器元素个数的较小值
  4. set_intersection返回的是交集中最后一个元素的位置

5.6.1 set_intersection

功能描述：求两个容器的交集

函数原型：

#include <iostream>
#include <vector>
#include <algorithm>  

void myPrint(int val) {
	std::cout << val << ' ';
}
class Print02 {
public:
	void operator()(int val) {
		std::cout << val << ' ';
	}
};
void test01() {
	std::vector<int> v1, v2;
	for (int i = 0; i < 10; i++) {
		v1.push_back(i);   // 0~9
		v2.push_back(i + 5);   // 5~14
	}
	// 要先创建一个接受合集的容器
	std::vector<int> vTarget;
	// 然后一定要记得指定目标容器大小
	vTarget.resize(min(v1.size(), v2.size()));
	// min(value1, value2)  这也需要头文件`<algorithm>`

	// 核心是这个
	std::vector<int>::iterator itEnd = std::set_intersection(v1.begin(), v1.end(), v2.begin(), v2.end(), vTarget.begin());
	std::for_each(vTarget.begin(), vTarget.end(), myPrint);  // 不要用这各容器的.end()，会有很多的0元素，因为空间没用完，有默认值
	std::cout << std::endl;
	// 记得使用函数返回值得到的最后一个元素的迭代器的位置
	std::for_each(vTarget.begin(), itEnd, Print02());  // 5 6 7 8 9
}

5.6.2 set_union

功能描述：求两个集合的并集

函数原型：

void test01() {
	std::vector<int> v1, v2;
	for (int i = 0; i < 10; i++) {
		v1.push_back(i);   // 0~9
		v2.push_back(i + 5);  // 5~14
	}
	// 要先创建一个接受合集的容器
	std::vector<int> vTarget;
	// 然后一定要记得指定目标容器大小
	vTarget.resize(v1.size() + v2.size());
	// 核心是这个
	std::vector<int>::iterator itEnd = std::set_union(v1.begin(), v1.end(), v2.begin(), v2.end(), vTarget.begin());
	std::for_each(vTarget.begin(), itEnd, Print02());   // 结果是它们的合集
}

5.6.3 set_difference

功能描述：求两个集合的差集

函数原型：

#include <iostream>
#include <vector>
#include <algorithm>  

void myPrint(int val) {
	std::cout << val << ' ';
}
class Print02 {
public:
	void operator()(int val) {
		std::cout << val << ' ';
	}
};
void test01() {
	std::vector<int> v1, v2;
	for (int i = 0; i < 10; i++) {
		v1.push_back(i);   // 0~9
		v2.push_back(i + 5);  // 5~14
	}
	// 要先创建一个接受合集的容器
	std::vector<int> vTarget;
	vTarget.resize(max(v1.size(), v2.size()));
	// v1相对v2的差集
	vector<int>::iterator itEnd = set_difference(v1.begin(), v1.end(), v2.begin(), v2.end(), vTarget.begin());
	for_each(vTarget.begin(), itEnd, myPrint);  // 0 1 2 3 4
	cout << endl;
	vector<int> vTarget1;
	vTarget1.resize(max(v1.size(), v2.size()));
	// v2相对于v1的差集
	std::vector<int>::iterator itEnd1 = std::set_difference(v2.begin(), v2.end(), v1.begin(), v1.end(), vTarget1.begin());
	std::for_each(vTarget1.begin(), itEnd1, Print02()); // 10 11 12 13 14
}

5.7 通用算法

5.7.1 equal

​ 用来确定两个序列是够保存相同的值,是只读的，所有元素都相等就返回true，否则返回false。

==std::equal(vec1.cbegin(), vec1.cend(), vec2.cbegin());==

而且vec1可以是vector<std::string>,而vec2是list<const char*>

​ 它有一个很重要的假设：假定第二个序列(vec2)长度大于等于第一个序列(vec1)，且算法要处理的第一个序列中的每个元素，它假定在第二个序列汇总都有一个与之对应的元素。

​ 注意：若两个容器保存的都是C风格字符串而不是string,调用equal算法，会发生什么？ 答：C风格字符串是指向字符的指针表示的，因此会比较两个指针的值(地址),而不会比较两个字符串的内容。

5.7.2 back_inserter

​ 插入迭代器，书上写它是定义在头文件 #include <iterator> 中的一个函数，但是我在vs或是linux下没有导入这个头文件都能使用。看这里，这是属于插入迭代器。

#include <iostream>
#include <vector>
int main() {
	std::vector<int> vec;   // 1.空的vector
	auto it = std::back_inserter(vec);  // 2.通过它赋值会将元素添加到vec中
	*it = 42;  // 3.vec中现在有一个元素，值为42
	// 4.像vec中往后添加3个值，值均为5
	std::fill_n(std::back_inserter(vec), 3, 5);
	return 0;
}

​ 注：第4.点中，由于我们传递的参数时back_inserter放回的迭代器，因此每次赋值都会在vec上调用push_back，最终这条std::fill_n语句想vec的末尾添加了3个元素，每个元素的值都是5。

5.7.3 unique

​ 消除重复单词，但前提是一定要先sort排序，std::sort和std::unique的使用都需要头文件 #include<algorithm>

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>    // 都要这头文件
int main() {
	std::vector<std::string> vec{"over", "fox", "the", "quick", "red", "fox", "the", "turtle"};
	
	// 必须要先排序才能使用 std::unique
	std::sort(vec.begin(), vec.end());   // 1.
	auto end_unique = std::unique(vec.begin(), vec.end());//2

	vec.erase(end_unique, vec.end()); //3.
	return 0;
}

问：算法不改变容器大小的原因是什么？答：

5.7.4 partition

​ 这是一个标准库定义的算法std::partition，需要导入头文件 #include<algorithm>, 它接受一个谓词，对容器内容进行划分(==有点像python的lambda表达式对列表进行筛选==)，使得谓词结果为true的值排在容器的前半部分，而使谓词为false的值排在后半部分，==结果是返回的一个迭代器，指向最后一个使谓词为true的元素的后一个位置==,(这也再次印证了标准算法库不会改变容器的)

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>   // 这个算法需要这个头文件
bool predicate(const std::string &s) {
	return s.size() > 3;
}
int main() {
	std::vector<std::string> vec{"over", "fox", "the", "quick", "red", "fox", "the", "turtle"};
	auto pivot = std::partition(vec.begin(), vec.end(), predicate);
	// 只会打印 over turtle quick
	for (auto iter = vec.cbegin(); iter != pivot; ++iter) {
		std::cout << *iter << std::endl;  
	}
	return 0;
}

5.7.5 distance

计算两个迭带器之间的距离，好像不需要什么头文件

std::vector<int> vec{ 1, 2, 0, 4, 5, 6, 7, 0, 9 };
auto it = std::find(vec.crbegin(), vec.crend(), 0);
std::cout << *it << std::endl;  // 0
std::cout << std::distance(it, vec.crend()) << std::endl;  // 8

注：for (auto iter = vec.crbegin(); iter != vec.crend(); iter++) {/*…*/} 这样就可以倒序遍历容器。

5.8 插入迭代器

三种迭代器的不同之处：

除了unique之外，标准库还定义了名为unique_copy的函数，它接收第三个迭代器，表示拷贝不重复元素的目的位置，即将一个vector中不重复的元素拷贝到一个初始化为空的list中。

#include <algorithm>    // std::unique_copy需要这个头文件
//#include <iterator>   // 看前面解释，这个头文件好像不是必须的
std::vector<int> vec{1, 1, 3, 5, 6, 6, 7};
std::list<int> li;
// 前面unique讲过了，vec一定是要排好序的，没排序就要先用sort
std::unique_copy(vec.begin(), vec.end(), std::back_inserter(li));

5.9 iostream迭代器

==std::istream_iterator==

#include <iostream>
#include <vector>
#include <numeric>   // std::accumulate要
#include <iterator>   // std::istream_iterator要
#include <fstream>   // 读文件要这个
#include <string>

int main(int argc, char **argv) {
	std::string path = "C:\\Users\\Administrator\\Music\\123.txt";	
	std::ifstream file_stream(path);  // 从123.txt中读取数字字符串
	// istream_iterator 必须要头文件 <iterator>
	std::istream_iterator<std::string> str_in(file_stream);  // 此时str_in和std::cin一样是流
	std::istream_iterator<std::string> a_eof;  // 表示尾后位置
	std::vector<std::string> vec1;
    
	// 构造vec方式一：(两种方式只能任选其一)
	while (str_in != a_eof) {  //当有数据可供读取时
		vec1.push_back(*str_in++);  // 解引用一个值后，再后置递增指针读取流
	}
	// 构造vec方式二：// 从迭代器范围构造vec
	std::vector<std::string> vec2(str_in, a_eof);
    // 或者
    std::copy(str_in, a_eof, std::back_inserter(vec2));  
    // 下面只是单纯打印出来看看
	for (auto e : vec2) {
		std::cout << e << std::endl;
	}
	return 0;
}

// 下面是一个打印的别的办法
void a_test() { 
	// 还可以直接使用算法操作流迭代器(输入一些数字，直接求得和)
	std::istream_iterator<int> in(std::cin), eof;
	std::cout << std::accumulate(in, eof, 0) << std::endl;   
}

==std::ostream_iterator==

int main(int argc, char **argv) {
	// ostream_iterator 必要要头文件 <iterator>
	std::vector<int> vec{1, 1, 3, 5, 6, 6, 7};

	// 可以用 ostream_iterator 来输出值的序列
	std::ostream_iterator<int> out_iter(std::cout, " ");  // 每个元素后面加一个空格
	// 方式一：下面就会将vec打印出来
	for (auto e : vec) {
		*out_iter++ = e;     // 赋值语句实际上将元素写到cout
		//out_iter = e;  // 两行的效果一模一样
	}
	/*详解：这会将vec中的每个元素写到cout,每个元素后加一个空格，每次向out_iter赋值时，写操作就会被提交
	但是，向out_iter赋值时，可以忽略解引用和递增运算，所以两行是一个意思*/ 
	std::cout << std::endl;

	// 方式二：通过调用copy来打印vec中的元素（copy在vs中什么头文件都不需要）
	std::copy(vec.begin(), vec.end(), out_iter);
	std::cout << std::endl;
	return 0;
}

Tips:

​ 示例：使用流迭代器、sort和copy从标准输入读取一个整数序列，将其排序，并将结果写到标准输出（每个元素只打印一次，即要去掉重复元素）

#include <iostream>
#include <iterator>  // std::istream_iterator、std::ostream_iterator需要
#include <algorithm>
#include <vector>
#include <functional>  //  std::greater兼容低版本需要这个头文件

int main(int argc, char **argv) {
	std::istream_iterator<int> in(std::cin), eof;

	//std::vector<int> vec;
	//std::copy(in, eof, std::back_inserter(vec));
	std::vector<int> vec(in, eof);  // 上面两行与这效果一样

	std::sort(vec.begin(), vec.end(), std::greater<int>());  // 排序

	std::vector<int> new_vec;   // 排序后才能去掉重复元素
	std::unique_copy(vec.begin(), vec.end(), std::back_inserter(new_vec));

	// 打印输出
	std::copy(new_vec.begin(), new_vec.end(), std::ostream_iterator<int>(std::cout, "\n"));
	return 0;
}

注意：参考答案里，是直接用的std::unique去改变最原来的vec容器，我这是创建了一个新的，我用std::unique，答案很奇怪，不是我想要的。

​ 习题：接受三个参数：一个输入文件和两个输出文件的文件名。输入文件保存的应该是整数。使用 istream_iterator 读取输入文件。使用 ostream_iterator 将奇数写入第一个输入文件，每个值后面都跟一个空格。将偶数写入第二个输出文件，每个值都独占一行。（这个需要准备一个txt文件，里面都是数字，用空格或是换行分开）

解答，我写的：

#include <iostream>
#include <string>
#include <vector>
#include <iterator>
#include <fstream>

// 因为没办法把string转成char的相关，所以这里不能是 char *input_file (这语法行，但是在这列传递不过来)
void my_iterator(std::string input_file, std::string out_file1, std::string out_file2) {
	// 1.先把要写的两个文件流创建好
	std::fstream ofs1(out_file1, std::ios::out);  // 写文件一定要写模式
	std::fstream ofs2(out_file2, std::ios::out);  // 两个输出文件
	// 2.把创建的文件流用ostream的迭代器写好
	std::ostream_iterator<std::string> my_cout1(ofs1, " ");
	std::ostream_iterator<std::string> my_cout2(ofs2, "\n");
	// 3.读取文件的istream的迭代器
	std::fstream ifs(input_file);
	std::istream_iterator<std::string> num_in(ifs), my_eof;
	while (num_in != my_eof) {
		int num = std::stoi(*num_in);
		if (num % 2 != 0) {  // 这种以后就用三目运算符吧
			// 这就是把文件写进去，如果不是文件流，是cout流,就会打印出来
			my_cout1 = *num_in;  
		}
		else {
			my_cout2 = *num_in;
		}
		++num_in;   // 把这个放到while里就是不对，很奇怪（别忘了，否则会死循环）
	}
	ofs1.close();
	ofs2.close();
	ifs.close();
}

int main(int argc, char **argv) {
	if (argc != 4) {
		std::cout << "参数输入有错误，请重新输入！" << std::endl;
		return -1;
	}
	my_iterator(argv[1], argv[2], argv[3]);
	std::cout << "处理完毕" << std::endl;
	system("pause");
	return 0;
}

参考答案的（确实太简练了，它用的lambda表达式，帅，但是17行那句，执行顺序，加定义的变量const int i ,还去做右值，确实很费解）：

但是这个案例给我们的启发式，如果读的文本全是数字。。那么可以直接

std::ostream_iterator<int> my_cout1(ofs1, “ “); // 直接用int接收，是可以自动转换的，而非读取文本就一定要用std::string去接收。

#include <fstream>
#include <iterator>
#include <algorithm>

int main(int argc, char **argv)
{
	if (argc != 4) return -1;

	std::ifstream ifs(argv[1]);
	std::ofstream ofs_odd(argv[2]), ofs_even(argv[3]);

	std::istream_iterator<int> in(ifs), in_eof;
	std::ostream_iterator<int> out_odd(ofs_odd, " "), out_even(ofs_even, "\n");

	std::for_each(in, in_eof, [&out_odd, &out_even](const int i)
	{
		*(i & 0x1 ? out_odd : out_even)++ = i;
	});
	return 0;
}
This site is open source. Improve this page.