【C++】黑马程序员C++提高编程（完结）一、模板二、STL三、STL- 函数对象四、STL- 常用算法（施工ing）

86 阅读 0 评论 57 点赞

我是靠谱客的博主乐观黑裤，最近开发中收集的这篇文章主要介绍【C++】黑马程序员C++提高编程（完结）一、模板二、STL三、STL- 函数对象四、STL- 常用算法（施工ing），觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

一、模板
- 1.1 函数模板
- - 1.1.1 函数模板基础知识
- 案例一：数组排序
- - 1.2.1 普通函数与函数模板
  - 1.2.2 函数模板的局限性
- 1.2 类模板
- - 1.2.1 类模板的基础知识
  - 1.2.2 类模板与函数模板
  - 1.2.3 类模板中的成员函数创建时机
  - 1.2.4 类模板成员函数类外实现
  - 1.2.5 类模板的对象做函数参数
  - 1.2.6 类模板与继承
  - 1.2.7 类模板分文件编写
  - 1.2.8 类模板与友元
- 案例二：通用的数组类
二、STL
- 2.1 STL的基础知识
- 2.2 STL中的容器，算法，迭代器
- - 2.2.1 用vector对容器算法迭代器再认识
  - - 1. vector存放内置数据类型
    - 2. vector存放自定义数据类型
    - 3. vector容器嵌套容器
- 2.3 常用容器
- - 2.3.1 string
  - - 2.3.1.1 string基础知识
    - 2.3.1.2 接口
  - 2.3.2 vector
  - - 2.3.2.1 vector基础知识
    - 2.3.2.2 接口
  - 2.3.3 deque
  - - 2.3.3.1 deque基础知识
    - 2.3.3.2 接口
- 案例三：评委打分
- - 2.3.4 stack
  - - 2.3.4.1 stack基础知识
    - 2.3.4.2 接口
  - 2.3.5 queue
  - - 2.3.5.1 queue基础知识
    - 2.3.5.2 接口
  - 2.3.6 list
  - - 2.3.6.1 list基础知识
    - 2.3.6.2 接口
  - 2.3.7 set/ multiset
  - - 2.3.7.1 set/ multiset 基础知识
    - 2.3.7.2 接口
  - 2.3.8 map/ multimap
  - - 2.3.8.1 map/ multimap基础知识
    - 2.3.8.2 接口
- 案例四：员工分组
三、STL- 函数对象
- 3.1 函数对象
- - 3.1.1 函数对象的基础知识
  - 3.1.2 函数对象使用
- 3.2 谓词
- - 3.2.1 谓词的基础知识
  - 3.2.2 一元谓词
  - 3.2.3 二元谓词
- 3.3 内建函数对象
- - 3.3.1 内建函数对象意义
  - 3.3.2 算术仿函数
  - 3.3.3 关系仿函数
  - 3.3.4 逻辑仿函数
四、STL- 常用算法（施工ing）
- 4.1 常用遍历算法
- - 4.1.1 for_each
  - 4.1.2 transform
- 4.2 常用查找算法
- - 4.2.1 find
  - 4.2.2 find_if
  - 4.2.3 adjacent_find
  - 4.2.4 binary_search
  - 4.2.5 count
  - 4.2.6 count_if
- 4.3 常用排序算法
- - 4.3.1 sort
  - 4.3.2 random_shuffle
  - 4.3.3 merge
  - 4.3.4 reverse
- 4.4 常用拷贝和替换算法
- - 4.4.1 copy
  - 4.4.2 replace
  - 4.4.3 replace_if
  - 4.4.4 swap
- 4.5 常用算术生成算法
- - 4.5.1 accumulate
  - 4.5.2 fill
- 4.6 常用集合算法
- - 4.6.1 set_intersection
  - 4.6.2 set_union
  - 4.6.3 set_difference

提高阶段主要针对泛型编程和STL技术

一、模板

模板就是建立通用的模具，大大提高复用性,也是泛型编程的思想。C++提供两种模板机制：①函数模板 ②类模板

????注意：
① 模板不是万能的。
② 模板不能直接使用。

1.1 函数模板

1.1.1 函数模板基础知识

语法：

template  <typename T >   
函数声明或定义

解释：template— 声明创建模板；typename — 可以用class代替；T — 通用的数据类型
使用：①自动类型推导 ②显示指定类型

????意义：提高复用性，将类型参数化。

//函数模板的使用
template<typename T>
void MySwap(T& a, T& b)
{
	T temp = a;
	a = b;
	b = temp;
}
int main()
{
	int a = 10;
	int b = 20;
	MySwap(a, b);//自动类型推导
	MySwap<int>(a, b);//显示类型推导
	cout << "a=" << a << "b=" << b << endl;
	return 0;
}

????注意：

① 自动类型推导，必须推导出一致的数据类型T。
② 模板必须要确定出T的数据类型，才可以使用，因为自动类型推导推不出来。

//自动类型推导必须推出一致的类型
template<typename T>
void MySwap(T& a, T& b)
{
	T temp = a;
	a = b;
	b = temp;
}
int main()
{
	int a = 10;
	double b = 20;
	MySwap(a, b);//err
	cout << "a=" << a << "b=" << b << endl;
	return 0;
}

//模板必须要确定出T的数据类型，才可以使用
template<typename T>
void MySwap( )
{
	cout << "MySwap的调用";
}
int main()
{
	MySwap( );//err 自动类型推导推导不出数据类型
	MySwap<int>();//显示指定类型强制推导数据类型
	return 0;
}

案例一：数组排序

问题描述：
利用函数模板封装一个排序的函数，可以对不同数据类型数组进行排序；排序规则从大到小，排序算法为选择排序；分别利用char数组和int数组进行测试

//交换模板
template <typename T>
void MySwap(T& a, T& b)
{
	T temp = a;
	a = b;
	b = temp;
}
//打印模板
template<typename T>
void MyPrint(T arr[], int sz)
{
	for (int i = 0; i < sz; i++)
	{
		cout << arr[i];
	}
}
//排序模板
template<typename T>
void MySort(T arr[], int sz)
{
	for (int i = 0; i < sz; i++)
	{
		T max = arr[i];
		for (int j = i + 1; j < sz; j++)
		{
			if (arr[j] > arr[i])
			{
				MySwap(arr[j], arr[i]);
			}
		}
	}
	MyPrint(arr,sz);
}

int main()
{
	//字符数组测试
	char arr1[] = "badcfeg";
	MySort(arr1, sizeof(arr1) / sizeof(char));
	//整形数组测试
	int arr2[] = { 1,3,4,5,2,6,7,9 };
	MySort(arr2, sizeof(arr2) / sizeof(int));
}

1.2.1 普通函数与函数模板

普通函数与函数模板的区别：

普通函数调用时可以发生自动类型转换（隐式类型转换）
函数模板调用时，如果利用自动类型推导，不会发生隐式类型转换
如果利用显示指定类型的方式，可以发生隐式类型转换

//普通函数
int add(int a, int b)
{
	return a + b;
}
//函数模板
template <typename T>
T MyAdd(T a, T b)
{
	return a + b;
}
int main()
{
	int a = 10;
	int b = 20;
	char c = a;
	cout<< add(a, b) <<endl;
	cout << add(a, c) << endl;//普通函数可以发生隐式类型转换
	cout << MyAdd(a, b) << endl;
	cout << MyAdd(a, c) << endl;//err 自动类型推导无法进行隐式类型转换
	cout << MyAdd<int>(a, c) << endl;//显示显示指定类型可以进行隐式类型转换
}

普通函数与函数模板调用规则：

同名普通函数与函数模板，优先调用普通函数。
可以通过空模板参数列表来强制调用函数模板。
如果函数模板可以产生更好的匹配,优先调用函数模板
函数模板可以函数重载

void print(int a)
{
	cout << "普通函数调用" << endl;
}
template <typename T>
void print(T a)
{
	cout << "函数模板调用" << endl;
}
template <typename T>
void print(T a, T b)
{
	cout << "重载调用" << endl;
}
int main()
{
	int a = 10;
	//1.同名普通函数与函数模板，优先调用普通函数。
	print(a);//输出：普通函数调用

	//2.可以通过空模板参数列表来强制调用函数模板。
	print<>(a);//输出：函数模板调用

	//3.如果函数模板可以产生更好的匹配,优先调用函数模板
	char c = a;
	print(c);//输出：函数模板调用

	//4.函数模板可以函数重载
	print(a, 1);//输出：重载调用
}

1.2.2 函数模板的局限性

❗ 模板的通用性并不是万能的

template<class T>
void f(T a, T b)
{ 
   	a = b;
   }

在上述代码中提供的赋值操作，如果传入的a和b是一个数组或是一个类，就无法实现了

✅ 可以为这些特定的类型提供具体化的模板

class person
{
public:

	person(string name,int age)
	{
		this->age = age;
		this->name = name;
	}
	string name;
	int age;
};

template <class T>
bool test(T a, T b)
{
	if (a == b)
		return true;
	else
		return false;
}
//特定的类型提供具体化的模板
//具体化优先于常规模板
template<>bool test(person p1, person p2)
{
	if (p1.age == p2.age && p1.name == p2.name)
		return true;
	else
		return false;
}
int main()
{
	person p1("张三", 10);
	person p2("张三", 10);
	if (test(p1, p2))
		cout << "a==b" << endl;
	else
		cout << "a!=b" << endl;
}

1.2 类模板

1.2.1 类模板的基础知识

语法：

template  <typename T >   
函数声明或定义

解释：template— 声明创建模板；typename — 可以用class代替；T — 通用的数据类型

作用：建立一个通用类，类中的成员数据类型可以不具体制定，用一个虚拟的类型来代表

//类模板的使用
template <class NameType, class AgeType>
class person
{
public:
	person(NameType name,AgeType age)
	{
		this->name = name;
		this->age = age;
	}
	NameType name;
	AgeType age;
};
int main()
{
	person <string, int>p("xiyang", 18);
}

1.2.2 类模板与函数模板

两者使用的区别主要有两个：

类模板无法进行自动类型推导。
类模板在模板的参数列表中可以有默认参数。

template <class NameType, class AgeType=int>
class person
{
public:
	person(NameType name,AgeType age)
	{
		this->name = name;
		this->age = age;
	}
	NameType name;
	AgeType age;
};
int main()
{
	//1.类模板没有自动类型推导
	person p1("xiyang", 18);//err
	//2.类模板在模板参数列表中可以有默认参数
	person <string>p2("xiyang", 18);
	person <string>p3("xiyang",18.1);
	cout << p3.age;//输出：18
}

1.2.3 类模板中的成员函数创建时机

类模板中成员函数和普通类中成员函数创建时机是有区别的：

普通类中成员函数一开始就创建。
类模板中的成员函数只有调用时才创建。

class person1
{
public:
	void test1()
	{
		cout << "test1()" << endl;
	}
};
class person2
{
public:
	void test2()
	{
		cout << "test2()" << endl;
	}
};
template <class T>
class MyClass
{
public:
	T t;
	void test()
	{
		t.test1();
		t.test2();
	}
};
int main()
{
	MyClass<person1> mc;
	//没有编译之前不会报错，编译之后报错
	//说明类模板的成员函数是在调用后创建的
}

1.2.4 类模板成员函数类外实现

template <class T>
class person
{
public:
	person(T name);
	void print();
	T name;
};
//构造函数的类外实现
template <class T>
person<T>::person(T name)
{
	this->name = name;
}
//成员函数的类外实现
template <class T>
void person<T>::print()
{
	cout << this->name << endl;
}

1.2.5 类模板的对象做函数参数

有三种方式：

指定传入的类型 — 直接显示对象的数据类型
参数模板化 — 将对象中的参数变为模板进行传递
整个类模板化 — 将这个对象类型模板化进行传递

template <class NameType,class AgeType>
class person
{
public:
	person(NameType name,AgeType age)
	{
		this->name = name;
		this->age = age;
	}
	void print()
	{
		cout << this->name  << this->age;
	}
	NameType name;
	AgeType age;
};

void print1(person <string, int>& p)
{
	p.print();
}

template <class T1,class T2>
void print2(person <T1 , T2>&p)
{
	p.print();

	cout << "T1的类型:" << typeid(T1).name() << endl;//模板推出的数据类型
	cout << "T2的类型:" << typeid(T2).name() << endl;
}

template <class T>
void print3(T& p)
{
	p.print();

	cout << "T的数据类型：" << typeid(T).name() << endl;
}
int main()
{
	person <string, int>p("xiyang", 18);
	// 1.指定传入的类型
	print1(p);
	// 2.参数模板化
	print2(p);
	// 3.整个类模板化
	print3(p);
}

1.2.6 类模板与继承

????注意：
① 当子类继承的父类是一个类模板时，子类在声明的时候，要指定出父类中T的类型

template <class T>
class Base
{
	T m;
};
class Son :public Base{};  //err T没有指定类型

class Son1 :public Base <int>{};

//灵活指定父类中的T类型，子类也需要变类模板
template <class T>
class Son2 :public Base<T>{};

1.2.7 类模板分文件编写

❗ 类模板中成员函数创建时机是在调用阶段，导致分文件编写时链接不到

//person.h
#pragma once
#include <iostream>
#include <string>
using namespace std;
template<class NameType,class AgeType>
class person
{
public:
	person(NameType name,AgeType age);
	void print();
	NameType name;
	AgeType age;
};

//person.cpp
#include "person.h"
template<class NameType, class AgeType>
person<NameType, AgeType>::person(NameType name, AgeType age)
{
	this->name = name;
	this->age = age;
}
template<class NameType, class AgeType>
void person<NameType, AgeType>::print()
{
	cout << this->age << this->name << endl;
}

//test.cpp
#include "person.h"
int main()
{
	person<string, int>p("xiyang", 18);
	p.print();
	return 0;
}

在这里插入图片描述
✅ 解决方案：
① 在test.cpp中，将 person.h 改为 person.cpp
② 直接将 person.h 和 person.cpp 合并，后缀为.hpp

//person.hpp
#pragma once
#include <iostream>
#include <string>
using namespace std;
template<class NameType,class AgeType>
class person
{
public:
	person(NameType name,AgeType age);
	void print();
	NameType name;
	AgeType age;
};
template<class NameType, class AgeType>
person<NameType, AgeType>::person(NameType name, AgeType age)
{
	this->name = name;
	this->age = age;
}
template<class NameType, class AgeType>
void person<NameType, AgeType>::print()
{
	cout << this->age << this->name << endl;
}

//test.cpp
#include "person.hpp"
int main()
{
	person<string, int>p("xiyang", 18);
	p.print();
	return 0;
}

1.2.8 类模板与友元

全局函数类内实现 - 直接在类内声明友元即可
全局函数类外实现 - 需要提前让编译器知道全局函数的存在

//类模板与友元
template<class T1, class T2>
class person;
template<class T1, class T2>
void print2(person<T1, T2>& p)
{
	cout << "类外" << p.age << p.name;
}
template <class T1, class T2>
class person
{
	//1.全局函数在类内实现
	friend void print1(person<T1, T2> &p)
	{
		cout << "类内" << p.age << p.name;
	}
	//2.全局函数类外实现
	//类外实现需要让编译器提前看到，所以全局函数放在前面
	//全局函数放在前面的同时，需要再提前看到person类，所以还需要声明person类
	friend void print2<>(person<T1, T2>& p);
public:
	person(T1 name, T2 age)
	{
		this->name = name;
		this->age = age;
	}

private:
	T1 name;
	T2 age;
};

int main()
{
	//全局函数类内实现测试
	person <string, int > p1 ("xiyang", 18);
	print1(p1);

	//全局函数类外实现测试
	person<string, int >p2("xiyang", 19);
	print2(p2);
}

案例二：通用的数组类

问题描述：实现一个通用的数组类，要求如下：

可以对内置数据类型以及自定义数据类型的数据进行存储
将数组中的数据存储到堆区
构造函数中可以传入数组的容量
提供对应的拷贝构造函数以及operator=防止浅拷贝问题
提供尾插法和尾删法对数组中的数据进行增加和删除
可以通过下标的方式访问数组中的元素
可以获取数组中当前元素个数和数组的容量

//MyArray.hpp
#pragma once
#include <iostream>
#include <string>
using namespace std;
template <class T>
class MyArray
{
public:
	//构造函数
	MyArray(int capacity)
	{
		this->capacity = capacity;
		this->size = 0;
		this->arr = new T[this->capacity];
	}
	// 拷贝构造——为了解决浅拷贝带来的问题
	MyArray(MyArray& ma)
	{
		this->capacity = ma.capacity;
		this->size = ma.size;
		this->arr = new	T[ma.capacity];
		for (int i = 0; i < ma.size; i++)
		{
			this->arr[i] = ma.arr[i];
		}
	}
	// operator= ——解决浅拷贝带来的问题
	MyArray& operator=(MyArray& ma)
	{
		//赋值前有内容则需要清空
		if (this->capacity != 0)
		{
			this->size = 0;
			this->capacity = 0;
			delete[] this->arr;
			this->arr = NULL;
		}
		this->size = ma.size;
		this->capacity = capacity;
		this->arr = new T[ma.capacity];
		for (int i = 0; i < ma.size; i++)
		{
			this->arr[i] = ma.arr[i];
		}
		return *this;
	}
	//通过下标访问数据
	T& operator[ ](int idex)
	{
		//越界
		if (idex<0 || idex>size)
			exit(0);//强制退出
		return this->arr[idex];
	}
	//尾插
	void PushBack(T val)
	{
		//判断是否满了
		if (this->capacity == this->size)
		{
			return;
		}
		this->arr[this->size] = val;
		this->size++;
	}
	//尾删
	void PopBack()
	{
		//判断是否是空的
		if (this->size == 0)
		{
			return;
		}
		this->size--;
	}
	//获取数组容量
	int GetCapacity()
	{
		return this->capacity;
	}
	//获取数组大小
	int	GetSize()
	{
		return this->size;
	}
	//析构函数
	~MyArray()
	{
		if (this->arr != NULL)
		{
			this->capacity = 0;
			this->size = 0;
			delete[] this->arr;
			this->arr = NULL;
		}
	}
private:
	T* arr; //指向数组
	int capacity; //容量
	int size;  //数组大小
};

//test.cpp
#include "MyArray.hpp"
//测试内置数据类型
void printIntArray(MyArray<int>& arr) {
	for (int i = 0; i < arr.GetSize(); i++) {
		cout << arr[i] << " ";
	}
	cout << endl;
}
void test01()
{
	MyArray<int> array1(10);
	for (int i = 0; i < 10; i++)
	{
		array1.PushBack(i);
	}
	cout << "array1打印输出：" << endl;
	printIntArray(array1);
	cout << "array1的大小：" << array1.GetSize() << endl;
	cout << "array1的容量：" << array1.GetCapacity() << endl;

	cout << "--------------------------" << endl;
}

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

void printPersonArray(MyArray<Person>& personArr)
{
	for (int i = 0; i < personArr.GetSize(); i++) {
		cout << "姓名：" << personArr[i].name << " 年龄： " << personArr[i].age << endl;
	}
}

void test02()
{
	//创建数组
	MyArray<Person> pArray(10);
	Person p1("孙悟空", 30);
	Person p2("韩信", 20);
	Person p3("妲己", 18);
	Person p4("王昭君", 15);
	Person p5("赵云", 24);

	//插入数据
	pArray.PushBack(p1);
	pArray.PushBack(p2);
	pArray.PushBack(p3);
	pArray.PushBack(p4);
	pArray.PushBack(p5);

	printPersonArray(pArray);

	cout << "pArray的大小：" << pArray.GetSize() << endl;
	cout << "pArray的容量：" << pArray.GetCapacity() << endl;

}

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

二、STL

2.1 STL的基础知识

定义：C++ STL（标准模板库）是一套功能强大的 C++ 模板类，提供了通用的模板类和函数，这些模板类和函数可以实现多种流行和常用的算法和数据结构，如向量、链表、队列、栈。

分类：广义上分为：① 容器(container) ② 算法(algorithm) ③ 迭代器(iterator)。其中容器和算法之间通过迭代器进行无缝连接。

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

组件名字	作用
容器	各种数据结构，如`vector`、`list`、`deque`、`set`、`map`等,用来存放数据
算法	各种常用的算法，如`sort`、`find`、`copy`、`for_each`等
迭代器	扮演了容器与算法之间的胶合剂
仿函数	行为类似函数，可作为算法的某种策略
适配器	一种用来修饰容器或者仿函数或迭代器接口的东西
空间配置器	负责空间的配置与管理

2.2 STL中的容器，算法，迭代器

容器：置物之所也。
STL容器：将运用最广泛的一些数据结构实现出来，常用的数据结构：数组, 链表,树, 栈, 队列, 集合, 映射表等。
分类：
① 序列式容器: 强调值的排序，序列式容器中的每个元素均有固定的位置。
② 关联式容器: 二叉树结构，各元素之间没有严格的物理上的顺序关系。
算法：问题之解法也。
算法(Algorithms)：有限的步骤，解决逻辑或数学上的问题。
分类：
① 质变算法：是指运算过程中会更改区间内的元素的内容。例如拷贝，替换，删除等等
② 非质变算法：是指运算过程中不会更改区间内的元素内容，例如查找、计数、遍历、寻找极值等等
迭代器：容器和算法之间粘合剂。
提供一种方法，使之能够依序寻访某个容器所含的各个元素，而又无需暴露该容器的内部表示方式。
每个容器都有自己专属的迭代器。迭代器使用非常类似于指针，初学阶段我们可以先理解迭代器为指针。
分类如下表：

种类	功能	支持运算
输入迭代器	对数据的只读访问	只读，支持++、==、！=
输出迭代器	对数据的只写访问	只写，支持++
前向迭代器	读写操作，并能向前推进迭代器	读写，支持++、==、！=
双向迭代器	读写操作，并能向前和向后操作	读写，支持++、–，
随机访问迭代器	读写操作，可以以跳跃的方式访问任意数据，功能最强的迭代器	读写，支持++、–、[n]、-n、<、<=、>、>=

2.2.1 用vector对容器算法迭代器再认识

STL中最常用的容器为vector，可以理解为数组。

1. vector存放内置数据类型

            容器： vector
            算法： for_each
            迭代器：vector<int>::iterator

//eg
#include<vector>//vector容器的头文件
#include<algorithm>//标准算法头文件
using namespace std;
void print(int val)
{
	cout << val;
}
int main()
{
	//创建一个int类型vector容器，相当于int数组
	vector <int> v;
	//向容器插入数据
	v.push_back(0);
	v.push_back(1);
	v.push_back(2);
	v.push_back(3);
	//通过迭代器访问容器中的数据
	vector <int>::iterator ItBegin = v.begin();//起始迭代器，指向容器中的第一个元素
	vector <int>::iterator ItEnd = v.end();//结束迭代器，指向容器中最后一个元素的下一个位置
	//vector 中：0 1 2 3
	//           |       |
	//         begin    end
	// 
	//第一种遍历方式
	while (ItBegin != ItEnd)
	{
		cout << *ItBegin;
		ItBegin++;
	}
	//第二种遍历方式(相当于整合第一种方式)
	for (vector<int >::iterator begin = v.begin(); begin != v.end(); begin++)
	{
		cout << *begin;
	}
	//第三种遍历方式 
	for_each(v.begin(), v.end(), print);
	/* FUNCTION TEMPLATE for_each
	template <class _InIt, class _Fn>
	_CONSTEXPR20 _Fn for_each(_InIt _First, _InIt _Last, _Fn _Func) { // perform function for each element [_First, _Last)
		_Adl_verify_range(_First, _Last);
		auto _UFirst = _Get_unwrapped(_First);
		const auto _ULast = _Get_unwrapped(_Last);
		for (; _UFirst != _ULast; ++_UFirst) {
			_Func(*_UFirst);
		}
		return _Func;
	}*/

}

2. vector存放自定义数据类型

// vector存放自定义数据类型
using namespace std;
class person
{
public:
	person(string name, int age)
	{
		this->age = age;
		this->name = name;
	}
	int age;
	string name;
};

int main()
{
	//person类
	vector <person> v;
	//创建
	person p1("a", 18);
	person p2("b", 18);
	person p3("c", 18);
	person p4("d", 18);
	//向容器中添加数据
	v.push_back(p1);
	v.push_back(p2);
	v.push_back(p3);
	v.push_back(p4);
	//遍历
	for (vector<person>::iterator it = v.begin(); it != v.end(); it++)
	{
		cout << "姓名：" << (*it).age << endl;//it->age
		cout << "年龄：" << (*it).name << endl;//it->name
	}

	//指针类
	vector <person*> v1;
	//向容器中添加数据
	v1.push_back(&p1);
	v1.push_back(&p2);
	v1.push_back(&p3);
	v1.push_back(&p4);
	//遍历
	for (vector<person*>::iterator it = v1.begin(); it != v1.end(); it++)
	{
		cout << "姓名：" << (*it)->age << endl;
		cout << "年龄：" << (*it)->name << endl;
	}
}

3. vector容器嵌套容器

//vector容器嵌套容器
int main() 
{
	//大容器
	vector< vector<int> >  v;
	//小容器
	vector<int> v1;
	vector<int> v2;
	vector<int> v3;
	vector<int> v4;
	//小容器中添加数据
	for (int i = 0; i < 4; i++) {
		v1.push_back(i + 1);
		v2.push_back(i + 2);
		v3.push_back(i + 3);
		v4.push_back(i + 4);
	}
	//将小容器的元素插入到大容器中
	v.push_back(v1);
	v.push_back(v2);
	v.push_back(v3);
	v.push_back(v4);
	//遍历
	for (vector<vector<int>>::iterator it = v.begin(); it != v.end(); it++)
	{
		for (vector<int>::iterator vit = (*it).begin(); vit != (*it).end(); vit++) 
		{
			cout << *vit << " ";
		}
		cout << endl;
	}
}

2.3 常用容器

2.3.1 string

2.3.1.1 string基础知识

本质：string是C++风格的字符串，而string本质上是一个类。

????特点：string类内部封装了很多成员方法，例如：查找find，拷贝copy，删除delete 替换replace，插入insert。
????注意：string管理char*所分配的内存，不用担心复制越界和取值越界等，由类内部进行负责。

2.3.1.2 接口

1. 构造函数原型

              ① string():创建一个空的字符串
              ② string(const char* s)：使用字符串s初始化
              ③ string(const string& str):使用一个string对象初始化另一个string对象
              ④ string(int n, char c):使用n个字符c初始化

//string的构造函数
#include<string>//string头文件记得写
using namespace std;
int main()
{
	//1.默认构造 string()
	string s1;
	//2.有参构造 string(const char* s);
	const char* str = "Hello";
	string s2(str);
	//3.拷贝构造 string(const string& str);
	string s3(s2);
	//4.特殊的一种构造 string(int n, char c);
	string s4(10, 'a');
}

2. 赋值操作

              ① string& operator=(char c) :字符赋值给当前的字符串
              ② string& operator=(const char* s)：char*类型字符串赋值给当前的字符串
              ③ string& operator=(const string& s):把字符串s赋给当前的字符串
              ④ string& assign(const char *s):把字符串s赋给当前的字符串
              ⑤ string& assign(const char *s, int n):把字符串s的前n个字符赋给当前的字符串
              ⑥ string& assign(const string &s):把字符串s赋给当前字符串
              ⑦ string& assign(int n, char c):用n个字符c赋给当前字符串

	//1.string& operator=(char c)
	string s1;
	s1 = 'a';
	//2.string& operator=(const char* s)
	const char* str = "hello";
	string s2;
	s2= str;
	//3.string& operator=(const string& s)
	string s3;
	s3 = s2;
	//4.string& assign(const char* s)
	string s4;
	s4.assign(str);
	//5.string& assign(const char* s, int n)
	string s5;
	s5.assign(str, 3);
	//6.string& assign(const string& s)
	string s6;
	s6.assign(s2);
	//7.string& assign(int n, char c)
	string s7;
	s7.assign(5, 'a');

3. 字符存取

①char& operator[](int n)：通过[]方式取字符
②char& at(int n)：通过at方法获取字符

int main() 
{
	string str = "hello world";
	//1.char& operator[](int n)
	for (int i = 0; i < str.size(); i++)
	{
		cout << str[i] << " ";
	}
	cout << endl;
	//2.char& at(int n)
	for (int i = 0; i < str.size(); i++)
	{
		cout << str.at(i) << " ";
	}
	cout << endl;

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

4.字符串查找、替换

              ① int find(const char c, int pos = 0) const ：查找字符c第一次出现位置
              ② 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 string& str, int pos = 0) const：查找str第一次出现位置,从pos开始查找
              ⑤ int rfind(const char c, int pos = 0) const:查找字符c最后一次出现位置
              ⑥ 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 string& str, int pos = npos) const:查找str最后一次位置,从pos开始查找
              ⑨ string& replace(int pos, int n, const string& str)：替换从pos开始n个字符为字符串str
              ⑩ string& replace(int pos, int n,const char* s)：替换从pos开始的n个字符为字符串s

	string s1 = "hello!";

	string s2 = "nihao,hello,haha";

	//1.int find(const char c, int pos = 0) const;
	int ret = s2.find('a');//找到返回下标（从0开始），未找到返回-1
	//2.int find(const char* s, int pos = 0) const
	ret = s2.find("ha");
	//3.int find(const char* s, int pos, int n) const
	ret = s2.find("ha", 5, 6);
	//4.int find(const string& str, int pos = 0) const
	ret = s2.find(s1);
	//5.int rfind(const char c, int pos = 0) const
	ret = s2.rfind('a');
	//6.int rfind(const char* s, int pos = npos) const
	ret = s2.rfind("ha", 5);
	//7.int rfind(const char* s, int pos, int n) const
	ret = s2.rfind("ha", 5, 6);
	//8.int rfind(const string& str, int pos = npos) const
	ret = s2.rfind(s1);
	//9.string& replace(int pos, int n,const char* s)
	s2.replace(0,7, s1);
	//10.string& replace(int pos, int n, const string& str)
	s2.replace(0, 7, "haha");

           5. 插入和删除
              ① 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个字符

int main()
{
	//字符串插入和删除
	string str = "hello";
	str.insert(1, "111");
	cout << str << endl;

	str.erase(1, 3);  //从1号位置开始3个字符
	cout << str << endl;
}

           6. 字符串比较
              ① int compare(const string &s) const:与字符串s按字符的ASCII码进行对比,= 返回 0 > 返回 1 < 返回 -1
              ② int compare(const char *s) const:同上

	const char* str = "nihao";
	string s1("nihao");
	string s2("nihaoa");
	//1.int compare(const string &s) const
	int ret=s1.compare(str);
	//2.int compare(const char *s) const
	ret = s1.compare(s2);

7. 字符串拼接

              ① string& operator+=(char c)
              ② string& operator+=(const char* s)
              ③ string& operator=(const string& s)
              ④ string& append(const char *s)
              ⑤ string& append(const char *s, int n):把字符串s的前n个字符连接到当前字符串结尾
              ⑥ string& append (const string &s)
              ⑦ string& append(const string &s, int pos, int n):字符串s中从pos开始的n个字符连接到字符串结尾

	string s1 = "hello!";
	string s2;
	s2 = 'a';
	const char* str = "haha";
	//1.string& operator+=(const char c)
	string s3;
	s3+= s2;
	//2.string& operator+=(const char* str)
	string s4;
	s4 += str;
	//3.string& operator+=(const string& str)
	string s5;
	s5 += s1;
	//4.string& append(const char* str)
	string s6;
	s6.append(str);
    //5.string& append(const char* s, int n)
	string s7;
	s7.append(str, 3);
	//6.string& append(const string& s)
	string s8;
	s8.append(s1);
	//7.string& append(const string& s, int pos, int n);
	string s9;
	s9.append(s1, 2, 2);

8. 子串
① string substr(int pos = 0, int n = npos) const ：返回由pos开始的n个字符组成的字符串

int main()
{
	string str = "abcdefg";
	string subStr = str.substr(1, 3);
	cout << "subStr = " << subStr << endl;

	string email = "hello@sina.com";
	int pos = email.find("@");
	string username = email.substr(0, pos);
	cout << "username: " << username << endl;

}

2.3.2 vector

2.3.2.1 vector基础知识

vector数据结构和数组非常相似，也称为单端数组。

????特点：
① vector可以动态扩展（不是在原空间之后续接新空间，而是找更大的内存空间，然后将原数据拷贝新空间，释放原空间）。
② vector容器的迭代器是支持随机访问的迭代器。

在这里插入图片描述

2.3.2.2 接口

           1. 构造函数原型
              ① vector<T> v :采用模板实现类实现，默认构造函数
              ② vector(v.begin(), v.end())：将v[begin(), end())区间中的元素拷贝给本身
              ③ vector(n, elem):构造函数将n个elem拷贝给本身
              ④ vector(const vector &vec):拷贝构造函数

	//1.vector<T> v
	vector <int > v1;
	for (int i = 0; i < 10; i++)
	{
		v1.push_back(i);
	}
	
	//2.vector(v.begin(), v.end())
	vector<int> v2(v1.begin(), v1.end());
	
	//3.vector(n, elem)
	vector<int>v3(10, 100);//10个100
	
	//4.vector(const vector& vec)
	vector<int>v4(v1);

           2. 赋值操作
              ① vector& operator=(const vector &vec) :重载等号操作符
              ② assign(beg, end)：将[beg, end)区间中的数据拷贝赋值给本身
              ③ assign(n, elem):构将n个elem拷贝赋值给本身

	vector<int>v1;
	for (int i = 0; i < 10; i++)
	{
		v1.push_back(i);
	}
	//1.vector& operator=(const vector &vec)
	vector <int>v2 = v1;
	
	//2.assign(beg, end)
	vector <int>v3;
	v3.assign(v1.begin(), v1.end());
	
	//3.assign(n, elem)
	vector <int>v4;
	v4.assign(10, 100);

           3. 数据存取
              ① at(int idx) :返回索引idx所指的数据
              ② operator[]：返回索引idx所指的数据
              ③ front():返回容器中第一个数据元素
              ④ back():返回容器中最后一个数据元素

	vector<int>v1;
	for (int i = 0; i < 10; i++)
	{
		v1.push_back(i);
	}
	//1.at(int idx)
	cout << v1.at(0) << endl;

	//2.operator[]
	cout << v1[0] << endl;

	//3.front()
	cout << v1.front() << endl;

	//4.back()
	cout << v1.back() << endl;

           4. 容量和大小
              ① empty() :判断容器是否为空
              ② capacity()：容器的容量
              ③ size():返回容器中元素的个数
              ④ resize(int num):重新指定容器的长度为num。若容器变长，则以默认值填充新位置；如果容器变短，则末尾超出容器长度的元素被删除。
              ⑤ resize(int num, elem):重新指定容器的长度为num。若容器变长，则以elem值填充新位置；如果容器变短，则末尾超出容器长度的元素被删除

int main()
{
	vector<int>v;
	for (int i = 0; i < 10; i++)
	{
		v.push_back(i);
	}
	if (v.empty())
	{
		cout << "vector is empty"<<endl;
	}
	else
	{
		cout << "Not empty"<<endl;
		cout << "The vector's capacity is :" << v.capacity() << endl;
		cout << "The vector's size is :" << v.size() << endl;
	}

	v.resize(10);
	v.resize(10, 1);
}

           5. 插入和删除
              ① push_back(ele) :尾部插入元素ele
              ② pop_back()：删除最后一个元素
              ③ insert(const_iterator pos, ele):迭代器指向位置pos插入元素ele
              ④ insert(const_iterator pos, int count,ele):迭代器指向位置pos插入count个元素ele               ⑤ erase(const_iterator pos):删除迭代器指向的元素
              ⑥ erase(const_iterator start, const_iterator end):删除迭代器从start到end之间的元素
              ⑦ clear():删除容器中所有元素

void print(vector<int> v)
{
	if (v.empty())
	{
		cout << "empty" << endl;
	}
	for (vector<int>::iterator it = v.begin(); it != v.end(); it++)
	{
		cout << *it ;
	}
	cout << endl;
}
int main()
{
	vector <int> v;
	v.push_back(1);
	v.push_back(2);
	v.push_back(3);
	v.push_back(4);
	print(v);

	v.pop_back();
	print(v);

	v.insert(v.begin(), 1);
	print(v);

	v.insert(v.begin(), 10, 1);
	print(v);

	v.erase(v.begin());
	v.erase(v.begin(), v.end());
	v.clear();
	print(v);
}

6. 互换容器
① swap(vec)：将vec与本身的元素互换

void print(vector<int> v)
{
	if (v.empty())
	{
		cout << "empty" << endl;
	}
	for (vector<int>::iterator it = v.begin(); it != v.end(); it++)
	{
		cout << *it ;
	}
	cout << endl;
}
int main()
{
	vector<int> v1;
	for (int i = 0; i < 10; i++)
	{
		v1.push_back(i);
	}
	vector<int> v2;
	for (int i = 9; i >= 0; i--)
	{
		v2.push_back(i);
	}
	cout << "交换前:" << endl;
	print(v1);
	print(v2);
	v2.swap(v1);
	cout << "交换后:" << endl;
	print(v1);
	print(v2);
}

????注意：swap有的收缩内存作用

//swap的收缩内存作用
int main()
{
	vector <int> v;
	for (int i = 0; i < 999999; 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;

	//收缩内存
	vector<int>(v).swap(v); //匿名对象

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

2.3.3 deque

2.3.3.1 deque基础知识

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

????特点：
① deque对头部的插入删除速度比vector快
② deque容器的迭代器是支持随机访问的迭代器。
在这里插入图片描述

内部工作原理
deque中有一个中控器，维护每段缓冲区，缓冲区里面存放数据。
在这里插入图片描述

2.3.3.2 接口

              ① push_back(ele) :尾部插入元素ele
              ② pop_back()：删除最后一个元素
              ③ insert(const_iterator pos, ele):迭代器指向位置pos插入元素ele
              ④ insert(const_iterator pos, int count,ele):迭代器指向位置pos插入count个元素ele               ⑤ erase(const_iterator pos):删除迭代器指向的元素
              ⑥ erase(const_iterator start, const_iterator end):删除迭代器从start到end之间的元素
              ⑦ clear():删除容器中所有元素

	//1.deque<T> deqT
	deque<int> d1;
	for (int i = 0; i < 10; i++)
	{
		d1.push_front(i);//头插
	}
	//2.deque(beg, end)
	deque<int> d2(d1.begin(), d1.end());
	//3.deque(n, elem)
	deque<int> d3(10, 100);
	//4.deque(const deque &deq)
	deque<int> d4(d1);

案例三：评委打分

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

#include<iostream>
#include<string>
#include<queue>
#include<vector>
#include <algorithm>
using namespace std;
class Person
{
public:
	Person(string name, double score)
	{
		this->score = score;
		this->name = name;
	}
	string name;
	double score;
};
void CreatPlayer(vector <Person>& v)
{
	string s1 = "选手";
	for (int i = 0; i < 5; i++)//5个选手
	{
		string s2 = "ABCDE";
		s2 = s1 + s2[i];//一个比较巧妙的办法，将选手 A两个字符串结合，作为类中的name
		double score = 0.0;//设置初始分数为0，作为类中的score
		Person p(s2, score);//实例化对象
		v.push_back(p);//将一个类放在vector容器中
	}
}
void SetScore(vector<Person>& v)
{
	deque<double> d;
	for (vector<Person>::iterator it = v.begin(); it != v.end(); it++)//ABCDE选手
	{
		//评委随机打分
		for (int i = 0; i < 10; i++)//10个评委
		{
			double x = rand() % 41 + 60;//40-60
			d.push_back(x);
		}
		//分数排序
		sort(d.begin(), d.end());
		//去掉最高分和最低分
		d.pop_front();
		d.pop_back();
		//计算平均分
		double sum = 0;
		for (deque<double>::iterator dit = d.begin(); dit != d.end(); dit++)
		{
			sum = sum + *dit;
		}
		double avg = sum / d.size();
		//将平均分给类中的score
		it->score = avg;
	}
}
void ShowScore(vector<Person>& v)
{
	for (vector<Person>::iterator it = v.begin(); it != v.end(); it++)
		cout << (*it).name << endl << "平均分：" << (*it).score << endl;
}
int main()
{
	vector<Person> v;//选手容器
	CreatPlayer(v);
	SetScore(v);
	ShowScore(v);
}

2.3.4 stack

2.3.4.1 stack基础知识

stack一种先进后出(First In Last Out,FILO)的数据结构，它只有一个出口。栈中进入数据称为 — 入栈 push，栈中弹出数据称为 — 出栈pop

????特点：栈中只有顶端的元素才可以被外界使用，因此栈不允许有遍历行为。

2.3.4.2 接口

构造函数：
① stack<T> stk ：stack采用模板类实现， stack对象的默认构造形式
② stack(const stack &stk): 拷贝构造函数

赋值操作：
stack& operator=(const stack &stk): 重载等号操作符

数据存取：
push(elem) : 向栈顶添加元素
pop(): 从栈顶移除第一个元素
top(): 返回栈顶元素

大小操作：
empty():判断堆栈是否为空
size():返回栈的大小

//eg.
#include <stack>
//栈容器常用接口
void test01()
{
	//创建栈容器 栈容器必须符合先进后出
	stack<int> s;

	//向栈中添加元素，叫做 压栈 入栈
	s.push(10);
	s.push(20);
	s.push(30);

	while (!s.empty()) {
		//输出栈顶元素
		cout << "栈顶元素为： " << s.top() << endl;
		//弹出栈顶元素
		s.pop();
	}
	cout << "栈的大小为：" << s.size() << endl;

}

int main() {

	test01();

	system("pause");

	return 0;
}

2.3.5 queue

2.3.5.1 queue基础知识

queue是一种先进先出(First In First Out,FIFO)的数据结构，它有两个出口。队列容器允许从一端新增元素，从另一端移除元素。队列中进数据称为 — 入队push，队列中出数据称为 — 出队 pop。

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

2.3.5.2 接口

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

赋值操作：
queue& operator=(const queue &que):重载等号操作符

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

大小操作：
empty():判断堆栈是否为空
size():返回栈的大小

#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("唐僧", 30);
	Person p2("孙悟空", 1000);
	Person p3("猪八戒", 900);
	Person p4("沙僧", 800);

	//向队列中添加元素  入队操作
	q.push(p1);
	q.push(p2);
	q.push(p3);
	q.push(p4);

	//队列不提供迭代器，更不支持随机访问	
	while (!q.empty()) {
		//输出队头元素
		cout << "队头元素-- 姓名： " << q.front().m_Name
			<< " 年龄： " << q.front().m_Age << endl;

		cout << "队尾元素-- 姓名： " << q.back().m_Name
			<< " 年龄： " << q.back().m_Age << endl;

		cout << endl;
		//弹出队头元素
		q.pop();
	}

	cout << "队列大小为：" << q.size() << endl;
}

int main() {

	test01();

	system("pause");

	return 0;
}

2.3.6 list

2.3.6.1 list基础知识

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

链表的组成：链表由一系列结点组成
结点的组成：一个是存储数据元素的数据域，另一个是存储下一个结点地址的指针域
在这里插入图片描述

????特点：
① 由于链表的存储方式并不是连续的内存空间，因此链表list中的迭代器只支持前移和后移，属于双向迭代器。
② STL中的链表是一个双向循环链表。
③ 插入操作和删除操作都不会造成原有list迭代器的失效，这在vector是不成立的。

list的优点：
① 采用动态存储分配，不会造成内存浪费和溢出
② 链表执行插入和删除操作十分方便，修改指针即可，不需要移动大量元素
list的缺点：
① 链表灵活，但是空间(指针域) 和时间（遍历）额外耗费较大

2.3.6.2 接口

           1. 构造函数原型
              ① list<T> lst :采用模板类实现,对象的默认构造形式
              ② list(beg,end)：构造函数将[beg, end)区间中的元素拷贝给本身
              ③ list(n,elem):构造函数将n个elem拷贝给本身
              ④ list(const list &lst):拷贝构造函数

#include <list>
void printList(const list<int>& L) 
{
	for (list<int>::const_iterator it = L.begin(); it != L.end(); it++) 
	{
		cout << *it << " ";
	}
	cout << endl;
}
void test01()
{
	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(L2);
	printList(L3);
	list<int>L4(10, 1000);
	printList(L4);
}
int main() 
{
	test01();
	system("pause");
	return 0;
}

           2.赋值和交换
              ① list& operator=(const list &lst) :重载等号操作符
              ② assign(beg, end)：将[beg, end)区间中的数据拷贝赋值给本身
              ③ assign(n, elem):构将n个elem拷贝赋值给本身
              ④ swap(lst):将lst与本身的元素互换

#include <list>

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

//赋值和交换
void test01()
{
	list<int>L1;
	L1.push_back(10);
	L1.push_back(20);
	L1.push_back(30);
	L1.push_back(40);
	printList(L1);

	//赋值
	list<int>L2;
	L2 = L1;
	printList(L2);

	list<int>L3;
	L3.assign(L2.begin(), L2.end());
	printList(L3);

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

}

//交换
void test02()
{

	list<int>L1;
	L1.push_back(10);
	L1.push_back(20);
	L1.push_back(30);
	L1.push_back(40);

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

	cout << "交换前： " << endl;
	printList(L1);
	printList(L2);

	cout << endl;

	L1.swap(L2);

	cout << "交换后： " << endl;
	printList(L1);
	printList(L2);

}

int main()
 {
	//test01();
	test02();
	system("pause");
	return 0;
}

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

#include <list>

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

//大小操作
void test01()
{
	list<int>L1;
	L1.push_back(10);
	L1.push_back(20);
	L1.push_back(30);
	L1.push_back(40);

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

	//重新指定大小
	L1.resize(10);
	printList(L1);

	L1.resize(2);
	printList(L1);
}

int main() {

	test01();
	system("pause");
	return 0;
}

           4. 数据存取
              ① front():返回容器中第一个数据元素
              ② back():返回容器中最后一个数据元素

#include <list>

//数据存取
void test01()
{
	list<int>L1;
	L1.push_back(10);
	L1.push_back(20);
	L1.push_back(30);
	L1.push_back(40);

	
	//cout << L1.at(0) << endl;//错误 不支持at访问数据
	//cout << L1[0] << endl; //错误  不支持[]方式访问数据
	cout << "第一个元素为： " << L1.front() << endl;
	cout << "最后一个元素为： " << L1.back() << endl;

	//list容器的迭代器是双向迭代器，不支持随机访问
	list<int>::iterator it = L1.begin();
	//it = it + 1;//错误，不可以跳跃访问，即使是+1
}

int main() {

	test01();

	system("pause");

	return 0;
}

           5. 插入和删除
              ① push_back(ele) :尾部插入元素ele
              ② push_front(elem)：开头插入元素ele
              ③ pop_front()：从容器开头移除第一个元素
              ④ pop_back()：删除容器中最后一个元素
              ⑤ insert(pos, ele):在pos位置插elem元素的拷贝，返回新数据的位置
              ⑥ insert(pos, int count,ele):在pos位置插入n个elem数据，无返回值
              ⑦ insert(pos,beg,end):在pos位置插入[beg,end)区间的数据，无返回值
              ⑧ erase(pos):删除pos位置的数据，返回下一个数据的位置
              ⑨ erase(start,end):删除[beg,end)区间的数据，返回下一个数据的位置
              ⑩ remove(elem):删除容器中所有与elem值匹配的元素
              ⑩① clear():删除容器中所有元素

#include <list>

void printList(const list<int>& L) {

	for (list<int>::const_iterator it = L.begin(); it != L.end(); it++) {
		cout << *it << " ";
	}
	cout << endl;
}

//插入和删除
void test01()
{
	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();
	printList(L);

	//头删
	L.pop_front();
	printList(L);

	//插入
	list<int>::iterator it = L.begin();
	L.insert(++it, 1000);
	printList(L);

	//删除
	it = L.begin();
	L.erase(++it);
	printList(L);

	//移除
	L.push_back(10000);
	L.push_back(10000);
	L.push_back(10000);
	printList(L);
	L.remove(10000);
	printList(L);
    
    //清空
	L.clear();
	printList(L);
}

int main() {

	test01();

	system("pause");

	return 0;
}

           6. 反转和排序
              ① reverse() :反转链表
              ② sort()：链表排序

void printList(const list<int>& L) {

	for (list<int>::const_iterator it = L.begin(); it != L.end(); it++) {
		cout << *it << " ";
	}
	cout << endl;
}

bool myCompare(int val1 , int val2)
{
	return val1 > val2;
}

//反转和排序
void test01()
{
	list<int> L;
	L.push_back(90);
	L.push_back(30);
	L.push_back(20);
	L.push_back(70);
	printList(L);

	//反转容器的元素
	L.reverse();
	printList(L);

	//排序
	L.sort(); //默认的排序规则 从小到大
	printList(L);

	L.sort(myCompare); //指定规则，从大到小
	printList(L);
}

int main() {

	test01();

	system("pause");

	return 0;
}

2.3.7 set/ multiset

2.3.7.1 set/ multiset 基础知识

set：所有元素都会在插入时自动被排序。set/multiset属于关联式容器，底层结构是用二叉树实现。

????注意：set和multiset区别：
set不允许容器中有重复的元素，multiset允许容器中有重复的元素

2.3.7.2 接口

           1. 构造函数原型和赋值
              ① set<T> st :采用模板实现类实现，默认构造函数
              ② set(const set &st):拷贝构造函数
              ③ set& operator=(const set &st):重载等号操作符

#include <set>

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

//构造和赋值
void test01()
{
	set<int> s1;

	s1.insert(10);
	s1.insert(30);
	s1.insert(20);
	s1.insert(40);
	printSet(s1);

	//拷贝构造
	set<int>s2(s1);
	printSet(s2);

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

int main() {

	test01();

	system("pause");

	return 0;
}

           2. 大小和交换
              ① empty() :判断容器是否为空
              ② size():返回容器中元素的个数
              ③ swap(st):交换两个集合容器

#include <set>

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

//大小
void test01()
{

	set<int> s1;
	
	s1.insert(10);
	s1.insert(30);
	s1.insert(20);
	s1.insert(40);

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

}

//交换
void test02()
{
	set<int> s1;

	s1.insert(10);
	s1.insert(30);
	s1.insert(20);
	s1.insert(40);

	set<int> s2;

	s2.insert(100);
	s2.insert(300);
	s2.insert(200);
	s2.insert(400);

	cout << "交换前" << endl;
	printSet(s1);
	printSet(s2);
	cout << endl;

	cout << "交换后" << endl;
	s1.swap(s2);
	printSet(s1);
	printSet(s2);
}

int main() {

	//test01();

	test02();

	system("pause");

	return 0;
}

3. 插入和删除

              ① insert(elem):在容器中插入元素
              ② erase(pos):删除pos迭代器所指的元素，返回下一个元素的迭代器
              ③ erase(start,end):删除区间[beg,end)的所有元素，返回下一个元素的迭代器
              ④ erase(elem):删除容器中值为elem的元素
              ⑤ clear():删除容器中所有元素

#include <set>

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

//插入和删除
void test01()
{
	set<int> s1;
	//插入
	s1.insert(10);
	s1.insert(30);
	s1.insert(20);
	s1.insert(40);
	printSet(s1);

	//删除
	s1.erase(s1.begin());
	printSet(s1);

	s1.erase(30);
	printSet(s1);

	//清空
	//s1.erase(s1.begin(), s1.end());
	s1.clear();
	printSet(s1);
}

int main() {

	test01();

	system("pause");

	return 0;
}

4. 查找和统计

① find(key):查找key是否存在,若存在，返回该键的元素的迭代器；若不存在，返回set.end()
② count(key):统计key的元素个数

#include <set>

//查找和统计
void test01()
{
	set<int> s1;
	//插入
	s1.insert(10);
	s1.insert(30);
	s1.insert(20);
	s1.insert(40);
	
	//查找
	set<int>::iterator pos = s1.find(30);

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

	//统计
	int num = s1.count(30);
	cout << "num = " << num << endl;
}

int main() {

	test01();

	system("pause");

	return 0;
}

5. set和multiset区别

① set不可以插入重复数据，而multiset可以
② set插入数据的同时会返回插入结果，表示插入是否成功，multiset不会检测数据，因此可以插入重复数据

#include <set>

//set和multiset区别
void test01()
{
	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
	multiset<int> ms;
	ms.insert(10);
	ms.insert(10);

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

int main() {

	test01();

	system("pause");

	return 0;
}

6. pair对组创建

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

① pair<type, type> p ( value1, value2 )
② pair<type, type> p = make_pair( value1, value2 )

#include <string>

//对组创建
void test01()
{
	pair<string, int> p(string("Tom"), 20);
	cout << "姓名： " <<  p.first << " 年龄： " << p.second << endl;

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

int main() {

	test01();

	system("pause");

	return 0;
}

7. 容器排序

利用仿函数，可以改变排序规则

//示例一：内置数据类型
#include <set>

class MyCompare 
{
public:
	bool operator()(int v1, int v2) {
		return v1 > v2;
	}
};
void test01() 
{    
	set<int> s1;
	s1.insert(10);
	s1.insert(40);
	s1.insert(20);
	s1.insert(30);
	s1.insert(50);

	//默认从小到大
	for (set<int>::iterator it = s1.begin(); it != s1.end(); it++) {
		cout << *it << " ";
	}
	cout << endl;

	//指定排序规则
	set<int,MyCompare> s2;
	s2.insert(10);
	s2.insert(40);
	s2.insert(20);
	s2.insert(30);
	s2.insert(50);

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

int main() {

	test01();

	system("pause");

	return 0;
}

//示例二 set存放自定义数据类型
#include <set>
#include <string>

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

	string m_Name;
	int m_Age;

};
class comparePerson
{
public:
	bool operator()(const Person& p1, const Person &p2)
	{
		//按照年龄进行排序  降序
		return p1.m_Age > p2.m_Age;
	}
};

void test01()
{
	set<Person, comparePerson> s;

	Person p1("刘备", 23);
	Person p2("关羽", 27);
	Person p3("张飞", 25);
	Person p4("赵云", 21);

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

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

	test01();

	system("pause");

	return 0;
}

2.3.8 map/ multimap

2.3.8.1 map/ multimap基础知识

map中所有元素都是pair。pair中第一个元素为key（键值），起到索引作用，第二个元素为value（实值），所有元素都会根据元素的键值自动排序。map/multimap属于关联式容器，底层结构是用二叉树实现。

????注意：map和multimap区别：
① map不允许容器中有重复key值元素
② multimap允许容器中有重复key值元素

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

2.3.8.2 接口

           1. 构造和赋值
              ① map<T1, T2> mp :采用模板实现类实现，默认构造函数
              ② map(const map &mp):拷贝构造函数
              ③ map& operator=(const map &mp):重载等号操作符

#include <map>

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

void test01()
{
	map<int,int>m; //默认构造
	m.insert(pair<int, int>(1, 10));
	m.insert(pair<int, int>(2, 20));
	m.insert(pair<int, int>(3, 30));
	printMap(m);

	map<int, int>m2(m); //拷贝构造
	printMap(m2);

	map<int, int>m3;
	m3 = m2; //赋值
	printMap(m3);
}

int main() {

	test01();

	system("pause");

	return 0;
}

           2. 大小和交换
              ① size() :返回容器中元素的数目
              ② empty():判断容器是否为空
              ③ swap(st):交换两个集合容器

#include <map>

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

void test01()
{
	map<int, int>m;
	m.insert(pair<int, int>(1, 10));
	m.insert(pair<int, int>(2, 20));
	m.insert(pair<int, int>(3, 30));

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


//交换
void test02()
{
	map<int, int>m;
	m.insert(pair<int, int>(1, 10));
	m.insert(pair<int, int>(2, 20));
	m.insert(pair<int, int>(3, 30));

	map<int, int>m2;
	m2.insert(pair<int, int>(4, 100));
	m2.insert(pair<int, int>(5, 200));
	m2.insert(pair<int, int>(6, 300));

	cout << "交换前" << endl;
	printMap(m);
	printMap(m2);

	cout << "交换后" << endl;
	m.swap(m2);
	printMap(m);
	printMap(m2);
}

int main() {

	test01();

	test02();

	system("pause");
	return 0;
}

3. 插入和删除

              ① insert(elem):在容器中插入元素
              ② erase(pos):删除pos迭代器所指的元素，返回下一个元素的迭代器
              ③ erase(start,end):删除区间[beg,end)的所有元素，返回下一个元素的迭代器
              ④ erase(key):删除容器中值为key的元素
              ⑤ clear():删除容器中所有元素

#include <map>

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

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; 
	printMap(m);

	//删除
	m.erase(m.begin());
	printMap(m);

	m.erase(3);
	printMap(m);

	//清空
	m.erase(m.begin(),m.end());
	m.clear();
	printMap(m);
}

int main() {

	test01();

	system("pause");

	return 0;
}

4. 查找和统计

① find(key):查找key是否存在,若存在，返回该键的元素的迭代器；若不存在，返回set.end()
② count(key):统计key的元素个数

#include <map>

//查找和统计
void test01()
{
	map<int, int>m; 
	m.insert(pair<int, int>(1, 10));
	m.insert(pair<int, int>(2, 20));
	m.insert(pair<int, int>(3, 30));

	//查找
	map<int, int>::iterator pos = m.find(3);

	if (pos != m.end())
	{
		cout << "找到了元素 key = " << (*pos).first << " value = " << (*pos).second << endl;
	}
	else
	{
		cout << "未找到元素" << endl;
	}

	//统计
	int num = m.count(3);
	cout << "num = " << num << endl;
}

int main() {

	test01();

	system("pause");

	return 0;
}

7. 容器排序

利用仿函数，可以改变排序规则

#include <map>

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

void test01() 
{
	//默认从小到大排序
	//利用仿函数实现从大到小排序
	map<int, int, MyCompare> m;

	m.insert(make_pair(1, 10));
	m.insert(make_pair(2, 20));
	m.insert(make_pair(3, 30));
	m.insert(make_pair(4, 40));
	m.insert(make_pair(5, 50));

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

	test01();

	system("pause");

	return 0;
}

案例四：员工分组

案例描述：

公司今天招聘了10个员工（ABCDEFGHIJ），10名员工进入公司之后，需要指派员工在那个部门工作
员工信息有: 姓名工资组成；部门分为：策划、美术、研发
随机给10名员工分配部门和工资
通过multimap进行信息的插入 key(部门编号) value(员工)
分部门显示员工信息

#include <string> 
#include <vector>
#include <map>
#include <ctime>
#include <iostream>
//部门的编号
#define CEHUA 0   //策划
#define MEISHU 1  //美术
#define YANFA 2   //研发
using namespace std;
//员工类
class Worker
{
public:
	Worker(string name,int salary)
	{
		this->name = name;
		this->salary = salary;
	}
	string name;//姓名
	int salary;//工资
};
//创建员工
void CreatWorker(vector<Worker>& w,int n)
{
	string name;
	int salary;
	for (int i = 0; i < n; i++)
	{
		name= "员工";
		char temp = (char)('A' + i);
		name = name + temp;//员工 ABCDEFG...

		salary = rand() % 1000 + 1000;//salary：1000-1999
		Worker worker(name, salary);//用name和salary实例化类
		w.push_back(worker);//将实例化的类放入vector容器中
	}

}
void ClassifyWorker(multimap<int, Worker>& m, vector <Worker> &w,int n)
{
	for (int i = 0;i < n; i++)
	{
		int id = rand() % 3;//0 1 2
		m.insert(make_pair(id, w.at(i)));
	}
}
void ShowWorkerByGourp(multimap<int, Worker>& m)
{
	cout << "策划部门：" << endl;

	multimap<int, Worker>::iterator pos = m.find(CEHUA);
	int count = m.count(CEHUA); // 统计具体人数
	int index = 0;
	for (; pos != m.end() && index < count; pos++, index++)
	{
		cout << "姓名： " << pos->second.name << " 工资： " << pos->second.salary << endl;
	}

	cout << "----------------------" << endl;
	cout << "美术部门： " << endl;
	pos = m.find(MEISHU);
	count = m.count(MEISHU); // 统计具体人数
	index = 0;
	for (; pos != m.end() && index < count; pos++, index++)
	{
		cout << "姓名： " << pos->second.name << " 工资： " << pos->second.salary << endl;
	}

	cout << "----------------------" << endl;
	cout << "研发部门： " << endl;
	pos = m.find(YANFA);
	count = m.count(YANFA); // 统计具体人数
	index = 0;
	for (; pos != m.end() && index < count; pos++, index++)
	{
		cout << "姓名： " << pos->second.name << " 工资： " << pos->second.salary << endl;
	}

}
int main()
{
	srand((unsigned int)time(NULL));//随机数种子，为了产生随机工资和部门编号
	vector <Worker> w;              //员工信息
	multimap<int, Worker> m;        //部门编号 + 员工信息
	int number;                     //员工数目
	cout << "please input the number of employees:";
	cin >> number;
	//创建员工
	CreatWorker(w,number);
	//员工分部门
	ClassifyWorker(m,w, number);
	//按部门输出
	ShowWorkerByGourp(m);
	return 0;
}

三、STL- 函数对象

3.1 函数对象

3.1.1 函数对象的基础知识

重载函数调用操作符的类，其对象常称为函数对象。
函数对象使用重载的()时，行为类似函数调用，也叫仿函数

3.1.2 函数对象使用

????特点：

普通函数共性：可以有参数，返回值
仿函数特性：可以有自己的状态
函数对象可以作为参数传递

class MyAdd
{
public:
	MyAdd()
	{
		count = 0;
	}
	int count;
	//1.普通函数共性：可以有参数，返回值
	int operator()(int a, int b)
	{
		//2.仿函数特性：可以有自己的状态
		count++;
		return a + b;
	}
};
//3.函数对象可以作为参数传递
void test(MyAdd& ma, int a, int b)
{
	cout<<ma(a, b)<<endl;
}
int main()
{
	MyAdd ma;
	cout << ma(10, 10) << endl;
	cout << ma(10, 20) << endl;
	cout << ma.count << endl;
	test(ma, 10, 30);
	return 0;
}

3.2 谓词

3.2.1 谓词的基础知识

            谓词：返回bool类型的仿函数
            一元谓词：operator()接受一个参数
            二元谓词 ：operator()接受两个参数

3.2.2 一元谓词

class GreatFive
{
public:
	bool operator()(int val)
	{
		return val > 5;
	}
};
int main()
{
	vector<int> v;
	srand((unsigned int)time(NULL));
	for (int i = 0; i < 10; i++)
	{
		v.push_back((rand() % 10));//随机放入0-9数字
	}
	for (int i = 0; i < 10; i++)
	{
		cout<<v.at(i);
	}
	cout << endl;
	//找第一个大于5的数字
	vector<int> ::iterator it=find_if(v.begin(), v.end(), GreatFive());//GreatFive 匿名函数对象
	if (it == v.end())
	{
		cout << "Not Find" << endl;
	}
	else
	{
		cout << "Find!" << *it << endl;
	}
	return 0;
}

find_if函数原型：
在这里插入图片描述

3.2.3 二元谓词

class MyCompare
{
public:
	//两个参数——二元谓词
	bool operator()(int num1,int num2)
	{
		return num1 > num2;
	}
};
int main()
{
	vector<int> v;
	v.push_back(1);
	v.push_back(3);
	v.push_back(2);
	v.push_back(5);
	//默认sort从小到大
	cout << "sort排序默认输出：" << endl;
	sort(v.begin(), v.end());
	for (vector<int>::iterator it = v.begin(); it != v.end(); it++)
	{
		cout << *it<<" ";
	}
	cout << endl;
	//从大到小
	cout << "sort排序从大到小输出：" << endl;
	sort(v.begin(), v.end(), MyCompare());
	for (vector<int>::iterator it = v.begin(); it != v.end(); it++)
	{
		cout << *it << " ";
	}
	cout << endl;

}

3.3 内建函数对象

3.3.1 内建函数对象意义

            概念：STL内建了一些函数对象。
            分类: ①算术仿函数 ②关系仿函数 ③逻辑仿函数
            用法: 和一般函数完全相同，但需要引入头文件 #include<functional>

3.3.2 算术仿函数

作用：实现四则运算

            仿函数原型：
            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> //取反仿函数

????注意：其中negate是一元运算，其他都是二元运算

void test1()
{
	//取反
	negate<int> n;
	cout << n(10) << endl;
}
void test2()
{
	//相加
	plus<int>p;
	cout << p(1, 2) << endl;
}
int main()
{
	test1();
	test2();
	return 0;
}

3.3.3 关系仿函数

            仿函数原型：
            template<class T> bool equal_to<T>//等于
            template<class T> bool not_equal_to<T> emplate<class T> T minus<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> //小于等于

class MyComper
{
public:
	bool operator()(int num1,int num2)
	{
		return num1 > num2;
	}
};
int main()
{
	vector<int> v;
	v.push_back(2);
	v.push_back(1);
	v.push_back(4);
	v.push_back(3);
	sort(v.begin(), v.end());     //默认：升序
	sort(v.begin(), v.end(), MyComper());  //自定义：降序
	sort(v.begin(), v.end(), greater<int>()); //与上面一条语句等价
	for (vector<int>::iterator it = v.begin(); it != v.end(); it++)
	{
		cout << *it;
	}
	cout << endl;
}

3.3.4 逻辑仿函数

            仿函数原型：
            template<class T> bool logical_and<T>//逻辑与
            template<class T> bool logical_or<T>//逻辑或
            template<class T> bool logical_not<T> //逻辑非

int main()
{
	vector<bool> v1;
	v1.push_back(true);
	v1.push_back(false);
	v1.push_back(true);
	v1.push_back(false);
	for (vector<bool>::iterator it = v1.begin(); it != v1.end(); it++)
	{
		cout << *it;
	}
	cout << endl;
	//将v的元素放在v1中而且元素取反
	vector<bool> v2;
	v2.resize(v1.size());
	transform(v1.begin(), v1.end(), v2.begin(), logical_not<bool>());
	for (vector<bool>::iterator it = v2.begin(); it != v2.end(); it++)
	{
		cout << *it;
	}
	cout << endl;

}

四、STL- 常用算法（施工ing）

4.1 常用遍历算法

4.1.1 for_each

函数原型：
for_each(iterator beg, iterator end, _func); //遍历算法遍历容器元素， beg 开始迭代器，end 结束迭代器， _func 函数或者函数对象

class  MyPrint
{
public:
	void operator()(int val)
	{
		cout << val << " ";
	}
};
void Print1(int val)
{
	cout << val << " ";
}
int main()
{
	vector<int> v;
	for (int i = 0; i < 10; i++)
	{
		v.push_back(i);
	}
	for_each(v.begin(), v.end(), Print1);
	cout << endl;
	for_each(v.begin(), v.end(), MyPrint());
	return 0;
}

4.1.2 transform

函数原型：
transform(iterator beg1, iterator end1, iterator beg2, _func); //beg1 源容器开始迭代器，end1 源容器结束迭代器，beg2 目标容器开始迭代器，_func 函数或者函数对象

class TransForm
{
public:
	int operator()(int val)
	{
		return val+10;//原数据+10
	}
};
void print(int val)
{
	cout << val << " ";
}
int main()
{
	vector<int> v;
	for (int i = 0; i < 10; i++)
		v.push_back(i);
	vector<int> TargetV; //目标容器
	TargetV.resize(v.size()); // 目标容器需要提前开辟空间
	transform(v.begin(), v.end(), TargetV.begin(), TransForm());
	for_each(TargetV.begin(), TargetV.end(), print);
}

4.2 常用查找算法

            find //查找元素
            find_if //按条件查找元素
            adjacent_find //查找相邻重复元素
            binary_search //二分查找法
            count //统计元素个数
            count_if //按条件统计元素个数

4.2.1 find

            函数原型：find(iterator beg, iterator end, value);
            // 按值查找元素，找到返回指定位置迭代器，找不到返回结束迭代器位置
            // beg 开始迭代器
            // end 结束迭代器
            // value 查找的元素

class person
{
public:
	person(string name, int age)
	{
		this->name = name;
		this->age = age;
	}
	bool operator==(const person& p)
	{
		if (this->name == p.name && this->age == p.age)
			return true;
		else
			return false;
	}
	string name;
	int age;
};
int main()
{
	//1.内置数据类型
	vector<int> v;
	for (int i = 0; i < 10; i++)
	{
		v.push_back(i);
	}
	vector<int>::iterator it1 = find(v.begin(), v.end(), 5);
	if (it1 == v.end())
		cout << "NOT FIND!" << endl;
	else
		cout << "FIND" << endl;
	//2.自定义数据类型
	vector<person> p;
	person p1("a", 0);
	person p2("b", 1);
	person p3("c", 2);
	p.push_back(p1);
	p.push_back(p2);
	p.push_back(p3);
	vector<person>::iterator it2 = find(p.begin(), p.end(), p2);
	if (it2 == p.end())
		cout << "NOT FIND!" << endl;
	else
		cout << "FIND" << endl;
	return 0;
}

4.2.2 find_if

            函数原型：find_if(iterator beg, iterator end, _Pred);
            // 按值查找元素，找到返回指定位置迭代器，找不到返回结束迭代器位置
            // beg 开始迭代器
            // end 结束迭代器
            // _Pred 函数或者谓词（返回bool类型的仿函数）

#include <algorithm>
#include <vector>
#include <string>

//内置数据类型
class GreaterFive
{
public:
	bool operator()(int val)
	{
		return val > 5;
	}
};

void test01() {

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

	vector<int>::iterator it = find_if(v.begin(), v.end(), GreaterFive());
	if (it == v.end()) {
		cout << "没有找到!" << endl;
	}
	else {
		cout << "找到大于5的数字:" << *it << endl;
	}
}

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

class Greater20
{
public:
	bool operator()(Person &p)
	{
		return p.m_Age > 20;
	}

};

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 it = find_if(v.begin(), v.end(), Greater20());
	if (it == v.end())
	{
		cout << "没有找到!" << endl;
	}
	else
	{
		cout << "找到姓名:" << it->m_Name << " 年龄: " << it->m_Age << endl;
	}
}

int main() {

	//test01();

	test02();

	system("pause");

	return 0;
}

4.2.3 adjacent_find

            函数原型：adjacent_find(iterator beg, iterator end);
            // 查找相邻重复元素,返回相邻元素的第一个位置的迭代器
            // beg 开始迭代器
            // end 结束迭代器

#include <algorithm>
#include <vector>

void test01()
{
	vector<int> v;
	v.push_back(1);
	v.push_back(2);
	v.push_back(5);
	v.push_back(2);
	v.push_back(4);
	v.push_back(4);
	v.push_back(3);

	//查找相邻重复元素
	vector<int>::iterator it = adjacent_find(v.begin(), v.end());
	if (it == v.end()) {
		cout << "找不到!" << endl;
	}
	else {
		cout << "找到相邻重复元素为:" << *it << endl;
	}

4.2.4 binary_search

            函数原型：bool binary_search(iterator beg, iterator end, value);
            // 查找指定的元素，查到返回true 否则false
            // 注意: 在无序序列中不可用
            // beg 开始迭代器
            // end 结束迭代器
            // value 查找的元素

#include <algorithm>
#include <vector>

void test01()
{
	vector<int>v;

	for (int i = 0; i < 10; i++)
	{
		v.push_back(i);
	}
	//二分查找
	bool ret = binary_search(v.begin(), v.end(),2);
	if (ret)
	{
		cout << "找到了" << endl;
	}
	else
	{
		cout << "未找到" << endl;
	}
}

int main() {

	test01();

	system("pause");

	return 0;
}

4.2.5 count

            函数原型：count(iterator beg, iterator end, value);
            // 统计元素出现次数
            // beg 开始迭代器
            // end 结束迭代器
            // value 统计的元素

#include <algorithm>
#include <vector>

//内置数据类型
void test01()
{
	vector<int> v;
	v.push_back(1);
	v.push_back(2);
	v.push_back(4);
	v.push_back(5);
	v.push_back(3);
	v.push_back(4);
	v.push_back(4);

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

	cout << "4的个数为： " << num << endl;
}

//自定义数据类型
class Person
{
public:
	Person(string name, int age)
	{
		this->m_Name = name;
		this->m_Age = age;
	}
	bool operator==(const Person & p)
	{
		if (this->m_Age == p.m_Age)
		{
			return true;
		}
		else
		{
			return false;
		}
	}
	string m_Name;
	int m_Age;
};

void test02()
{
	vector<Person> v;

	Person p1("刘备", 35);
	Person p2("关羽", 35);
	Person p3("张飞", 35);
	Person p4("赵云", 30);
	Person p5("曹操", 25);

	v.push_back(p1);
	v.push_back(p2);
	v.push_back(p3);
	v.push_back(p4);
	v.push_back(p5);
    
    Person p("诸葛亮",35);

	int num = count(v.begin(), v.end(), p);
	cout << "num = " << num << endl;
}
int main() {

	//test01();

	test02();

	system("pause");

	return 0;
}

4.2.6 count_if

            函数原型：count_if(iterator beg, iterator end, _Pred);
            // 按条件统计元素出现次数
            // beg 开始迭代器
            // end 结束迭代器
            // _Pred 谓词

#include <algorithm>
#include <vector>

class Greater4
{
public:
	bool operator()(int val)
	{
		return val >= 4;
	}
};

//内置数据类型
void test01()
{
	vector<int> v;
	v.push_back(1);
	v.push_back(2);
	v.push_back(4);
	v.push_back(5);
	v.push_back(3);
	v.push_back(4);
	v.push_back(4);

	int num = count_if(v.begin(), v.end(), Greater4());

	cout << "大于4的个数为： " << num << endl;
}

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

	string m_Name;
	int m_Age;
};

class AgeLess35
{
public:
	bool operator()(const Person &p)
	{
		return p.m_Age < 35;
	}
};
void test02()
{
	vector<Person> v;

	Person p1("刘备", 35);
	Person p2("关羽", 35);
	Person p3("张飞", 35);
	Person p4("赵云", 30);
	Person p5("曹操", 25);

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

	int num = count_if(v.begin(), v.end(), AgeLess35());
	cout << "小于35岁的个数：" << num << endl;
}


int main() {

	//test01();

	test02();

	system("pause");

	return 0;
}

4.3 常用排序算法

             sort//对容器内元素进行排序
            random_shuffle //洗牌指定范围内的元素随机调整次序
            merge // 容器元素合并，并存储到另一容器中
            reverse // 反转指定范围的元素

4.3.1 sort

            函数原型：sort(iterator beg, iterator end, _Pred);
            // 按值查找元素，找到返回指定位置迭代器，找不到返回结束迭代器位置
            // beg 开始迭代器
            // end 结束迭代器
            // _Pred 谓词

#include <algorithm>
#include <vector>

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

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

	//sort默认从小到大排序
	sort(v.begin(), v.end());
	for_each(v.begin(), v.end(), myPrint);
	cout << endl;

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

int main() {

	test01();

	system("pause");

	return 0;
}

4.3.2 random_shuffle

            函数原型：random_shuffle(iterator beg, iterator end);
            // 指定范围内的元素随机调整次序
            // beg 开始迭代器
            // end 结束迭代器

#include <algorithm>
#include <vector>
#include <ctime>

class myPrint
{
public:
	void operator()(int val)
	{
		cout << val << " ";
	}
};

void test01()
{
	srand((unsigned int)time(NULL));
	vector<int> v;
	for(int i = 0 ; i < 10;i++)
	{
		v.push_back(i);
	}
	for_each(v.begin(), v.end(), myPrint());
	cout << endl;

	//打乱顺序
	random_shuffle(v.begin(), v.end());
	for_each(v.begin(), v.end(), myPrint());
	cout << endl;
}

int main() {

	test01();

	system("pause");

	return 0;
}

4.3.3 merge

函数原型：merge(iterator beg1, iterator end1, iterator beg2, iterator end2, iterator dest);
// 容器元素合并，并存储到另一容器中

// 注意: 两个容器必须是有序的

            // beg1 容器1开始迭代器
            // end1 容器1结束迭代器
            // beg2 容器2开始迭代器
            // end2 容器2结束迭代器
            // dest 目标容器开始迭代器

#include <algorithm>
#include <vector>

class myPrint
{
public:
	void operator()(int val)
	{
		cout << val << " ";
	}
};

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(), myPrint());
	cout << endl;
}

int main() {

	test01();

	system("pause");

	return 0;
}

4.3.4 reverse

            函数原型：reverse(iterator beg, iterator end);
            // 反转指定范围的元素
            // beg 开始迭代器
            // end 结束迭代器

#include <algorithm>
#include <vector>

class myPrint
{
public:
	void operator()(int val)
	{
		cout << val << " ";
	}
};

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

	cout << "反转前： " << endl;
	for_each(v.begin(), v.end(), myPrint());
	cout << endl;

	cout << "反转后： " << endl;

	reverse(v.begin(), v.end());
	for_each(v.begin(), v.end(), myPrint());
	cout << endl;
}

int main() {

	test01();

	system("pause");

	return 0;
}

4.4 常用拷贝和替换算法

            copy// 容器内指定范围的元素拷贝到另一容器中
            replace // 将容器内指定范围的旧元素修改为新元素
            replace_if // 容器内指定范围满足条件的元素替换为新元素
            swap // 互换两个容器的元素

4.4.1 copy

            函数原型：copy(iterator beg, iterator end, iterator dest);
            // 按值查找元素，找到返回指定位置迭代器，找不到返回结束迭代器位置
            // beg 开始迭代器
            // end 结束迭代器
            // dest 目标起始迭代器

#include <algorithm>
#include <vector>

class myPrint
{
public:
	void operator()(int val)
	{
		cout << val << " ";
	}
};

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

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

int main() {

	test01();

	system("pause");

	return 0;
}

4.4.2 replace

            函数原型：replace(iterator beg, iterator end, oldvalue, newvalue);
            // 将区间内旧元素替换成新元素
            // beg 开始迭代器
            // end 结束迭代器
            // oldvalue 旧元素
            // newvalue 新元素

#include <algorithm>
#include <vector>

class myPrint
{
public:
	void operator()(int val)
	{
		cout << val << " ";
	}
};

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

	cout << "替换前：" << endl;
	for_each(v.begin(), v.end(), myPrint());
	cout << endl;

	//将容器中的20 替换成 2000
	cout << "替换后：" << endl;
	replace(v.begin(), v.end(), 20,2000);
	for_each(v.begin(), v.end(), myPrint());
	cout << endl;
}

int main() {

	test01();

	system("pause");

	return 0;
}

4.4.3 replace_if

            函数原型：replace_if(iterator beg, iterator end, _pred, newvalue);
            // 按条件替换元素，满足条件的替换成指定元素
            // beg 开始迭代器
            // end 结束迭代器
            // _pred 谓词
            // newvalue 替换的新元素

#include <algorithm>
#include <vector>

class myPrint
{
public:
	void operator()(int val)
	{
		cout << val << " ";
	}
};

class ReplaceGreater30
{
public:
	bool operator()(int val)
	{
		return val >= 30;
	}

};

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

	cout << "替换前：" << endl;
	for_each(v.begin(), v.end(), myPrint());
	cout << endl;

	//将容器中大于等于的30 替换成 3000
	cout << "替换后：" << endl;
	replace_if(v.begin(), v.end(), ReplaceGreater30(), 3000);
	for_each(v.begin(), v.end(), myPrint());
	cout << endl;
}

int main() {

	test01();

	system("pause");

	return 0;
}

4.4.4 swap

            函数原型：swap(container c1, container c2);
            // 互换两个容器的元素
            // c1容器1
            // c2容器2

#include <algorithm>
#include <vector>

class myPrint
{
public:
	void operator()(int val)
	{
		cout << val << " ";
	}
};

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

	cout << "交换前： " << endl;
	for_each(v1.begin(), v1.end(), myPrint());
	cout << endl;
	for_each(v2.begin(), v2.end(), myPrint());
	cout << endl;

	cout << "交换后： " << endl;
	swap(v1, v2);
	for_each(v1.begin(), v1.end(), myPrint());
	cout << endl;
	for_each(v2.begin(), v2.end(), myPrint());
	cout << endl;
}

int main() {

	test01();

	system("pause");

	return 0;
}

4.5 常用算术生成算法

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

accumulate// 计算容器元素累计总和
fill// 向容器中添加元素

4.5.1 accumulate

            函数原型：accumulate(iterator beg, iterator end, value);
            // 计算容器元素累计总和
            // beg 开始迭代器
            // end 结束迭代器
            // value 起始值

#include <numeric>
#include <vector>
void test01()
{
	vector<int> v;
	for (int i = 0; i <= 100; i++) {
		v.push_back(i);
	}

	int total = accumulate(v.begin(), v.end(), 0);

	cout << "total = " << total << endl;
}

int main() {

	test01();

	system("pause");

	return 0;
}

4.5.2 fill

            函数原型：fill(iterator beg, iterator end, value);
            // 向容器中填充元素
            // beg 开始迭代器
            // end 结束迭代器
            // value 填充的值

#include <numeric>
#include <vector>
#include <algorithm>

class myPrint
{
public:
	void operator()(int val)
	{
		cout << val << " ";
	}
};

void test01()
{

	vector<int> v;
	v.resize(10);
	//填充
	fill(v.begin(), v.end(), 100);

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

int main() {

	test01();

	system("pause");

	return 0;
}

4.6 常用集合算法

            set_intersection // 求两个容器的交集
            set_union// 求两个容器的并集
            set_difference// 求两个容器的差集

4.6.1 set_intersection

            函数原型：set_intersection(iterator beg1, iterator end1, iterator beg2, iterator end2, iterator dest);
            // 求两个集合的交集
            // 注意:两个集合必须是有序序列
            // beg1 容器1开始迭代器
            // end1 容器1结束迭代器
            // beg2 容器2开始迭代器
            // end2 容器2结束迭代器
            // dest 目标容器开始迭代器

#include <vector>
#include <algorithm>

class myPrint
{
public:
	void operator()(int val)
	{
		cout << val << " ";
	}
};

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, myPrint());
	cout << endl;
}

int main() {

	test01();

	system("pause");

	return 0;
}

4.6.2 set_union

            函数原型：set_union(iterator beg1, iterator end1, iterator beg2, iterator end2, iterator dest);
            // 求两个集合的并集
            // 注意:两个集合必须是有序序列
            // beg1 容器1开始迭代器
            // end1 容器1结束迭代器
            // beg2 容器2开始迭代器
            // end2 容器2结束迭代器
            // dest 目标容器开始迭代器

#include <vector>
#include <algorithm>

class myPrint
{
public:
	void operator()(int val)
	{
		cout << val << " ";
	}
};

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(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, myPrint());
	cout << endl;
}

int main() {

	test01();

	system("pause");

	return 0;
}

4.6.3 set_difference

函数原型：set_difference(iterator beg1, iterator end1, iterator beg2, iterator end2, iterator dest);
// 求两个集合的差集

// 注意:两个集合必须是有序序列

            // beg1 容器1开始迭代器
            // end1 容器1结束迭代器
            // beg2 容器2开始迭代器
            // end2 容器2结束迭代器
            / dest 目标容器开始迭代器

#include <vector>
#include <algorithm>

class myPrint
{
public:
	void operator()(int val)
	{
		cout << val << " ";
	}
};

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( max(v1.size() , v2.size()));

	//返回目标容器的最后一个元素的迭代器地址
	cout << "v1与v2的差集为： " << endl;
	vector<int>::iterator itEnd = 
        set_difference(v1.begin(), v1.end(), v2.begin(), v2.end(), vTarget.begin());
	for_each(vTarget.begin(), itEnd, myPrint());
	cout << endl;


	cout << "v2与v1的差集为： " << endl;
	itEnd = set_difference(v2.begin(), v2.end(), v1.begin(), v1.end(), vTarget.begin());
	for_each(vTarget.begin(), itEnd, myPrint());
	cout << endl;
}

int main() {

	test01();

	system("pause");

	return 0;
}

完结散花????????????

最后

以上就是乐观黑裤为你收集整理的【C++】黑马程序员C++提高编程（完结）一、模板二、STL三、STL- 函数对象四、STL- 常用算法（施工ing）的全部内容，希望文章能够帮你解决【C++】黑马程序员C++提高编程（完结）一、模板二、STL三、STL- 函数对象四、STL- 常用算法（施工ing）所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。

本图文内容来源于网友提供，作为学习参考使用，或来自网络收集整理，版权属于原作者所有。

本文分类：# C++
浏览次数：86 次浏览
发布日期：2023-12-04 09:45:08
本文链接：https://www.kaopuke.com/article/k-p-k_13_u_23_o_6_fx_13__23__22_0.html