开发: C++知识库 Java知识库 JavaScript Python PHP知识库人工智能区块链大数据移动开发嵌入式开发工具数据结构与算法开发测试游戏开发网络协议系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑笔记本显卡显示器固态硬盘硬盘耳机手机 iphone vivo oppo 小米华为单反装机图拉丁

-> C++知识库 -> STL简介 -> 正文阅读

[C++知识库]STL简介

一、STL

1.STL简介

1、STL六大组件
容器、算法、迭代器、仿函数、适配器（配接器）、空间配置器

2、容器分类:序列式容器和关联式容器
2.1、序列式容器强调值的排序，序列式容器中的每个元素均有固定的位置，除非用删除或插入的操作改变这个位置。Vector容器、Deque容器、List容器等。
2.2、关联式容器是非线性的树结构，更准确的说是二叉树结构。各元素之间没有严格的物理上的顺序关系，也就是说元素在容器中并没有保存元素置入容器时的逻辑顺序。关联式容器另一个显著特点是：在值中选择一个值作为关键字key，这个关键字对值起到索引的作用，方便查找。Set/multiset容器 Map/multimap容器

3、算法分类：质变算法和非质变算法。
3.1、质变算法：是指运算过程中会更改区间内的元素的内容。例如拷贝，替换，删除等等
3.2、非质变算法：是指运算过程中不会更改区间内的元素内容，例如查找、计数、遍历、寻找极值等等

2.STL初识

1、算法 for_each 头  algorithm
2、迭代器  iterator  每个容器有专属迭代器
3、vector<int >v  
	vector<int>::iterator  it = …..
	v.begin() 指向第一个数据
	v.end 指向 最后一个数据的下一个地址

void test01()
{
	int arr[5] = { 1,2,3,4,5 };
	int* p = arr;
	for (int i = 0; i < 5; i++)
	{
		cout << *(p++) << endl;
	}
}

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

void test02()
{
	vector<int> v;
	v.push_back(12);
	v.push_back(13);
	v.push_back(14);

	//第一种遍历
	vector<int>::iterator itBegin = v.begin();
	vector<int>::iterator itEnd = v.end();
	cout << "第一种遍历" << endl;
	while (itBegin != itEnd)
	{
		cout << *itBegin << endl;
		itBegin++;
	}

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

	//第三种遍历
	cout << "第三种遍历" << endl;
	//回调函数myPrint
	for_each(v.begin(), v.end(),myPrint);
}


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

void test03()
{
	vector<Person> v;
	Person p1("aa", 10);
	Person p2("bb", 20);
	Person p3("cc", 30);
	Person p4("dd", 40);
	Person p5("ee", 50);
	Person p6("ff", 60);
	v.push_back(p1);
	v.push_back(p2);
	v.push_back(p3);
	v.push_back(p4);
	v.push_back(p5);
	v.push_back(p6);

	for (vector<Person>::iterator it = v.begin(); it != v.end(); it++) {
		cout<<"name:"<<(*it).m_Name<<"  age:"<<(*it).m_Age<< endl;
	}
}

void test04()
{
	vector<vector<int>> res;
	vector<int> v1;
	vector<int> v2;
	vector<int> v3;

	for (int i = 0; i < 5; i++) {
		v1.push_back(i + 1);
		v1.push_back(i + 10);
		v1.push_back(i + 100);
	}

	res.push_back(v1);
	res.push_back(v2);
	res.push_back(v3);

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

3.string

1、string 构造函数
string();//创建一个空的字符串 例如: string str;      
string(const string& str);//使用一个string对象初始化另一个string对象
string(const char* s);//使用字符串s初始化
string(int n, char c);//使用n个字符c初始化 

2、string基本赋值操作
string& operator=(const char* s);//char*类型字符串 赋值给当前的字符串
string& operator=(const string &s);//把字符串s赋给当前的字符串
string& operator=(char c);//字符赋值给当前的字符串
string& assign(const char *s);//把字符串s赋给当前的字符串
string& assign(const char *s, int n);//把字符串s的前n个字符赋给当前的字符串
string& assign(const string &s);//把字符串s赋给当前字符串
string& assign(int n, char c);//用n个字符c赋给当前字符串
string& assign(const string &s, int start, int n);//将s从start开始n个字符赋值给字符串

3、string存取字符操作
char& operator[](int n);//通过[]方式取字符
char& at(int n);//通过at方法获取字符

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

5、string查找和替换
int find(const string& str, int pos = 0) const; //查找str第一次出现位置,从pos开始查找
int find(const char* s, int pos = 0) const;  //查找s第一次出现位置,从pos开始查找
int find(const char* s, int pos, int n) const;  //从pos位置查找s的前n个字符第一次位置
int find(const char c, int pos = 0) const;  //查找字符c第一次出现位置
int rfind(const string& str, int pos = npos) const;//查找str最后一次位置,从pos开始查找
int rfind(const char* s, int pos = npos) const;//查找s最后一次出现位置,从pos开始查找
int rfind(const char* s, int pos, int n) const;//从pos查找s的前n个字符最后一次位置
int rfind(const char c, int pos = 0) const; //查找字符c最后一次出现位置
string& replace(int pos, int n, const string& str); //替换从pos开始n个字符为字符串str
string& replace(int pos, int n, const char* s); //替换从pos开始的n个字符为字符串s

6、string比较操作
/*
compare函数在>时返回 1，<时返回 -1，==时返回 0。
比较区分大小写，比较时参考字典顺序，排越前面的越小。
大写的A比小写的a小。
*/
int compare(const string &s) const;//与字符串s比较
int compare(const char *s) const;//与字符串s比较

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

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

9、string和c-style字符串转换
//string 转 char*
string str = "itcast";
const char* cstr = str.c_str();
//char* 转 string 
char* s = "itcast";
string str(s);

#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
using namespace std;
#include <string>
#include <stdexcept>
#include <vector>
/*
string 构造函数
string();//创建一个空的字符串 例如: string str;
string(const string& str);//使用一个string对象初始化另一个string对象
string(const char* s);//使用字符串s初始化
string(int n, char c);//使用n个字符c初始化

3.1.2.2 string基本赋值操作
string& operator=(const char* s);//char*类型字符串 赋值给当前的字符串
string& operator=(const string &s);//把字符串s赋给当前的字符串
string& operator=(char c);//字符赋值给当前的字符串
string& assign(const char *s);//把字符串s赋给当前的字符串
string& assign(const char *s, int n);//把字符串s的前n个字符赋给当前的字符串
string& assign(const string &s);//把字符串s赋给当前字符串
string& assign(int n, char c);//用n个字符c赋给当前字符串
string& assign(const string &s, int start, int n);//将s从start开始n个字符赋值给字符串

*/

void test01()
{
	string str; //默认构造
	string str2(str); //拷贝构造
	string str3 = str;

	string str4 = "abcd";
	string str5(10, 'a');

	cout << str4 << endl;
	cout << str5 << endl;

	//基本赋值
	str = "hello";
	str2 = str4;

	//string& assign(const char *s, int n);//把字符串s的前n个字符赋给当前的字符串
	str3.assign("abcdef", 4);
	cout << str3 << endl;


	//string& assign(const string &s, int start, int n);//将s从start开始n个字符赋值给字符串
	string str6;
	str6.assign(str, 1, 3); //ell ? hel 从0索引

	cout << str6 << endl;
}


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

*/
void test02()
{
	string s = "hello world";

	for (int i = 0; i < s.size(); i++)
	{
		//cout << s[i] << endl;
		cout << s.at(i) << endl;
	}
	/*[] 和at区别？[]访问越界  直接挂掉
							   at会抛出异常
	*/
	try
	{
		//cout << s[100] << endl;
		cout << s.at(100) << endl;
	}
	catch (out_of_range& e)
	{
		cout << e.what() << endl;
	}
	catch (...)
	{
		cout << "越界异常" << endl;
	}
}

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

3.1.2.5 string查找和替换
int find(const string& str, int pos = 0) const; //查找str第一次出现位置,从pos开始查找
int find(const char* s, int pos = 0) const;  //查找s第一次出现位置,从pos开始查找
int find(const char* s, int pos, int n) const;  //从pos位置查找s的前n个字符第一次位置
int find(const char c, int pos = 0) const;  //查找字符c第一次出现位置
int rfind(const string& str, int pos = npos) const;//查找str最后一次位置,从pos开始查找
int rfind(const char* s, int pos = npos) const;//查找s最后一次出现位置,从pos开始查找
int rfind(const char* s, int pos, int n) const;//从pos查找s的前n个字符最后一次位置
int rfind(const char c, int pos = 0) const; //查找字符c最后一次出现位置
string& replace(int pos, int n, const string& str); //替换从pos开始n个字符为字符串str
string& replace(int pos, int n, const char* s); //替换从pos开始的n个字符为字符串s

*/

void test03()
{
	//拼接
	string s1 = "我";
	string s2 = "爱北京";
	s1 += s2;
	cout << s1 << endl;
	s1.append("天安门");

	cout << s1 << endl;

	//find查找

	string s = "abcdefg";
	int pos = s.find("bcf"); //找不到返回是 -1
	cout << "pos = " << pos << endl;

	int pos2 = s.rfind("bc"); //rfind  和find 结果一样，内部查找顺序相反
	cout << "pos2 = " << pos2 << endl; // 4 2 


	//替换
	string s3 = "hello"; //替换从pos开始n个字符为字符串str
	s3.replace(1, 3, "1111");
	cout << s3 << endl; // h1111o


}

/*
string比较操作
/*
compare函数在>时返回 1，<时返回 -1，==时返回 0。
比较区分大小写，比较时参考字典顺序，排越前面的越小。
大写的A比小写的a小。

int compare(const string &s) const;//与字符串s比较
int compare(const char *s) const;//与字符串s比较
*/

void test04()
{
	string s1 = "abc";
	string s2 = "abcd";

	if (s1.compare(s2) == 0)
	{
		cout << "s1 等于 s2" << endl;
	}
	else if (s1.compare(s2) == 1)
	{
		cout << "s1 大于 s2" << endl;
	}
	else
	{
		cout << "s1 小于 s2" << endl;
	}

}


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

*/

void test05()
{
	string s1 = "abcde";

	string s2 = s1.substr(1, 3);
	cout << "s2 = " << s2 << endl;

	//需求  查找一个右键的 用户名
	string email = "zhangtao@sina.com";

	int pos = email.find("@");//8 
	cout << "pos " << pos << endl;

	string usrName = email.substr(0, pos);
	cout << "用户名为：" << usrName << endl;
}


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

*/

void test06()
{
	string s1 = "hello";
	s1.insert(1, "111");
	cout << s1 << endl; //h111ello

	//删除 111
	s1.erase(1, 3);
	cout << s1 << endl;

}


/*
string和c-style字符串转换
*/

void func(string s)
{
	cout << s << endl;
}

void func2(const char* s)
{
	cout << s << endl;
}

void test07()
{
	string s = "abc";
	//string -> const char *

	const char* p = s.c_str();

	func(p); //const char * 隐式类型转换为 string

	//const char * -> string 

	string s2(p);
	//func2(s2); //string 不能隐式类型转换为 char * 
}

void test08()
{
	string s = "abcdefg";
	char& a = s[2];
	char& b = s[3];

	a = '1';
	b = '2';

	cout << s << endl;
	cout << (int*)s.c_str() << endl;

	s = "pppppppppppppp";

	//a = '1';
	//b = '2';

	cout << s << endl;
	cout << (int*)s.c_str() << endl;

}

/*
写一个函数，函数内部将string字符串中的所有小写字母都变为大写字母。
*/

void test09()
{
	string s = "abCdEfg";

	for (int i = 0; i < s.size(); i++)
	{
		//s[i] = toupper(s[i]);

		//全变小写
		s[i] = tolower(s[i]);
	}

	cout << s << endl;
}


void test10()
{
	string str = "wwww.itcast.com.cn";
	vector<string> res;

	int start = 0;
	int pos = -1;
	while (true) {
		pos = str.find(".",start);
		if (pos == -1) {
			string temstr = str.substr(start, str.size()-start);
			break;
		}
		string temstr = str.substr(start, pos - start);
		res.push_back(temstr);
		start = pos + 1;
	}
	for (auto x : res) {
		cout << x << endl;
	}
}
int main() {

	//	test01();

		//test02();

		//test03();

		//test04();

		//test05();

		//test06();

	//	test07();

		//test08();

	//test09();
	test10();

	system("pause");
	return EXIT_SUCCESS;
}

二、容器

1.vector容器

vector容器
1、单端数组 
2、动态数组，自动扩展内存，所谓动态扩展内存，并不是在原有空间后续进行扩展，而是找一个更大的内存空间，将原有数据拷贝到新空间下，并且释放原有空间
3、接口
	3.1 构造、赋值
	3.2 交换 swap
	3.3 大小 size 
	3.4 是否为空  empty
	3.5 重置大小 resize
		3.5.1 如果重置的比原来大，有默认值填充新位置
		3.5.2 如果重置的比原来小，超出的部分删除掉
	3.6 front 返回容器中第一个元素
	3.7 back 返回容器中最后一个元素
4、插入  insert  （迭代器）
5、删除  erase   （迭代器）
6、尾插  push_back
7、尾删  pop_back
8、清空  clear
9、案例1 ：巧用swap收缩内存
10、案例2: ： 巧用reserve 预留内存
11、逆序遍历  reverse_iterator   非质变
12、判断容器的迭代器是否支持随机访问

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

//例子 使用第二个构造函数 我们可以...
int arr[] = {2,3,4,1,9};
vector<int> v1(arr, arr + sizeof(arr) / sizeof(int)); 

2、vector常用赋值操作
assign(beg, end);//将[beg, end)区间中的数据拷贝赋值给本身。
assign(n, elem);//将n个elem拷贝赋值给本身。
vector& operator=(const vector  &vec);//重载等号操作符
swap(vec);// 将vec与本身的元素互换。

3、vector大小操作
size();//返回容器中元素的个数
empty();//判断容器是否为空
resize(int num);//重新指定容器的长度为num，若容器变长，则以默认值填充新位置。如果容器变短，则末尾超出容器长度的元素被删除。
resize(int num, elem);//重新指定容器的长度为num，若容器变长，则以elem值填充新位置。如果容器变短，则末尾超出容器长>度的元素被删除。
capacity();//容器的容量
reserve(int len);//容器预留len个元素长度，预留位置不初始化，元素不可访问。

4、vector数据存取操作
at(int idx); //返回索引idx所指的数据，如果idx越界，抛出out_of_range异常。
operator[];//返回索引idx所指的数据，越界时，运行直接报错
front();//返回容器中第一个数据元素
back();//返回容器中最后一个数据元素

5、vector插入和删除操作
insert(const_iterator pos, int count,ele);//迭代器指向位置pos插入count个元素ele.
push_back(ele); //尾部插入元素ele
pop_back();//删除最后一个元素
erase(const_iterator start, const_iterator end);//删除迭代器从start到end之间的元素
erase(const_iterator pos);//删除迭代器指向的元素
clear();//删除容器中所有元素

#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include <vector>
#include <list>
using namespace std;

void test01()
{
	vector<int> v;
	for (int i = 0; i < 10; i++){
		v.push_back(i);
		cout << v.capacity() << endl;  // v.capacity()容器的容量
	}
}

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

//例子 使用第二个构造函数 我们可以...
int arr[] = {2,3,4,1,9};
vector<int> v1(arr, arr + sizeof(arr) / sizeof(int));

3.2.4.2 vector常用赋值操作
assign(beg, end);//将[beg, end)区间中的数据拷贝赋值给本身。
assign(n, elem);//将n个elem拷贝赋值给本身。
vector& operator=(const vector  &vec);//重载等号操作符
swap(vec);// 将vec与本身的元素互换。

3.2.4.3 vector大小操作
size();//返回容器中元素的个数
empty();//判断容器是否为空
resize(int num);//重新指定容器的长度为num，若容器变长，则以默认值填充新位置。如果容器变短，则末尾超出容器长度的元素被删除。
resize(int num, elem);//重新指定容器的长度为num，若容器变长，则以elem值填充新位置。如果容器变短，则末尾超出容器长>度的元素被删除。
capacity();//容器的容量
reserve(int len);//容器预留len个元素长度，预留位置不初始化，元素不可访问。

*/

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

void test02()
{
	vector <int >v;
	int arr[] = { 2, 3, 4, 1, 9 };
	vector<int> v1(arr, arr + sizeof(arr) / sizeof(int));

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

	printVector(v2);

	vector<int>v3(10, 100);

	printVector(v3);

	//赋值使用
	vector<int>v4;
	v4.assign(v3.begin(), v3.end());
	printVector(v4);


	v4.swap(v2);

	cout << "交换后的v4 " << endl;
	printVector(v4);

	cout << "v4容器的大小" << v4.size() << endl;

	if (v4.empty())
	{
		cout << "v4空" << endl;
	}
	else
	{
		cout << "v4不空" << endl;
	}
	
	//v4 23419
	v4.resize(10,-1); //第二个参数是默认值 ，默认0 
	printVector(v4);

	v4.resize(3);
	printVector(v4);

}

//巧用swap收缩空间
void test03()
{
	vector<int>v;
	for (int i = 0; i < 100000; i++)
	{
		v.push_back(i);
	}

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

	v.resize(3);

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

	//巧用swap
	vector<int>(v).swap(v);

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

//reserve(int len);//容器预留len个元素长度，预留位置不初始化，元素不可访问。

void test04()
{
	vector<int>v;

	v.reserve(100000); //预留出空间

	int * p = NULL;
	int num = 0;
	for (int i = 0; i < 100000;i++)
	{
		v.push_back(i);
		if (p!=&v[0])
		{
			p = &v[0];
			num++;
		}
	}
	cout << num << endl;
	// 开辟100000数据用了多少次
}


/*
vector数据存取操作
at(int idx); //返回索引idx所指的数据，如果idx越界，抛出out_of_range异常。
operator[];//返回索引idx所指的数据，越界时，运行直接报错
front();//返回容器中第一个数据元素
back();//返回容器中最后一个数据元素

3.2.4.5 vector插入和删除操作
insert(const_iterator pos, int count,ele);//迭代器指向位置pos插入count个元素ele.
push_back(ele); //尾部插入元素ele
pop_back();//删除最后一个元素
erase(const_iterator start, const_iterator end);//删除迭代器从start到end之间的元素
erase(const_iterator pos);//删除迭代器指向的元素
clear();//删除容器中所有元素

*/

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

	cout << "v的front" << v.front() << endl;
	cout << "v的back" << v.back() << endl;


	v.insert(v.begin(), 2 ,100); //参数1  迭代器   参数2  N个数  参数3 具体插入的内容

	printVector(v);

	v.pop_back(); //尾删
	printVector(v);

	v.erase(v.begin()); //删除 
	printVector(v);

	//v.erase(v.begin(), v.end());
	//v.clear(); //清空所有数据
	if (v.empty() )
	{
		cout << "为空" << endl;
	}

}

void test06()
{
	//逆序遍历
	vector<int>v;
	for ( int  i = 0; i < 10; i++)
	{
		v.push_back(i);
	}

//	printVector(v);
	//reverse_iterator 逆序迭代器
	for (vector<int>::reverse_iterator it = v.rbegin(); it != v.rend();it++)
	{
		cout << *it << " ";
	}
	cout << endl;

	//vector迭代器是随机访问的迭代器  支持跳跃式访问
	vector<int>::iterator itBegin = v.begin();
	itBegin = itBegin + 3;
	//如果上述写法不报错，这个迭代器是随机访问迭代器


	list<int>l;
	for (int i = 0; i < 10;i++)
	{
		l.push_back(i);
	}
	list<int>::iterator lIt = l.begin();
	//lIt = lIt + 1; //不支持随机访问

}


int main(){
//	test01();

//	test02();

//	test03();

//	test04();

//	test05();

	test06();

	system("pause");
	return EXIT_SUCCESS;
}

2.deque容器

5deque容器
1、双端数组
2、可以对头部进行插入和删除操作，内部有中控器控制数据
3、接口
	3.1 构造、赋值
	3.2 交换  swap
	3.3 大小 size
	3.4 是否为空 empty
	3.5 重置大小  resize
	3.6 front 返回容器中第一个元素
	3.7 back 返回容器中最后一个元素
	3.8 插入  insert  （迭代器）
	3.9 删除  erase   （迭代器）
	3.10 头部插入  push_front
	3.11 头部删除  pop_front
	3.12 尾插  push_back
	3.13 尾删  pop_back
	3.14 清空  clear
4、sort排序 sort(v.begin(),v.end(), 回调函数)

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

2 deque赋值操作
assign(beg, end);//将[beg, end)区间中的数据拷贝赋值给本身。
assign(n, elem);//将n个elem拷贝赋值给本身。
deque& operator=(const deque &deq); //重载等号操作符 
swap(deq);// 将deq与本身的元素互换

3 deque大小操作
deque.size();//返回容器中元素的个数
deque.empty();//判断容器是否为空
deque.resize(num);//重新指定容器的长度为num,若容器变长，则以默认值填充新位置。如果容器变短，则末尾超出容器长度的元素被删除。
deque.resize(num, elem); //重新指定容器的长度为num,若容器变长，则以elem值填充新位置,如果容器变短，则末尾超出容器长度的元素被删除。

4 deque双端插入和删除操作
push_back(elem);//在容器尾部添加一个数据
push_front(elem);//在容器头部插入一个数据
pop_back();//删除容器最后一个数据
pop_front();//删除容器第一个数据

5 deque数据存取
at(idx);//返回索引idx所指的数据，如果idx越界，抛出out_of_range。
operator[];//返回索引idx所指的数据，如果idx越界，不抛出异常，直接出错。
front();//返回第一个数据。
back();//返回最后一个数据

6 deque插入操作
insert(pos,elem);//在pos位置插入一个elem元素的拷贝，返回新数据的位置。
insert(pos,n,elem);//在pos位置插入n个elem数据，无返回值。
insert(pos,beg,end);//在pos位置插入[beg,end)区间的数据，无返回值。

7 deque删除操作
clear();//移除容器的所有数据
erase(beg,end);//删除[beg,end)区间的数据，返回下一个数据的位置。
erase(pos);//删除pos位置的数据，返回下一个数据的位置。

#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
using namespace std;
#include <deque>
#include <algorithm>
/*
3.3.3.1 deque构造函数
deque<T> deqT;//默认构造形式
deque(beg, end);//构造函数将[beg, end)区间中的元素拷贝给本身。
deque(n, elem);//构造函数将n个elem拷贝给本身。
deque(const deque &deq);//拷贝构造函数。

3.3.3.2 deque赋值操作
assign(beg, end);//将[beg, end)区间中的数据拷贝赋值给本身。
assign(n, elem);//将n个elem拷贝赋值给本身。
deque& operator=(const deque &deq); //重载等号操作符
swap(deq);// 将deq与本身的元素互换

3.3.3.3 deque大小操作
deque.size();//返回容器中元素的个数
deque.empty();//判断容器是否为空
deque.resize(num);//重新指定容器的长度为num,若容器变长，则以默认值填充新位置。如果容器变短，则末尾超出容器长度的元素被删除。
deque.resize(num, elem); //重新指定容器的长度为num,若容器变长，则以elem值填充新位置,如果容器变短，则末尾超出容器长度的元素被删除。
*/

void printDeque( const deque<int>&d)
{
	//iterator普通迭代器
	//reverse_iterator 反转迭代器
	//const_iterator  只读迭代器

	for (deque<int>::const_iterator it = d.begin(); it != d.end();it++)
	{
		//*it = 1000;
		cout << *it << " ";
	}
	cout << endl;
}

void test01()
{
	deque<int>d;

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


	deque<int>d2;
	d2 = d;

	printDeque(d2);


	if (d2.empty())
	{
		cout << "d2为空" << endl;
	}
	else
	{
		cout << "d2不为空 size = " << d2.size() << endl;
	}
}


/*
3.3.3.4 deque双端插入和删除操作
push_back(elem);//在容器尾部添加一个数据
push_front(elem);//在容器头部插入一个数据
pop_back();//删除容器最后一个数据
pop_front();//删除容器第一个数据

3.3.3.5 deque数据存取
at(idx);//返回索引idx所指的数据，如果idx越界，抛出out_of_range。
operator[];//返回索引idx所指的数据，如果idx越界，不抛出异常，直接出错。
front();//返回第一个数据。
back();//返回最后一个数据
*/

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

	d.pop_back(); //尾删
	d.pop_front(); //头删
	// 200 100 10 20
	printDeque(d);

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

/*
3.3.3.6 deque插入操作
insert(pos,elem);//在pos位置插入一个elem元素的拷贝，返回新数据的位置。
insert(pos,n,elem);//在pos位置插入n个elem数据，无返回值。
insert(pos,beg,end);//在pos位置插入[beg,end)区间的数据，无返回值。
3.3.3.7 deque删除操作
clear();//移除容器的所有数据
erase(beg,end);//删除[beg,end)区间的数据，返回下一个数据的位置。
erase(pos);//删除pos位置的数据，返回下一个数据的位置。
*/

void test03()
{
	deque<int>d;
	d.push_back(10);
	d.push_back(20);
	d.push_back(30);
	d.push_front(100);
	d.push_front(200);
	d.push_front(300);

	//插入 insert
	d.insert(++d.begin(),2, 1000);
	//  300 1000 1000  200 100 10 20 30
	printDeque(d);

	//删除erase
	//d.erase(++d.begin());
	//d.erase(++d.begin());
	deque<int>::iterator it1 = d.begin();
	it1 = it1 + 1;

	deque<int>::iterator it2 = d.begin();
	it2 = it2 + 3;

	d.erase(it1, it2);
	printDeque(d);

	//清空
	d.clear();
	printDeque(d);
}


bool myCompare(int v1,int v2)
{
	return v1 < v2;
}

void test04()
{
	deque<int>d;
	d.push_back(10);
	d.push_back(20);
	d.push_back(30);
	d.push_front(100);
	d.push_front(200);
	d.push_front(300);

	//默认排序从小到大
	//sort(d.begin(), d.end());
	
	sort(d.begin(), d.end(), myCompare);

	printDeque(d);

}

int main(){
	//test01();
	//test02();
	//test03();
	test04();

	system("pause");
	return EXIT_SUCCESS;
}

3.栈stack容器

1、stack构造函数
stack<T> stkT;//stack采用模板类实现， stack对象的默认构造形式： 
stack(const stack &stk);//拷贝构造函数

2、stack赋值操作
stack& operator=(const stack &stk);//重载等号操作符

3、stack数据存取操作
push(elem);//向栈顶添加元素
pop();//从栈顶移除第一个元素
top();//返回栈顶元素

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

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

/*
3.4.3.1 stack构造函数
stack<T> stkT;//stack采用模板类实现， stack对象的默认构造形式：
stack(const stack &stk);//拷贝构造函数
3.4.3.2 stack赋值操作
stack& operator=(const stack &stk);//重载等号操作符
3.4.3.3 stack数据存取操作
push(elem);//向栈顶添加元素
pop();//从栈顶移除第一个元素
top();//返回栈顶元素
3.4.3.4 stack大小操作
empty();//判断堆栈是否为空
size();//返回堆栈的大小
*/

void test01()
{
	stack<int>S;
	//入栈
	S.push(10);
	S.push(20);
	S.push(30);
	S.push(40);

	cout << "size  = " << S.size() << endl;

	while (!S.empty())
	{
		//访问栈顶元素
		cout << S.top() << endl;
		//出栈
		S.pop();
	}
	cout << "size  = " << S.size() << endl;

}

int main(){

	test01();

	system("pause");
	return EXIT_SUCCESS;
}

4.队列queue容器

1、queue构造函数
queue<T> queT;//queue采用模板类实现，queue对象的默认构造形式：
queue(const queue &que);//拷贝构造函数

2、queue存取、插入和删除操作
push(elem);//往队尾添加元素
pop();//从队头移除第一个元素
back();//返回最后一个元素
front();//返回第一个元素

3、queue赋值操作
queue& operator=(const queue &que);//重载等号操作符

4、queue大小操作
empty();//判断队列是否为空
size();//返回队列的大小

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

void test01()
{
	queue<Person> Q; //队列容器

	Person p1("aaa", 10);
	Person p2("bbb", 20);
	Person p3("ccc", 30);
	Person p4("ddd", 40);

	//入队
	Q.push(p1);
	Q.push(p2);
	Q.push(p3);
	Q.push(p4);

	cout << "size = " << Q.size() << endl;

	while ( !Q.empty())
	{
		cout << "队头元素--- 姓名：  " << Q.front().m_Name << " 年龄： " << Q.front().m_Age << endl;
		cout << "队尾元素--- 姓名：  " << Q.back().m_Name << " 年龄： " << Q.back().m_Age << endl;

		//出队
		Q.pop();
	}
	cout << "size = " << Q.size() << endl;

}

int main(){
	test01();
	system("pause");
	return EXIT_SUCCESS;
}

5.双向循环链表list容器

list容器
1 双向循环链表
2 对外接口
	2.1 构造、赋值、大小、重置大小、是否为空
	2.2 反转 reverse
	2.3 排序 sort
		2.3.1 如果容器的迭代器支持随机访问，可以使用系统提供的标志算法
		2.3.2 不支持随机访问的迭代器的容器，内部会提供对应的算法接口
		2.3.3 对于自定义数据类型，必须要指定排序规则
	2.4 对自定义数据类型做了高级排序
	2.5 如果利用remove删除自定义数据类型，需要重载 ==

1、list构造函数
list<T> lstT;//list采用采用模板类实现,对象的默认构造形式：
list(beg,end);//构造函数将[beg, end)区间中的元素拷贝给本身。
list(n,elem);//构造函数将n个elem拷贝给本身。
list(const list &lst);//拷贝构造函数。

2、list数据元素插入和删除操作
push_back(elem);//在容器尾部加入一个元素
pop_back();//删除容器中最后一个元素
push_front(elem);//在容器开头插入一个元素
pop_front();//从容器开头移除第一个元素
insert(pos,elem);//在pos位置插elem元素的拷贝，返回新数据的位置。
insert(pos,n,elem);//在pos位置插入n个elem数据，无返回值。
insert(pos,beg,end);//在pos位置插入[beg,end)区间的数据，无返回值。
clear();//移除容器的所有数据
erase(beg,end);//删除[beg,end)区间的数据，返回下一个数据的位置。
erase(pos);//删除pos位置的数据，返回下一个数据的位置。
remove(elem);//删除容器中所有与elem值匹配的元素。

3、list大小操作
size();//返回容器中元素的个数
empty();//判断容器是否为空
resize(num);//重新指定容器的长度为num，
若容器变长，则以默认值填充新位置。
如果容器变短，则末尾超出容器长度的元素被删除。
resize(num, elem);//重新指定容器的长度为num，
若容器变长，则以elem值填充新位置。
如果容器变短，则末尾超出容器长度的元素被删除。

4、list赋值操作
assign(beg, end);//将[beg, end)区间中的数据拷贝赋值给本身。
assign(n, elem);//将n个elem拷贝赋值给本身。
list& operator=(const list &lst);//重载等号操作符
swap(lst);//将lst与本身的元素互换。

5、list数据的存取
front();//返回第一个元素。
back();//返回最后一个元素。

6、list反转排序
reverse();//反转链表，比如lst包含1,3,5元素，运行此方法后，lst就包含5,3,1元素。
sort(); //list排序

#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
using namespace std;
#include <list>
#include <algorithm>
#include <string>
void test01()
{

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

	list<int>::_Nodeptr node = myList._Myhead->_Next;

	for (int i = 0; i < myList._Mysize * 2; i++){
		cout << "Node:" << node->_Myval << endl;
		node = node->_Next;
		if (node == myList._Myhead){
			node = node->_Next;
			//node = node->_Prev
		}
	}


}

/*
3.6.4.1 list构造函数
list<T> lstT;//list采用采用模板类实现,对象的默认构造形式：
list(beg,end);//构造函数将[beg, end)区间中的元素拷贝给本身。
list(n,elem);//构造函数将n个elem拷贝给本身。
list(const list &lst);//拷贝构造函数。
3.6.4.2 list数据元素插入和删除操作
push_back(elem);//在容器尾部加入一个元素
pop_back();//删除容器中最后一个元素
push_front(elem);//在容器开头插入一个元素
pop_front();//从容器开头移除第一个元素
insert(pos,elem);//在pos位置插elem元素的拷贝，返回新数据的位置。
insert(pos,n,elem);//在pos位置插入n个elem数据，无返回值。
insert(pos,beg,end);//在pos位置插入[beg,end)区间的数据，无返回值。
clear();//移除容器的所有数据
erase(beg,end);//删除[beg,end)区间的数据，返回下一个数据的位置。
erase(pos);//删除pos位置的数据，返回下一个数据的位置。
remove(elem);//删除容器中所有与elem值匹配的元素。
*/

//遍历链表
void printList(const list<int> & L)
{
	for (list<int>::const_iterator it = L.begin(); it != L.end(); it++)
	{
		cout << *it << " ";
	}
	cout << endl;
}

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

	//正序遍历
	//for (list<int>::iterator it = L1.begin(); it != L1.end();it++)
	//{
	//	cout << *it << endl;
	//}
	//逆序遍历
	for (list<int>::reverse_iterator it = L1.rbegin(); it != L1.rend();it++)
	{
		cout << *it << endl;
	}

	//list迭代器是不是支持随机访问 ,答案：不支持，是一个双向迭代器
	list<int>::iterator itBegin = L1.begin();
	//itBegin = itBegin + 1;
}

void test03()
{
	list<int>L;
	L.push_back(10);
	L.push_back(20);
	L.push_back(30);
	L.push_front(100);
	L.push_front(200);
	L.push_front(300);

	printList(L);

	L.pop_back(); //尾删
	L.pop_front(); //头删
	// 200 100 10 20
	printList(L);


	//插入
	L.insert(L.begin(), 10000);
	// 10000 200 100 10 20
	printList(L);

	L.erase(L.begin());
	// 200 100 10 20 
	printList(L);

	//remove 删除容器中所有与elem值匹配的元素。
	L.push_back(100);
	L.push_back(100);
	L.remove(100);
	printList(L);

}

/*
3.6.4.3 list大小操作
size();//返回容器中元素的个数
empty();//判断容器是否为空
resize(num);//重新指定容器的长度为num，
若容器变长，则以默认值填充新位置。
如果容器变短，则末尾超出容器长度的元素被删除。
resize(num, elem);//重新指定容器的长度为num，
若容器变长，则以elem值填充新位置。
如果容器变短，则末尾超出容器长度的元素被删除。

3.6.4.4 list赋值操作
assign(beg, end);//将[beg, end)区间中的数据拷贝赋值给本身。
assign(n, elem);//将n个elem拷贝赋值给本身。
list& operator=(const list &lst);//重载等号操作符
swap(lst);//将lst与本身的元素互换。
3.6.4.5 list数据的存取
front();//返回第一个元素。
back();//返回最后一个元素。
*/
void test04()
{
	list<int>L;
	L.push_back(10);
	L.push_back(20);
	L.push_back(30);
	L.push_front(100);
	L.push_front(200);
	L.push_front(300);

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

	L.swap(L2);

	printList(L);

}


/*
3.6.4.6 list反转排序
reverse();//反转链表，比如lst包含1,3,5元素，运行此方法后，lst就包含5,3,1元素。
sort(); //list排序
*/
bool myCompare(int v1 ,int v2)
{
	return v1 > v2;
}

void test05()
{
	list<int>L;
	L.push_back(10);
	L.push_back(20);
	L.push_back(30);
	L.push_front(100);
	L.push_front(200);
	L.push_front(300);

	//反转
	L.reverse();

	printList(L);

	//排序  
	//如果容器的迭代器支持随机访问，可以使用系统提供的标志算法
	//不支持随机访问的迭代器的容器，内部会提供对应的算法接口
	//sort(L.begin(), L.end());
	/*L.sort(myCompare);
	printList(L);*/
}


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

	bool operator==( const Person & p )
	{
		if (this->m_Name == p.m_Name && this->m_Age == p.m_Age && this->m_Height == p.m_Height)
		{
			return true;
		}
		return false;
	}

	string m_Name;
	int m_Age;
	int m_Height;
};

bool myComparePerson( 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 test06()
{
	list<Person> L;

	Person p1("亚瑟", 40 ,  180);
	Person p2("赵云", 20 , 160);
	Person p3("妲己", 30 , 120);
	Person p4("孙悟空", 50 , 200);
	Person p5("关羽", 10 ,  170 );
	Person p6("刘备", 10  , 165);
	Person p7("张飞", 10 , 185);

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

	//按照年龄进行降序   从大到下 , 如果年龄相等，按照身高进行升序 
	//对于自定义数据类型，必须要指定排序规则
	L.sort(myComparePerson);

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

	//删除孙悟空
	L.remove(p4);

	cout << "删除孙悟空后：" << endl;
	for (list<Person>::iterator it = L.begin(); it != L.end(); it++)
	{
		cout << "姓名： " << (*it).m_Name << " 年龄： " << it->m_Age << " 身高： " << it->m_Height << endl;
	}

}

int main(){

	//test01();
	//test02();
	//test03();
	//test04();
	//test05();
	test06();
	system("pause");
	return EXIT_SUCCESS;
}

6.set/multiset容器

set 容器
1、关联式容器  key就是value
2、默认排好序  从小到大
3、插入  insert    大小  size  是否为空  empty
4、查找  find  返回值  迭代器
5、统计 count   对于set的结果 要么是0  要么是1
6、lower_bound(keyElem);//返回第一个key>=keyElem元素的迭代器。
7、upper_bound(keyElem);//返回第一个key>keyElem元素的迭代器。
8、equal_range(keyElem);//返回容器中key与keyElem相等的上下限的两个迭代器。
9、pair对组
	9.1、创建方式
	9.2、pair<string, int> p("Tom", 10);
	9.3、pair<string, int> p2 = make_pair("Jerry", 18);
10、set.insert的返回值是个对组  pair<iterator, bool> bool代表插入是否成功
11、multiset可以插入重复的key值
12、可以指定set容器的排序规则，但是必须在插入前指定，利用仿函数的技术
13、对于自定义数据类型，set通常都会指定出排序规则

1、set构造函数
set<T> st;//set默认构造函数：
mulitset<T> mst; //multiset默认构造函数: 
set(const set &st);//拷贝构造函数

2、set赋值操作
set& operator=(const set &st);//重载等号操作符
swap(st);//交换两个集合容器

3、set大小操作
size();//返回容器中元素的数目
empty();//判断容器是否为空

4、set插入和删除操作
insert(elem);//在容器中插入元素。
clear();//清除所有元素
erase(pos);//删除pos迭代器所指的元素，返回下一个元素的迭代器。
erase(beg, end);//删除区间[beg,end)的所有元素 ，返回下一个元素的迭代器。
erase(elem);//删除容器中值为elem的元素。

5、set查找操作
find(key);//查找键key是否存在,若存在，返回该键的元素的迭代器；若不存在，返回set.end();
count(key);//查找键key的元素个数
lower_bound(keyElem);//返回第一个key>=keyElem元素的迭代器。
upper_bound(keyElem);//返回第一个key>keyElem元素的迭代器。
equal_range(keyElem);//返回容器中key与keyElem相等的上下限的两个迭代器。

对组(pair):对组(pair)将一对值组合成一个值，这一对值可以具有不同的数据类型，两个值可以分别用pair的两个公有属性first和second访问。
    
类模板：template <class T1, class T2> struct pair.
    
如何创建对组?  
//第一种方法创建一个对组
pair<string, int> pair1(string("name"), 20);
cout << pair1.first << endl; //访问pair第一个值
cout << pair1.second << endl;//访问pair第二个值
//第二种
pair<string, int> pair2 = make_pair("name", 30);
cout << pair2.first << endl;
cout << pair2.second << endl;
//pair=赋值
pair<string, int> pair3 = pair2;
cout << pair3.first << endl;
cout << pair3.second << endl;

#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
using namespace std;
#include <set>
#include <string>

/*
3.7.2.1 set构造函数
set<T> st;//set默认构造函数：
mulitset<T> mst; //multiset默认构造函数:
set(const set &st);//拷贝构造函数
3.7.2.2 set赋值操作
set& operator=(const set &st);//重载等号操作符
swap(st);//交换两个集合容器
3.7.2.3 set大小操作
size();//返回容器中元素的数目
empty();//判断容器是否为空

3.7.2.4 set插入和删除操作
insert(elem);//在容器中插入元素。
clear();//清除所有元素
erase(pos);//删除pos迭代器所指的元素，返回下一个元素的迭代器。
erase(beg, end);//删除区间[beg,end)的所有元素 ，返回下一个元素的迭代器。
erase(elem);//删除容器中值为elem的元素。
*/

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

void test01()
{
	set<int>s;

	s.insert(10);
	s.insert(50);
	s.insert(30);
	s.insert(20);
	s.insert(40);

	printSet(s);

	if (s.empty())
	{
		cout << "set容器为空" << endl;
	}
	else
	{
		cout << "set容器不为空  大小为： " << s.size() << endl;
	}

	s.erase(30);

	printSet(s);
}

/*
3.7.2.5 set查找操作
find(key);//查找键key是否存在,若存在，返回该键的元素的迭代器；若不存在，返回set.end();
count(key);//查找键key的元素个数
lower_bound(keyElem);//返回第一个key>=keyElem元素的迭代器。
upper_bound(keyElem);//返回第一个key>keyElem元素的迭代器。
equal_range(keyElem);//返回容器中key与keyElem相等的上下限的两个迭代器。
*/

void test02()
{
	set<int>s;

	s.insert(10);
	s.insert(50);
	s.insert(30);
	s.insert(20);
	s.insert(40);

	set<int>::iterator pos = s.find(30);
	if (pos != s.end())
	{
		cout << "找到了元素：" << *pos << endl;
	}
	else
	{
		cout << "未找到" << endl;
	}

	//对于set而言，count的结果  要么是0  要么是1
	int num = s.count(40);

	cout << "key为40的个数为：" << num << endl;

	//lower_bound(keyElem);//返回第一个key>=keyElem元素的迭代器。
	set<int>::iterator pos2 = s.lower_bound(30);

	if (pos2 != s.end())
	{
		cout << "lower_bound的值为：" << *pos2 << endl;
	}
	else
	{
		cout << "未找到" << endl;
	}

	//upper_bound(keyElem);//返回第一个key>keyElem元素的迭代器。
	pos2 = s.upper_bound(30);
	if (pos2 != s.end())
	{
		cout << "upper_bound的值为：" << *pos2 << endl;
	}
	else
	{
		cout << "未找到" << endl;
	}

	//equal_range(keyElem);//返回容器中key与keyElem相等的上下限的两个迭代器。

	pair< set<int>::iterator, set<int>::iterator>  ret = s.equal_range(30);

	if (ret.first != s.end())
	{
		cout << "equal_range中的lower_bound的值为：" << *ret.first << endl;
	}
	else
	{
		cout << "未找到" << endl;
	}

	if (ret.second != s.end())
	{
		cout << "equal_range中的upper_bound的值为：" << *ret.second << endl;
	}
	else
	{
		cout << "未找到" << endl;
	}

}

//pair创建
void test03()
{
	pair<string, int> p("Tom", 10);

	cout << "姓名： " << p.first << " 年龄： " << p.second << endl;


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

void test04()
{
	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;
	}

	printSet(s);

	//允许插入重复的key值
	multiset<int> ms;
	ms.insert(10);
	ms.insert(10);
	cout << "---------" << endl;
	for (multiset<int>::iterator it = ms.begin(); it != ms.end(); it++)
	{
		cout << (*it) << endl;
	}

}

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

void test05()
{
	//set容器的排序规则要在插入之前指定
	set<int, myCompareInt >s;

	s.insert(10);
	s.insert(50);
	s.insert(30);
	s.insert(20);
	s.insert(40);

	//printSet(s);

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

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

	string m_Name;
	int m_Age;
};

class myComparePerson
{
public:
	bool operator()(const Person& p1, const Person& p2)
	{
		//按照年龄 升序  从小到大
		return p1.m_Age < p2.m_Age;
	}
};

void test06()
{
	//利用仿函数  指定出自定义数据类型的排序规则
	set<Person, myComparePerson> s;

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

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

	for (set<Person, myComparePerson>::iterator it = s.begin(); it != s.end(); it++)
	{
		cout << "姓名： " << (*it).m_Name << " 年龄： " << (*it).m_Age << endl;
	}

}

int main() {
	//test01();
	//test02();
	//test03();
	//test04();
	//test05();
	test06();

	system("pause");
	return EXIT_SUCCESS;
}

7.map/multimap容器

map容器
1、关联式容器
2、默认按照key从小到大排序
3、插入 
	3.1、m.insert(pair<int, int>(1, 10));
	3.2、m.insert(make_pair(2, 20));
	3.3、m.insert(map<int, int>::value_type(3, 30));
	3.4、m[4] = 40;
4、查找 find  返回值 是迭代器
5、统计 count  
6、lower_bound(keyElem);//返回第一个key>=keyElem元素的迭代器。
7、upper_bound(keyElem);//返回第一个key>keyElem元素的迭代器。
8、equal_range(keyElem);//返回容器中key与keyElem相等的上下限的两个迭代器。
9、利用仿函数  实现指定排序规则

1、map构造函数
map<T1, T2> mapTT;//map默认构造函数: 
map(const map &mp);//拷贝构造函数

2、map赋值操作
map& operator=(const map &mp);//重载等号操作符
swap(mp);//交换两个集合容器

3、map大小操作
size();//返回容器中元素的数目
empty();//判断容器是否为空

4、map插入数据元素操作
map.insert(...); //往容器插入元素，返回pair<iterator,bool>
map<int, string> mapStu;
// 第一种 通过pair的方式插入对象
mapStu.insert(pair<int, string>(3, "小张"));
// 第二种 通过pair的方式插入对象
mapStu.inset(make_pair(-1, "校长"));
// 第三种 通过value_type的方式插入对象
mapStu.insert(map<int, string>::value_type(1, "小李"));
// 第四种 通过数组的方式插入值
mapStu[3] = "小刘";
mapStu[5] = "小王";

5、map删除操作
clear();//删除所有元素
erase(pos);//删除pos迭代器所指的元素，返回下一个元素的迭代器。
erase(beg,end);//删除区间[beg,end)的所有元素 ，返回下一个元素的迭代器。
erase(keyElem);//删除容器中key为keyElem的对组。

6、map查找操作
find(key);//查找键key是否存在,若存在，返回该键的元素的迭代器；/若不存在，返回map.end();
count(keyElem);//返回容器中key为keyElem的对组个数。对map来说，要么是0，要么是1。对multimap来说，值可能大于1。
lower_bound(keyElem);//返回第一个key>=keyElem元素的迭代器。
upper_bound(keyElem);//返回第一个key>keyElem元素的迭代器。
equal_range(keyElem);//返回容器中key与keyElem相等的上下限的两个迭代器。

#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
using namespace std;
#include <map>
/*
3.8.2.1 map构造函数
map<T1, T2> mapTT;//map默认构造函数:
map(const map &mp);//拷贝构造函数
3.8.2.2 map赋值操作
map& operator=(const map &mp);//重载等号操作符
swap(mp);//交换两个集合容器

3.8.2.3 map大小操作
size();//返回容器中元素的数目
empty();//判断容器是否为空
3.8.2.4 map插入数据元素操作
map.insert(...); //往容器插入元素，返回pair<iterator,bool>
map<int, string> mapStu;
// 第一种 通过pair的方式插入对象
mapStu.insert(pair<int, string>(3, "小张"));
// 第二种 通过pair的方式插入对象
mapStu.inset(make_pair(-1, "校长"));
// 第三种 通过value_type的方式插入对象
mapStu.insert(map<int, string>::value_type(1, "小李"));
// 第四种 通过数组的方式插入值
mapStu[3] = "小刘";
mapStu[5] = "小王";
*/

void test01()
{
	map<int, int> m;

	//第一种插入方式
	m.insert(pair<int, int>(1, 10));

	//第二种插入方式  推荐
	m.insert(make_pair(2, 20));

	//第三种插入方式
	m.insert(map<int, int>::value_type(3, 30));

	//第四种
	m[4] = 40;

	//cout << m[10] << endl; //如果利用第四种 使用未指定的key，生成一个key为为指定的值，value为0的数据插入到容器中

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

}

/*
3.8.2.5 map删除操作
clear();//删除所有元素
erase(pos);//删除pos迭代器所指的元素，返回下一个元素的迭代器。
erase(beg,end);//删除区间[beg,end)的所有元素 ，返回下一个元素的迭代器。
erase(keyElem);//删除容器中key为keyElem的对组。
*/
void test02()
{
	map<int, int> m;
	m.insert(pair<int, int>(1, 10));
	m.insert(make_pair(2, 20));
	m.insert(map<int, int>::value_type(3, 30));
	m[4] = 40;

	m.erase(3); //删除传入key值

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

}

/*
3.8.2.6 map查找操作
find(key);//查找键key是否存在,若存在，返回该键的元素的迭代器；/若不存在，返回map.end();
count(keyElem);//返回容器中key为keyElem的对组个数。对map来说，要么是0，要么是1。对multimap来说，值可能大于1。
lower_bound(keyElem);//返回第一个key>=keyElem元素的迭代器。
upper_bound(keyElem);//返回第一个key>keyElem元素的迭代器。
equal_range(keyElem);//返回容器中key与keyElem相等的上下限的两个迭代器。
*/

void test03()
{
	map<int, int> m;
	m.insert(pair<int, int>(1, 10));
	m.insert(make_pair(2, 20));
	m.insert(map<int, int>::value_type(3, 30));
	m[4] = 40;

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

	//统计  count 
	int num = m.count(4);
	cout << "key为4的对组个数为： " << num << endl;

	//lower_bound(keyElem);//返回第一个key>=keyElem元素的迭代器。
	map<int, int>::iterator pos = m.lower_bound(3);

	if (pos != m.end())
	{
		cout << "找到了lower_bound key: " << pos->first << " value: " << pos->second << endl;
	}
	else
	{
		cout << "未找到" << endl;
	}

	//upper_bound(keyElem);//返回第一个key>keyElem元素的迭代器。
	pos = m.upper_bound(3);
	if (pos != m.end())
	{
		cout << "找到了upper_bound key: " << pos->first << " value: " << pos->second << endl;
	}
	else
	{
		cout << "未找到" << endl;
	}


	//equal_range(keyElem);//返回容器中key与keyElem相等的上下限的两个迭代器。
	pair<map<int, int>::iterator, map<int, int>::iterator>  ret2 = m.equal_range(3);

	if (ret2.first != m.end())
	{
		cout << "找到了equal_range中的 lower_bound的 key =  " << ret2.first->first << " value = " << ret2.first->second << endl;
	}
	else
	{
		cout << "未找到" << endl;
	}

	if (ret2.second != m.end())
	{
		cout << "找到了equal_range中的 upper_bound的 key =  " << ret2.second->first << " value = " << ret2.second->second << endl;
	}
	else
	{
		cout << "未找到" << endl;
	}

}


class myCompareInt
{
public:
	bool operator()(int v1, int v2)
	{
		return v1 > v2;
	}
};
void test04()
{
	map<int, int, myCompareInt> m;

	m.insert(pair<int, int>(1, 10));
	m.insert(make_pair(2, 20));
	m.insert(map<int, int>::value_type(3, 30));
	m[4] = 40;

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

}

int main() {
	//test01();
	//test02();
	//test03();
	test04();

	system("pause");
	return EXIT_SUCCESS;
}

三、算法

1.函数对象

函数对象
1本质是一个类的对象，因此称为函数对象，也叫仿函数
2函数对象 超出了普通函数的概念，可以拥有自己状态
3函数对象可以作为函数参数

#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
using namespace std;

class MyPrint
{
public:
	void operator()(int num)
	{
		cout << num << endl;
		m_Count++;
	}

	int m_Count = 0;
};

void myPrint02(int num)
{
	cout << num << endl;
}

void test01()
{
	MyPrint myPrint;
	myPrint(100); //本质是一个类的对象，因此称为函数对象，也叫仿函数

	myPrint02(100);
}

void test02()
{
	//函数对象 超出了普通函数的概念，可以拥有自己状态

	MyPrint myPrint;
	myPrint(100);
	myPrint(100);
	myPrint(100);
	myPrint(100);

	cout << "调用次数为： " << myPrint.m_Count << endl;
}


//函数对象可以作为函数参数
void doPrint(MyPrint myPrint , int num)
{
	myPrint(num);
}

void test03()
{
	doPrint(MyPrint(), 1000);
}

int main(){

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

	system("pause");
	return EXIT_SUCCESS;
}

2.谓词

谓词
1普通函数或者仿函数的返回值是bool类型，称为谓词
2一元谓词
	查找容器中大于20的数字    find_if
3 二元谓词
	对容器进行排序  sort
4 lambda表达式 	[](){}

#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
using namespace std;
#include <vector>
#include <algorithm>

//一元谓词
class GreaterThan20
{
public:
	bool operator()(int val)
	{
		return val > 20;
	}
};

void test01()
{
	vector<int>v;

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


	vector<int>::iterator ret = find_if(v.begin(), v.end(), GreaterThan20());
	if ( ret != v.end())
	{
		cout << "找到大于20的数字为： " << *ret << endl;
	}
	else
	{
		cout << "未找到" << endl;
	}


}


//二元谓词
void myPrintInt( int val)
{
	cout << val << " ";
}

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

void test02()
{
	vector<int>v;

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

	sort(v.begin(), v.end()); //从小到大

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


	sort(v.begin(), v.end(), MyCompare());

	//lambda表达式  匿名函数  []代表lambda表达式标志  [](){}
	for_each(v.begin(), v.end(), [](int val){ cout << val << " "; });

	cout << endl;
}


int main(){
	//test01();
	test02();

	system("pause");
	return EXIT_SUCCESS;
}

3.内建函数对象

1 引入头文件  #include< functional>
2 取反  negate<int>
3 加法  plus<int>
4 大于  greater<int>

6个算数类函数对象,除了negate是一元运算，其他都是二元运算。
template<class T> T plus<T>//加法仿函数
template<class T> T minus<T>//减法仿函数
template<class T> T multiplies<T>//乘法仿函数
template<class T> T divides<T>//除法仿函数
template<class T> T modulus<T>//取模仿函数
template<class T> T negate<T>//取反仿函数

6个关系运算类函数对象,每一种都是二元运算。
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>//小于等于

逻辑运算类运算函数,not为一元运算，其余为二元运算。
template<class T> bool logical_and<T>//逻辑与
template<class T> bool logical_or<T>//逻辑或
template<class T> bool logical_not<T>//逻辑非

#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
using namespace std;
#include <functional>  //内建函数对象  头文件
#include <vector>
#include <algorithm>
/*
template<class T> T negate<T>//取反仿函数  一元运算
*/

void test01()
{
	negate<int>n;

	cout << n(10) << endl;

}
//template<class T> T plus<T>//加法仿函数
void test02()
{
	plus<int> p;

	cout << p(10, 10) << endl;

}

//template<class T> bool greater<T>//大于
void test03()
{
	vector<int>v;
	v.push_back(20);
	v.push_back(50);
	v.push_back(10);
	v.push_back(30);
	v.push_back(40);

	//从大到小排序
	sort(v.begin(), v.end(), greater<int>());


	for_each(v.begin(), v.end(), [](int val){cout << val << " "; });
	cout << endl;
}

int main(){

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

	system("pause");
	return EXIT_SUCCESS;
}

4.适配器

1 函数对象适配器
	1.1 利用bind2nd 进行绑定
	1.2 继承public binary_function<参数1 类型,参数2类型,返回值类型>
	1.3 加const
2取反适配器
	2.1 一元取反  not1
		2.1.1 利用not1进行取反
		2.1.2 继承 public unary_function<int,bool>
		2.1.3 加const
	2.2 二元取反  not2
3 函数指针适配器
	3.1 ptr_fun将普通函数指针 适配成函数对象
4 成员函数适配器
	4.1 如果存放的是对象实体   mem_fun_ref
	4.2 如果存放的是对象指针   mem_fun

#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
using namespace std;
#include <vector>
#include <algorithm>
#include <functional>
#include <string>

class MyPrint :public binary_function<int,int,void>
{
public:
	void operator()(int val , int start)const 
	{
		cout << "val = " << val << " start = " << start <<  " sum = " <<val +  start << endl;
	}
};
//1、函数对象适配器
void test01()
{
	vector<int>v;

	for (int i = 0; i < 10;i++)
	{
		v.push_back(i);
	}
	cout << "请输入起始累加值： " << endl;
	int num;
	cin >> num;

	for_each(v.begin(), v.end(), bind2nd( MyPrint(), num ) );
	//for_each(v.begin(), v.end(), bind1st(MyPrint(), num));
}

//1、利用bind2nd 进行绑定
//2、继承 public binary_function<参数1 类型,参数2类型,返回值类型>
//3、加const


//2、取反适配器
class GreaterThanFive:public unary_function<int,bool>
{
public:
	bool operator()(int val) const
	{
		return val > 5;
	}
};
void test02()
{
	vector<int>v;
	for (int i = 0; i < 10;i++)
	{
		v.push_back(i);
	}

	//一元取反
	//vector<int>::iterator pos = find_if(v.begin(), v.end(), not1( GreaterThanFive()));

	vector<int>::iterator pos = find_if(v.begin(), v.end(), not1( bind2nd( greater<int>() , 5 )));

	if (pos != v.end())
	{
		cout << "找到小于5的值为： " << *pos << endl;
	}
	else
	{
		cout << "未找到" << endl;
	}


	//二元取反
	sort(v.begin(), v.end(),  not2 (less<int>()));
	for_each(v.begin(), v.end(), [](int val){cout << val << endl; });
}

//1、利用not1进行取反
//2、继承 public unary_function<int,bool>
//3、加const


void myPrint3( int val , int start) 
{
	cout << val + start << endl;
}
//3、 函数适配器
void test03()
{
	vector<int>v;

	for (int i = 0; i < 10; i++)
	{
		v.push_back(i);
	}
	//将函数指针 适配成函数对象  ptr_fun
	for_each(v.begin(), v.end(), bind2nd(ptr_fun(myPrint3), 1000));
}


//4、成员函数适配器
class Person
{
public:
	Person(string name, int age)
	{
		this->m_Name = name;
		this->m_Age = age;
	}

	void showPerson()
	{
		cout << "成员函数----姓名： " << this->m_Name << " 年龄： " << this->m_Age << endl;
	}

	void addAge()
	{
		this->m_Age += 100;
	}

	string m_Name;
	int m_Age;
};

//void myPrint4( Person & p)
//{
//	cout << "姓名： " << p.m_Name << " 年龄： " << p.m_Age << endl;
//}

void test04()
{
	vector< Person > v;

	Person p1("aaa", 10);
	Person p2("bbb", 20);
	Person p3("ccc", 30);
	Person p4("ddd", 40);
	v.push_back(p1);
	v.push_back(p2);
	v.push_back(p3);
	v.push_back(p4);
	//利用 mem_fun_ref
	for_each(v.begin(), v.end(),  mem_fun_ref(&Person::showPerson));
	for_each(v.begin(), v.end(), mem_fun_ref(&Person::addAge));
	for_each(v.begin(), v.end(), mem_fun_ref(&Person::showPerson));
}

int main(){

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

	system("pause");
	return EXIT_SUCCESS;
}

5.常用遍历算法

1 for_each
	1.1 用于遍历
	1.2 有返回值
	1.3 可以绑定参数进行输出
2 transform
	2.1 搬运
	2.2 注意：目标容器要有容量

/*
    遍历算法 遍历容器元素
	@param beg 开始迭代器
	@param end 结束迭代器
	@param _callback  函数回调或者函数对象
	@return 函数对象
*/
for_each(iterator beg, iterator end, _callback);

/*
	transform算法 将指定容器区间元素搬运到另一容器中
	注意 : transform 不会给目标容器分配内存，所以需要我们提前分配好内存
	@param beg1 源容器开始迭代器
	@param end1 源容器结束迭代器
	@param beg2 目标容器开始迭代器
	@param _cakkback 回调函数或者函数对象
	@return 返回目标容器迭代器
*/
transform(iterator beg1, iterator end1, iterator beg2, _callbakc)

#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
using namespace std;
#include <vector>
#include <algorithm>
#include <functional>

class MyPrint
{
public:
	void operator()(int val)
	{
		cout << val << endl;
		m_Count++;
	}

	int m_Count = 0;
};

//for_each  用于遍历
//有返回值的
void test01()
{
	vector<int>v;
	for (int i = 0; i < 10;i++)
	{
		v.push_back(i);
	}

	MyPrint print = for_each(v.begin(), v.end(), MyPrint());

	cout << "print.count = " << print.m_Count << endl;

}

//for_each可以绑定参数输出
class MyPrint2 :public binary_function<int,int,void>
{
public:
	void operator()(int val , int start) const
	{
		cout << val << endl;
		
	}

};

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

	for_each(v.begin(), v.end(),  bind2nd( MyPrint2(), 1000));

}


//transform算法 将指定容器区间元素搬运到另一容器中
class MyTransform
{
public:
	int operator()(int val)
	{	
		return val + 10000;
	}
};
void test03()
{
	vector<int>v;
	for (int i = 0; i < 10; i++)
	{
		v.push_back(i);
	}



	vector<int>v2;
	v2.resize(v.size());

	transform(v.begin(), v.end(), v2.begin(), MyTransform());

	for_each(v2.begin(), v2.end(), [](int val){cout << val << " "; });

}

int main(){
	//test01();
	//test02();
	test03();


	system("pause");
	return EXIT_SUCCESS;
}

6.常用查找算法

1 find  查找
2 find_if  按条件查找
3 adjacent_find算法 查找相邻重复元素
4 binary_search算法 二分查找法
	4.1注意: 在无序序列中不可用
5 count算法 统计元素出现次数
6 count_if 按条件进行统计

/*
	find算法 查找元素
	@param beg 容器开始迭代器
	@param end 容器结束迭代器
	@param value 查找的元素
	@return 返回查找元素的位置
*/
find(iterator beg, iterator end, value)
/*
	find_if算法 条件查找
	@param beg 容器开始迭代器
	@param end 容器结束迭代器
	@param  callback 回调函数或者谓词(返回bool类型的函数对象)
	@return bool 查找返回true 否则false
*/
find_if(iterator beg, iterator end, _callback);

/*
	adjacent_find算法 查找相邻重复元素
	@param beg 容器开始迭代器
	@param end 容器结束迭代器
	@param  _callback 回调函数或者谓词(返回bool类型的函数对象)
	@return 返回相邻元素的第一个位置的迭代器
*/
adjacent_find(iterator beg, iterator end, _callback);
/*
	binary_search算法 二分查找法
	注意: 在无序序列中不可用
	@param beg 容器开始迭代器
	@param end 容器结束迭代器
	@param value 查找的元素
	@return bool 查找返回true 否则false
*/
bool binary_search(iterator beg, iterator end, value);
/*
	count算法 统计元素出现次数
	@param beg 容器开始迭代器
	@param end 容器结束迭代器
	@param  value回调函数或者谓词(返回bool类型的函数对象)
	@return int返回元素个数
*/
count(iterator beg, iterator end, value);
/*
	count算法 统计元素出现次数
	@param beg 容器开始迭代器
	@param end 容器结束迭代器
	@param  callback 回调函数或者谓词(返回bool类型的函数对象)
	@return int返回元素个数
*/
count_if(iterator beg, iterator end, _callback);

#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
using namespace std;
#include <vector>
#include <algorithm>
#include <string>
#include <functional>
/*
find算法 查找元素
@param beg 容器开始迭代器
@param end 容器结束迭代器
@param value 查找的元素
@return 返回查找元素的位置


find_if算法 条件查找
@param beg 容器开始迭代器
@param end 容器结束迭代器
@param  callback 回调函数或者谓词(返回bool类型的函数对象)
@return bool 查找返回true 否则false

*/



void test01()
{
	vector<int>v;
	for (int i = 0; i < 10;i++)
	{
		v.push_back(i);
	}
	
	vector<int>::iterator pos = find(v.begin(), v.end(), 5);

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

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

	bool operator==(const Person & p)
	{
		return this->m_Name == p.m_Name && this->m_Age == p.m_Age;
	}

	string m_Name;
	int m_Age;
};

void test02()
{
	vector<Person> v;

	Person p1("aaa", 10);
	Person p2("bbb", 20);
	Person p3("ccc", 30);
	Person p4("ddd", 40);

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

 
	vector<Person>::iterator pos = find(v.begin(), v.end(), p2);
	if (pos != v.end())
	{
		cout << "找到了元素  姓名： " << (*pos).m_Name << " 年龄： " << (*pos).m_Age << endl;
	}

}

class MyComparePerson :public binary_function< Person *, Person *, bool>
{
public:
	bool operator()(  Person * p1 ,  Person *p2 ) const
	{
		return p1->m_Name == p2->m_Name  && p1->m_Age == p2->m_Age; 
	}
};

void test03()
{
	vector<Person *> v;

	Person p1("aaa", 10);
	Person p2("bbb", 20);
	Person p3("ccc", 30);
	Person p4("ddd", 40);

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

	Person * p = new Person("bbb", 20);

	vector<Person *>::iterator pos = find_if(v.begin(), v.end(), bind2nd( MyComparePerson() ,p)  );

	if (pos != v.end())
	{
		cout << "找到了元素--- 姓名： " << (*pos)->m_Name << " 年龄： " << (*pos)->m_Age << endl;
	}
	else
	{
		cout << "未找到" << endl;
	}
}


//adjacent_find算法 查找相邻重复元素
void test04()
{
	vector<int>v;

	v.push_back(3);
	v.push_back(2);
	v.push_back(300);
	v.push_back(300);
	v.push_back(6);
	v.push_back(3);

	vector<int>::iterator ret = adjacent_find(v.begin(), v.end());

	if (ret != v.end())
	{
		cout << "找到了相邻的重复元素： " << *ret << endl;
	}
	else
	{
		cout << "未找到" << endl;
	}

}


/*
binary_search算法 二分查找法
注意: 在无序序列中不可用
*/

void test05()
{
	vector<int>v;
	for (int i = 0; i < 10; i++)
	{
		v.push_back(i);
	}
	//v.push_back(4);  必须是有序序列，如果无效 结果未知

   bool ret=binary_search(v.begin(), v.end(), 2);
   if (ret)
   {
	   cout << "查到了数据2" << endl;
   }
   else
   {
	   cout << "未找到数据2" << endl;
   }

}

/*
count算法 统计元素出现次数
@param beg 容器开始迭代器
@param end 容器结束迭代器
@param  value回调函数或者谓词(返回bool类型的函数对象)
@return int返回元素个数
*/
class GreaterThan3
{
public:
	bool operator()(int val)
	{
		return val >= 3;
	}
};

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

	v.push_back(3);
	v.push_back(3);
	v.push_back(3);

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

	cout << "3的个数为： " << num << endl;


	//统计大于等于3的个数
	num = count_if(v.begin(), v.end(), GreaterThan3());
	// 0 1 2 3 4 5 6 7 8 9 3 3 3 
	cout << "大于等于3的个数为： " << num << endl;

}


int main(){
	//test01();
	//test02();
	//test03();
	//test04();
	//test05();
	test06();


	system("pause");
	return EXIT_SUCCESS;
}

7.常用排序算法

1 merge 合并  
	1.1 将两个容器合并到 目标容器中 
	1.2 注意： 两个容器必须是有序序列
	1.3 目标容器必须有容量
2 sort 排序
3 random_shuffle 洗牌
4 reverse 反转

/*
	merge算法 容器元素合并，并存储到另一容器中
	@param beg1 容器1开始迭代器
	@param end1 容器1结束迭代器
	@param beg2 容器2开始迭代器
	@param end2 容器2结束迭代器
	@param dest  目标容器开始迭代器
*/
merge(iterator beg1, iterator end1, iterator beg2, iterator end2, iterator dest)
/*
	sort算法 容器元素排序
	注意:两个容器必须是有序的
	@param beg 容器1开始迭代器
	@param end 容器1结束迭代器
	@param _callback 回调函数或者谓词(返回bool类型的函数对象)
*/
sort(iterator beg, iterator end, _callback)
/*
	sort算法 对指定范围内的元素随机调整次序
	@param beg 容器开始迭代器
	@param end 容器结束迭代器
*/
random_shuffle(iterator beg, iterator end)
/*
	reverse算法 反转指定范围的元素
	@param beg 容器开始迭代器
	@param end 容器结束迭代器
*/
reverse(iterator beg, iterator end)

#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
using namespace std;
#include <vector>
#include <algorithm>
#include <functional>
#include <ctime>
/*
merge算法 容器元素合并，并存储到另一容器中
注意 : 两个容器必须是有序的,顺序要一致
*/

void test01()
{
	vector<int>v1;
	vector<int>v2;

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

	vector<int>vTarget; //目标容器
	vTarget.resize(v1.size() + v2.size());

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

	for_each(vTarget.begin(), vTarget.end(), [](int val){cout << val << " "; });

}

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

	//降序排序

	sort(v.begin(), v.end(), greater<int>());
	for_each(v.begin(), v.end(), [](int val){cout << val << " "; });
	cout << endl;
}


//random_shuffle算法 对指定范围内的元素随机调整次序
void test03()
{
	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(), [](int val){cout << val << " "; });
	cout << endl;
}

//reverse算法 反转指定范围的元素
void test04()
{
	vector<int>v;
	for (int i = 0; i < 10; i++)
	{
		v.push_back(i);
	}

	cout << "反转前打印：" << endl;
	for_each(v.begin(), v.end(), [](int val){cout << val << " "; });
	cout << endl;


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

	cout << "反转后打印： " << endl;
	for_each(v.begin(), v.end(), [](int val){cout << val << " "; });
	
	cout << endl;
}

int main(){

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

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


	system("pause");
	return EXIT_SUCCESS;
}

8.常用的拷贝和替换算法

1 copy 拷贝
1.1 实现打印  copy(v.begin(),v.end() , ostream_iterator<int>(cout , “ ”));
2 replace 替换
3 replace_if 按条件替换
4 swap 交换

/*
	copy算法 将容器内指定范围的元素拷贝到另一容器中
	@param beg 容器开始迭代器
	@param end 容器结束迭代器
	@param dest 目标起始迭代器
*/
copy(iterator beg, iterator end, iterator dest)
/*
	replace算法 将容器内指定范围的旧元素修改为新元素
	@param beg 容器开始迭代器
	@param end 容器结束迭代器
	@param oldvalue 旧元素
	@param oldvalue 新元素
*/
replace(iterator beg, iterator end, oldvalue, newvalue)
/*
	replace_if算法 将容器内指定范围满足条件的元素替换为新元素
	@param beg 容器开始迭代器
	@param end 容器结束迭代器
	@param callback函数回调或者谓词(返回Bool类型的函数对象)
	@param oldvalue 新元素
*/
replace_if(iterator beg, iterator end, _callback, newvalue)
/*
	swap算法 互换两个容器的元素
	@param c1容器1
	@param c2容器2
*/
swap(container c1, container c2)

#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
using namespace std;
#include <vector>
#include <algorithm>
#include <iterator>
//copy算法 将容器内指定范围的元素拷贝到另一容器中
void test01()
{
	vector<int>v;
	for (int i = 0; i < 10;i++)
	{
		v.push_back(i);
	}

	vector<int>v2;
	v2.resize(v.size());
	copy(v.begin(), v.end(), v2.begin());

	//for_each(v2.begin(), v2.end(), [](int val){cout << val << " "; });
	//cout << endl;

	copy(v2.begin(), v2.end(), ostream_iterator<int>(cout, " "));
	cout << endl;
}

//replace算法 将容器内指定范围的旧元素修改为新元素
//replace_if(iterator beg, iterator end, _callback, newvalue) 按条件替换

class MyReplace
{
public:
	bool operator()(int val)
	{
		return val > 3;
	}
};
void test02()
{
	vector<int>v;
	for (int i = 0; i < 10; i++)
	{
		v.push_back(i);
	}

	//将容器中的3替换为 3000
	replace(v.begin(), v.end(), 3, 3000);

	copy(v.begin(), v.end(), ostream_iterator<int>(cout, " "));
	cout << endl;



	//将容器中所有大于3的都替换为 30000;
	replace_if(v.begin(), v.end(), MyReplace() , 30000);
	// 0 1 2 30000 ...
	copy(v.begin(), v.end(), ostream_iterator<int>(cout, " "));
	cout << endl;
}


//swap交换
void test03()
{
	vector<int>v;
	for (int i = 0; i < 10; i++)
	{
		v.push_back(i);
	}

	vector<int>v2(10, 100);

	cout << "交换数据前：" << endl;
	copy(v.begin(), v.end(), ostream_iterator<int>(cout, " "));
	cout << endl;

	copy(v2.begin(), v2.end(), ostream_iterator<int>(cout, " "));
	cout << endl;


	cout << "交换数据后：" << endl;
	swap(v, v2);

	copy(v.begin(), v.end(), ostream_iterator<int>(cout, " "));
	cout << endl;

	copy(v2.begin(), v2.end(), ostream_iterator<int>(cout, " "));
	cout << endl;

}

int main(){

	//test01();
	//test02();
	test03();
	system("pause");
	return EXIT_SUCCESS;
}

9.常用的算数生成算法

1 头文件  #include <numeric>
2 accumulate算法 计算容器元素累计总和
3 fill算法 向容器中添加元素

/*
	accumulate算法 计算容器元素累计总和
	@param beg 容器开始迭代器
	@param end 容器结束迭代器
	@param value累加值
*/
accumulate(iterator beg, iterator end, value)
/*
	fill算法 向容器中添加元素
	@param beg 容器开始迭代器
	@param end 容器结束迭代器
	@param value t填充元素
*/
fill(iterator beg, iterator end, value)

#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
using namespace std;
#include <vector>
#include <algorithm>
#include <functional>
#include <numeric> //accumulate算法头文件


//accumulate算法 计算容器元素累计总和
void test01()
{
	vector<int>v;
	for (int i = 0; i <= 100;i++)
	{
		v.push_back(i);
	}

	int num = accumulate(v.begin(), v.end(),1000); // 参数3代表 累加起始值

	cout << "num = " << num << endl;
}

//fill算法 向容器中添加元素
void test02()
{
	vector<int>v;
	v.resize(10);

	fill(v.begin(), v.end(), 100);

	for_each(v.begin(), v.end(), [](int val){cout << val << " "; });
	cout << endl;

}


int main(){

	//test01();
	test02();


	system("pause");
	return EXIT_SUCCESS;
}

10.常用集合算法

1 set_intersection算法 求两个set集合的交集
2 set_union算法 求两个set集合的并集
3 set_difference算法 求两个set集合的差集
4 注意:两个集合必须是有序序列

/*
	set_intersection算法 求两个set集合的交集
	注意:两个集合必须是有序序列
	@param beg1 容器1开始迭代器
	@param end1 容器1结束迭代器
	@param beg2 容器2开始迭代器
	@param end2 容器2结束迭代器
	@param dest  目标容器开始迭代器
	@return 目标容器的最后一个元素的迭代器地址
*/
set_intersection(iterator beg1, iterator end1, iterator beg2, iterator end2, iterator dest)
/*
	set_union算法 求两个set集合的并集
	注意:两个集合必须是有序序列
	@param beg1 容器1开始迭代器
	@param end1 容器1结束迭代器
	@param beg2 容器2开始迭代器
	@param end2 容器2结束迭代器
	@param dest  目标容器开始迭代器
	@return 目标容器的最后一个元素的迭代器地址
*/
set_union(iterator beg1, iterator end1, iterator beg2, iterator end2, iterator dest)
/*
	set_difference算法 求两个set集合的差集
	注意:两个集合必须是有序序列
	@param beg1 容器1开始迭代器
	@param end1 容器1结束迭代器
	@param beg2 容器2开始迭代器
	@param end2 容器2结束迭代器
	@param dest  目标容器开始迭代器
	@return 目标容器的最后一个元素的迭代器地址
*/
set_difference(iterator beg1, iterator end1, iterator beg2, iterator end2, iterator dest)

#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
using namespace std;
#include <vector>
#include <algorithm>

/*
set_intersection算法 求两个set集合的交集
注意:两个集合必须是有序序列
@param beg1 容器1开始迭代器
@param end1 容器1结束迭代器
@param beg2 容器2开始迭代器
@param end2 容器2结束迭代器
@param dest  目标容器开始迭代器
@return 目标容器的最后一个元素的迭代器地址
*/
void test01()
{
	vector<int>v1;
	vector<int>v2;

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

	vector<int>vTarget;

	vTarget.resize(min(v1.size(), v2.size()));

	vector<int>::iterator itEnd = set_intersection(v1.begin(), v1.end(), v2.begin(), v2.end(), vTarget.begin());

	for_each(vTarget.begin(), itEnd, [](int val){cout << val << " "; });
	cout << endl;
}


/*
set_union算法 求两个set集合的并集
注意:两个集合必须是有序序列
@param beg1 容器1开始迭代器
@param end1 容器1结束迭代器
@param beg2 容器2开始迭代器
@param end2 容器2结束迭代器
@param dest  目标容器开始迭代器
@return 目标容器的最后一个元素的迭代器地址
*/

void test02()
{
	vector<int>v1;
	vector<int>v2;

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

	vector<int>vTarget;
	vTarget.resize(v1.size() + v2.size());
	vector<int>::iterator itEnd  = set_union(v1.begin(), v1.end(), v2.begin(), v2.end(), vTarget.begin());

	for_each(vTarget.begin(), itEnd , [](int val){cout << val << " "; });
	cout << endl;
}

/*
set_difference算法 求两个set集合的差集
注意:两个集合必须是有序序列
@param beg1 容器1开始迭代器
@param end1 容器1结束迭代器
@param beg2 容器2开始迭代器
@param end2 容器2结束迭代器
@param dest  目标容器开始迭代器
@return 目标容器的最后一个元素的迭代器地址
*/

void test03()
{
	vector<int>v1;
	vector<int>v2;

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

	vector<int>vTarget;
	vTarget.resize( max(v1.size(),v2.size()) );

	// A 与 B 差集
	//vector<int>::iterator itEnd  = set_difference(v1.begin(), v1.end(), v2.begin(), v2.end(), vTarget.begin());

	// B 与 A 差集
	vector<int>::iterator itEnd = set_difference(v2.begin(), v2.end(), v1.begin(), v1.end(), vTarget.begin());


	for_each(vTarget.begin(), itEnd, [](int val){cout << val << " "; });
	cout << endl;

}

int main(){
	//test01();
	//test02();
	test03();

	system("pause");
	return EXIT_SUCCESS;
}