[C++知识库]STL整理

目录

STL 6大组件

一、容器

1. string

1.1 构造函数原型

1.2?赋值操作

1.3 字符串拼接

1.4 查找和替换

1.5 字符串比较

1.6 字符存取

1.7 插入和删除

1.8?从字符串中获取想要的子串

2. vector 单端数组

2.1 构造函数

2.2 赋值操作

2.3?对vector容量和大小操作

2.4?插入与删除

2.5?数据存取

2.6?互换容器和预留空间

3. deque 双端数组，可以对头端进行插入删除操作

3.1 构造函数

3.2 赋值

3.3 大小操作

3.4 插入与删除

3.5 数据存取

3.6 排序

4.?stack 栈，先进后出

5. queue 队列，先进先出

6. list 链表

6.1 构造函数

6.2 赋值

6.3 大小操作

6.4 插入和删除

6.5 数据存取

6.6 反转和排序

7. set/multset 关联式容器

7.1 构造和赋值

7.2 大小和交换

7.3 插入和删除

7.4 查找和统计

7.5 pair对组创建

7.6 set容器排序，仿函数

8. map，所有元素都是pair

8.1 构造和赋值

8.2 大小和交换

8.3 插入和删除

8.4 查找和统计

8.5 排序

二、函数对象、谓词

1. 函数对象

1.1 概念

1.2?函数对象在使用时可以像普通函数调用

1.3?函数对象超出普通函数的概念，函数对象可以有自己的状态

1.4?函数对象可以作为参数传递

2. 谓词

3. 内建函数对象（仿函数）

3.1 算术仿函数

3.2 关系仿函数

3.3 逻辑仿函数

三、STL常用算法

1. 常用遍历算法

1.1 for_each

1.2?transform

2. 常用查找算法

2.1?find

2.2?find_if

2.3?adjacent_find

2.4?binary_search

2.5?count

2.6?count_if

3. 常用排序算法

3.1?sort

3.2?random_shuffle

3.3?merge

3.4?reverse

4. 常用拷贝和替换算法

4.1?copy

4.2?replace

4.3?replace_if

4.4?swap

5. 常用算术生成算法

5.1?accumulate

5.2?fill

6. 常用集合算法

6.1?set_intersection 交集

6.2?set_union 并集

6.3?set_difference 差集

STL 6大组件

?? ?1.容器：各种数据结构，vector、list、deque、set、map等，用来存放数据
?? ?2.算法：各种常用的算法，如sort、find、copy、for_each等
?? ?3.迭代器：扮演了容器与算法之间的粘合剂
?? ?4.仿函数：行为类似函数，可作为算法的某种策略
?? ?5.适配器（配接器）：一种用来修饰容器或者仿函数或者迭代器接口的东西
?? ?6.空间适配器：负责空间的配置与管理

一、容器

1. string

string本质是一个类

1.1 构造函数原型

string();?? ??? ??? ??? ??? ??? ?// 创建一个空的字符串
string(const char* s);?? ??? ??? ?// 使用字符串s初始化
string(const string& str);?? ??? ?// 使用一个string对象初始化另一个string对象
string(int n,char c);?? ??? ??? ?// 使用n个字符c初始化

// ex
void test1()
{
	string s1;		// 默认构造

	// const char* str = "hello"
	string s2("hello");
	cout << "s2 = " << s2 << endl;

	string s3(s2);
	cout << "s3 = " << s3 << endl;

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

1.2?赋值操作

string& operator=(const char* s);		// char*类型字符串赋值给当前字符串
string& operator=(const string &s);		// 把字符串s赋给当前字符串
string& operator=(char c);				// 字符赋值给当前的字符串
string& assign(const char *s);			// 把字符串s赋给当前字符串
string& assign(const char *s，int n);	// 把字符串s的前n个字符赋给当前字符串
string& assign(const string &s);		// 把字符串s赋给当前字符串
string& assign(int n, char c);			// 用n个字符c赋给当前字符

// ex
void test2()
{
	string s1;
	s1 = "hello";
	cout << "s1 = " << s1 << endl;

	string s2;
	s2 = s1;
	cout << "s2 = " << s2 << endl;

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

	string s4;
	s4.assign("hello,aa");
	cout << "s4 = " << s4 << endl;

	string s5;
	s5.assign("hello,aa", 3);
	cout << "s5 = " << s5 << endl;

	string s6;
	s6.assign(s5);
	cout << "s6 = " << s6 << endl;

	string s7;
	s7.assign(8,'w');
	cout << "s7 = " << s7 << endl;
}

1.3 字符串拼接

string& operator+=(const char* str);	// 重载+=运算符
string& operator+=(const char c);		// 重载+=操作符
string& operator+=(const string& str);	// 重载+=操作符
string& append(const char *s);			// 把字符串s连接到当前字符串结尾
string& append(const char *s, int n);	// 把字符串s的前n个字符连接到当前字符串结尾
string& append(const string &s);		// 同operator+=(const string& str)
string& append(const string &s, int pos, int n);	// 字符串从pos开始的n个字符连接到字符串结尾

// ex
void test3()
{
	string s1("I");
	s1 += " lov";
	cout << s1 << endl;

	s1 += 'e';
	cout << s1 << endl;

	string s2(" hahaha");
	s1 += s2;
	cout << s1 << endl;
	
	s1.append(".www");
	cout << s1 << endl;

	s1.append("abcdefg", 3);
	cout << s1 << endl;

	string s3("xixixi");
	s1.append(s3);
	cout << s1 << endl;

	string s4("abcde");
	s1.append(s4, 0, 2);
	cout << s1 << endl;
}

1.4 查找和替换

// 函数后的const：告诉系统，这个函数，不会修改对象里的任何成员变量的值
int find(const string& str, int pos = 0) const;		// 查找str第一次出现位置，从pos开始查找
int find(const char* s, int pos = 0) const;			// 查找s第一次出现位置，从pos开始查找
int find(const char* s, int pos, int n) const;		// 从pos位置查找s的前n个字符第一次出现位置
int find(const char c, int pos = 0) const;			// 查找字符c第一次出现位置
int rfind(const string& str, int pos = npos) const;	// 查找str最后一次位置，从POS开始查找
int rfind(const char* s, int pos = npos) const;		// 查找s最后一次位置，从POS开始查找
int rfind(const char* s, int pos = 0, int n) const;		// 从pos查找s的前n个字符最后一次位置
int rfind(const char c, int pos = 0) const;			// 查找字符c最后一次位置
string& replace(int pos, int n, const string& str); // 替换从pos开始n个字符为字符串str
string& replace(int pos, int n, const char* s);		// 替换从pos开始的n个字符为字符串s

// ex
void test4()
{
	string str1 = "abcdefghijde";

	// find从左向右查找，ifind从右向左查找
	// 未查找到，返回-1
	int pos1 = str1.find("de");
	int pos2 = str1.rfind("de");
	cout << pos1 << endl;
	cout << pos2 << endl;

	str1.replace(0, 2, "hhhhh");
	cout << str1 << endl;
}

1.5 字符串比较

// = 返回0；> 返回1；< 返回-1
int compare(const string& s) const;		// 与字符串s比较
int compare(const char* s) const;		// 与字符串s比较

// ex
void test5()
{
	string s1 = "hellop";
	string s2 = "hello";

	if (s1.compare(s2))
	{
		cout << "相等" << endl;
	}
	else
	{
		cout << "不相等" << endl;
	}
}

1.6 字符存取

char& operator[](int n);			// 通过[]方式取字符
char& at(int n);					// 通过at方法获取字符

// ex
void test6()
{
	string s = "hello";

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

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

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

1.7 插入和删除

string& insert(int pos, const char* s);		// 插入字符串
string& insert(int pos, const string& str);	// 插入字符串
string& insert(int pos, int n, char c);		// 在指定位置插入n个字符c
string& erase(int pos, int n = npos);		// 删除从pos开始的n个字符

// ex
void test7()
{
	string s = "hellp";
	s.insert(1, "111");
	cout << s << endl;

	// 删除
	s.erase(1,3);
	cout << s << endl;
}

1.8?从字符串中获取想要的子串

string substr(int pos = 0, int n = npos) const;		// 返回由pos开始的n个字符组成的字符串

// ex
void test8()
{
	string s = "abcde";
	
	string s2 = s.substr(1, 3);
	cout << s2 << endl;
}

2. vector 单端数组

vector与普通数组区别：
?? ?数组是静态空间，vector可以动态扩展，vector容器的迭代器是支持随机访问的迭代器。
?? ?动态扩展不是在原空间之后续接空间，而是找更大的内存空间，将源数据拷贝新空间，释放原空间。

2.1 构造函数

vector<T> v;				// 采用模板实现类实现，默认构造函数
vector(v.begin(),v.end());	// 将 v中 [begin(),end())区间的元素拷贝给本身
vector(n,elem);				// 将n个elem拷贝给本身
vector(const vector &v);	// 拷贝构造

// ex
void test1()
{
	vector<int> v1;
	for (int i = 0; i < 10; i++)
	{
		v1.push_back(i);
	}
	printVec(v1);

	// 通过区间进行构造
	vector<int>v2(v1.begin(), v1.end());
	printVec(v2);

	// n个elem
	vector<int>v3(5, 10);
	printVec(v3);

	vector<int>v4(v3);
	printVec(v4);
}

2.2 赋值操作

vector& operator=(const vector &v);		// 重载等号操作符
assign(v.begin(),v.end());				// 将 [begin(),end()) 区间中的数据拷贝赋值给本身
assign(n,elem);							// 将n个elem拷贝赋值给本身

// ex
void test2()
{
	vector<int> v1;
	for (int i = 0; i < 10; i++)
	{
		v1.push_back(i);
	}
	printVec(v1);

	vector<int>v2;
	v2 = v1;
	printVec(v2);

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

	vector<int>v4;
	v4.assign(3, 5);
	printVec(v4);
}

2.3?对vector容量和大小操作

empty();		// 判断容器是否为空
capacity();		// 容器的容量
size();			// 返回容器中元素的个数
resize(int num);	// 重新指定容器的长度num，若容器变长，则以默认值填充；若变短，则末尾超出容器长度的元素被删除
resize(int num, elem);	// 重新指定容器的长度num，若容器变长，则以elem填充；若变短，则末尾超出容器长度的元素被删除

// ex
void test3()
{
	vector<int> v1;
	for (int i = 0; i < 10; i++)
	{
		v1.push_back(i);
	}
	printVec(v1);

	if (v1.empty())
	{
		cout << "v1为空" << endl;
	}
	else
	{
		cout << "v1容量为：" << v1.capacity() << endl;
		cout << "v1大小为：" << v1.size() << endl;
	}

	// 改变大小
	v1.resize(15);
	printVec(v1);
	v1.resize(5);
	printVec(v1);
}

2.4?插入与删除

push_back(ele);			// 尾部插入元素ele
pop_back();				// 删除最后一个元素
insert(const_interator pos, ele);		// 迭代器指向pos，插入元素ele
insert(const_interator pos, int count, ele);		// 迭代器指向pos，插入count个元素ele
erase(const_interator pos);		// 删除迭代器指向的元素
erase(const_interator start, const_interator end);		// 删除迭代器从start到end之间的元素
clear();				// 删除容器中的所有元素

// ex
void test4()
{
	vector<int>v1;

	// 尾插
	v1.push_back(1);
	v1.push_back(2);
	v1.push_back(3);
	v1.push_back(4);
	v1.push_back(5);
	v1.push_back(6);
	v1.push_back(7);
	printVec(v1);

	// 尾删
	v1.pop_back();
	printVec(v1);

	// 插入
	v1.insert(v1.begin(), 10);
	printVec(v1);

	// 删除
	v1.erase(v1.begin());
	printVec(v1);

	// 清空
	v1.clear();
	printVec(v1);
}

2.5?数据存取

at(int idx);		// 返回索引idx所指的数据
operator[];			// 返回索引idx所指的数据
front();			// 返回容器中第一个数据元素
back();				// 返回容器中最后一个数据元素

// ex
void test5()
{
	vector<int> v1;
	for (int i = 0; i < 10; i++)
	{
		v1.push_back(i);
	}
	
	// at访问
	for (int i = 0; i < v1.size(); i++)
	{
		cout << v1.at(i) << " ";
	}
	cout << endl;

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

	cout << "第一个元素" << v1.front() << endl;
	cout << "最后一个元素" << v1.back() << endl;
}

2.6?互换容器和预留空间

swap(vec);			// 将vec与本身的元素互换
reserve(int len);	// 容器预留len个元素长度，预留位置不初始化，元素不可访问

// ex
// 预留空间
void test7()
{
	vector<int>v;
	v.reserve(10000);	// 给容器足够空间，让它不用反复开辟空间
	int num = 0;	// 统计开辟次数
	int* p = NULL;
	for (int i = 0; i < 10000; i++)
	{
		v.push_back(i);
		if (p != &v[0])
		{
			p = &v[0];
			num++;
		}
	}
	cout << "num = " << num << endl;
}

// 互换容器
void test6()
{
	vector<int> v1;
	for (int i = 0; i < 10; i++)
	{
		v1.push_back(i);
	}
	printVec(v1);

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

	v1.swap(v2);
	printVec(v1);
	printVec(v2);

	// 使用swap收缩内存
	vector<int>v3;
	for (int i = 0; i < 10000; i++)
	{
		v3.push_back(i);
	}
	cout << "v3的容量为：" << v3.capacity() << endl;
	cout << "v3的大小为：" << v3.size() << endl;

	v3.resize(3);
	cout << "v3的容量为：" << v3.capacity() << endl;
	cout << "v3的大小为：" << v3.size() << endl;

	vector<int>(v3).swap(v3);
	cout << "v3的容量为：" << v3.capacity() << endl;
	cout << "v3的大小为：" << v3.size() << endl;

	// vector<int>(v3)   创建匿名对象，拷贝了v3的内容，此时v3的大小为3，会根据v3大小开辟内存
}

3. deque 双端数组，可以对头端进行插入删除操作

deque与vector区别
????????vector对于头部的插入删除效率太低，数据量越大，效率越低
????????deque相对vector，对头部的插入删除速度更快
????????vector访问元素时的速度比deque快，这与两者内部实现有关

3.1 构造函数

deque<T>deqT;		// 默认构造形式
deque(beg,end);		// 构造函数将[beg, end)区间中的元素拷贝给本身
deque(n,elem);		// 构造函数将n个elem拷贝给本身
deque(const deque &deq);		// 拷贝构造函数

// ex
void test1()
{
	deque<int>d1;
	for (int i = 0; i < 10; i++)
	{
		d1.push_back(i);
	}
	printDeque(d1);

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

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

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

3.2 赋值

deque& operator=(const deque &d);		// 重载等号操作符
assign(d.begin(),d.end());				// 将 [begin(),end()) 区间中的数据拷贝赋值给本身
assign(n,elem);							// 将n个elem拷贝赋值给本身

// ex
void test2()
{
	deque<int>d1;
	for (int i = 0; i < 10; i++)
	{
		d1.push_back(i);
	}
	printDeque(d1);

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

	deque<int>d3;
	d3.assign(5, 10);
	printDeque(d3);
}

3.3 大小操作

empty();			// 判断是否为空
size();				// 返回容器中元素个数
resize(int num);	// 重新指定容器的长度num，若容器变长，则以默认值填充；若变短，则末尾超出容器长度的元素被删除
resize(int num, elem);	// 重新指定容器的长度num，若容器变长，则以elem填充；若变短，则末尾超出容器长度的元素被删除

3.4 插入与删除

push_back(ele);			// 尾部插入元素ele
push_front(ele);		// 头部插入元素ele
pop_back();				// 删除最后一个数据
pop_front();			// 删除容器第一个数据
insert(const_interator pos, ele);		// 迭代器指向pos，插入元素ele，返回新元素的位置
insert(const_interator pos, int count, ele);		// 迭代器指向pos，插入count个元素ele，无返回值
insert(pos,beg,end);	// 在pos位置插入[beg,end)区间的数据，无返回值
erase(const_interator pos);		// 删除迭代器指向的元素，返回下一个数据的位置
erase(const_interator begin, const_interator end);		// 删除迭代器从begin到end之间的数据，返回下一个数据的位置
clear();				// 删除容器中的所有元素

// ex
void test4()
{
	deque<int>d1;
	d1.push_back(10);
	d1.push_back(20);
	d1.push_back(25);

	// 头插
	d1.push_front(30);
	printDeque(d1);

	// 尾删
	d1.pop_back();
	printDeque(d1);

	// 头删
	d1.pop_front();
	printDeque(d1);

	d1.insert(d1.begin(), 5);
	printDeque(d1); 

	d1.insert(d1.begin(), 5, 8);
	printDeque(d1);
}

3.5 数据存取

at(int idx);		// 返回索引idx所指的数据
operator[];			// 返回索引idx所指的数据
front();			// 返回容器中第一个数据元素
back();				// 返回容器中最后一个数据元素

// ex
void test5()
{
	deque<int>d1;
	for (int i = 0; i < 10; i++)
	{
		d1.push_back(i);
	}
	for (int i = 0; i < d1.size(); i++)
	{
		cout << d1[i] << " ";
	}
	cout << endl;

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

3.6 排序

sort(iterator beg, iterator end)		// 对beg和end区间内元素进行排序

// ex
void test6()
{
	deque<int>d1;
	d1.push_back(10);
	d1.push_back(60);
	d1.push_back(50);
	d1.push_back(40);
	d1.push_back(30);
	d1.push_back(20);
	d1.push_back(70);
	printDeque(d1);

	// 排序，默认从小到大
	// 对于支持随机访问的迭代器的容器，都可以利用sort算法直接对其进行排序
	sort(d1.begin(), d1.end());
	printDeque(d1);
}

4.?stack 栈，先进后出

stack是一种先进后出的数据结构，它只有一个出口
栈中只有顶端的元素才可以被外界使用，因此栈不允许有遍历行为

// 构造函数
	stack<T> stk;		// stack采用模板类实现，stack对象的默认构造形式

// 赋值操作
	stack& operator=(const stack &stk);		

// 数据存取
	push(elem);		// 存数据
	pop();			// 取数据
	top();			// 返回栈顶元素

// 大小操作
	empty();		// 判断是否为空
	size();			// 返回栈的大小

5. queue 队列，先进先出

queue是一种先进先出的数据结构，它有两个出口
队列中只有队头和队尾才可以被外界使用，因此不允许有遍历行为

// 构造函数
	queue<T> que;
	queue(const queue& que);

// 赋值操作
	queue& operate=(const queue &que);

// 数据存取
	push(elem);		// 队尾添加元素
	pop();			// 移除队头第一个元素
	back();			// 返回最后一个元素
	front();		// 返回第一个元素

// 大小操作
	empty();
	size();	

6. list 链表

链表（list）是一种物理存储单元上的非连续存储结构，逻辑顺序是通过链表中的指针连接实现的

功能：将数据进行链式存储，STL中的链表是一个双向循环链表

优点：可以对任意位置快速插入或删除元素；采用动态存储分配，不会造成内存浪费和溢出
缺点：遍历速度没有数组快；占用空间比数组大

void printList(const list<int>& ls)
{
	for (list<int>::const_iterator it = ls.begin(); it != ls.end(); it++)
	{
		cout << *it << "   ";
	}
	cout << endl;
}

6.1 构造函数

list<T>list;
list(beg,end);		// 将[beg,end)区间的元素拷贝给本身
list(n,elem);
list(const list &list);

// ex
void test1()
{
	list<int>l1;
	l1.push_back(10);
	l1.push_back(20);
	l1.push_back(30);
	l1.push_back(40);
	printList(l1);

	list<int>l2(l1.begin(), l1.end());
	printList(l2);

	list<int>l3(5, 8);
	printList(l3);

	list<int>l4(l3);
	printList(l4);
}
 

6.2 赋值

assign(begin,end);
assign(n,elem);
list& operator=(const list &list);
swap(lst);			// 将lst与本身的元素互换

// ex
void test2()
{
	list<int>l1;
	for (int i = 0; i < 5; i++)
	{
		l1.push_back(i);
	}
	printList(l1);

	list<int>l2;
	l2.assign(l1.begin(), l1.end());
	printList(l2);

	list<int>l3;
	l3.assign(5, 8);
	printList(l3);

	list<int>l4;
	l4 = l1;
	printList(l4);

	l4.swap(l3);
	cout << "L3:";
	printList(l3);
	cout << "L4:";
	printList(l4);
}

6.3 大小操作

size();
empty();
resize(num);
resize(num,elem);

// ex
void test3()
{
	list<int>l1;
	for (int i = 0; i < 5; i++)
	{
		l1.push_back(i);
	}
	printList(l1);

	if (l1.empty())
	{
		cout << "l1为空" << endl;
	}
	else
	{
		cout << "l1的大小为：" << l1.size() << endl;
	}

	l1.resize(8);
	printList(l1);

	l1.resize(10, 3);
	printList(l1);
}

6.4 插入和删除

push_back(elem);
pop_back();
push_front(elem);
pop_front();
insert(pos,elem);		// 返回新数据的位置
insert(pos,n,elem);		// 无返回值
insert(pos,beg,end);	// 无返回值
clear();
erase(beg,end);		// 删除[beg,end)区间数据，返回下一个数据的位置
erase(pos);			// 删除pos位置的数据，返回下一个数据的位置
remove(elem);		// 删除所有与elem值匹配的元素

// ex
void test4()
{
	list<int>l1;

	l1.push_back(10);
	l1.push_back(20);
	l1.push_back(30);
	l1.push_back(40);
	l1.push_front(100);
	l1.push_front(200);
	l1.push_front(300);
	printList(l1);

	l1.pop_back();
	l1.pop_front();
	printList(l1);

	l1.insert(l1.begin(), 5);
	printList(l1);

	list<int>::iterator it = l1.begin();
	l1.insert(++it, 1000);
	printList(l1);

	it = l1.begin();
	l1.erase(++it);
	printList(l1);

	l1.remove(10);
	printList(l1);

	l1.clear();
	printList(l1);
}

6.5 数据存取

front();
back();

// ex
void test5()
{
	list<int>l1;

	l1.push_back(10);
	l1.push_back(20);
	l1.push_back(30);
	l1.push_back(40);

	cout << "第一个元素：" << l1.front() << endl;
	cout << "最后一个元素：" << l1.back() << endl;
}

6.6 反转和排序

reverse();		// 反转链表
sort();			// 链表排序

// ex
// 7.排序案例
typedef struct Person
{
	Person(string name, int age, int height)
	{
		this->name = name;
		this->age = age;
		this->height = height;
	}
	string name;
	int age;
	int height;
}Person;

// 按指定规则进行排序
bool comparePerson(Person& p1, Person& p2)
{
	if (p1.age == p2.age)
	{
		return p1.height < p2.height;
	}
	else
	{
		return p1.age < p2.age;
	}
}

void test7()
{
	list<Person>l;

	Person p1("张三", 35, 166);
	Person p2("李四", 45, 156);
	Person p3("王五", 60, 178);
	Person p4("张飞", 35, 180);
	Person p5("周武", 35, 173);

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

	for (list<Person>::iterator it = l.begin(); it != l.end(); it++)
	{
		cout << "姓名：" << it->name << "  " << "年龄：" << it->age << "  " << "身高：" << it->height << endl;
	}

	cout << "----------------------------------------------" << endl;
	cout << "排序后：" << endl;
	l.sort(comparePerson);			// 自定义数据类型，需要指定排序规则
	for (list<Person>::iterator it = l.begin(); it != l.end(); it++)
	{
		cout << "姓名：" << it->name << "  " << "年龄：" << it->age << "  " << "身高：" << it->height << endl;
	}
}

// 6.反转和排序
void test6()
{
	list<int>l1;

	l1.push_back(10);
	l1.push_back(20);
	l1.push_back(50);
	l1.push_back(40);
	printList(l1);

	// 所有不支持随机访问迭代器的容器，不可以用标准算法，sort(l1.begin(),l1.end())是无法使用的
	l1.sort();
	printList(l1);

	l1.reverse();
	printList(l1);
}

7. set/multset 关联式容器

set/multset属于关联式容器，底层结构由二叉树实现，所有元素都会在插入时自动被排序
二者区别
?? ?set不允许容器中有重复的元素
?? ?multiset允许容器中有重复的元素

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

// 5.set和muliset区别
void test5()
{
	set<int>s;

	pair<set<int>::iterator, bool>ret = s.insert(10);
	if (ret.second)
	{
		cout << "第一次插入成功" << endl;
	}
	else
	{
		cout << "第一次插入失败" << endl;
	}

	ret = s.insert(10);
	if (ret.second)
	{
		cout << "第二次插入成功" << endl;
	}
	else
	{
		cout << "第二次插入失败" << endl;
	}

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

7.1 构造和赋值

set<T>st;	
set(const set &st);

set& operator=(const set &st);

// ex
void test1()
{
	set<int>s1;

	// 插入数据只有insert方式
	s1.insert(10);
	s1.insert(40);
	s1.insert(30);
	s1.insert(50);
	s1.insert(10);
	printSet(s1);

	set<int>s2(s1);
	printSet(s2);

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

7.2 大小和交换

size();
empty();
swap(st);

// ex
void test2()
{
	set<int>s1;
	s1.insert(10);
	s1.insert(40);
	s1.insert(30);
	s1.insert(50);

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

	set<int>s2;
	s2.insert(5);

	cout << "----------------" << endl;
	s1.swap(s2);
	cout << "s1:";
	printSet(s1);
	cout << "s2:";
	printSet(s2);
}

7.3 插入和删除

insert(elem);		// set插入数据时会返回插入结果，表示是否插入成功，multset不会
clear();
erase(pos);
erase(beg,end);
erase(elem);		// 删除值为elem的元素

// ex
void test3()
{
	set<int>s1;
	s1.insert(10);
	s1.insert(40);
	s1.insert(30);
	s1.insert(50);
	printSet(s1);

	set<int>::iterator it = s1.begin();
	s1.erase(++it);
	printSet(s1);

	s1.erase(40);
	printSet(s1);
}

7.4 查找和统计

find(key);		// 查找key是否存在，若存在，返回该键的元素的迭代器；不存在返回set.end();
count(key);		// 统计key元素的个数; 对set来说，结果要么为1，要么为0

// ex
void test4()
{
	set<int>s1;
	s1.insert(10);
	s1.insert(40);
	s1.insert(30);
	s1.insert(50);
	s1.insert(50);
	printSet(s1);

	set<int>::iterator pos = s1.find(80);
	if (pos != s1.end())
	{
		cout << "找到元素：" << *pos << "  " << "数量：" << s1.count(*pos) << endl;
	}
	else
	{
		cout << "未找到元素" << endl;
	}
}

7.5 pair对组创建

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

pair<T,T> p(v1,v2);
pair<T,T> p = make_pair(v1,v2);

// ex
// pair对组创建
void test6()
{
	// 第一种方式
	pair<string, int>p("aa", 10);
	cout << p.first << "   " << p.second << endl;

	// 第二种方式
	pair<string, int>p2 = make_pair("bb", 15);
	cout << p2.first << "   " << p2.second << endl;
}

7.6 set容器排序，仿函数

默认排序规则从小到大
利用仿函数，可以改变排序规则

// 7.排序
// 7.1内置类型排序
class MyCompare
{
public:
	bool operator()(int v1,int v2)const
	{
		return v1 > v2;
	}
};

void test7()
{
	set<int>s1;
	s1.insert(10);
	s1.insert(40);
	s1.insert(30);
	s1.insert(50);
	printSet(s1);

	// 指定排序规则从大到小
	set<int, MyCompare>s2;
	s2.insert(10);
	s2.insert(40);
	s2.insert(30);
	s2.insert(50);
	for (set<int, MyCompare>::iterator it = s2.begin(); it != s2.end(); it++)
	{
		cout << *it << "  ";
	}
	cout << endl;

}

// 7.2自定义数据类型
class Person
{
public:
	Person(string name, int age)
	{
		this->name = name;
		this->age = age;

	}
	string name;
	int age;
};

class comPerson
{
public:
	bool operator()(const Person& p1, const Person& p2)const
	{
		return p1.age > p2.age;
	}
};

void test8()
{
	set<Person, comPerson>s;
	Person p1("张三", 35);
	Person p2("李四", 25);
	Person p3("王五", 30);
	Person p4("张飞", 45);
	Person p5("周武", 75);

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

	for (set<Person,comPerson>::iterator it = s.begin(); it != s.end(); it++)
	{
		cout << it->name << "  " << it->age << "  " << endl;
	}
}

8. map，所有元素都是pair

pair第一个元素为 key(键值)，起到索引作用，第二个元素为value（实值）
所有元素都会根据元素的键值自动排序

本质
?? ?map/multimap属于关联式容器，底层结构是用二叉树实现

优点
?? ?可以根据key值快速找到value

map 和 multimap区别
?? ?map不允许容器中有重复 key 值元素
?? ?multimap允许容器中有重复 key 值元素

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

8.1 构造和赋值

map<T1,T2>mp;
map(const map &mp);

map& operator=(const map &mp);

// ex
void test1()
{
	map<int, int>mp;
	mp.insert(pair<int, int>(1, 10));
	mp.insert(pair<int, int>(2, 20));
	mp.insert(pair<int, int>(3, 30));
	mp.insert(pair<int, int>(4, 40));

	printmap(mp);

	map<int, int>mp2(mp);
	printmap(mp2);

	map<int, int>mp3;
	mp3 = mp2;
	printmap(mp2);
}

8.2 大小和交换

size();
empty()
swap(m1); 

// ex
void test2()
{
	map<int, int>mp;
	mp.insert(pair<int, int>(1, 10));
	mp.insert(pair<int, int>(2, 20));

	if (mp.empty())
	{
		cout << "为空" << endl;
	}
	else
	{
		cout << "大小为：" << mp.size() << endl;
	}

	map<int, int>mp2;
	mp2.insert(pair<int, int>(5, 15));
	mp2.insert(pair<int, int>(4, 25));
	printmap(mp);
	printmap(mp2);

	cout << "----------------" << endl;
	printmap(mp);
	printmap(mp2);
}

8.3 插入和删除

insert(elem);		// set插入数据时会返回插入结果，表示是否插入成功，multset不会
clear();
erase(pos);
erase(beg,end);
erase(key);			// 删除值为key的元素

// ex
void test3()
{
	map<int, int>mp;

	mp.insert(pair<int, int>(1, 10));

	mp.insert(make_pair(2, 20));

	mp.insert(map<int, int>::value_type(3, 30));

	// 不建议插入，可以利用key访问value
	mp[4] = 40;

	cout << mp[3] << endl;
	printmap(mp);
}

8.4 查找和统计

find(key);		// 查找key是否存在，若存在，返回该键的元素的迭代器；不存在返回set.end();
count(key);		// 统计key元素的个数; 对set来说，结果要么为1，要么为0

// ex
void test4()
{
	map<int, int>mp;
	mp.insert(make_pair(1, 10));
	mp.insert(make_pair(2, 20));
	mp.insert(make_pair(3, 30));

	map<int, int>::iterator pos = mp.find(3);
	if (pos != mp.end())
	{
		cout << "key:" << pos->first << "value:" << pos->second << endl;
	}
	else
	{
		cout << "未找到" << endl;
	}
}

8.5 排序

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

void test5()
{
	map<int, int, MyCompare>mp;
	mp.insert(make_pair(1, 10));
	mp.insert(make_pair(2, 20));
	mp.insert(make_pair(3, 30));

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

二、函数对象、谓词

1. 函数对象

1.1 概念

概念
????????重载函数调用操作符的类，其对象常称为函数对象
????????函数对象使用重载的（）时，行为类似函数调用，也叫仿函数

本质
????????函数对象（仿函数）是一个类，不是一个函数

使用特点
????????函数对象在使用时，可以像普通函数调用，可以有参数，可以有返回值
????????函数对象超出普通函数的概念，函数对象可以有自己的状态
????????函数对象可以作为参数传递

1.2?函数对象在使用时可以像普通函数调用

class MyAdd
{
public:
	int operator()(int v1, int v2)
	{
		return v1 + v2;
	}
};

1.3?函数对象超出普通函数的概念，函数对象可以有自己的状态

class MyPrint
{
public:
	MyPrint()
	{
		count = 0;
	}
	void operator()(string test)
	{
		cout << test << endl;
		count++;
	}
	int count;
};

1.4?函数对象可以作为参数传递

void doPrint(MyPrint& mp, string test)
{
	mp(test);
}

void test1()
{
	MyAdd myadd;
	cout << myadd(10, 10) << endl;

	MyPrint myprint;
	myprint("hhhhh");

	doPrint(myprint, "aaaa");

}

2. 谓词

返回bool类型的仿函数称为谓词
operator（）接受一个参数叫一元谓词，接受两个参数叫二元谓词

class Check
{
public:
	bool operator()(int v)
	{
		return v > 5;
	}
};

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

	// 查找容器中大于5的数字
	vector<int>::iterator it = find_if(v.begin(), v.end(), Check());
	if (it == v.end())
	{
		cout << "未找到" << endl;
	}
	else
	{
		cout << *it << endl;
	}
}

3. 内建函数对象（仿函数）

分类
?? ?算术仿函数
?? ?关系仿函数
?? ?逻辑仿函数

用法
?? ?仿函数产生的对象，用法和一般函数完全相同
?? ?使用内建函数对象，需要引入头文件 ?#include<functional>

3.1 算术仿函数

// 实现四则运算，其中negate是一元运算，其他都是二元
template<class T> T plus<T>				// 加法仿函数
template<class T> T minus<T>			// 减法仿函数
template<class T> T multiplies<T>		// 乘法仿函数
template<class T> T divides<T>			// 除法仿函数
template<class T> T negate<T>			// 取反仿函数

// ex
void test1()
{
	negate<int>n;
	cout << n(50) << endl;

	plus<int>p;
	cout << p(10, 3) << endl;
}

3.2 关系仿函数

// 实现关系对比
template<class T> bool equal_to<T>				// 等于
template<class T> bool not_equal_to<T>			// 不等于
template<class T> bool greater<T>				// 大于
template<class T> bool greater_equal<T>			// 大于等于
template<class T> bool less<T>					// 小于
template<class T> bool less_equal<T>			// 小于等于

// ex
void test2()
{
	vector<int>v;
	for (int i = 0; i < 10; i++)
	{
		v.push_back(i);
	}
	sort(v.begin(),v.end(),greater<int>());
	for (int i = 0; i < 10; i++)
	{
		cout << v[i] << endl;
	}
}

3.3 逻辑仿函数

template<class T> bool logical_and<T>				// 逻辑与
template<class T> bool logical_or<T>				// 逻辑或
template<class T> bool logical_not<T>				// 逻辑非

// ex
// 逻辑仿函数
void test3()
{
	vector<bool>v;
	v.push_back(true);
	v.push_back(true);
	v.push_back(false);
	v.push_back(true);

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

	vector<bool>v2;
	v2.resize(v.size());
	// 利用逻辑非搬运到v2中
	transform(v.begin(), v.end(), v2.begin(), logical_not<bool>());
	for (vector<bool>::iterator it = v2.begin(); it != v2.end(); it++)
	{
		cout << *it << "   ";
	}
	cout << endl;
}

三、STL常用算法

算法主要是由头文件<algorithm><functional><numeric>组成
<algorithm>是STL头文件中最大的一个，涉及到比较、交换、查找、遍历操作、复制、修改等
<numeric>体积很小，只包括几个在序列上进行简单数学运算的模板函数
<functional>定义了一些模板类，用以声明函数对象

1. 常用遍历算法

for_each(iterator beg, iterator end, _func)			// 遍历容器, _func 函数或者函数对象
transform(iterator beg, iterator end, iterator beg2, _func)		// 搬运容器到另一个容器中

1.1 for_each

void fun01(int v)
{
	cout << v << "   ";
}

class fun1
{
public:
	void operator()(int v1)
	{
		cout << v1 << "   ";
	}
};

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

	// for_each(v.begin(), v.end(), fun01);    // 普通函数
	for_each(v.begin(), v.end(), fun1());		// 仿函数
}

1.2?transform

class fun2
{
public:
	int operator()(int v)
	{
		return v;
	}
};

void test2()
{
	vector<int>v;
	v.push_back(10);
	v.push_back(50);
	v.push_back(20);
	v.push_back(40);
	v.push_back(30);
	for_each(v.begin(), v.end(), fun1());
	cout << endl;

	vector<int>v2;
	v2.resize(v.size());
	transform(v.begin(), v.end(), v2.begin(), fun2());
	
	for_each(v2.begin(), v2.end(), fun1());
}

2. 常用查找算法

find(iterator beg, iterator end, val)			// 查找元素,找到返回指定元素的迭代器，找不到返回结束迭代器end()
find_if(iterator beg, iterator end, _Pred)		// 按条件查找元素,_Pred:函数或者谓词（返回bool类型仿函数），找不到返回结束迭代器end()
adjacent_find(iterator beg, iterator end)		// 查找相邻重复元素,返回相邻元素的第一个位置的迭代器，找不到返回结束迭代器end()
binary_search(iterator beg, iterator end, val)		// 二分查找法,查找指定元素，查到返回true，否则false，在无序序列中不可用
count(iterator beg, iterator end, val)				// 统计元素个数
count_if(iterator beg, iterator end, _Pred)			// 按条件统计元素个数

// ex
class Per
{
public:
	Per(string name, int age)
	{
		this->age = age;
		this->name = name;
	}

	bool operator==(const Per& p)
	{
		if (this->age == p.age && this->name == p.name)
		{
			return true;
		}
		else
		{
			return false;
		}
	}
	string name;
	int age;
};

2.1?find

class vprint
{
public:
	void operator()(int v)
	{
		cout << v << "   ";
	}
};

void test1()
{
	vector<int>v1;
	for (int i = 0; i < 10; i++)
	{
		v1.push_back(i);
	}
	for_each(v1.begin(), v1.end(), vprint());
	cout << endl;

	vector<int>::iterator pos = find(v1.begin(), v1.end(), 5);
	if (pos == v1.end())
	{
		cout << "未找到" << endl;
	}

	// 自定义类型查找，需要在类中重定义 == 
	Per p1("a", 4);
	Per p2("b", 3);
	Per p3("c", 5);
	Per p4("d", 1);
	vector<Per>v2;
	v2.push_back(p1);
	v2.push_back(p2);
	v2.push_back(p3);
	v2.push_back(p4);

	vector<Per>::iterator pos2 = find(v2.begin(), v2.end(), p2);
	if (pos2 == v2.end())
	{
		cout << "未找到" << endl;
	}
}

2.2?find_if

class GreaterFive
{
public:
	bool operator()(int val)
	{
		return val > 5;
	}
};

class Greater3
{
public:
	bool operator()(Per &p)
	{
		return p.age > 3;
	}
};

void test2()
{
	vector<int>v1;
	for (int i = 0; i < 10; i++)
	{
		v1.push_back(i);
	}
	vector<int>::iterator pos = find_if(v1.begin(), v1.end(), GreaterFive());
	if (pos == v1.end())
	{
		cout << "未找到" << endl;
	}
	else
	{
		cout << *pos << endl;
	}

	// 自定义类型
	Per p1("a", 4);
	Per p2("b", 3);
	Per p3("c", 5);
	Per p4("d", 1);
	vector<Per>v2;
	v2.push_back(p1);
	v2.push_back(p2);
	v2.push_back(p3);
	v2.push_back(p4);

	vector<Per>::iterator it =  find_if(v2.begin(), v2.end(), Greater3());
	if (it == v2.end())
	{
		cout << "未找到" << endl;
	}
	else
	{
		cout << it->name << "   " << it->age << endl;
	}
}

2.3?adjacent_find

void test3()
{
	vector<int>v1;
	v1.push_back(0);
	v1.push_back(2);
	v1.push_back(0);
	v1.push_back(3);
	v1.push_back(1);
	v1.push_back(4);
	v1.push_back(3);
	v1.push_back(3);

	vector<int>::iterator pos = adjacent_find(v1.begin(), v1.end());
	if (pos == v1.end())
	{
		cout << "未找到" << endl;
	}
	else
	{
		cout << *pos << endl;
	}
}

2.4?binary_search

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

	// 查找是否有9
	bool ret = binary_search(v1.begin(), v1.end(), 9);
	if (ret)
	{
		cout << "找到" << endl;
	}
	else
	{
		cout << "未找到" << endl;
	}
}

2.5?count

void test5()
{
	vector<int>v1;
	v1.push_back(0);
	v1.push_back(2);
	v1.push_back(0);
	v1.push_back(3);
	v1.push_back(1);
	v1.push_back(4);
	v1.push_back(3);
	v1.push_back(3);

	int num = count(v1.begin(), v1.end(), 3);
	cout << "有" << num << "个3" << endl;

	Per p1("a", 4);
	Per p2("b", 3);
	Per p3("c", 5);
	Per p4("d", 1);
	Per p5("d", 1);
	Per p6("e", 1);
	vector<Per>v2;
	v2.push_back(p1);
	v2.push_back(p2);
	v2.push_back(p3);
	v2.push_back(p4);
	v2.push_back(p5);
	v2.push_back(p6);
	num = count(v2.begin(), v2.end(), p2);
	cout << "有" << num << "个p2" << endl;
}

2.6?count_if

class Greater2
{
public:
	bool operator()(int v)
	{
		return v > 2;
	}
};

void test6()
{
	vector<int>v1;
	v1.push_back(0);
	v1.push_back(2);
	v1.push_back(0);
	v1.push_back(3);
	v1.push_back(1);
	v1.push_back(4);
	v1.push_back(3);
	v1.push_back(3);

	int num = count_if(v1.begin(), v1.end(), Greater2());
	cout << "有" << num << "个大于2的数" << endl;

	//Per p1("a", 4);
	//Per p2("b", 3);
	//Per p3("c", 5);
	//Per p4("d", 1);
	//Per p5("d", 1);
	//Per p6("e", 1);
	//vector<Per>v2;
	//v2.push_back(p1);
	//v2.push_back(p2);
	//v2.push_back(p3);
	//v2.push_back(p4);
	//v2.push_back(p5);
	//v2.push_back(p6);
	//num = count(v2.begin(), v2.end(), p2);
	//cout << "有" << num << "个p2" << endl;
}

3. 常用排序算法

sort(iterator beg, iterator end, _Pred);				// 对容器内元素进行排序，_Pred 谓词
random_shuffle(iterator beg, iterator end)				// 洗牌，指定范围内元素随机调整次序
merge(iterator beg1,iterator end1,iterator beg2, iterator end2, iterator dest)			//容器元素合并，并存储到另一容器汇总，dest目标容器，两个容器必须是有序的,且规律相同，目标容器也会按照对应规律
reverse(iterator beg, iterator end)		 // 反转指定范围内的元素，首尾对调

// ex
class printint
{
public:
	void operator()(int a)
	{
		cout << a << "   ";
	}
};

3.1?sort

class large
{
public:
	bool operator()(int a1, int a2)
	{
		return a1 > a2;
	}
};

void test1()
{
	vector<int>v1;
	v1.push_back(0);
	v1.push_back(2);
	v1.push_back(0);
	v1.push_back(3);
	v1.push_back(1);
	v1.push_back(4);
	v1.push_back(3);
	v1.push_back(3);

	// sort(v1.begin(), v1.end(), large());
	sort(v1.begin(), v1.end(), greater<int>());		// 内建函数对象

	for_each(v1.begin(), v1.end(), printint());
}

3.2?random_shuffle

void test2()
{
	srand((unsigned int)time(NULL));
	vector<int>v;
	for (int i = 0; i < 10; i++)
	{
		v.push_back(i);
	}
	random_shuffle(v.begin(), v.end());

	for_each(v.begin(), v.end(), printint());
}

3.3?merge

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

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

	vector<int>v3;
	v3.resize(20);

	merge(v1.begin(), v1.end(), v2.begin(), v2.end(), v3.begin());

	for_each(v3.begin(), v3.end(), printint());
}

3.4?reverse

void test4()
{
	vector<int>v1;
	for (int i = 0; i < 10; i++)
	{
		v1.push_back(i);
	}
	for_each(v1.begin(), v1.end(), printint());
	reverse(v1.begin(), v1.end());
	
	cout << endl;
	for_each(v1.begin(), v1.end(), printint());
}

4. 常用拷贝和替换算法

copy(iterator beg, iterator end, iterator dest)				// 容器内指定范围元素拷贝到另一个容器中
replace(iterator beg, iterator end, oldval,newval)			// 容器内指定范围旧元素修改为新元素
replace_if(iterator beg, iterator end, _Pred, newval)		// 容器内指定范围满足条件的元素替换为新元素
swap(container c1, container c2)			// 互换两个容器的元素

// ex
class printint
{
public:
	void operator()(int a)
	{
		cout << a << "   ";
	}
};

4.1?copy

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

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

4.2?replace

void test2()
{
	vector<int>v1;
	for (int i = 0; i < 10; i++)
	{
		v1.push_back(i);
	}
	for_each(v1.begin(), v1.end(), printint());
	cout << endl;
	replace(v1.begin(), v1.end(), 3, 20);
	for_each(v1.begin(), v1.end(), printint());
}

4.3?replace_if

class greater5
{
public:
	bool operator()(int val)
	{
		return val > 5;
	}
};

void test3()
{
	vector<int>v1;
	for (int i = 0; i < 10; i++)
	{
		v1.push_back(i);
	}
	for_each(v1.begin(), v1.end(), printint());
	cout << endl;
	replace_if(v1.begin(), v1.end(), greater5(), 20);
	for_each(v1.begin(), v1.end(), printint());
}

4.4?swap

void test4()
{
	vector<int>v1;
	for (int i = 0; i < 10; i++)
	{
		v1.push_back(i);
	}
	vector<int>v2;
	v2.push_back(34);
	//v2.resize(v1.size());

	for_each(v1.begin(), v1.end(), printint());
	cout << endl;
	for_each(v2.begin(), v2.end(), printint());
	cout << endl;
	cout << "替换后" << endl;

	swap(v1, v2);
	for_each(v1.begin(), v1.end(), printint());
	cout << endl;
	for_each(v2.begin(), v2.end(), printint());
}

5. 常用算术生成算法

算术生成算法属于小型算法，包含头文件 #include<numeric>

accumulate(iterator beg, iterator end, val)			// 计算容器元素累加总和,val:起始值
fill(iterator beg, iterator end, val)				// 向容器中添加元素

// ex
class printint
{
public:
	void operator()(int a)
	{
		cout << a << "   ";
	}
};

5.1?accumulate

void test1()
{
	vector<int>v;
	for (int i = 0; i <= 100; i++)
	{
		v.push_back(i);
	}
	int total = accumulate(v.begin(), v.end(), 0);
	cout << total << endl;
}

5.2?fill

void test2()
{
	vector<int>v;
	v.resize(10);

	fill(v.begin(), v.end(), 100);
	for_each(v.begin(), v.end(), printint());
}

6. 常用集合算法

set_intersection(iterator beg1, iterator end1,iterator beg2, iterator end2, iterator dest)		// 求两个容器的交集,返回交集最后的叠加器
set_union(iterator beg1, iterator end1,iterator beg2, iterator end2, iterator dest)				// 求两个容器的并集,返回并集最后的叠加器
set_difference(iterator beg1, iterator end1,iterator beg2, iterator end2, iterator dest)		// 求两个容器的差集，v1容器与v2不相交的那部分元素

6.1?set_intersection 交集

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

	// 目标容器需要提前开辟空间
	vector<int>v3;
	v3.resize(min(v1.size(), v2.size()));
	vector<int>::iterator pos = set_intersection(v1.begin(), v1.end(), v2.begin(), v2.end(), v3.begin());
	for_each(v3.begin(), pos, printint());
}

6.2?set_union 并集

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

	vector<int>v3;
	v3.resize(v1.size()+v2.size());
	vector<int>::iterator pos = set_union(v1.begin(), v1.end(), v2.begin(), v2.end(), v3.begin());
	for_each(v3.begin(), pos, printint());
	cout << endl;
}

6.3?set_difference 差集

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

	vector<int>v3;
	v3.resize(v1.size());
	vector<int>::iterator pos = set_difference(v1.begin(), v1.end(), v2.begin(), v2.end(), v3.begin());
	for_each(v3.begin(), pos, printint());
	cout << endl;

	vector<int>v4;
	v4.resize(v2.size());
	pos = set_difference(v2.begin(), v2.end(), v1.begin(), v1.end(), v4.begin());
	for_each(v4.begin(), pos, printint());
}