07.C++ STL

本节分为十部分：

vector 容器
deque 容器
list 容器
vector、deque、list 对比分析
详解容器适配器
无序关联容器
有序关联容器
迭代器 iterator
函数对象
泛型算法和绑定器

STL：其英文全称为：standard template libaray，即标准模板库。我们根据需要直接实例化这些模板，提高了我们使用的效率。

1. vector 容器

vector：向量容器，底层数据结构是动态开辟的数组，每次以原来空间大小的 2 倍进行扩容。

容器中对象的构造析构，内存的开辟释放通过空间配置器 allocator 实现：allocate(内存开辟)、deallocate(内存释放)、construct(对象构造)、destroy(对象析构)。

1. 使用方法合集

语法结构：

1	`vector<type> TypeName;`

使用方式： 使用前包含头文件

1	`#include <vector>`

增加：

**push_back()**：在容器末尾增加一个元素，时间复杂度O(1)，会导致容器扩容。
**insert(迭代器，迭代器位置)**：在 it 迭代器指向的位置增加一个元素，时间复杂度O(n)，也会导致容器扩容。

删除：

**pop_back()**：在容器末尾删除一个元素，时间复杂度O(1)。
**erase()**：删除it迭代器指向的元素，时间复杂度O(n)。

查询：

**operator[]**：数据下标的随机访问vec[5]，时间复杂度O(1)。
**iterator**：迭代器进行遍历，一定要考虑迭代器失效问题。
**find()\for_each**：泛型算法。
**foreach**：C++11提供的语法糖，通过迭代器iterator来实现的。

常用方法：

**size()**：返回容器底层有效元素的个数。
**empty()**：判断容器是否为空。
**reserve()**：为 vector 预留空间，只给容器底层开辟指定大小空间并不添加新的元素。
**resize()**：扩容。不仅给容器底层开辟指定大小空间，还会添加新的元素。
**swap()**：两个容器进行元素交换。

2. 容器使用

对 vector 容器中元素遍历。

#include <iostream>
// 使用 vector 库
#include <vector>
using namespace std;

int main()
{
	// 定义 vector 
	vector<int> vec;
	int i = 0;
	for (i = 0; i < 20; i++)
	{
		vec.push_back(rand() % 100 + 1);
	}

	// 1. 运算符重载遍历
	int size = vec.size();
	for (int i = 0; i < size; i++)
	{
		cout << vec[i] << " ";
	}
	cout << endl;

	// 2. 迭代器遍历
	auto it = vec.begin();
	for (; it != vec.end(); it++)
	{
		cout << *it << " ";
	}

	return 0;
}

把 vec 容器中所有偶数全部删除

#include <iostream>
// 使用 vector 库
#include <vector>
using namespace std;

int main()
{
	// 定义 vector 
	vector<int> vec;
	int i = 0;
	for (i = 0; i < 20; i++)
	{
		vec.push_back(rand() % 100 + 1);
	}

	auto it1 = vec.begin();
	while (it1 != vec.end())
	{
		if (*it1 % 2 == 0) 
		{
			it1 = vec.erase(it1);
		}
		else
		{
			it1++;
		}
	}

	// 2. 迭代器遍历
	auto it2 = vec.begin();
	for (; it2 != vec.end(); it2++)
	{
		cout << *it2 << " ";
	}

	return 0;
}

在 2 删除的基础上，给 vector 容器中所有的奇数前面都添加一个小于 1的偶数例：44 45

#include <iostream>
// 使用 vector 库
#include <vector>
using namespace std;

int main()
{
	// 定义 vector 
	vector<int> vec;
	int i = 0;
	for (i = 0; i < 20; i++)
	{
		vec.push_back(rand() % 100 + 1);
	}

	//vec的operator[]运算符重载函数进行vector遍历
	int size = vec.size();
	for (int i = 0; i < size; ++i)
	{
		cout << vec[i] << " ";
	}
	cout << endl;

	// 删除
	auto it1 = vec.begin();
	while (it1 != vec.end())
	{
		if (*it1 % 2 == 0) 
		{
			it1 = vec.erase(it1);
		}
		else
		{
			it1++;
		}
	}

	// 迭代器遍历
	auto it2 = vec.begin();
	for (; it2 != vec.end(); it2++)
	{
		cout << *it2 << " ";
	}
	cout << endl;

	// 添加
	for (it2 = vec.begin(); it2 != vec.end(); it2++)
	{
		if (*it2 % 2 != 0)
		{
			it2 = vec.insert(it2, *it2-1);
			++it2;
		}
	}

	it2 = vec.begin();
	for (; it2 != vec.end(); it2++)
	{
		cout << *it2 << " ";
	}
	cout << endl;

	return 0;
}

reserve 预留空间，只给容器底层开辟指定大小空间并不添加新的元素。

默认定义的 vector 底层为 0，第一次插入从 0 变更为 1，再变为 2，4，8… 一直进行扩容，代价十分高，使用初始的内存效率太低，若开始知道问题的数据量大小，即可使用 reserve 预留空间。

#include <iostream>
// 使用 vector 库
#include <vector>
using namespace std;

int main()
{
	vector<int> vec;// 默认定义的 vector 底层为 0
	vec.reserve(20);// 给 vector 容器预留空间

	cout << "Before，vec.empty()：" << vec.empty() << endl;
	cout << "Before，vec.size()：" << vec.size() << endl;

	for (int i = 0; i < 20; i++)
	{
		vec.push_back(rand() % 100 + 1);
	}

	cout << "After，vec.empty()：" << vec.empty() << endl;
	cout << "After，vec.size()：" << vec.size() << endl;

}

输出结果: empty() 是 1 为空，0 为非空。刚开始为空，reserve(20) 并没有为容器添加元素，只是为容器底层开辟空间，容器里面元素个数依旧是 0。再添加 20个元素的时候，不需要扩容了，效率提高。

resize 扩容，不仅给容器底层开辟指定大小空间，还会添加新的元素。

resize() 不仅给容器底层开辟指定大小空间，还会添加新的元素，元素值为 0。

#include <iostream>
// 使用 vector 库
#include <vector>
using namespace std;

int main()
{
	vector<int> vec;//默认定义的vector底层为0
	vec.resize(20);

	cout << "Before，vec.empty()：" << vec.empty() << endl;
	cout << "Before，vec.size()：" << vec.size() << endl;

	for (int i = 0; i < 20; i++)
	{
		vec.push_back(rand() % 100 + 1);
	}

	cout << "After，vec.empty()：" << vec.empty() << endl;
	cout << "After，vec.size()：" << vec.size() << endl;

	return 0;
}

2. deque 容器

deque：双端队列容器，底层为动态开辟的二维数组。 **

一维数组从 2 开始，以 2 倍的方式进行扩容，每次扩容后，原来第二维的数组，从新的第一维数组的下标 oldsize/2 开始存放，上下都预留相同的空行，方便支持 deque 的首尾元素添加。

1. 容器结构

其底层为：动态开辟的二维数组。

其有两个宏：MAP_SIZE，为2；QUE_SIZE，为 4096/sizeof(T)，T 为实际的类型。底层有 2 个维度，还有一个 mapper 指针，指向第一维的一维数组，默认大小为 MAP_SIZE 2；第二维为动态开辟的 QUE_SIZE 的大小，例如：使用整型时会有1024个元素。

双端队列两端都可以做为队头与队尾，现在可以从队尾入，队尾出，也可以队头入，队头出；

简易的画了一个方向，first 与 last 处于最中间的位置，便于两头都预留足够的空间，每一边都可以进行插入。

2. 扩容方式

当我们元素的不断增加，相应的指示位置向后移动。

如图 2；当元素入满时候，还要从last方向入队，已经没有空间了，就需要再开辟一个二维数组，last移动到第二行开始部分。

如图2，3，4；当我们再继续添加元素时，发现满了，再想继续添加元素deque就需要扩容，此时需要扩容第一维了，按照2倍大小扩容为4。

如图5，6；刚才的第二维移动到第一维中间部分(oldsize/2)，方便任何一边的元素改动。若需再次扩容，同理。

3. 使用方法合集

使用前提：

1	`#include <deque>`

语法：

1	`deque<type> TypeName;`

增加：

**push_back()**：从末尾添加元素，时间复杂度O(1)，可能引起扩容。
**push_front()**：从首部添加元素，时间复杂度O(1)，可能引起扩容。vector 中没有该方法，需要使用 insert()，为O(n)。
**insert()**：迭代器指向的位置添加元素，时间复杂度O(n)。

删除：

**pop_back()**：从末尾删除元素，时间复杂度O(1)。
**pop_front()**：从首部删除，时间复杂度O(1)。
**erase()**：迭代器指向的位置进行元素删除，时间复杂度O(n)。

查询：

**iterator**：迭代器进行遍历，一定要考虑迭代器失效问题。

常用方法：

**size()**：返回容器底层有效元素的个数。
**empty()**：判断容器是否为空。
**resize()**：扩容。不仅给容器底层开辟指定大小空间，还会添加新的元素。
**swap()**：两个容器进行元素交换。

4. 使用

和 vector 实例类似，直接参考 vector 容器实例即可。

3. list 容器

list：链表容器，底层数据结构为双向循环链表。

1. 使用方法合集

使用前提：

1	`#include <list>`

语法：

1	`list<type> TypeName;`

增加：

**push_back()**：从末尾添加元素，时间复杂度O(1)，可能引起扩容。
**push_front()**：从首部添加元素，时间复杂度O(1)，可能引起扩容。vector 中没有该方法，需要使用 insert()，为O(n)。
**insert()**：迭代器指向的位置添加元素，时间复杂度O(1)。往往链表进行 insert() 时，要先进行 query() 操作，效率就慢了。

删除：

**pop_back()**：从末尾删除元素，时间复杂度O(1)。
**pop_front()**：从首部删除，时间复杂度O(1)。
**erase()**：迭代器指向的位置进行元素删除，时间复杂度O(n)。

查询：

**iterator**：迭代器进行遍历，一定要考虑迭代器失效问题。

常用方法：

**size()**：返回容器底层有效元素的个数。
**empty()**：判断容器是否为空。
**resize()**：扩容。不仅给容器底层开辟指定大小空间，还会添加新的元素。
**swap()**：两个容器进行元素交换。

2. 使用

使用实例与vector类似。

4. vector、deque、list 对比分析

deque 底层内存是否是连续的？

不是，deque 底层是动态开辟的二维数组，第二维都是独立开辟的空间，每一个第二维是连续的，但是所有的二维不是连续的。

vector 与 deque 容器之间的区别：

vector 特点： 底层是一个动态开辟数组，内存是连续的，2 倍的方式进行扩容。当默认定义一个 vector 时候，容器底层没有开辟空间，当添加元素时候才从：0-1-2-4-8… 进行扩容，扩容效率低。reserve 函数可以预留空间，并未添加元素。
deque 特点： 底层为动态开辟的二维数组空间，第二维是固定长度的数组空间，扩容时候(第一维的数组进行 2 倍扩容，原来的第二维的数组放入新扩容的数组中间)，支持前后插入删除为 O(1) 的操作。

区别：

底层数据结构不同：vector 底层为动态开辟的数组，内存是连续的；deque 底层是动态开辟的二维数组空间，内存不连续。
前中后删除的时间复杂度不同：它们中间与末尾插入删除一样为 O(1)，但最前面进行元素添加时候 deque 为 O(1)，vector 为 O(n)。
内存使用效率不同：vector 低，需要的内存空间必须是连续的；deque 第二维内存空间不一定连续，可以分块进行数据存储，对内存使用效率会更高。
在中间进行 insert 或者 erase，vector 与 deque 的效率不同：它们时间复杂度都为 O(n)，但 vecto r内存完全连续，其他元素容易移动；但 deque 内存不连续，元素移动更加麻烦一些，效率不如 vector。

vector 与 list 容器之间的区别：

vector 特点：底层是一个动态开辟的数组，内存是连续的，2 倍的方式进行扩容。当我们默认定义一个 vector 时候，容器底层没有开辟空间，当添加元素时候才从：0-1-2-4-8… 进行扩容，扩容效率低。reserve 函数可以预留空间，并未添加元素。
list 特点：底层是一个双向循环链表。

区别：

数组与链表区别：数组增加删除为 O(n)，查询 O(n)，随机访问为 O(1)；链表增加删除一个结点本身为 O(1)，但搜索的时间为 O(n)。如果增加删除使用多，优先使用 list；随机访问使用多，优先使用 vector。

5. 详解容器适配器

容器适配器：适配器底层没有自己的数据结构，它是另外一个容器的封装，它的方法全部由底层依赖的容器进行实现的；它没有实现自己的迭代器，不能使用迭代器遍历。

使用容器适配器实现栈

#include <iostream>
#include <deque>
using namespace std;

template<class T, typename Container=deque<T>>
class Stack
{
public:
	void push(const T& val)
	{
		con.push_back(val);
	}
	void pop()
	{
		con.pop_back();
	}
	T top()const
	{
		return con.back();
	}

private:
	Container con;
};

int main()
{
	Stack<int> s;
	
	int i = 0;
	for (i = 0; i < 10; i++)
	{
		s.push(i);
	}

	for (i = 0; i < 10; i++)
	{
		cout << s.top() << " ";
		s.pop();
	}

	return 0;
}

实现成功，相当于栈将 deque 代理了一下，也成为代理模式。push 将底层容器的 push_back 代理了，pop 将底层 pop_back 代理了，栈的 top 将容器底层的 back 代理了。

1. Stack 栈容器

stack<T> 容器适配器中的数据是以 LIFO（Last In First Out）的方式组织的，这和自助餐馆中堆叠的盘子、箱子中的一堆书类似。

上图：展示了一个理论上的 stack 容器及其一些基本操作。只能访问 stack 顶部的元素；只有在移除 stack 顶部的元素后，才能访问下方的元素。

使用前提：

1	`#include <stack>`

常用方法：

**push()**：入栈
**pop()**：出栈
**top()**：查看栈顶元素
**empty()**：判断栈空
**size()**：返回元素个数

使用：

#include <iostream>
#include <stack>
using namespace std;

int main()
{
	stack<int> s;

	int i = 0;
	for (i = 0; i < 20; i++)
	{
		s.push(rand() % 100 + 1);
	}

	cout << "栈中元素个数:" << s.size() << endl;

	while (!s.empty())
	{
		cout << s.top() << " ";
		s.pop();
	}

	return 0;
}

2. 队列

只能访问 queue<T> 容器适配器的第一个和最后一个元素。只能在容器的末尾添加新元素，只能从头部移除元素。

许多程序都使用了 queue 容器。queue 容器可以用来表示超市的结账队列或服务器上等待执行的数据库事务队列。对于任何需要用 FIFO（First In First Out）准则处理的序列来说，使用 queue 容器适配器都是好的选择。

使用前提：

1	`#include <queue>`

常用方法：

**push()**：入栈
**pop()**：出栈
**front()**：查看对头元素
**back()**：查看队尾元素
**empty()**：判断空
**size()**：返回元素个数

使用：

#include <iostream>
#include <queue>
using namespace std;

int main()
{
	queue<int> q;

	int i = 0;
	for (i = 0; i < 20; i++)
	{
		q.push(rand() % 100 + 1);
	}

	cout << "队列中元素个数:" << q.size() << endl;

	while (!q.empty())
	{
		cout << q.front() << " ";
		q.pop();
	}

	return 0;
}

3. 优先级队列

优先级队列：底层数据结构为大根堆。

使用库中的优先级队列，需要加上头文件<queue>；优先级队列，谁优先级大谁先出队，谁优先级小，谁后出队。

常用方法：

**push()**：入栈
**pop()**：出栈
**top()**：查看栈顶元素
**empty()**：判断栈空
**size()**：返回元素个数

使用：

#include <iostream>
#include <queue>
using namespace std;

int main()
{
	priority_queue<int> q;

	int i = 0;
	for (i = 0; i < 20; i++)
	{
		q.push(rand() % 100 + 1);
	}

	cout << "优先队列中元素个数:" << q.size() << endl;

	while (!q.empty())
	{
		cout << q.top() << " ";
		q.pop();
	}

	return 0;
}

数据从大到小依次出队，数据越大优先级越高。

问题一：stack 与 queue 第二个模板类型参数依赖 deque，为什么不依赖 vector？

vector 的初始化内存使用效率太低了，没有 deque 好。
对于 queue 来说，需要支持尾部插入，头部删除，时间复杂度需要为 O(1)，deque 恰好符合条件，若用 vector 其底层效率太低。
vector 需要大片的连续内存，而 deque 只需要分段的内存，当存储大量数据时，显然 deuqe 对于内存的利用率更高更好一些。

问题二：优先级队列为什么底层依赖 vector？

优先级队列底层默认把数据组成一个大根堆结构，将大根堆结构看作一棵树，如果将大根堆结构所有元素放入数组中，使用下标计算其结点。若根节点为 i，左孩子为 2i+1，右孩子为 2i+2；大根堆为堆顶，其元素最大，结点与左右孩子关系使用下标计算，就需要每一个元素内存必须是连续的，因此底层依赖 vector；而 deque 的第二维不是连续的，不能使用。

6. 无序关联容器

关联容器分为：无序关联容器与有序关联容器，简单对比下：

无序关联容器：底层为哈希表，里面元素无顺序，增删查为O(1)。

1. 单重集合与多重集合

set 集合：存储的是关键字。[key]
unordered_set：单重集合；不允许 key 重复。
unordered_multiset：多重集合；允许 key 重复。

包含文件：

1	`#include <unordered_set>`

常用方法：

增加：insert(val);
遍历：iterator 自己搜索，调用 find()；
删除：erase(key); 或 erase(it);

**size()**：返回容器中元素个数。
**count(val)**：返回元素值为val的个数，val不会重复。
**find(val)**：在集合容器中查找key,存在返回迭代器，不存在返回容器末尾迭代器。

使用1：

#include <iostream>
#include <unordered_set>
using namespace std;

int main()
{
	// 不允许存储key值重复的元素
	unordered_set<int> set1;
	for (int i = 0; i < 50; ++i)
	{
		// 与vector/deque/list插入不同
		set1.insert(rand() % 20 + 1);
	}

	cout << "set1.size() = " << set1.size() << endl;
	// 返回key为15的元素的个数
	cout << "set1.count(15) = " << set1.count(15) << endl;

	return 0;
}

使用2：

#include <iostream>
#include <unordered_set>
using namespace std;

int main()
{
	// 不允许存储key值重复的元素
	unordered_set<int> set1;
	for (int i = 0; i < 50; ++i)
	{
		// 与vector/deque/list插入不同
		set1.insert(rand() % 20 + 1);
	}

	// 迭代器遍历容器
	auto it1 = set1.begin();
	for (; it1 != set1.end(); ++it1)
	{
		cout << *it1 << " ";
	}
	cout << endl;

	// 按key值删除元素
	set1.erase(20);
	for (it1 = set1.begin(); it1 != set1.end();)
	{
		if (*it1 == 30)
		{
			// 迭代器删除元素
			it1 = set1.erase(it1);
		}
		else
		{
			++it1;
		}
	}

	it1 = set1.find(20);
	if (it1 != set1.end())
	{
		set1.erase(it1);
	}

	for (int v : set1)
	{
		cout << v << " ";
	}
	cout << endl;

	return 0;
}

使用3：unordered_multiset

#include <iostream>
#include <unordered_set>
using namespace std;

int main()
{
	// 允许存储key值重复的元素
	unordered_multiset<int> set1;
	for (int i = 0; i < 50; ++i)
	{
		// 与vector/deque/list插入不同	
		set1.insert(rand() % 20 + 1);
	}

	cout << "set1.size() = " << set1.size() << endl;
	// 返回key为15的元素的个数
	cout << "set1.count(15) = " << set1.count(15) << endl;

	return 0;
}

2. 单重映射表与多重映射表

map 集合：存储的是键值对。[key，value]
unordered_map：单重映射表；不可重复。
unordered_multimap：多重映射表；可重复。

包含文件：

1	`#include <unordered_map>`

常用方法：

增加：insert(val);
遍历：iterator 自己搜索，调用 find()；
删除：erase(key); 或 erase(it);

使用1：unordered_map

#include <iostream>
#include <unordered_map>
using namespace std;

int main()
{
	unordered_map<int, string> map1;

	map1.insert(make_pair(1000, "张三"));
	map1.insert(make_pair(1010, "李四"));
	map1.insert(make_pair(1020, "王五"));

	map1.insert(make_pair(1000, "王五"));

	cout << "size: " << map1.size() << endl;//键值对个数

	return 0;
}

使用2：unordered_multimap

#include <iostream>
#include <unordered_map>
using namespace std;

int main()
{
	unordered_multimap<int,string> map1;
	map1.insert(make_pair(1000,"张三"));//打包成键值对
	map1.insert(make_pair(1010,"李四"));
	map1.insert(make_pair(1020,"王五"));

	map1.insert(make_pair(1000,"王五"));

	cout << "size: " << map1.size() << endl;// 键值对个数

	return 0;
}

使用3：查询

1 2	`//map operator[](key) =>value cout << map1[1000] << endl;`

#include <iostream>
#include <unordered_map>
using namespace std;

int main()
{
	unordered_map<int, string> map1;

	map1.insert(make_pair(1000, "张三"));
	map1.insert(make_pair(1010, "李四"));
	map1.insert(make_pair(1020, "王五"));

	map1.insert(make_pair(1000, "王五"));

	map1.erase(1020);//删除
	map1[2000] = "刘帅";//相当于插入
	map1[1000] = "张三2";//相当于修改操作

	cout << map1.size() << endl;//键值对个数
	// map operator[](key) =>value 查询
	cout << map1[1000] << endl;

	return 0;
}

使用4：iterator 查找

#include <iostream>
#include <unordered_map>
using namespace std;

int main()
{
	unordered_map<int, string> map1;

	map1.insert(make_pair(1000, "张三"));
	map1.insert(make_pair(1010, "李四"));
	map1.insert(make_pair(1020, "王五"));
	map1.insert(make_pair(1030, "赵六"));

	auto it1 = map1.find(1030);
	if (it1 != map1.end())
	{
		cout << "key:" << it1->first << " value:" << it1->second << endl;
	}

	return 0;
}

3. 海量数据

案例1：处理海量数据数据查重，经常会使用map。

#include <iostream>
#include <unordered_map>
using namespace std;

const int ARR_LEN = 1000;

int main()
{
	int arr[ARR_LEN] = { 0 };

	int i = 0;
	for (i = 0; i < ARR_LEN; i++)
	{
		arr[i] = rand() % 20 + 1;
	}

	// 上面的1000个整数中，统计哪些数字重复了，并且统计数字重复的次数

	unordered_map<int, int> map1;
	for (int k : arr)
	{
		auto it = map1.find(k);
		if (it == map1.end())//数字没出现过
		{
			map1.insert(make_pair(k, 1));
		}
		else
		{
			it->second++;
		}
	}

	auto it = map1.begin();
	for (; it != map1.end(); ++it)
	{
		if (it->second > 1)
		{
			cout << "key:" << it->first << " value:" << it->second << endl;
		}
	}

	return 0;
}

案例2：海量数据去重。

#include <iostream>
#include <unordered_set>
using namespace std;

const int ARR_LEN = 1000;

int main()
{
	int arr[ARR_LEN] = { 0 };
	for (int i = 0; i < ARR_LEN; i++)
	{
		arr[i] = rand() % 20 + 1;
	}

	// 上面的整数中，将数字进行去重打印
	unordered_set<int> set;
	for (int v : arr)
	{
		set.insert(v);
	}

	for (int v : set)
	{
		cout << v << " ";
	}
	cout << endl;

	return 0;
}

7. 有序关联容器

有序关联容器：底层为红黑树，里面元素有序，增删查 $O(log^{2n})$。

包含文件：

1 2	`#include <map> #include <set>`

set：单重集合，重复的只出现一次，从小到大元素有序排列(红黑树的中序遍历)。
multiset：多重集合，可以存储重复的元素，从小到大元素有序排列。
map：单重映射表，重复的只出现一次，从小到大元素有序排列。
multimap：多重映射表，可以存储重复的元素，从小到大元素有序排列。

实例1：set 实例

set<int> set1;
for (int i=0; i<20; i++)
{
	set1.insert(rand()%20 + 1);
}

for (int v : set1)
{
	cout << v << " ";
}
cout << endl;

实例2：set 存放自定义类型

#include <iostream>
#include <ostream>
#include <string>
#include <set>
using namespace std;

class Student
{
public:
	Student(int id, string name)
		: _id(id)
		, _name(name)
	{
		// 舒适化列表
	}

	bool operator<(const Student& stu) const
	{
		return _id < stu._id;
	}

private:
	int _id;
	string _name;
	// 友元
	friend ostream& operator<<(ostream& out, const Student& str);
};

ostream& operator<<(ostream& out, const Student& stu)
{
	out << "id: " << stu._id << endl;
	out << "name: " << stu._name;

	return out;
}

int main()
{
	set<Student> set1;
	set1.insert(Student(1000, "张文"));
	set1.insert(Student(1020, "李广"));

	for (auto it = set1.begin(); it != set1.end(); ++it)
	{
		cout << *it << endl;
		cout << "---------------------" << endl;
	}

	return 0;
}

实例3：map 实例

class Student
{
public:
	Student(int id = 0, string name = "")
		:_id(id), _name(name){}
private:
	int _id;
	string _name;
	friend ostream& operator<<(ostream &out, const Student &stu);
};

ostream& operator<<(ostream &out, const Student &stu)
{
	out << "id:" << stu._id << " name:" << stu._name << endl;
	return out;
}

int main()
{
	map<int, Student> stuMap;
	stuMap.insert(make_pair(1010,Student(1010,"张文")));
	stuMap.insert(make_pair(1020,Student(1020,"李广")));
	stuMap.insert(make_pair(1030,Student(1030,"高阳")));

	//stuMap.erase(it) stuMap.erase(1020)
	//cout << stuMap[1020] << endl;
	auto it = stuMap.begin();
	for (; it!=stuMap.end(); ++it)
	{
		cout << "key:" << it->first << "value:" << it->second << endl;
	}
	cout << endl;

	return 0;
}

8. 迭代器 iterator

正向迭代器 iterator：输出元素时从第一个到对后一个，既可以读也可修改。
常量的正向迭代器 const_iterator：输出元素时从第一个到对后一个，只可以读。
反向迭代器 reverse_iterator：输出元素时从最后一个到第一个，既可以读也可修改。
常量的反向迭代器 const_reverse_iterator：输出元素时从最后一个到第一个，既可以读也可修改。

顺序容器、关联容器，都支持正向迭代器与反向迭代器。

1. iterator

#include <iostream>
#include <vector>
using namespace std;

int main()
{
	vector<int> vec;
	int i = 0;
	for (i = 0; i < 20; i++)
	{
		vec.push_back(rand() % 100 + 1);
	}

	vector<int>::iterator it = vec.begin();
	for (; it != vec.end(); it++)
	{
		cout << *it << " ";
		if (*it % 2 == 0)
		{
			*it = 0;
		}
	}
	cout << endl;

	for (int v : vec)
	{
		cout << v << " ";
	}
	cout << endl;

	return 0;
}

2. const_iterator

底层原理：

// const_iterator <= iterator
class const_iterator
{
public:
	const T& operator*()
	{
		return *_ptr;
	}
}
class iterator : public const_iterator
{
	T& operator*()
	{
		return *_ptr;
	}
}
// class const_iterator{}基类
// class iterator : public const_iterator派生类

语法：

1 2	`// vector<int>::iterator it1 = vec.begin();//可以接受派生类对象 vector<int>::const_iterator it1 = vec.begin();`

将上面普通的正向迭代器换为常量的正向迭代器，编译器报错。

3. reverse_iterator

#include <iostream>
#include <vector>
using namespace std;

int main()
{
	vector<int> vec;
	int i = 0;
	for (i = 0; i < 20; i++)
	{
		vec.push_back(rand() % 100 + 1);
	}

	vector<int>::reverse_iterator it = vec.rbegin();
	for (; it != vec.rend(); it++)
	{
		cout << *it << " ";
		if (*it % 2 == 0)
		{
			*it = 0;
		}
	}
	cout << endl;

	return 0;
}

4. const_reverse_iterator

1 2	`//vector<int>::reverse_iterator rit = vec.rbegin(); vector<int>::const_reverse_iterator rit = vec.rbegin();`

9. 函数对象

函数对象：拥有 ()operator 重载函数的对象即函数对象，函数对象类似 C 语言里面的函数指针，但在 C++ 里为函数对象。

1. 函数对象解释

下图为，C 语言进行函数调用与 C++ 中两个函数调用。

看起来它们好像一模一样，但是 C 语言中的 sum()，是函数名为一个地址；但 C++ 中的 sum() 为一个对象，sum 调用自己的 ( ) 重载函数将 10 与 20 传给 sum 调用的 () 运算符重载函数了，它接受两个实参，再执行 a+b。

这里就把 () 运算符重载函数的对象，称作函数对象，或者称作仿函数。

好处：

template<typename T>
bool compare(T a, T b)
{
	return a > b;
}

int main()
{
	cout << compare(10, 20) << endl;
	cout << compare('b','y') << endl;

	return 0;
}

实现了一个比较大于的函数模板，这里编译器会根据实参推导出 T 的类型，再从原模板实例化处理整型与 char 类型的 compare() 函数。

但是它不够灵活，有时想比较小于，每次改动符号有些麻烦，C 语言中的函数指针刚好可以很好解决这个问题。

#include <iostream>
using namespace std;

// 使用C的函数指针解决
template<typename T>
bool myGreater(T a, T b)
{
	return a > b;
}

template<typename T>
bool myLess(T a, T b)
{
	return a < b;
}

// compare是C++的库函数模板
template<typename T, class Compare>
bool compare(T a, T b, Compare comp)
{
	return comp(a, b);
}

int main()
{
	
	cout << "大于："
		<< compare(10, 20, myGreater<int>) << endl;
	cout << "小于："
		<< compare(10, 20, myLess<int>) << endl;

	return 0;
}

此时，就可以很好的解决这个问题了，当传入不同的函数指针来解决，想比较大就传入 myGreater，想比较小就传入 myLess，通过函数指针间接调用函数。

这里，使用函数指针虽然解决了问题，但函数指针无法进行内联，有函数的调用开销，效率很低；即使将其能够写为内联函数，编译的时候还是不知道调用时 myGreater，myLess。这里是通过函数指针间接调用的，编译器在编译过程中看到函数指针时候，不知道其调用的哪个函数，只有运行时候才知道。

因此，C++ 有一个专门的函数对象来解决这个问题。

#include <iostream>
using namespace std;

// C++ 对象实现
template<class T>
class myGreater {
public:
	bool operator()(T a, T b)
	{
		return a > b;
	}
};

template<class T>
class myLess {
public:
	bool operator()(T a, T b)
	{
		return a < b;
	}
};

// compare 是 C++ 的库函数模板
template<typename T, class Compare>
bool compare(T a, T b, Compare comp)
{
	// 编译过程知道调用对象的函数 operator()(a, b);
	return comp(a, b);
}

int main()
{
	
	cout << "大于："
		<< compare(10, 20, myGreater<int>()) << endl;
	cout << "小于："
		<< compare(10, 20, myLess<int>()) << endl;

	return 0;
}

通过函数对象调用 () 运算符重载，可以省略函数的调用开销，比通过函数指针调用函数(不能内联调用)效率高。
因为函数对象是用类生成的，所以可以添加相关的成员变量用来记录函数对象使用时更多的信息。

2. 使用示例

优先级队列

#include <iostream>
#include <queue>
using namespace std;

int main()
{
	// 底层vector
	priority_queue<int> que;
	// 大根堆
	int i = 0;
	for (i = 0; i < 10; i++)
	{
		que.push(rand() % 100 + 1);
	}

	while (!que.empty())
	{
		cout << que.top() << " ";
		que.pop();
	}
	cout << endl;

	return 0;
}

如何使用小根堆：

库中的实现：

1
2
3

template<class _Ty,
	class _Container = vector<_Ty>,
	class _Pr = less<typename _Container::value_type> >

将 less 改为 greater 即可变为小根堆即可。

1	`using MinHeap = priority_queue<int, vector<int>, greater<int>>;`

完整代码：

#include <iostream>
#include <queue>
using namespace std;

using MinHeap = priority_queue<int, vector<int>, greater<int>>;

int main()
{
	// 底层vector
	MinHeap que;
	// 大根堆
	int i = 0;
	for (i = 0; i < 10; i++)
	{
		que.push(rand() % 100 + 1);
	}

	while (!que.empty())
	{
		cout << que.top() << " ";
		que.pop();
	}
	cout << endl;

	return 0;
}

set 集合

set 底层为红黑树，默认底层从小到大进行输出。底层为：

1
2
3

template<class _Kty,
	class _Pr = less<_Kty>,
	class _Alloc = allocator<_Kty> >

set<int, greater<int>> set;
for (int i=0; i<10; ++i)
{
	set.insert(rand() % 100);
}

for (int v : set)
{
	cout << v << " ";
}
cout << endl;

10. 泛型算法和绑定器

1. 泛型算法

使用 STL 库中提供的泛型算法需要引入：

1	`#include <algorithm>`

泛型算法：template + 迭代器 + 函数对象；用模板实现的，接收的是容器的迭代器，还可以更改运算结果。

特点：

泛型算法的参数接受的都是迭代器。
泛型算法的参数还可以接受函数对象。

int arr[] = {12, 4, 78, 9, 21, 43, 56, 52, 42, 31};
vector<int> vec(arr, arr+sizeof(arr)/sizeof(arr[0]));

for (int v : vec)
{
	cout << v << " ";
}
cout << endl;

sort(vec.begin(), vec.end());//begin——end之间元素默认小到大排序

for (int v : vec)
{
	cout << v << " ";
}
cout << endl;

在上面有序的容器进行二分查找

int arr[] = {12, 4, 78, 9, 21, 43, 56, 52, 42, 31};
vector<int> vec(arr, arr+sizeof(arr)/sizeof(arr[0]));

for (int v : vec)
{
	cout << v << " ";
}
cout << endl;

sort(vec.begin(), vec.end());//begin——end之间元素默认小到大排序

for (int v : vec)
{
	cout << v << " ";
}
cout << endl;

if (binary_search(vec.begin(), vec.end(), 21));
{
	cout << "21存在" <<endl;
}

改变 sort 排序方式

// 传入函数对象greater，改变容器元素比较方式
sort(vec.begin(), vec.end(), greater<int>());

for (int v : vec)
{
	cout << v << " ";
}
cout << endl;

for_each 将容器中所有偶数打印出来。

// for_each可以遍历容器的所有元素，可以自行添加合适的函数对象
// 对容器的元素进行过滤。
for_each(vec.begin(), vec.end(), 
	[](int val)->void   // 拉姆达表达式
{
	if (val %2 == 0)
	{
		cout << val << " ";
	}
});

2. 绑定器

包含头文件：

1	`#include <functional>`

绑定器：绑定器 + 二元函数对象 = 一元函数对象。

bind1st：把二元函数对象 operator()(a,b) 第一个形参绑定起来，绑定为固定的值，只需要传入一个实参。
bind2nd：把二元函数对象 operator()(a,b) 第二个形参绑定起来，绑定为固定的值，只需要传入一个实参。

//78 56 52 43 42 31 21 12 9 4
//find_if
//将48按序插入到vector中 找第一个小于48的数字，需要的是一元函数对象
//因此我们需要绑定器
//greater a > b   less a < b
auto it2 = find_if(vec.begin(), vec.end(), 
	bind1st(greater<int>(), 48));
//bind2nd(less<int>(),48);
//[](int val)->bool{return val < 48;}); 拉姆达表达式
vec.insert(it2, 48);
for (int v : vec)
{
	cout << v << " ";
}
cout << endl;

#C++

07.C++ STL

http://example.com/2023/08/09/02.C++ 基础部分/07.C++ STL/

Author

Yakumo

Posted on

August 9, 2023

Licensed under

08.C++ 优化 Previous

04.C++ 函数模板 Next