c++基础2

模板

c++另一种编程思想称为泛型编程,主要利用的技术就是模板

c++提供两种模板机制:函数模板和类模板

函数模板

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

语法:

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

当使用class的时候,如果T有子类,编译器会认为是声明,所以还是使用typename吧

template<typename T>
void test(T& a, T& b) {
	T temp = a;
	a = b;
	b = temp;
}
int main() {
	int a = 1, b = 2;
	//自动推导类型
	test(a, b);
	//指定类型
	test<int>(a, b);
	cout << a << "==" << b << endl;
}       

注意事项:

自动类型推导,必须推导出一致的数据类型T才可以使用

模板必须要确定出T的数据类型,才可以使用

template<typename T>
void test(T& a, T& b) {
	T temp = a;
	a = b;
	b = temp;
}
int main() {
	int a = 1, b = 2;
	char c='1';
	//自动推导类型错误,因为两个类型不同
	test(a, c);
}    

template<typename T>
void test() {
	cout << "hhhh" << endl;
}
int main() {
	test();//错误,因为推导不出T是什么类型
}                                  

template<typename T>
void test() {
	cout << "hhhh" << endl;
}
int main() {
	test<int>(); //明确指定就可以
    test<string>();//这个也可以
}                                  

普通模板和函数模板区别

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

普通函数会发生隐式转换,例如下面的例子中,将char类型的c转换为了int,对应的就是c的ascll码

void print1(int a, int b) {
	cout << a + b << endl;
}
int main() {
	int a = 1;
	char b = 'c';
	print1(a,b);
}   

而使用模板函数时

template<typename T>
void print(T a,T b) {
	cout << a+b << endl;
}
int main() {
	int a = 1;
	char b = 'c';
	print(a,b);  //报错
}   

template<typename T>
void print(T a,T b) {
	cout << a+b << endl;
}
int main() {
	int a = 1;
	char b = 'c';
	print<int>(a,b);  //除非我们指定了数据类型为int
}     

普通函数和模板函数的调用规则

• 如果函数模板和普通函数都可以实现,优先调普通函数
• 可以通过空模板参数来强制调用函数模板
• 函数模板也可以发生重载
• 如果函数模板可以产生更好的匹配,优先调用函数模板

如果函数模板和普通函数都可以实现,优先调普通函数

template<typename T>
void test(T a) {
	cout <<"函数模板" << endl;
}
void test(int a) {
	cout << "普通函数" << endl;
}
int main() {
	int a = 1;
	test(a);
}                                  

结果:普通函数

template<typename T>
void test(T a) {
	cout <<"函数模板" << endl;
}
void test(int a);
int main() {
	int a = 1;
	test(a);
}    

如果普通函数只有声明也是调用普通函数,会报错没有找到定义

可以通过空模板参数来强制调用函数模板

template<typename T>
void test(T a) {
	cout <<"函数模板" << endl;
}
void test(int a) {
	cout << "普通函数" << endl;
}
int main() {
	int a = 1;
	test<>(a);
}     

这样就可以强制调用函数模板,当然,尖括号里面随便写个类型也可以,但没必要

函数模板也可以发生重载

template<typename T>
void test(T a) {
	cout <<"函数模板一个参数" << endl;
}
template<typename T>
void test(T a,T b) {
	cout << "函数模板两个参数" << endl;
}
int main() {
	int a = 1;
	test<>(a); //函数模板一个参数
	test<>(a,a); //函数模板两个参数
} 

如果函数模板可以产生更好的匹配,优先调用函数模板

template<typename T>
void test(T a) {
	cout <<"函数模板一个参数" << endl;
}
void test(int a) {
	cout << "普通函数" << endl;
}
int main() {
	char a = '1';
	test(a);
}     

会优先使用函数模板,因为普通函数确定了类型为int,而char需要转int,调用函数模板则不需要任何转换

模板的局限性

模板并不是万能的,例如

template<typename T>
bool test(T& a,T& b) {
	return a == b;
}
int main() {
	char a = '1';
	char b = '2';
	cout<<test(a,b);
}    

当我们传基础的数据类代码可以正常使用,但是当传入的数据是自定义类型的时候

class A {
public:
	string name;
};
template<typename T>
bool test(T& a,T& b) {
	return a == b;
}
int main() {
	A a1 = { "小明" };
	A a2 = { "大明" };
	cout<<test(a1,a2);
}  

就会报错了,因为没有找到A类型的==判断

解决办法有两个:

1 重写运算符

class A {
public:
	string name;
	bool operator==(A& a) {
		return (this->name == a.name);
	}
};
template<typename T>
bool test(T& a, T& b) {
	return a == b;
}
int main() {
	A a1 = { "小明" };
	A a2 = { "大明" };
	cout << test(a1, a2);
}

2 重写一个针对A类的函数模板

class A {
public:
	string name;
};
template<typename T>
bool test(T& a, T& b) {
	return a == b;
}
template<> bool test(A& a, A& b) {
	return a.name == b.name;
}
int main() {
	A a1 = { "小明" };
	A a2 = { "大明" };
	cout << test(a1, a2);
}

利用具体化的模板,可以解决自定义类型的通用化

类模板

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

语法:

template<typename T>
class 类名 {
};

//声明下面的类中可以使用这两个类型
template<typename NameType,typename AgeType>
class A {
public:
	NameType name;
	AgeType age;
};
int main() {
    //使用时指定两个类型
	A<string, int> a = { "小明",19 };
	cout << a.age << "==" << a.name << endl;
}

类模板和函数模板区别

• 类模板没有自动推导类型的使用方式

  template<typename NameType,typename AgeType>
  class A {
  public:
  	A(NameType _name, AgeType _age) {
  		this->name = _name;
  		this->age = _age;
  	}
  	NameType name;
  	AgeType age;
  };
  int main() {
      //A a("哈哈哈", 1); 报错,类模板没有自动推导
      A<string,int> a("哈哈哈", 1);  //可以正常使用
  	cout << a.age << "==" << a.name << endl;
  }
  

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

  template<typename NameType, typename AgeType=int>  //这里给AgeType设置了默认类型为int
  class A {
  public:
  	A(NameType _name, AgeType _age) {
  		this->name = _name;
  		this->age = _age;
  	}
  	NameType name;
  	AgeType age;
  };
  int main() {
  	//下面在使用时就只需要指定一个string即可
  	A<string> a("哈哈哈", 1);
  	cout << a.age << "==" << a.name << endl;
  }
  

需要注意的是,如果有两个或多个参数,只能从最右边开始指定默认类型

例如下面的就是错误的

template<typename NameType=string, typename AgeType>

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

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

• 普通类中的成员函数一开始就可以创建
• 模板类中的成员函数在调用的时候才会创建

class A {
public:
	void func1() {
		cout << "A-func" << endl;
	}
    A() {
		cout << "A-init"<<endl;
	}
};
class B {
public:
	void func2() {
		cout << "A-func" << endl;
	}
};
template <typename T>
class MyRun {
public:
	T t;
	void run1() {
		t.func1();
	}
	void run2() {
		t.func2();
	}
};
int main() {
	MyRun<A> m;
	m.run1();
	//m.run2();
}

当main方法中什么都不写的时候,可以正常运行,因为MyRun类中的属性t并没有确认是什么类型,只有在运行的时候才能确认t的类型,判断t有没有func1或func2的函数

当指定类型为A的时候就已经初始化创建了一个A对象

A-init
A-func

类模板对象做函数参数

三种传入方式

• 指定传入类型
• 参数模板化
• 整个类模板化

1 指定传入类型

template <typename NameType,typename AgeType>
class User {
public:
	NameType name;
	AgeType age;
	User(NameType _name,AgeType _age) :name(_name), age(_age) {
	}
};
//直接标明都是什么类型
void print(User<string, int>& u) {
	cout <<   u.name << "==" << u.age << endl;
}
int main() {
	User<string, int> user("小明", 20);
	print(user);
}

2 参数模板化

template <typename NameType,typename AgeType>
class User {
public:
	NameType name;
	AgeType age;
	User(NameType _name,AgeType _age) :name(_name), age(_age) {
	}
};
//模板的名称不需要和类模板定义名称一样,只是单纯定义函数模板
template <typename F_NameType,typename F_AgeType>
void print(User<F_NameType, F_AgeType>& u) {
	cout <<   u.name << "==" << u.age << endl;
    cout <<"F_NameType的数据类型为:" << typeid(F_NameType).name() << endl;
	cout <<"F_AgeType的数据类型为:" << typeid(F_AgeType).name() << endl;
}
int main() {
	User<string, int> user("小明", 20);
	print(user);
}

3 整个类模板化

template <typename NameType,typename AgeType>
class User {
public:
	NameType name;
	AgeType age;
	User(NameType _name,AgeType _age) :name(_name), age(_age) {
	}
};
//再定义有一个模板函数作为接收参数
template <typename T>
void print(T& u) {
	cout <<   u.name << "==" << u.age << endl;
	cout <<"T的数据类型dfsdfs为:" << typeid(T).name() << endl;
}
int main() {
	User<string, int> user("小明", 20);
	print(user);
}

类模板与继承

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

1 当子类继承的父类是一个类模板时,子类在声明的时候,要指出父类中T的类型

template <typename T>
class Father {
public:
	T obj;
};
class Son : public Father<int> {
};
int main() {
	Son s;
	s.obj = 100;
	cout << s.obj << endl;
}

2 如果想灵活指定父类中的T类型,子类也需要变为类模板

template <typename T>
class Father {
public:
	T obj;
};
//声明同时指定T2类型
template <typename T1,typename T2=int>
class Son : public Father<T1> {
public:
	T2 t2;
};
int main() {
	//传入的是Father的模板类型,Son的已经有默认类型了
	Son<int> s;
	s.obj = 100;
	s.t2 = 200;
	cout << s.obj << endl;
	cout << s.t2 << endl;
}

类模板成员函数类外实现

template<typename T>
class A {
public:
	A(T n); //声明构造
	void print(); //声明函数
	T number;
};
//类外实现构造
template<typename T>
A<T>::A(T n) {
	this->number = n;
}
//类外实现函数
template<typename T>
void A<T>::print() {
		cout << this->number;
}
int main() {
	A<int> a(1);
	a.print();
}

类模板分文件编写

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

解决方式1: 直接包含.cpp源文件

解决方式2 将声明和实现写到同一个文件中,并将后缀改为hpp,hpp是约定名称,不是强制

A.h

#pragma once
#include <iostream>
#include<string>
using namespace std; 
template<typename T>
class A {
public:
	A(T n);
	void print();
	T number;
};

A.cpp

#include "A.h"
template<typename T>
A<T>::A(T n) {
	this->number = n;
}
template<typename T>
void A<T>::print() {
	cout << this->number;
}

主文件

#include "A.h"
int main() {
	A<int> a(1);
	a.print();
}

运行报错,无法解析符号

方式1:把主文件中的#include "A.h" 改为#include "A.cpp"

方式2:将A.cpp的内容移动到A.h中,然后修改A.h为A.hpp

A.hpp

#pragma once
#include <iostream>
#include<string>
using namespace std; 
template<typename T>
class A {
public:
	A(T n);
	void print();
	T number;
};
template<typename T>
A<T>::A(T n) {
	this->number = n;
}
template<typename T>
void A<T>::print() {
	cout << this->number;
}

主函数

#include "A.hpp"
int main() {
	A<int> a(1);
	a.print();
}

类模板和友元

全局函数类外实现- 直接在类中声明友元即可

全局函数类外实现,需要提前让编译器知道全局函数的存在

类内实现:

#include <iostream>
#include<string>
using namespace std;
template <typename T>
class G {
    //这个就是全局函数,不是成员函数
    //还有一种是类内声明,类外实现,这个是直接实现
    //因为要指定那个方法作为当前类的友元,所以会在类中定义全局函数
	friend void print(G<T> g) {
		cout << g.name << endl;
	}
public:
	G(T t) {
		this->name = t;
	}
private:
	T name;
};
int main() {
	G<string> g("小明");
	print(g);
}

类外实现1:

template <typename T>
class G {
    //标明这个函数是一个函数模板
	template <typename T>
	friend void print(G<T>& g);
public:
	G(T t) {
		this->name = t;
	}
private:
	T name;
};
//实现
template <typename T>
void print(G<T>& g) {
	cout << g.name << endl;
};
int main() {
	G<string> g("小明");
	print(g);
}

类外实现2:

//因为print方法提前到了G类的定义前
//需要让编译器提前知道还有个G类
template <typename T>
class G;
//在G类上方定义函数模板,让编译器知道这个方法
template <typename T>
void print(G<T>& g) {
	cout << g.name << endl;
};
template <typename T>
class G {
	//=======注意! 需要加一个空模板参数列表
	friend void print<>(G<T>& g);
public:
	G(T t) {
		this->name = t;
	}
private:
	T name;
};
int main() {
	G<string> g("小明");
	print(g);
}

练习-使用模板类实现一个容器

MyArray.hpp

#pragma once
#include <iostream>
#include <string>
using namespace std;
template <typename T>
class MyArray {
public:
	MyArray(int _size) {
		//cout << "有参构造" << endl;
		this->size = _size;
		this->count = 0;
		this->p = new T[_size];
	}
    //重写拷贝构造,解决浅拷贝问题
	MyArray(const MyArray& arr) {
		//cout << "拷贝构造" << endl;
		this->count = arr.count;
		this->size = arr.size;
		//深拷贝
		this->p = new T[arr.size];
		for (int i = 0; i < size; i++) {
			this->p[i] = arr.p[i];
		}
	}
	//重载赋值符号,解决浅拷贝问题
	MyArray& operator=(const MyArray& arr) {
		//cout << "赋值重载" << endl;
		if (this->p != NULL) {
			delete[] this->p;
			p = NULL;
		}
		this->count = arr.count;
		this->size = arr.size;
		this->p = new T[arr.size];
		for (int i = 0; i < size; i++) {
			this->p[i] = arr.p[i];
		}
		return *this;
	}
	T& operator[](int index) {
		return this->p[index];
	}
	int getSize() {
		return this->size;
	}
	int getCount() {
		return this->count;
	}
	~MyArray() {
		//cout << "析构函数" << endl;
		if (this->p != NULL)
		{
			//删除数组
			delete[] this->p;
			p = NULL;
		}
	}
	void add(const T& t) {
		if (this->count == this->size) {
			cout << "已经满了" << endl;
			return;
		}
		this->p[count++] = t;
	}
	void remove() {
		if (this->count == 0) {
			return;
		}
		this->p[--count] = 0;
	}
private:
	T* p;
	//数组已占用个数
	int count;
	//数组大小
	int size;
};

主函数

1 测试基础数据类型

#include <iostream>
#include "MyArray.hpp" //引入自定义的头文件需要使用""而不是<>
#include<string>
using namespace std;
int main() {
	MyArray<int>* p = new MyArray<int>(10);
	cout << "数组大小:" << p->getSize() << endl;
	cout << "数组容量:" << p->getCount() << endl;
	for (int b = 0; b < 10; b++) {
		p->add(b);
	}
	cout << "数组容量:" << p->getCount() << endl;
	for (int i = 0; i < p->getCount(); i++) {
		//因为是指针,所有需要先解引用然后再[下标]取值
		cout << (*p)[i] << endl;
	}
	p->remove();
	p->remove();
	p->remove();
	MyArray<int> arr2 = *p;
	cout << "arr2===copy===:" <<  endl;
	for (int i = 0; i < arr2.getCount(); i++) {
		cout << arr2[i] << endl;
	}
	cout << "arr2===end:" << endl;
	for (int i = 0; i < p->getCount(); i++) {
		cout << (*p)[i] << endl;
	}
	delete p;
	p = NULL;
}

2 测试自定义数据类型

#include <iostream>
#include "MyArray.hpp"
#include<string>
using namespace std;
class A {
public:
	//无参构造,用于自定义容器中的深拷贝的创建对象
	// this->p = new T[_size];
	A() {}
	A(string _name, int _age) :name(_name), age(_age) {
	}
    string name;
	int age;
};
ostream& operator<<(ostream& o, A& a) {
	cout <<"年龄:" << a.age<<" 姓名:" << a.name;
	return o;
}
int main() {
	MyArray<A> arr(10);
	A a2 = { "A2",20 };
	A a3 = { "A3",30 };
	A a4 = { "A4",40 };
	arr.add(a1);
	arr.add(a2);
	arr.add(a3);
	arr.add(a4);
	for (int i = 0; i < arr.getCount(); i++) {
		cout << arr[i]<<"====地址:"<<&(arr[i]) << endl;
	}
	MyArray<A> arr2(arr);
	for (int i = 0; i < arr2.getCount(); i++) {
		cout << arr2[i] <<"====地址:" << &(arr[i])<< endl;
	}
	cout << "两个数组地址==arr:" << (int) & arr << "  arr2:" << (int)&arr2 << endl;
}

STL容器

• STL(Standard Template Library) 标准模板库

• STL从广义上分为容器,算法,迭代器

• 容器和算法直接通过迭代器进行无缝衔接

• STL几乎所有代码都使用了模板类或模板函数

STL六大组件

容器,算法,迭代器,仿函数,适配器(配接器),空间配置器

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

容器

常用数据结构:数组,链表,数,栈,队列,集合等

容器分为序列式容器和关联式容器

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

算法

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

质变算法:指运算过程中会改变区间内容的元素内容例如拷贝,替换,删除等

非质变算法:指运算过程中不会更改区间的元素内容,例如查找,计数,变量,寻找极值等

迭代器

提供一种方法,能够依序寻访某个容器中所包含的每个元素,而又无需暴露该容器的内部表示方式

每个容器都有自己的迭代器,迭代器非常类似于指针,初学阶段可以先理解为指针

迭代器种类:

输入迭代器:对数据的只读访问,支持++ == !=

输出迭代器:对数据的只写操作,支持++

前向迭代器 读写操作,并能向前推进迭代器 支持++ == !=

双向迭代器 读写,并能向前和向后操作 支持++ --

随机访问迭代器 读写操作 可以跳跃的访问任何数据 支持++ -- [n] -n < <= > >=

string容器

**string和char ***区别

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

string 构造函数

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

int main() {
	//默认构造
	string s;
	const char* str = "hello!";
	string s1(str);
	cout << "s1" << s1 << endl;
	//拷贝构造
	string s2(s1);
	cout << "s2" << s2 << endl;
	//4个h
	string s3(4, 'h');
	cout << "s3" << s3 << endl;
}

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

int main() {
	//默认构造
	string s;
	const char* str = "hello!";
	s = str;
	cout << "s=" << s << endl;
	string s1 = s;
	cout << "s1=" << s1 << endl;
	string s2;
	s2 = 'a';
	cout << "s2=" << s2 << endl;
	string s3;
	s3.assign("hellowwww");
	cout << "s3=" << s3 << endl;
	string s4;
	s4.assign("hellowwww",3);
	cout << "s4=" << s4 << endl;
	string s5;
	s5.assign(s4);
	cout << "s5=" << s5 << endl;
	string s6;
	s6.assign(6, 't');
	cout << "s6=" << s6 << endl;
}

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) 把c字符串前n个字符拼接到当前字符串结尾
• string& append(const string& s) 同operator+=(const string& str)
• string& append(const string& s,int pos,int n) 字符串s中从pos开始的n个字符拼接到字符串结尾

int main() {
	//默认构造
	string s = "hello!";
	s += " i ";
	s += 'a';
	string s1 = "m";
	s += s1;
	s.append(" j");
	s.append("a==", 1);
	s.append(s1);
	string s2 = "asme";
	s.append(s2,3,1);
	cout << s << endl;
	// hello! i am jame
}

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

find和rfind区别 find是从左往右,rfind是从右往左

int main() {
	string s = "2===2=";
	string s1 = "6";
	cout<<s.find(s1)<<endl; //s.find(s1,0) 省略
	cout << s.find("2") << endl; //s.find("2",0) 省略
	cout << s.find("234", 0, 1) << endl; //先把234拆开,从0开始,拆一个,获取到2,然后再查
	cout << s.find('2') << endl;//s.find('2',0)省略 
	cout << s.rfind(s1,6) << endl;//从下标6开始从右往左查 
	cout << s.rfind("2",6) << endl;//从下标6开始从右往左查 
	cout << s.rfind('2',6) << endl;//从下标6开始从右往左查 
	cout<<s.replace(0, 1, s1)<<endl;//从0开始1个字符替换为6
	cout<<s.replace(0, 1, "7")<<endl;//从0开始1个字符替换为6
}

string 比较

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

= 返回0 > 返回 1 < 返回-1

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

int main() {
	string s = "hello";
	string s1 = "hello";
	string s2 = "xello";
	cout << (s.compare(s1) == 0) << endl;
	cout << (s.compare(s2) == 0) << endl;
	cout << (s.compare("hello") == 0) << endl;
	cout << (s.compare("xello") == 0) << endl;
}

string 字符串存取

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

int main() {
	string s = "hello";
	s[0] = 'y';
	for (int i = 0; i < s.length(); i++) {
		cout << s[i];
	}
	s.at(0) = 'y';
	for (int i = 0; i < s.length(); i++) {
		cout << s.at(i);
	}
}

string 插入和删除

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

int main() {
	string s = "hello";
	string s1 = "wu";
	cout<<s.insert(1, "+")<<endl; //在下标1后面插入---
	cout << s.insert(1, s1) << endl;  //在下标1后面插入s1
	cout << s.insert(1, 4, 'x') << endl; //在下标1后面插入4个字符x
	cout << s.erase(1, 2) << endl;//从下标1后删除2个字符
}

string 子串

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

int main() {
	string s = "hello";
	cout << s.substr() << endl;
	cout << s.substr(0,1) << endl;
}

vector容器

vector数据结构和数组非常相似,也称之为单端数组,但是不同于数组是静态空间,vector是可以动态扩展的

动态扩展

并不是在原空间后继续开辟空间,而是找一段更大的空间,之后将原数据复制到新空间上,释放原空间

vector的迭代器是支持随机访问的

容器:vector

算法:for_each

迭代器:vector<int>::iterator

#include <iostream>
#include <vector>
using namespace std;  //vector需要导入
#include<algorithm>  //for_each 导入
void print(int val) {
	cout << val;
}
int main() {
	vector<int> v;
	v.push_back(10);
	v.push_back(20);
	v.push_back(30);
	v.push_back(40);
	//直接通过下标访问
	int& a = v[1];
	//通过迭代器访问1
	//vector<int>::iterator itBegin = v.begin();
	//vector<int>::iterator itEnd = v.end();
	//while (itBegin != itEnd) {
	//	cout << *itBegin << endl;
	//	itBegin++;
	//
	//}
	// 
	//通过迭代器访问2
	//for (vector<int>::iterator itBegin = v.begin(); itBegin != v.end(); itBegin++){
	//	cout << *itBegin << endl;
	//	
	//}
	//通过for_each 
	for_each(v.begin(), v.end(), print);
}

添加自定义的类型

class A {
public :
	string name;
};
int main() {
	vector<A> v;
	A a1 = { "a1" };
	A a2 = { "a2" };
	A a3 = { "a3" };
	v.push_back(a1);
	v.push_back(a2);
	v.push_back(a3);
	//通过迭代器访问2
	for (vector<A>::iterator itBegin = v.begin(); itBegin != v.end(); itBegin++){
		cout << (* itBegin).name << endl;
	}
}

存放类的指针

int main() {
	vector<A*> v;
	A a1 = { "a1" };
	A a2 = { "a2" };
	A a3 = { "a3" };
	v.push_back(&a1);
	v.push_back(&a2);
	v.push_back(&a3);
	//通过迭代器访问2
	for (vector<A*>::iterator itBegin = v.begin(); itBegin != v.end(); itBegin++){
		cout <<  (*itBegin)->name << endl;
		cout <<  (**itBegin).name << endl;//或者
	}
}

容器内存放容器

	vector<vector<A>> v;
	A a1 = { "a1" };
	A a2 = { "a2" };
	A a3 = { "a3" };
	vector<A> v1;
	v1.push_back(a1);
	v1.push_back(a2);
	v1.push_back(a3);
	vector<A> v2;
	v2.push_back(a1);
	v2.push_back(a3);
	v2.push_back(a2);
	vector<A> v3;
	v3.push_back(a1);
	v3.push_back(a3);
	v3.push_back(a2);
	v.push_back(v1);
	v.push_back(v2);
	v.push_back(v3);
	for (vector<vector<A>>::iterator itBegin = v.begin(); itBegin != v.end(); itBegin++){
		for (vector<A>::iterator itb = itBegin->begin(); itb != itBegin->end(); itb++) {
			cout << itb->name << endl;
		}
	}

vector 构造

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

int main() {
	vector<int> v;
	for (int i = 0; i < 10; i++){
		v.push_back(i);
	}
	//把v的begin到end的数据复制给v2
	vector<int> v2(v.begin(), v.end());
	//创建10个100放到v3
	vector<int> v3(10, 100);
	//拷贝构造
	vector<int> v4(v3);
	for (vector<int>::iterator it = v3.begin(); it != v3.end(); it++) {
		cout << *it << endl;
	}
}

vector 赋值操作

• vector& operator=(const vector &vec) 重载=
• assign(beg,end) 将v[begin(),end()]区间中的元素拷贝给本身
• assign(n,elem) 将n个elem拷贝赋值给本身

int main() {
	vector<int> v;
	for (int i = 0; i < 10; i++){
		v.push_back(i);
	}
	//直接=赋值
	vector<int> v2 = v;
	vector<int> v3;
	//把v的begin到end数据赋值给v3
	v3.assign(v.begin(), v.end());
	//放10个100到v4里面
	vector<int> v4;
	v4.assign(10, 100);
	for (vector<int>::iterator it = v4.begin(); it != v4.end(); it++) {
		cout << *it << endl;
	}
}

vector 容量和大小

• 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);
	}
	cout << v.empty() << endl;
	cout << v.capacity() << endl;
	cout << v.size() << endl;
	v.resize(9);
	v.resize(9,4);
}

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到en之间的元素
• clear() 删除容器中所有元素

int main() {
	vector<int> v;
	for (int i = 0; i < 10; i++){
		v.push_back(i);
	}
	v.push_back(1);
	v.pop_back();
	v.insert(v.begin(), 1);
	v.insert(v.begin(), 1, 2);
	v.erase(v.begin());
	v.erase(v.begin(), v.end());
	v.clear();
}

vector 数据存取

• at(int index) 返回索引指向的数据
• operator[] 返回索引指向的数据
• front() 返回容器中第一个元素
• back() 返回最后一个元素

int main() {
	vector<int> v;
	for (int i = 0; i < 10; i++) {
		v.push_back(i);
	}
	cout << v.at(2) << endl;
	cout << v[2] << endl;
	cout << v.front() << endl;
	cout << v.back() << endl;
}

vector 互换容器

• swap(vec) 与另一个vector容器互换元素

int main() {
	vector<int> v;
	for (int i = 0; i < 10; i++) {
		v.push_back(i);
	}
	vector<int> v2;
	for (int i = 0; i < 5; i++) {
		v2.push_back(i);
	}
	v.swap(v2);
	for (vector<int>::iterator t = v.begin(); t != v.end(); t++) {
		cout << *t;
	}
	cout << "\n";
	for (vector<int>::iterator t = v2.begin(); t != v2.end(); t++) {
		cout << *t ;
	}
}

还可以使用swap来重构vector的大小

例如有一个容量为1万的容器,之后删除到只剩10个元素,现在希望缩小它的容量

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

首先vector<int>(v)调用复制拷贝来初始化一个新的vector对象,会使用v的元素个数来初始化新vector的容量大小,之后交换两个容器的指针,因为是匿名对象,运行完销毁原来的容器占用空间

vector 预留空间

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

• reserve(int len) 给容器预留len个位置,预留位置不可访问,不初始化

int main() {
	vector<int> v;
//	v.reserve(100000);
	int number = 0;
	int* p = NULL;
	for (int i = 0; i < 100000; i++) {
		v.push_back(i);
		if (p != &(v[0])) {
			p = &(v[0]);
			number++;
		}
	}
    //查看扩容次数
	cout << number << endl;
}

deque容器

双端操作,可以对头端进行插入删除,也支持随机访问

deque与vector的区别

• vector对于头部的插入删除效率低,数据量越大,效率越低

• deque相对vector头部的插入删除速度要快

• vector访问元素时的速度会比deque快

• deque<T> deqT; 默认构造

• deque(beg,end) 构造函数将beg,end区间的元素拷贝给本身

• deque(n,elem) 构造函数将n个elem拷贝给本身

• deque(const deque &deq) 拷贝构造

#include <iostream>
#include <deque>
using namespace std;
void pirnt(deque<int> &d) {
	for (deque<int>::iterator i = d.begin(); i != d.end(); i++) {
		cout << *i << endl;
	}
}
int main() {
	//默认构造
	deque<int> d;
	for (int i = 0; i < 10; i++)
	{
		//尾部添加
		//d.push_back(i);
		//头添加
		d.push_front(i);
	}
	//pirnt(d);
	cout << "====" << endl;
	deque<int> d2(++d.begin(), d.end());
	//初始化10个100
	deque<int> d3(10, 100) ;
	//拷贝构造
	deque<int> d4(d3);
	pirnt(d4);
}

deque赋值操作

• deque&~operator=(const deque &deq) 重载等号
• assign(beg,end) 将beg,end区间数据拷贝赋值给本身
• assign(n,elem) 将n个elem赋值给本身

#include <deque>
using namespace std;
void pirnt(const deque<int> &d) {
	for (deque<int>::const_iterator i = d.begin(); i != d.end(); i++) {
		cout << *i << endl;
	}
}
int main() {
	//默认构造
	deque<int> d;
	for (int i = 0; i < 10; i++)
	{
		//尾部添加
		//d.push_back(i);
		//头添加
		d.push_front(i);
	}
	//pirnt(d);
	cout << "====" << endl;
	deque<int> d2;
	//重载=赋值
	d2 = d;
	deque<int> d3;
	d3.assign(d2.begin(), d2.end());
	deque<int> d4;
	d4.assign(10, 100);
	pirnt(d4);
}

deque大小操作

• deque.empty() 判断容器是否为空
• deque.size() 返回容器中的元素个数
• deque.resize(num) 重新指定容器长度num,若容器边长,则默认值填充新位置,若变短,删除末尾元素
• deque.resize(num,elem) 重新指定容器长度num,若容器边长,则elem填充新位置,若变短,删除末尾元素

deque没有容量概念

void pirnt(const deque<int> &d) {
	for (deque<int>::const_iterator i = d.begin(); i != d.end(); i++) {
		cout << *i << endl;
	}
}
int main() {
	//默认构造
	deque<int> d;
	for (int i = 0; i < 10; i++)
	{
		//尾部添加
		//d.push_back(i);
		//头添加
		d.push_front(i);
	}
	cout << d.empty() << endl;
	cout << d.size() << endl;
	d.resize(15, 6);
	pirnt(d);
	cout << "====" << endl;
	d.resize(5);
	pirnt(d);
}

deque插入删除

两端插入

• push_back(e) 尾部添加e
• push_front(e) 头部插入e
• pop_back() 删除最后的一个元素
• poh_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位置的数据,返回下一个数据的位置

int main() {
	//默认构造
	deque<int> d;
	//尾部添加
	d.push_back(1);
	//头添加
	d.push_front(2);
	//尾删
	d.pop_back();
	//头删
	d.pop_front();
	//根据位置插入返回一个迭代器
	deque<int>::iterator i = d.insert(d.begin(), 1);
	//插入两个10
	d.insert(d.begin(), 2, 10);
	//在头部添加了容器中所有的元素
	d.insert(d.begin(), d.begin(), d.end());
	//从第二个删到倒数第二个
	deque<int>::iterator i2=d.erase(++d.begin(), --d.end());
	//删除第一个
	d.erase(d.begin());
	//清空
	d.clear();
}

deque数据存取

• at(int ind) 返回ind位置的数据
• operator[] 返回索引位置的数据
• front() 返回第一个元素
• back() 返回容器最后一个元素

int main() {
	//默认构造
	deque<int> d;
	d.push_front(1);
	d.push_front(2);
	d.push_front(3);
	d.push_front(4);
	//重载[]符
	cout << d[2] << endl;
	//at获取
	cout << d.at(2) << endl;
	//取第一个
	cout << d.front() << endl;
	//取最后一个
	cout << d.back() << endl;
}

stack容器

栈容器,先进后出,只有顶端元素才能被使用,因此栈不允许有遍历行为

stack构造

• stack<T> stk 默认构造
• stack(const stack &stk); 拷贝构造

stack赋值

• stack& operator=(const stack &stk) 重载=

stack数据存取

• push(elem) 压入一个元素
• pop() 弹出一个元素
• top() 获取栈顶元素

stack大小

• empty() 返回是否为空
• size() 返回栈大小

#include <stack>
using namespace std;
int main() {
	stack<int> s;
	//压入一个元素
	s.push(1);
	s.push(2);
	//拷贝构造
	stack<int> s2(s);
	//重载=赋值
	stack<int> s3 = s2;
	//是否为空
	cout << s3.empty() << endl;
	//弹出一个元素
	s3.pop();
	//栈大小
	cout << s3.size() << endl;
	//获取栈顶元素
	cout << s3.top() << endl;
}

queue容器

队列,先进先出,只有头尾能被外界访问,因此没有遍历行为

queue构造

• queue<T> que; 默认构造
• queue(const queue & q) 拷贝构造

queue赋值操作

• queue& operator=(const queue &que) 重载=

queue数据存取

• push(e) 队尾添加一个元素
• pop() 队头移出第一个元素
• back() 返回最后一个元素
• front() 返回第一个元素

queue大小操作

• empty() 返回是否为空
• size() 返回大小

#include <queue>
using namespace std;
int main() {
	queue<int> q;
	queue<int> q2(q);
	queue<int> q3 = q2;
	q3.push(1);
	q3.push(2);
	q3.pop();
	cout << q3.front() << endl;
	cout << q3.back() << endl;
	cout << q3.size();
	cout << q3.empty();
}

list容器

通过双向链表实现,list的迭代器只支持前移和后移,属于双向迭代器

list构造

• list<T> list 默认构造
• list(beg,end) 构造函数将beg-end区间元素拷贝给本身
• list(n,elem) 使用n个elem初始化本身
• list(const list &list) 拷贝构造

#include <iostream>
#include <list>
using namespace std;
int main() {
	//默认构造
	list<int> l;
	//拷贝构造
	list<int> l2(l);
	//区间赋值
	list<int> l3(l2.begin(), l2.end());
	//使用4个5初始化
	list<int> l4(4, 5);
}

list赋值和交换

• assign(beg,end) 将beg-end区间数据拷贝给本身
• assign(n,m) 将n个m拷贝赋值给本身
• list& operatpr=(const list &list) 重载=
• swap(list) 交换

#include <iostream>
#include <list>
using namespace std;
int main() {
	//默认构造
	list<int> l;
	l.assign(6, 1);
	list<int> l2;
	l2.assign(l.begin(), l.end());
	//重载=
	list<int> l3 = l2;
	list<int> l4;
	//交换
	l4.swap(l3);
	for (list<int>::iterator it = l4.begin(); it != l4.end(); it++) {
		cout << *it << endl;
	}
}

list大小操作

• size() 返回容器中元素个数
• empty() 返回是否为空
• resize(n) 重新指定长度为n,如果边长,则默认值填充新位置,变短则超出长度的元素被删除
• resize(n,e)重新指定长度为n,如果边长,则e填充新位置,变短则超出长度的元素被删除

int main() {
	//默认构造
	list<int> l;
	l.assign(6, 1);
	l.resize(10);
	l.resize(15,7);
	for  (auto a : l)
	{
		cout << a ;
	}
	cout << l.size() << endl;
	cout << l.empty() << endl;
}

list插入删除

• push_back(e) 尾部加入一个元素
• pop_back() 删除容器中最后一个元素
• push_front(e) 头部插入一个元素
• 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值匹配的元素

int main() {
	//默认构造
	list<int> l;
	//尾部添加
	l.push_back(1);
	l.push_back(2);
	l.push_back(3);
	//删除尾部
	l.pop_back();
	//删除头部
	l.pop_front();
	list<int> l2;
	l2.insert(l2.begin(), 2);
	l2.insert(l2.begin(), 2, 1);
	l2.insert(l2.begin(), l.begin(), l.end());
	l2.clear();
	l2.erase(++l2.begin(), --l2.end());
	l2.erase(l2.begin());
	l2.remove(2);
}

list数据获取

• front() 返回第一个元素
• back() 返回最后一个元素

int main() {
	//默认构造
	list<int> l;
	//尾部添加
	l.push_back(1);
	l.push_back(2);
	l.push_back(3);
	cout<<l.back();
	cout << l.front();
}

list反转和排序

因为list不支持随机访问,所以不能用自带的sort排序

• revers() 反转链表
• sort() 链表排序 默认从小到大

bool a(int a,int b) {
	return a > b;
}
int main() {
	//默认构造
	list<int> l;
	//尾部添加
	l.push_back(1);
	l.push_back(4);
	l.push_back(3);
	l.reverse();
	//如果想自定义排序规则,传入方法a
	l.sort(a);
	cout<<l.back();
	cout << l.front();
}

自定义数据类型排序

#include <iostream>
#include <list>
#include <string>
using namespace std;
class User {
public:
	User() {
	}
	User(int _age, int _money, string _name):age(_age), money(_money), name(_name) {
	}
	int age;
	int money;
	string  name;
};
bool a(User &a, User &b) {
	if (a.age >= b.age) {
		return a.money >= b.money;
	}
	return false;
}
int main() {
	User u1 = { 18,600,"小明" };
	User u2 = { 30,300,"小王" };
	User u3 = { 20,400,"小周" };
	list<User> l;
	l.push_back(u1);
	l.push_back(u2);
	l.push_back(u3);
	l.sort(a);
	for (list<User>::iterator it = l.begin(); it != l.end(); it++) {
		cout << it->age << "=" << it->money << "=" << it->name << endl;
	}
}

set/multiset容器

所有元素都会在插入时自动被排序.set/multiset属于关联式容器,底层使用二叉树实现

set和multiset区别:

• set不允许有重复的元素,插入会返回插入结果和插入位置的迭代器
• multiset允许存在重复的元素,返回插入只有插入位置的迭代器

set的构造和赋值

构造:

• set<T> st 默认构造
• set(const set& st) 拷贝构造

赋值:

• set& operator=(const set& set) 重载=

#include <iostream>
#include <set>
using namespace std;
int main() {
	set<int> s;
	s.insert(1);
	set<int> s2(s);
	set<int> s3 = s2;
	for (set<int>::iterator it = s3.begin(); it != s3.end(); it++) {
		cout << *it << endl;
	}
}

set容器大小和交换

• size() 返回元素个数
• empty() 返回是否为空
• swap(st) 交换两个集合容器

#include <iostream>
#include <set>
using namespace std;
int main() {
	set<int> s;
	s.insert(1);
	s.insert(1);
	cout << s.empty() << endl;
	cout << s.size() << endl;
	set<int> s2;
	s2.swap(s);
	cout << s2.size() << endl;
}

set的插入删除

• insert(elem) 容器插入元素
• clear() 清空所有元素
• erase(pos) 删除pos迭代器所指向的元素,返回下一个元素的迭代器
• erase(beg,end) 删除区间beg-end的所有元素,返回下一个元素的迭代器
• erase(elem) 删除容器中值为elem的元素

#include <iostream>
#include <set>
using namespace std;
int main() {
	set<int> s;
	s.insert(1);
	s.clear();
	s.insert(2);
	s.insert(3);
	s.insert(4);
	s.insert(5);
	set<int>::iterator it1 = s.erase(s.begin());
	set<int>::iterator it2 = s.erase(s.begin(), --s.end());
	int a = s.erase(5);
}

set容器查找和统计

• find(key) 查找元素是否存在,返回元素的迭代器,如果不存在返回set.end()
• count(key) 统计key的元素个数 在set中作用不大,因为不可重复,要么0要么1

#include <iostream>
#include <set>
using namespace std;
int main() {
	set<int> s;
	s.insert(1);
	s.insert(2);
	set<int>::iterator it=s.find(1);
	if (it != s.end()) {
		cout << "find!" << endl;
	}
	else {
		cout << "null" << endl;
	}
	cout << s.count(1) << endl;
}

两个set插入返回结果

#include <iostream>
#include <set>
using namespace std;
int main() {
	set<int> s;
	pair<set<int>::iterator, bool> p = s.insert(1);
	set<int>::iterator it = p.first;
	cout << p.second << endl; 
	multiset<int> ms;
	set<int>::iterator it2= ms.insert(1);
}

pair对组创建

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

• pair<type,type p (v1,v2)
• pair<type,type> p=make_pair(v1,v2)

#include <iostream>
#include <set>
using namespace std;
int main() {
	pair<string, int> p("老王", 50);
	cout << p.first << endl; //输出第一个
	cout << p.second << endl;//输出第二个
	pair<string, int> p2 = make_pair("小明", 15);
	cout << p2.first << endl;
	cout << p2.second << endl;
}

set容器排序

利用仿函数,修改排序规则

#include <iostream>
#include <set>
using namespace std;
class MyCompare {
public:
    //这里需要加const作用不知道,以后学了在回来解释
	bool operator() (int v1,int v2)const {
		return v1 > v2;
	}
};
int main() {
	set<int,MyCompare> s;
	s.insert(4);
	s.insert(1);
	s.insert(2);
	s.insert(3);
	for (set<int>::iterator it = s.begin(); it != s.end(); it++) {
		cout << *it << endl;
	}
}

自定义类型的排序

对于自定义的数据类型,必须指定排序规则才能插入

#include <iostream>
#include <set>
using namespace std;
class People {
public:
	People(int _age) :age(_age) {
	}
	int age;
};
class MyCompare {
public:
    //	bool operator() (const People& v1,const  People& v2)const 
    //只加& 就会报错 必须加const修饰
	bool operator() (People v1, People v2)const {
		return v1.age > v2.age;
	}
};
int main() {
	set<People,MyCompare> s;
	s.insert(People(1));
	s.insert(People(4));
	s.insert(People(6));
	s.insert(People(2));
	for (set<People>::iterator it = s.begin(); it != s.end(); it++) {
		cout << it->age << endl;
	}
}

map/multimap容器

• map的所有元素都是pair
• pair的第一个元素为key,起到索引作用,第二个元素的value
• 所有元素都会根据元素的键值自动排序
• map/multimap都属于关联式容器,底层是用二叉树实现
• 可以根据key快速找到value

二者区别: map不允许存在相同的key,mulitmap可以存在

map构造和赋值

• map<T1,T2> m 默认构造
• map(const map& m) 拷贝构造
• map& operator=(consst map& m) 重载=

#include <iostream>
#include <map>
using namespace std;
int main() {
	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));
	m.insert(pair<int, int>(4, 40));
	map<int, int> m1(m);
	map<int, int>m2 = m1;
	for (map<int, int>::iterator it = m2.begin(); it != m2.end(); it++) {
		cout << it->first << "===" << it->second << endl;
	}
}

map大小和交换

• size() 返回元素个数
• empty() 返回是否为空
• swap(m) 交换两个map的元素

int main() {
	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));
	m.insert(pair<int, int>(4, 40));
	map<int, int> m2;
	m2.swap(m);
	cout << m2.size() << endl;
	cout << m2.empty() << endl;
}

map的插入和删除

• insert(elem) 容器插入元素
• clear() 清空元素
• erase(pos) 删除pos迭代器指向的元素,返回下一个元素的迭代器
• erase(beg,end) 删除区间beg-end的元素,返回下一个元素的迭代器
• erase(key) 根据key删除元素

int main() {
	map<int, int> m;
	m.insert(pair<int, int>(1, 10));
	m.clear();
	m.insert(pair<int, int>(2, 20));
	m.insert(make_pair(3, 30));
	m.insert(map<int,int>::value_type(4,40));
    //不要使用[]方式来获取,因为如果没有这个就会给你创建一个key为5,value为0的元素
	m[5] = 50;
	map<int, int>::iterator it = m.erase(m.begin());
	map<int, int>::iterator it2 = m.erase(m.begin(), --m.end());
	int deleted = m.erase(5);
	cout << m.size();
}

map查找和统计

• find(key) 查找key是否存在,返回元素的迭代器,不存在返回set.end()
• count(key) 统计key的个数,map中不是0就是1,在multimap中有用

int main() {
	map<int, int> m;
	m.insert(pair<int, int>(1, 10));
	m.insert(make_pair(2, 20));
	map<int,int>::iterator it=m.find(1);
	cout << it->first<<"====" << it->second << endl;
	cout << m.count(1) << endl;
}

int main() {
	multimap<int, int> m;
	m.insert(pair<int, int>(1, 10));
	m.insert(make_pair(1, 20));
	multimap<int,int>::iterator it=m.find(1);
	cout << it->first<<"====" << it->second << endl;
	it++;
	cout << it->first<<"====" << it->second << endl;
	cout << m.count(1) << endl;
}

map排序

利用仿函数,改变排序规则 两个参数是key,根据key排

class MyR {
public :
	bool operator()( int p1,  int p2) const  {
		return p1>p2;
	}
};
int main() {
	multimap<int, int, MyR> m;
	m.insert(pair<int, int>(1, 10));
	m.insert(make_pair(2, 20));
	m.insert(make_pair(4, 40));
	m.insert(make_pair(3, 30));
	for (map<int, int>::iterator it = m.begin(); it != m.end(); it++) {
		cout << it->first << "==" << it->second << endl;
	}
}

STL函数对象

函数对象

• 重载函数调用操作符的类,其对象称为函数对象
• 函数对象使用重载的()时,行为类似函数的调用,也叫仿函数
• 函数对象(仿函数)是一个类,不是一个函数

函数对象的使用

• 函数对象使用可以像普通函数一样,有参数和返回值
• 函数对象超出了普通函数的概念呢,函数对象可以有自己的状态
• 函数对象可以作为参数

class MyR {
public :
	bool v() {
		this->count++;
		return false;
	}
	bool operator()( int p1,  int p2){
		this->count++;
		cout << "operator" << endl;
		return p1<p2;
	}
	int count = 0;
};
int main() {
	MyR mr;
	mr(1, 2);
	mr(1, 2);
	mr(1, 2);
	cout << mr.count << endl;
}

class MyR {
public :
	bool v() {
		this->count++;
		return false;
	}
	bool operator()( int p1,  int p2){
		this->count++;
		cout << "operator" << endl;
		return p1<p2;
	}
	int count = 0;
};
void print(MyR & m,int a,int b) {
	m(a, b);
}
int main() {
	MyR mr;
	print(mr, 1, 2);
}

谓词

返回bool类型的仿函数称为谓词

如果operator接收一个参数,叫一元谓词,两个就叫二元谓词

class MyR {
public :
	bool operator()( int a){
		return a>0;
	}
};
int main() {
	vector<int> v;
	v.push_back(-1);
	v.push_back(1);
	v.push_back(3);
	v.push_back(-2);
	v.push_back(2);
	for (vector<int>::iterator it = v.begin(); it != v.end(); it++) {
		vector<int>::iterator it2 = find_if(it, v.end(), MyR());
		it = it2;
		cout << *it2 << endl;
	}
} 

class MyR {
public :
	bool operator()( int a,int b){
		return a<b;
	}
};
int main() {
	vector<int> v;
	v.push_back(-1);
	v.push_back(1);
	v.push_back(3);
	v.push_back(-2);
	v.push_back(2);
	sort(v.begin(), v.end(), MyR());
	for (vector<int>::iterator it = v.begin(); it != v.end(); it++) {
		cout << *it << endl;
	}
}

内建函数对象

分类:

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

这些仿函数产生的对象,用法和普通函数完全相同

使用内建函数对象,需要引入头文件#include <functional>

算术仿函数

其中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 <iostream>
#include <functional>
using namespace std;
int main() {
	negate<int> n;
	cout << n(2) << endl;
	minus<int> m;
	cout << m(10, 4) << endl;
}

关系仿函数

• 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 <iostream>
#include <functional>
using namespace std;
int main() {
	less<int> l;
	cout << l(10, 20) << endl;
	equal_to<int> e;
	cout << e(10, 20) << endl;
}

#include <iostream>
#include <functional>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
	vector<int> v;
	v.push_back(1);
	v.push_back(2);
	v.push_back(3);
	v.push_back(4);
	sort(v.begin(), v.end(), greater_equal<int>());
	for (vector<int>::iterator i = v.begin(); i != v.end(); i++) {
		cout << *i << endl;
	}
}

逻辑仿函数

• template<class T> bool logical_and 与
• template<class T> bool logical_or 或
• template<class T> bool logical_not 非'

移动数据同时取反

#include <iostream>
#include <functional>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
	vector<bool> v;
	v.push_back(1);
	v.push_back(0);
	v.push_back(1);
	v.push_back(0);
	vector<int> v2;
    //需要提前开辟空间
	v2.resize(v.size());
	transform(v.begin(), v.end(), v2.begin(), logical_not<bool>());
	for (vector<int>::iterator it = v2.begin(); it != v2.end(); it++) {
		cout << *it << endl;
	}
}

STL常用算法

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

遍历

for_each

for_each(iterator beg,iterator end,_func)

beg 开始迭代器,

end 结束迭代器,

func函数或函数对象

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
//普通函数
void print(bool a) {
	cout << a << endl;
}
//仿函数
class print2 {
public:
	void operator()(int a) {
		cout << a << endl;
	}
};
int main() {
	vector<bool> v;
	v.push_back(1);
	v.push_back(0);
	v.push_back(1);
	v.push_back(0);
	for_each(v.begin(), v.end(), print);
	for_each(v.begin(), v.end(), print2());
}

transform

将容器中元素转移到另一个容器

转移的容器需要提前开辟空间

transform(iterator beg, iterator end, iterator beg2, _func)

beg 原始容器开始迭代器

end 原始容器结束迭代器,

beg2 目标容器开始迭代器

func函数或函数对象

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
//普通函数
bool tran(bool a) {
	return !a;
}
//普通函数
bool print(bool a) {
	cout << a << endl;
	return a;
}
int main() {
	vector<bool> v;
	v.push_back(1);
	v.push_back(0);
	v.push_back(1);
	v.push_back(0);
	vector<bool> v2;
	v2.resize(v.size());
	transform(v.begin(),v.end(),v2.begin(), tran);
	for_each(v2.begin(), v2.end(), print);
}

查找

find

查找指定元素,找到返回对应位置的迭代器,否则返回end()

find(iterator beg,iterator end,value)

beg 开始迭代器

end 结束迭代器

value 元素

基础数据类型

int main() {
	vector<bool> v;
	v.push_back(1);
	v.push_back(0);
	v.push_back(1);
	v.push_back(0);
	vector<bool>::iterator it = find(v.begin(), v.end(), 0);
	while (it != v.end())
	{
		cout << *it << endl;
		it = find(++it, v.end(), 0);
	}
}

自定义数据类型

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
class A {
public:
	A(int _a):a(_a) {
	}
	int a;
	bool operator==(const A& a) {
		return this->a == a.a;
	}
};
/*
* 底层是调用==来判断,我们需要重载==
    for (; _First != _Last; ++_First) {
        if (*_First == _Val) {
            break;
        }
    }
*/
int main() {
	vector<A> v;
	A a(1);
	v.psh_back(a);
	v.push_back(A(4));
	v.push_back(A(2));
	v.push_back(A(3));
	vector<A>::iterator it = find(v.begin(), v.end(),a);
	while (it != v.end())
	{
		cout << it->a << endl;
		it = find(++it, v.end(), 0);
	}
}

find_if

条件查找,找到返回指向元素位置的迭代器,否则返回end()

find_if(iterator beg, iterator end, _Pred)

beg 开始迭代器

end 结束迭代器

_Pred 函数或谓词

基础数据类型

bool myFind(int a) {
	return a == 3;
}
int main() {
	vector<int> v;
	v.push_back(1);
	v.push_back(2);
	v.push_back(3);
	v.push_back(4);
	v.push_back(5);
	vector<int>::iterator it = find_if(v.begin(), v.end(), myFind);
	while (it != v.end()){
		cout << *it << endl;
		it = find(++it, v.end(), 0);
	}
}

自定义数据类型

#include <iostream>
#include <string>
#include <vector>
using namespace std;
class User {
public:
	User(int _age) :age(_age) {
	}
	int age;
};
class MyG {
public:
	bool operator()(const User& u) {
		return u.age == 100;
	}
};
int main() {
	vector<User> v;
	v.push_back(User(100));
	v.push_back(User(120));
	v.push_back(User(100));
	vector<User>::iterator it = find_if(v.begin(), v.end(), MyG());
	while (it != v.end()) {
		cout << it->age << endl;
		it = find_if(++it, v.end(), MyG());
	}
}

adjavent_find

查找相邻重复元素,返回相邻元素第一个迭代器

adjavent_find(iterator beg, iterator end)

beg 迭代器开始

end 迭代器结束

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
void test1() {
	vector<int> v;
	v.push_back(1);
	v.push_back(1);
	v.push_back(3);
	v.push_back(2);
	v.push_back(2);
	v.push_back(3);
	vector<int>::iterator it = adjacent_find(v.begin(), v.end());
	cout << *it << endl;
}

binary_search

查找指定元素是否存在,在无序列中不可用,返回bool类型

binary_search(iterator beg, iterator end, value)

beg 开始迭代器

end 结束迭代器

value 值

void test1() {
	vector<int> v;
	v.push_back(1);
	v.push_back(2);
	v.push_back(3);
	cout<<binary_search(v.begin(), v.end(), 4);
}

count

统计元素个数

count(iterator beg, iterator end, value)

beg 开始迭代器

end 结束迭代器

value 值

void test1() {
	vector<int> v;
	v.push_back(1);
	v.push_back(2);
	v.push_back(3);
	v.push_back(2);
	cout<<count(v.begin(),v.end(),2);
}

count_if

按条件统计元素个数

count_if(iterator beg,iterator end, _Pred)

_pred 谓词

class My {
public:
	bool operator()(const int a){
		return a >= 2;
	}
};
void test1() {
	vector<int> v;
	v.push_back(1);
	v.push_back(2);
	v.push_back(3);
	v.push_back(2);
	cout << count_if(v.begin(), v.end(), My());
}

排序

sort

sort(iterator beg, iterator end, _Pred)

void test1() {
	vector<int> v;
	v.push_back(1);
	v.push_back(2);
	v.push_back(3);
	v.push_back(2);
	sort(v.begin(), v.end());
	sort(v.begin(), v.end(), greater<int>());
}

random_shuffle

洗牌,指定范围内元素随机调整次序

random_shuffle(iterator beg, iterator end)

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <ctime>
void pirnt(int a) {
	cout << a << endl;
}
void test1() {
    //随机种子
    srand((unsigned int)time(NULL));
	vector<int> v;
	v.push_back(1);
	v.push_back(2);
	v.push_back(3);
	v.push_back(2);
	random_shuffle(v.begin(), v.end());
	for_each(v.begin(), v.end(), pirnt);
}

merge

合并两个容器元素到另一个容器中,注意,两个容器必须是有序的

merge(iterator beg1, iterator end1, iterator beg2, iterator beg2, iterator dest)

void test1() {
	vector<int> v;
	v.push_back(1);
	v.push_back(2);
	vector<int> v2;
	v2.push_back(2);
	v2.push_back(3);
	vector<int> v3;
	//先开辟空间
	v3.resize(v.size() + v2.size());
	//合并不会去重
	merge(v.begin(), v.end(), v2.begin(), v2.end(), v3.begin());
	for_each(v3.begin(), v3.end(), pirnt);
}

reverse

将容器内元素进行反转

reverse(iterator beg, iterator end)

void test1() {
	vector<int> v;
	v.push_back(1);
	v.push_back(2);
	v.push_back(3);
	v.push_back(4);
	reverse(v.begin(), v.end());
	for_each(v.begin(), v.end(), pirnt);
}

拷贝和替换

copy

容器指定范围元素拷贝到另一容器中

copy(iterator beg, iterator end, iterator dest)

void test1() {
	vector<int> v;
	v.push_back(1);
	v.push_back(2);
	v.push_back(3);
	v.push_back(4);
	vector<int> v2;
	v2.resize(v.size());
	copy(v.begin(), v.end(), v2.begin());
	for_each(v2.begin(), v2.end(), pirnt);
}

replace

将容器指定范围内的元素替换

replace(iterator beg, iterator end, oldValue, newValue)

void test1() {
	vector<int> v;
	v.push_back(1);
	v.push_back(2);
	v.push_back(3);
	v.push_back(4);
	replace(v.begin(), v.end(), 1, 6);
	for_each(v.begin(), v.end(), pirnt);
}

replae_if

在指定区间内判断如果符合条件则替换元素

replace_if(iterator beg, iterator end, _pred, newValue)

class My {
public:
	bool operator()(const int a) {
		return a >= 2;
	}
};
void pirnt(int a) {
	cout << a << endl;
}
void test1() {
	vector<int> v;
	v.push_back(1);
	v.push_back(2);
	v.push_back(3);
	v.push_back(4);
	replace_if(v.begin(), v.end(), My(), 6);
	for_each(v.begin(), v.end(), pirnt);
}

swap

互换两个容器中的元素,两个容器的类型需要相同

swap(container c1, container c2)

void test1() {
	vector<int> v;
	v.push_back(1);
	v.push_back(2);
	v.push_back(3);
	v.push_back(4);
	vector<int> v2;
	v2.push_back(444);
	swap(v, v2);
	for_each(v.begin(), v.end(), pirnt);
	cout << "===========" << endl;
	for_each(v2.begin(), v2.end(), pirnt);
}

算术生成

包含头文件#include <numeric>

accumulate

accumulate(iterator beg, iterator end, value)

value 起始值

计算区间容器元素总和

void test1() {
	vector<int> v;
	v.push_back(1);
	v.push_back(2);
	v.push_back(3);
	v.push_back(4);
	cout<<accumulate(v.begin(), v.end(),0);
}

fill

向容器内填充指定元素

fill(iterator beg,iterator end,value)

void test1() {
	vector<int> v;
	v.push_back(1);
	v.push_back(2);
	v.push_back(3);
	v.push_back(4);
	fill(v.begin(), v.end(),0);
	for_each(v.begin(), v.end(), pirnt);
}

集合算法

set_intersection

求两个集合的交集,源容器必须是有序序列

set_interaection(iterator beg1,iterator end1,iterator beg2,iterator end2,iterator dest)

void test1() {
	vector<int> v;
	v.push_back(1);
	v.push_back(2);
	vector<int> v1;
	v1.push_back(2);
	v1.push_back(3);
	vector<int> v2;
	//先初始化空间,任意一个集合的大小都行,因为交集不可能大于任意一个集合
	//使用min取最小的大小
	v2.resize(min(v.size(),v1.size()));
	vector<int>::iterator itEnd =set_intersection(v.begin(), v.end(), v1.begin(), v1.end(), v2.begin());
	for_each(v2.begin(), itEnd, pirnt);
}

set_union

取并集,源容器必须是有序序列

set_union(iterator beg1,iterator end1,iterator beg2,iterator end2,iterator dest)

void test1() {
	vector<int> v;
	v.push_back(1);
	v.push_back(2);
	vector<int> v1;
	v1.push_back(2);
	v1.push_back(3);
	vector<int> v2;
	//先初始化空间,最极端的情况就是两个容器中没有相同的元素
	v2.resize(v.size()+v1.size());
	vector<int>::iterator itEnd=set_union(v.begin(), v.end(), v1.begin(), v1.end(), v2.begin());
	for_each(v2.begin(), itEnd, pirnt);
}

set_difference

set_difference(iterator beg1,iterator end1,iterator beg2,iterator end2,iterator dest)

取差集,源容器必须是有序序列

void test1() {
	vector<int> v;
	v.push_back(1);
	v.push_back(2);
	vector<int> v1;
	v1.push_back(2);
	v1.push_back(3);
	vector<int> v2;
	//先初始化空间,差集不可能大于自己
	v2.resize(v.size());
	vector<int>::iterator itEnd=set_difference(v.begin(), v.end(), v1.begin(), v1.end(), v2.begin());
	for_each(v2.begin(), itEnd, pirnt);
}