C++学习（二）

模板

模板的概念

模板的特点：

模板不可以直接使用，它只是一个框架
模板的通用并不是万能的

C++的一种编程思想就是：泛型编程，主要利用的就是模板

函数模板

函数模板语法

函数模板作用：

建立一个通用函数，其函数返回值类型和指定形参类型可以不具体指定，用一个虚拟的类型来代表

语法：

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

解释：

template – 声明创建模板

typename – 表明其后面的是一种数据类型，可以用class代替

T – 通用的数据类型，名称可以替换，通常为大写字母

实例：

#include<iostream>
using namespace std;
template<typename T>
void mySwap(T& a, T& b){
	T temp = a;
	a = b;
	b = temp;
} 
int main() {

	double a = 10.2;
	double b = 20.1;
	
	//1.自动类型推导 
	mySwap(a, b);
	cout << a << endl;  // 20.1
	cout << b << endl;  // 10.2

	//2.显示指定类型 
	mySwap<double>(a, b);
	cout << a << endl;  // 10.2
	cout << b << endl;  // 20.1

	system("pause");

	return 0;
}

总结：

函数模板利用关键字 template
使用函数模板有两种方式：自动类型推导、显示指定类型
模板的目的是为了提高复用性，将类型参数化

函数模板注意事项

使用模板时必须确定出通用数据类型T，并且能够推导出一致的类型

#include<iostream>
using namespace std;
//1、自动类型推导，必须推导出一致的数据类型T,才可以使用
template<typename T>
void mySwap(T& a, T& b){
	T temp = a;
	a = b;
	b = temp;
}

//2、模板必须要确定出T的数据类型，才可以使用
template<typename T>
void func(){
	cout << "func函数执行..." << endl; 
} 
int main() {
	
	int a = 10;
	int b = 20;
	char c = 'a';
	//mySwap(a, c);  //错误，推导不出一致的T类型
	mySwap(a, b);  //正确，推导出一致的T类型

	//func();  //错误，模板不能独立使用，必须确定出T的类型
	func<int>();  //利用显示指定类型的方式，给T一个类型，才可以使用该模板
	
	system("pause");

	return 0;
}

函数模板案例

案例描述：

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

实例：

#include<iostream>
using namespace std;
//交换 
template<typename T>
void mySwap(T& a, T& b){
	T temp = a;
	a = b;
	b = temp;
}
//排序 
template<typename T>
void mySort(T a[], int len){
	int i,j,min;
	for(i=0;i<len;i++){
		min = i;
		for(j=i;j<len;j++){
			if(a[j] < a[min]){
				min = j;
			}
		}
		if(min != i){
			mySwap(a[i], a[min]);
		}
	}
}
//输出 
template<typename T>
void printArr(T arr[], int len){
	for(int i=0;i<len;i++){
		if(i == len -1){
			cout << arr[i] << endl;
			break;
		}
		cout << arr[i] << " -> ";
	} 	
}
//测试数字 
void test01(){
	int arr[] = {5,1,3,2,4,6};
	int len = sizeof(arr) / sizeof(int);
	mySort(arr, len);
	printArr(arr, len);
}
//测试字符 
void test02(){
	char arr[] = {'c', 'a', 'd', 'e', 'b'};
	int len = sizeof(arr) / sizeof(char);
	mySort(arr, len);
	printArr(arr, len);
} 
int main() {
	
	test01();  // 1 -> 2 -> 3 -> 4 -> 5 -> 6
	test02();  // a -> b -> c -> d -> e

	system("pause");

	return 0;
}

模板的局限性

例如：

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

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

再例如：

template<typename T>
void f(T a, T b){
    if(a >b){
        ...;
    }
}

在上述代码中，如果传入的是我们自定义的类，就无法进行

因此C++为了解决这一问题，提供模板的重载，可以为这些特定的类型提供具体化的模板

实例：

#include<iostream>
#include<string>
using namespace std;
class Person{
public:
	Person(string name, int age){
		this->name = name;
		this->age = age;
	}
	string name;
	int age;	
};
//普通函数模板 
template<typename T>
bool myCompare(T& a, T& b){
	if(a == b)
		return true;
	return false;
}
//具体化，显示具体化的原型和定意思以template<>开头，并通过名称来指出类型
//具体化优先于常规模板 
template<> bool myCompare(Person& a, Person& b){
	if(a.name == b.name && a.age == b.age)
		return true;
	return false;
}
void test01(){
	int a = 10;
	int b = 10;
	bool ret = myCompare(a, b);
	cout << ret << endl;  // 1
}
void test02(){
	Person p1("zhangsan", 20);
	Person p2("zhangsan", 20);
	bool ret = myCompare(p1, p2);
	cout << ret << endl;  // 1
}
int main() {
	
	test01();
	test02();
	
	system("pause");

	return 0;
}

总结：

利用具体化的模板，可以解决自定义类型的通化
学习模板并不是为了写模板，而是在STL能运用系统提供的模板

类模板

类模板语法

类模板作用：

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

语法：

1 2	template<class T> 类

实例：

#include<iostream>
#include<string>
using namespace std;
template<class NameType, class AgeType>
class Person{
public:
	Person(NameType name, AgeType age){
		this->name = name;
		this->age = age;
	}
	void showPerson(){
		cout << "name : " << this->name << " , age : " << this->age << endl; 
	}
	NameType name;
	AgeType age;
};
int main() {

	Person<string, int> p1("zhangsan", 20);
	p1.showPerson();  // name : zhangsan , age : 20

	system("pause");

	return 0;
}

类模板与函数模板的区别

类模板使用只能用显示指定类型方式
1
Person<string, int> p1("zhangsan", 20);

类模板中的模板参数列表可以有默认参数

template<class NameType, class AgeType = int>
class Person{
    
}

类模板与继承

当类模板碰到继承时，需要注意一下几点：

当子类继承的父类是一个类模板时，子类在声明的时候，要指定出父类中T的类型
如果不指定，编译器无法给子类分配内存
如果想灵活指定出父类中T的类型，子类也需变为类模板

实例：

#include<iostream>
#include<string>
#include<typeinfo>
using namespace std;
template<class T>
class Base
{
	T m;
};

//class Son:public Base  //错误，c++编译需要给子类分配内存，必须知道父类中T的类型才可以向下继承
class Son :public Base<int> //必须指定一个类型
{
};
void test01()
{
	Son c;
}

//类模板继承类模板 ,可以用T2指定父类中的T类型
template<class T1, class T2>
class Son2 :public Base<T2>
{
public:
	Son2()
	{
	}
};
void test02()
{
	Son2<int, char> child1;
}
int main() {

	test01();
	test02();
	system("pause");

	return 0;
}

总结：如果父类是类模板，子类需要指定出父类中T的数据类型

类模板成员函数类外实现

#include<iostream>
#include<string>
using namespace std;
template<class T1, class T2>
class Person{
public:
	Person(T1 name, T2 age);
	void showPerson();
	T1 name;
	T2 age;
};

template<class T1, class T2>
Person<T1, T2>::Person(T1 name, T2 age){
	this->name = name;
	this->age = age; 
}

template<class T1, class T2>
void Person<T1, T2>::showPerson(){
	cout << "姓名：" << this->name << "，年龄：" << this->age << endl;
}
int main() {

	Person<string, int> p1("zhangsan", 20);
	p1.showPerson();  // 姓名：zhangsan，年龄：20
	
	system("pause");

	return 0;
}

总结：类模板中成员函数类外实现时，需要加上模板参数列表

类模板分文件编写

编写person.hpp文件代码如下（hpp是约定的名称，并不是强制）：

#pragma once //防止头文件重复包含 
#include<iostream>
#include<string>
using namespace std;
template<class T1, class T2>
class Person{
public:
	Person(T1 name, T2 age);
	void showPerson();
	T1 name;
	T2 age;
};

template<class T1, class T2>
Person<T1, T2>::Person(T1 name, T2 age){
	this->name = name;
	this->age = age; 
}

template<class T1, class T2>
void Person<T1, T2>::showPerson(){
	cout << "姓名：" << this->name << "，年龄：" << this->age << endl;
}

新建cpp文件包含上个hpp模板并使用：

#include<iostream>
#include<string>
#include "person.hpp" 
using namespace std;
int main() {

	Person<string, int> p1("zhangsan", 20);
	p1.showPerson();  // 姓名：zhangsan，年龄：20	
	
	system("pause");

	return 0;
}

总结：主流的解决方式是将类模板成员函数写到一起，并将后缀名改为.hpp

STL初识

STL的诞生

长久以来，软件界一直希望建立一种可重复利用的东西
C++的面向对象和泛型编程思想，目的就是复用性的提升
大多情况下，数据结构和算法都未能有一套标准,导致被迫从事大量重复工作
为了建立数据结构和算法的一套标准,诞生了STL

STL基本概念

STL(Standard Template Library,标准模板库)
STL 从广义上分为: 容器(container) 算法(algorithm) 迭代器(iterator)
容器和算法之间通过迭代器进行无缝连接。
STL 几乎所有的代码都采用了模板类或者模板函数

STL六大组件

STL大体分为六大组件，分别是:容器、算法、迭代器、仿函数、适配器（配接器）、空间配置器

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

2.4 STL中容器、算法、迭代器

容器：置物之所也

STL容器就是将运用最广泛的一些数据结构实现出来

常用的数据结构：数组, 链表,树, 栈, 队列, 集合, 映射表等

这些容器分为序列式容器和关联式容器两种:

序列式容器:强调值的排序，序列式容器中的每个元素均有固定的位置。
关联式容器:二叉树结构，各元素之间没有严格的物理上的顺序关系

算法：问题之解法也

有限的步骤，解决逻辑或数学上的问题，这一门学科我们叫做算法(Algorithms)

算法分为:质变算法和非质变算法。

质变算法：是指运算过程中会更改区间内的元素的内容。例如拷贝，替换，删除等等

非质变算法：是指运算过程中不会更改区间内的元素内容，例如查找、计数、遍历、寻找极值等等

迭代器：容器和算法之间粘合剂

提供一种方法，使之能够依序寻访某个容器所含的各个元素，而又无需暴露该容器的内部表示方式。

每个容器都有自己专属的迭代器

迭代器使用非常类似于指针，初学阶段我们可以先理解迭代器为指针

迭代器种类：

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

常用的容器中迭代器种类为双向迭代器，和随机访问迭代器

STL-常用容器

3.1 string容器

3.1.1 string基本概念

本质：

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

string和char * 区别：

char * 是一个指针
string是一个类，类内部封装了char*，管理这个字符串，是一个char*型的容器。

特点：

string 类内部封装了很多成员方法

例如：查找find，拷贝copy，删除delete 替换replace，插入insert

string管理char*所分配的内存，不用担心复制越界和取值越界等，由类内部进行负责

3.1.2 string构造函数

构造函数原型：

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

3.1.3 string赋值操作

功能描述：

给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赋给当前字符串

3.1.4 string字符串拼接

功能描述：

实现在字符串末尾拼接字符串

函数原型：

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

3.1.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

3.1.6 string字符串比较

功能描述：

字符串之间的比较

比较方式：

字符串比较是按字符的ASCII码进行对比

= 返回 0

> 返回 1

< 返回 -1

函数原型：

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

3.1.7 string字符存取

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

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

3.1.8 string插入和删除

功能描述：

对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个字符

3.1.9 string子串

功能描述：

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

函数原型：

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

3.2 vector容器

3.2.1 vector基本概念

功能：

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

vector与普通数组区别：

不同之处在于数组是静态空间，而vector可以动态扩展

动态扩展：

并不是在原空间之后续接新空间，而是找更大的内存空间，然后将原数据拷贝新空间，释放原空间
vector容器的迭代器是支持随机访问的迭代器

3.2.2 vector构造函数

功能描述：

创建vector容器

函数原型：

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

3.2.3 vector赋值操作

功能描述：

给vector容器进行赋值

函数原型：

vector& operator=(const vector &vec);//重载等号操作符

assign(beg, end); //将[beg, end)区间中的数据拷贝赋值给本身。
assign(n, elem); //将n个elem拷贝赋值给本身。

3.2.4 vector容量和大小

功能描述：

对vector容器的容量和大小操作

函数原型：

empty(); //判断容器是否为空
capacity(); //容器的容量
size(); //返回容器中元素的个数
resize(int num); //重新指定容器的长度为num，若容器变长，则以默认值填充新位置。

//如果容器变短，则末尾超出容器长度的元素被删除。
resize(int num, elem); //重新指定容器的长度为num，若容器变长，则以elem值填充新位置。

//如果容器变短，则末尾超出容器长度的元素被删除

总结：

判断是否为空 — empty
返回元素个数 — size
返回容器容量 — capacity
重新指定大小 — resize

3.2.5 vector插入和删除

功能描述：

对vector容器进行插入、删除操作

函数原型：

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(); //删除容器中所有元素

总结：

尾插 — push_back
尾删 — pop_back
插入 — insert (位置迭代器)
删除 — erase （位置迭代器）
清空 — clear

3.2.6 vector数据存取

功能描述：

对vector中的数据的存取操作

函数原型：

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

3.2.7 vector互换容器

功能描述：

实现两个容器内元素进行互换

函数原型：

swap(vec); // 将vec与本身的元素互换

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

3.2.8 vector预留空间

功能描述：

减少vector在动态扩展容量时的扩展次数

函数原型：

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

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

3.3 deque容器

3.3.1 deque容器基本概念

功能：

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

deque与vector区别：

vector对于头部的插入删除效率低，数据量越大，效率越低
deque相对而言，对头部的插入删除速度回比vector快
vector访问元素时的速度会比deque快,这和两者内部实现有关

deque内部工作原理:

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

中控器维护的是每个缓冲区的地址，使得使用deque时像一片连续的内存空间

deque容器的迭代器也是支持随机访问的

3.3.2 deque构造函数

功能描述：

deque容器构造

函数原型：

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

3.3.3 deque赋值操作

功能描述：

给deque容器进行赋值

函数原型：

deque& operator=(const deque &deq); //重载等号操作符

assign(beg, end); //将[beg, end)区间中的数据拷贝赋值给本身。
assign(n, elem); //将n个elem拷贝赋值给本身。

3.3.4 deque大小操作

功能描述：

对deque容器的大小进行操作

函数原型：

deque.empty(); //判断容器是否为空
deque.size(); //返回容器中元素的个数
deque.resize(num); //重新指定容器的长度为num,若容器变长，则以默认值填充新位置。

//如果容器变短，则末尾超出容器长度的元素被删除。
deque.resize(num, elem); //重新指定容器的长度为num,若容器变长，则以elem值填充新位置。

//如果容器变短，则末尾超出容器长度的元素被删除。

3.3.5 deque 插入和删除

功能描述：

向deque容器中插入和删除数据

函数原型：

两端插入操作：

push_back(elem); //在容器尾部添加一个数据
push_front(elem); //在容器头部插入一个数据
pop_back(); //删除容器最后一个数据
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位置的数据，返回下一个数据的位置。

总结：

插入和删除提供的位置是迭代器！
尾插 — push_back
尾删 — pop_back
头插 — push_front
头删 — pop_front

3.3.6 deque 数据存取

功能描述：

对deque 中的数据的存取操作

函数原型：

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

总结：

除了用迭代器获取deque容器中元素，[ ]和at也可以
front返回容器第一个元素
back返回容器最后一个元素

3.3.7 deque 排序

功能描述：

利用算法实现对deque容器进行排序

算法：

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

3.5 stack容器

3.5.1 stack 基本概念

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

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

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

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

3.5.2 stack 常用接口

功能描述：栈容器常用的对外接口

构造函数：

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

赋值操作：

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

数据存取：

push(elem); //向栈顶添加元素
pop(); //从栈顶移除第一个元素
top(); //返回栈顶元素

大小操作：

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

3.6 queue 容器

3.6.1 queue 基本概念

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

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

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

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

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

3.6.2 queue 常用接口

功能描述：栈容器常用的对外接口

构造函数：

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

赋值操作：

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

数据存取：

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

大小操作：

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

3.7 list容器

3.7.1 list基本概念

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

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

链表的组成：链表由一系列结点组成

结点的组成：一个是存储数据元素的数据域，另一个是存储下一个结点地址的指针域

STL中的链表是一个双向循环链表

由于链表的存储方式并不是连续的内存空间，因此链表list中的迭代器只支持前移和后移，属于双向迭代器

list的优点：

采用动态存储分配，不会造成内存浪费和溢出
链表执行插入和删除操作十分方便，修改指针即可，不需要移动大量元素

list的缺点：

链表灵活，但是空间(指针域) 和时间（遍历）额外耗费较大

List有一个重要的性质，插入操作和删除操作都不会造成原有list迭代器的失效，这在vector是不成立的。

总结：STL中List和vector是两个最常被使用的容器，各有优缺点

3.7.2 list构造函数

功能描述：

创建list容器

函数原型：

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

3.7.3 list 赋值和交换

功能描述：

给list容器进行赋值，以及交换list容器

函数原型：

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

3.7.4 list 大小操作

功能描述：

对list容器的大小进行操作

函数原型：

size(); //返回容器中元素的个数
empty(); //判断容器是否为空
resize(num); //重新指定容器的长度为num，若容器变长，则以默认值填充新位置。

//如果容器变短，则末尾超出容器长度的元素被删除。
resize(num, elem); //重新指定容器的长度为num，若容器变长，则以elem值填充新位置。
```
                        //如果容器变短，则末尾超出容器长度的元素被删除。
```

3.7.5 list 插入和删除

功能描述：

对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值匹配的元素。

总结：

尾插 — push_back
尾删 — pop_back
头插 — push_front
头删 — pop_front
插入 — insert
删除 — erase
移除 — remove
清空 — clear

3.7.6 list 数据存取

功能描述：

对list容器中数据进行存取

函数原型：

front(); //返回第一个元素。
back(); //返回最后一个元素。

3.7.7 list 反转和排序

功能描述：

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

函数原型：

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

3.8 set/ multiset 容器

3.8.1 set基本概念

简介：

所有元素都会在插入时自动被排序

本质：

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

set和multiset区别：

set不允许容器中有重复的元素
multiset允许容器中有重复的元素

3.8.2 set构造和赋值

功能描述：创建set容器以及赋值

构造：

set<T> st; //默认构造函数：
set(const set &st); //拷贝构造函数

赋值：

set& operator=(const set &st); //重载等号操作符

3.8.3 set大小和交换

功能描述：

统计set容器大小以及交换set容器

函数原型：

size(); //返回容器中元素的数目
empty(); //判断容器是否为空
swap(st); //交换两个集合容器

3.8.4 set插入和删除

功能描述：

set容器进行插入数据和删除数据

函数原型：

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

总结：

插入 — insert
删除 — erase
清空 — clear

3.8.5 set查找和统计

功能描述：

对set容器进行查找数据以及统计数据

函数原型：

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

3.9 map/ multimap容器

3.9.1 map基本概念

简介：

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

本质：

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

优点：

可以根据key值快速找到value值

map和multimap区别：

map不允许容器中有重复key值元素
multimap允许容器中有重复key值元素

3.9.2 map构造和赋值

功能描述：

对map容器进行构造和赋值操作

函数原型：

构造：

map<T1, T2> mp; //map默认构造函数:
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;
}

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

3.9.3 map大小和交换

功能描述：

统计map容器大小以及交换map容器

函数原型：

size(); //返回容器中元素的数目
empty(); //判断容器是否为空
swap(st); //交换两个集合容器

3.9.4 map插入和删除

功能描述：

map容器进行插入数据和删除数据

函数原型：

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

3.9.5 map查找和统计

功能描述：

对map容器进行查找数据以及统计数据

函数原型：

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

3.9.6 map容器排序

学习目标：

map容器默认排序规则为按照key值进行从小到大排序，掌握如何改变排序规则

主要技术点:

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

STL- 函数对象

4.1 函数对象

4.1.1 函数对象概念

概念：

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

本质：

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

4.1.2 函数对象使用

特点：

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

示例:

#include <string>

//1、函数对象在使用时，可以像普通函数那样调用, 可以有参数，可以有返回值
class MyAdd
{
public :
	int operator()(int v1,int v2)
	{
		return v1 + v2;
	}
};

void test01()
{
	MyAdd myAdd;
	cout << myAdd(10, 10) << endl;
}

//2、函数对象可以有自己的状态
class MyPrint
{
public:
	MyPrint()
	{
		count = 0;
	}
	void operator()(string test)
	{
		cout << test << endl;
		count++; //统计使用次数
	}

	int count; //内部自己的状态
};
void test02()
{
	MyPrint myPrint;
	myPrint("hello world");
	myPrint("hello world");
	myPrint("hello world");
	cout << "myPrint调用次数为： " << myPrint.count << endl;
}

//3、函数对象可以作为参数传递
void doPrint(MyPrint &mp , string test)
{
	mp(test);
}

void test03()
{
	MyPrint myPrint;
	doPrint(myPrint, "Hello C++");
}

int main() {

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

	system("pause");

	return 0;
}

总结：

仿函数写法非常灵活，可以作为参数进行传递。

4.2 谓词

4.2.1 谓词概念

概念：

返回bool类型的仿函数称为谓词
如果operator()接受一个参数，那么叫做一元谓词
如果operator()接受两个参数，那么叫做二元谓词

4.2.2 一元谓词

示例：

#include <vector>
#include <algorithm>

//1.一元谓词
struct GreaterFive{
	bool operator()(int val) {
		return val > 5;
	}
};

void test01() {

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

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

}

int main() {

	test01();

	system("pause");

	return 0;
}

总结：参数只有一个的谓词，称为一元谓词

4.2.3 二元谓词

示例：

#include <vector>
#include <algorithm>
//二元谓词
class MyCompare
{
public:
	bool operator()(int num1, int num2)
	{
		return num1 > num2;
	}
};

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

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

	//使用函数对象改变算法策略，排序从大到小
	sort(v.begin(), v.end(), MyCompare());
	for (vector<int>::iterator it = v.begin(); it != v.end(); it++)
	{
		cout << *it << " ";
	}
	cout << endl;
}

int main() {

	test01();

	system("pause");

	return 0;
}

总结：参数只有两个的谓词，称为二元谓词

4.3 内建函数对象

4.3.1 内建函数对象意义

概念：

STL内建了一些函数对象

分类:

算术仿函数
关系仿函数
逻辑仿函数

用法：

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

4.3.2 算术仿函数

功能描述：

实现四则运算
其中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> //取反仿函数

示例：

#include <functional>
//negate
void test01()
{
	negate<int> n;
	cout << n(50) << endl;
}

//plus
void test02()
{
	plus<int> p;
	cout << p(10, 20) << endl;
}

int main() {

	test01();
	test02();

	system("pause");

	return 0;
}

总结：使用内建函数对象时，需要引入头文件 #include <functional>

4.3.3 关系仿函数

功能描述：

实现关系对比

仿函数原型：

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> //小于等于

示例：

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

class MyCompare
{
public:
	bool operator()(int v1,int v2)
	{
		return v1 > v2;
	}
};
void test01()
{
	vector<int> v;

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

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

	//自己实现仿函数
	//sort(v.begin(), v.end(), MyCompare());
	//STL内建仿函数  大于仿函数
	sort(v.begin(), v.end(), greater<int>());

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

int main() {

	test01();

	system("pause");

	return 0;
}

总结：关系仿函数中最常用的就是greater<>大于

4.3.4 逻辑仿函数

功能描述：

实现逻辑运算

函数原型：

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

示例：

#include <vector>
#include <functional>
#include <algorithm>
void test01()
{
	vector<bool> v;
	v.push_back(true);
	v.push_back(false);
	v.push_back(true);
	v.push_back(false);

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

	//逻辑非  将v容器搬运到v2中，并执行逻辑非运算
	vector<bool> v2;
	v2.resize(v.size());
	transform(v.begin(), v.end(),  v2.begin(), logical_not<bool>());
	for (vector<bool>::iterator it = v2.begin(); it != v2.end(); it++)
	{
		cout << *it << " ";
	}
	cout << endl;
}

int main() {

	test01();

	system("pause");

	return 0;
}

总结：逻辑仿函数实际应用较少，了解即可

STL- 常用算法

概述:

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

5.1 常用遍历算法

学习目标：

掌握常用的遍历算法

算法简介：

for_each //遍历容器
transform //搬运容器到另一个容器中

5.1.1 for_each

功能描述：

实现遍历容器

函数原型：

for_each(iterator beg, iterator end, _func);

// 遍历算法遍历容器元素

// beg 开始迭代器

// end 结束迭代器

// _func 函数或者函数对象

示例：

#include <algorithm>
#include <vector>

//普通函数
void print01(int val) 
{
	cout << val << " ";
}
//函数对象
class print02 
{
 public:
	void operator()(int val) 
	{
		cout << val << " ";
	}
};

//for_each算法基本用法
void test01() {

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

	//遍历算法
	for_each(v.begin(), v.end(), print01);
	cout << endl;

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

int main() {

	test01();

	system("pause");

	return 0;
}

总结：for_each在实际开发中是最常用遍历算法，需要熟练掌握

5.1.2 transform

功能描述：

搬运容器到另一个容器中

函数原型：

transform(iterator beg1, iterator end1, iterator beg2, _func);

//beg1 源容器开始迭代器

//end1 源容器结束迭代器

//beg2 目标容器开始迭代器

//_func 函数或者函数对象

示例：

#include<vector>
#include<algorithm>

//常用遍历算法  搬运 transform

class TransForm
{
public:
	int operator()(int val)
	{
		return val;
	}

};

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

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

	vector<int>vTarget; //目标容器

	vTarget.resize(v.size()); // 目标容器需要提前开辟空间

	transform(v.begin(), v.end(), vTarget.begin(), TransForm());

	for_each(vTarget.begin(), vTarget.end(), MyPrint());
}

int main() {

	test01();

	system("pause");

	return 0;
}

总结： 搬运的目标容器必须要提前开辟空间，否则无法正常搬运

5.2 常用查找算法

学习目标：

掌握常用的查找算法

算法简介：

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

5.2.1 find

功能描述：

查找指定元素，找到返回指定元素的迭代器，找不到返回结束迭代器end()

函数原型：

find(iterator beg, iterator end, value);

// 按值查找元素，找到返回指定位置迭代器，找不到返回结束迭代器位置

// beg 开始迭代器

// end 结束迭代器

// value 查找的元素

示例：

#include <algorithm>
#include <vector>
#include <string>
void test01() {

	vector<int> v;
	for (int i = 0; i < 10; i++) {
		v.push_back(i + 1);
	}
	//查找容器中是否有 5 这个元素
	vector<int>::iterator it = find(v.begin(), v.end(), 5);
	if (it == v.end()) 
	{
		cout << "没有找到!" << endl;
	}
	else 
	{
		cout << "找到:" << *it << 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_Name == p.m_Name && this->m_Age == p.m_Age) 
		{
			return true;
		}
		return false;
	}

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

总结：利用find可以在容器中找指定的元素，返回值是迭代器

5.2.2 find_if

功能描述：

按条件查找元素

函数原型：

find_if(iterator beg, iterator end, _Pred);

// 按值查找元素，找到返回指定位置迭代器，找不到返回结束迭代器位置

// beg 开始迭代器

// end 结束迭代器

// _Pred 函数或者谓词（返回bool类型的仿函数）

5.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;
	}
}

总结：面试题中如果出现查找相邻重复元素，记得用STL中的adjacent_find算法

5.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;
}

总结：二分查找法查找效率很高，值得注意的是查找的容器中元素必须的有序序列

5.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;
}

总结： 统计自定义数据类型时候，需要配合重载 operator==

5.2.6 count_if

功能描述：

按条件统计元素个数

函数原型：

count_if(iterator beg, iterator end, _Pred);

// 按条件统计元素出现次数

// beg 开始迭代器

// end 结束迭代器

// _Pred 谓词

5.3 常用排序算法

学习目标：

掌握常用的排序算法

算法简介：

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

5.3.1 sort

功能描述：

对容器内元素进行排序

函数原型：

sort(iterator beg, iterator end, _Pred);

// 按值查找元素，找到返回指定位置迭代器，找不到返回结束迭代器位置

// beg 开始迭代器

// end 结束迭代器

// _Pred 谓词

5.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;
}

总结：random_shuffle洗牌算法比较实用，使用时记得加随机数种子

5.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;
}

总结：merge合并的两个容器必须的有序序列

5.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;
}

总结：reverse反转区间内元素，面试题可能涉及到

5.4 常用拷贝和替换算法

学习目标：

掌握常用的拷贝和替换算法

算法简介：

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

5.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;
}

总结：利用copy算法在拷贝时，目标容器记得提前开辟空间

5.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;
}

总结：replace会替换区间内满足条件的元素

5.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;
}

总结：replace_if按条件查找，可以利用仿函数灵活筛选满足的条件

5.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;
}

总结：swap交换容器时，注意交换的容器要同种类型

5.5 常用算术生成算法

学习目标：

掌握常用的算术生成算法

注意：

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

算法简介：

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

5.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;
}

总结：accumulate使用时头文件注意是 numeric，这个算法很实用

5.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;
}

总结：利用fill可以将容器区间内元素填充为指定的值

5.6 常用集合算法

学习目标：

掌握常用的集合算法

算法简介：

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

5.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;
}

总结：

求交集的两个集合必须的有序序列
目标容器开辟空间需要从两个容器中取小值
set_intersection返回值既是交集中最后一个元素的位置

5.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;
}

总结：

求并集的两个集合必须的有序序列
目标容器开辟空间需要两个容器相加
set_union返回值既是并集中最后一个元素的位置

5.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;
}

总结：

求差集的两个集合必须的有序序列
目标容器开辟空间需要从两个容器取较大值
set_difference返回值既是差集中最后一个元素的位置