C++ 模板.

STL初识

STL的诞生

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

STL基本概念

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

STL六大组件

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

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

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

容器: 置物之所也

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

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

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

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

算法: 问题之解法也

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

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

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

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

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

• 每个容器都有自己专属的迭代器
• 迭代器使用非常 类似于指针，初学阶段我们可以先理解迭代器为指针

迭代器种类：

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

容器算法迭代器初识

STL中最常用的容器为Vector，可以理解为数组，下面我们将学习如何向这个容器中插入数据、并遍历这个容器

vector存放内置数据类型

容器: vector
算法: for_each
迭代器: vector::iterator

#include <iostream>
#include <vector>
#include <algorithm>//标准算法头文件

using namespace std;

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

void test01() 
{
	//创建一个vector容器
	vector<int> v;

	//向容器中插入数据
	v.push_back(10);

	//通过迭代器访问容器中的数据
	vector<int>::iterator itBegin = v.begin(); //起始迭代器  指向容器的第一个元素 （类似指针）
	vector<int>::iterator itEnd = v.end();     //结束迭代器  指向容器的最后一个元素的下一个位置

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

	//使用STL提供标准遍历算法  头文件 algroithm
	for_each(v.begin(), v.end(), myPrint);
}

int main() {

	test01();

	system("pause");

	return 0;
}

STL — 常用容器

string容器

本质:

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

string 和 char 区别:*

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

特点:

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

1. string构造函数

• 构造函数原型:

#include <string> //使用容器都要包含头文件

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

总结:string的多种构造方式没有可比性，灵活使用即可。

2. string赋值操作

功能描述:

• 给string字符串进行赋值

赋值的函数原型:

#include <string> //包含头文件

string& operator=(const char* s);           //char*类型字符串赋值给当前的字符串
string& operator=(const string &s);         //把字符串s赋给当前的字符串
string& operator=(char c);                  //把 字符 赋值给当前的字符串

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

例如：

string str1;
str1 = "hello world";

string str2;
str2.assign("hello world");

总结: string的赋值方式很多, operator= 这种方式是比较实用的。

3. 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个字符连接到字符串结尾

总结:字符串拼接的重载版本很多，初学阶段记住几种即可。

4. 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第一次出现位置

//find从左往右查找，rfind从右往左查找

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

5. string字符串比较

功能描述:

• 字符串之间的比较

比较方式:

• 字符串比较是按字符的 ASCII 码进行对比
  • = 返回 0
  • > 返回 1
  • < 返回 -1

函数原型:

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

总结:字符串对比主要是用于比较两个字符串是否相等，判断谁大谁小的意义并不是很大。

6. string字符 存 (修改) 取 (读取)

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

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

总结: string字符串中单个字符 存 取 有两种方式，利用 [] 或 at 。

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

总结: 插和删除的起始下标都是从0开始

8. string子串

功能描述:

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

函数原型:

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

vector容器

vector基本概念

• 功能:
  • vector数据结构和数组非常相似,也称为 单端数组

vector与普通数组区别:

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

动态扩展:

• 并不是在原空间之后续接新空间，而是找更大的内存空间，然后将原数据拷贝新空间，释放原空间

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

1.vector 构造函数：

功能描述:

• 创建vector容器

函数原型:

#include <vector> //使用容器都要包含头文件

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

总结: vector的多种构造方式没有可比性，灵活使用即可。

2.vector 赋值操作：

功能描述:

• 给vector容器进行赋值

函数原型:

vector& operator=(const vector &vec);     //重载等号操作符
assign(beg, end);                         //将[beg, end)区间(前闭后开)中的数据拷贝赋值给本身。
assign(n, elem);                          //将n个elem拷贝赋值给本身。

总结: vector赋值方式比较简单，使用operator=，或者assign都可以

3.vector 容量和大小：

功能描述:

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

函数原型:

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

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

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

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

5.vector 数据存取：

功能描述:

• 对vector中的数据的存取操作

函数原型:

at(int idx);        //返回索引idx所指的数据
operator[];         //返回索引idx所指的数据

front();            //返回容器中第一个数据元素
back();             //返回容器中最后一个数据元素

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

6.vector 互换容器：

功能描述;

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

函数原型:

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

//巧用swap收缩内存
vector<int>(v).swap(v);  //vector<int>(v)  为通过 拷贝构造函数 创造 匿名对象
                         // .swap(v)  容器交换

实际用途:
swap可以使两个容器互换,可以达到实用的收缩内存效果

7.vector 预留空间：

功能描述:

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

函数原型：

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

deque容器

功能:

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

deque与vector区别:

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

deque内部工作原理:

• deque内部有个中控器，维护每段缓冲区中的内容，缓冲区中存放真实数据
• 中控器维护的是每个缓冲区的地址，使得使用deque时像—片连续的内存空间

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

1. deque构造函数：

功能描述:

• deque容器构造

函数原型: （和vector差不多）

#include <deque> //使用容器都要包含头文件

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

只读不可以修改时，使用 const_iterator

void printDeuque(const deque<int>&d)
{
	for(deque<int>::const_iterator it = d.begin(); it != d.end(); it++)
	{
		//*it = 100;容需中的数据不可以修改了
		cout << *it << " ";
	}
	cout << endl;
}

总结: deque容器和vector容器的构造方式几乎一致，灵活使用即可

2. deque赋值操作：

功能描述:

• 给deque容器进行赋值

函数原型:（和vector完全一样）

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

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

总结: deque赋值操作也与vector相同，需熟练掌握

3. deque大小操作：

功能描述:

• 对deque容器的大小进行操作

函数原型: (和 vector 很像)，没有容量概念，deque对容量没有限制

deque.empty();               //判断容器是否为空
deque.size();                //返回容器中元素的个数

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

总结:
deque没有容量的概念
判断是否为空 – empty
返回元素个数 — size
重新指定个数 — resize

4. 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(迭代器)位置的数据，返回下一个数据的位置。

例如：

deque<int>::iterator it = d1.begin(); //迭代器
it++;
d1.erase(it);

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

5. deque数据存取：

功能描述: (和 vector 一样)

• 对deque中的数据的存取操作

函数原型:

at(int idx);           //返回索引idx所指的数据
operator[];            //返回索引idx所指的数据

front();               //返回容器中第一个数据元素
back();                //返回容器中最后一个数据元素

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

6. deque排序：

功能描述:

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

算法:

#include <algorithm>                 //标准算法的头文件

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

使用：

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

总结: sort 算法非常实用，使用时包含头文件 algorithm 即可

stack容器

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

• 栈中 只有顶端的元素 才可以被外界使用，因此栈不允许有 遍历 行为
  • 栈中进入数据称为 — 入栈 push
  • 栈中弹出数据称为 — 出栈 pop

stack常用接口

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

构造函数:

#include <stack>              //使用容器都要包含头文件

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

赋值操作:

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

数据存取:

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

大小操作:

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

总结:
入栈 — bush
出栈 — pop
返回栈顶 — top
判断栈是否为空 — empty
返回栈大小 — size

queue容器

queue基本概念

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

• 队列容器允许从一端新增元素，从另一端移除元素
• 队列中只有 队头 和 队尾 才 可以被外界使用，因此队列 不允许有遍历 行为
• 队列中进数据称为 — 入队 push
• 队列中出数据称为—出队 pop

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

构造函数:

#include <queue>                    //使用容器都要包含头文件

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

赋值操作:

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

数据存取:

push(elem);                          //往队尾添加元素
pop();                               //从队头移除第一个元素

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

大小操作:

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

list容器

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

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

链表的组成: 链表由—系列 结点 组成

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

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

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

list的优点:

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

list的缺点:

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

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

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

1. list 构造函数

功能描述:

• 创建 list 容器

函数原型: (构造方式和其他几个STL常用容器基本一样，熟练掌握即可！)

#include <list>            //包含list头文件

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

2. list 赋值和交换

功能描述:

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

函数原型:

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

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

总结:list赋值和交换操作能够灵活运用即可

3. list 大小操作 (函数原型和其他所学的容器是一样的)

功能描述:

• 对 list 容器的大小进行操作

函数原型:

size();                 //返回容器中元素的个数
empty();                //判断容器是否为空

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

总结:
判断是否为空 — empty
返回元素个数 — size
重新指定个数 — resize

4. 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)区间的数据，无返回值。

erase(beg, end);                    //删除[beg,end)区间的数据，返回下一个数据的位置。
erase(pos);                         //删除pos(迭代器)位置的数据，返回下一个数据的位置。

remove(elem);                       //删除容器中 所有 与elem值匹配的元素。
clear();                            //移除容器的所有数据

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

5. list 数据存取

功能描述:

• 对list容器中数据进行存取

函数原型: (不支持随机访问！)

// L[0] 不可以用 [] 访问list容器中的元素
//L.at(0) 不可以用 at 方式访问list容器中的元素
//原因是list本质链表，不是用连续线性空间存储数据，迭代器也是不支持随机访问的

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

//验证迭代器是不支持随机访问的
list<int>::iterator it = L.begin();

it--;				//正确
it++;               //正确，支持双向

//it = it+1;          //错误，不支持随机访问

总结:
list容器中不可以通过 [] 或者 at 方式访问数据
返回第一个元素 — front
返回最后一个元素 — back

6. list 反转和排序

功能描述:

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

函数原型:

# include<algorithm>

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

使用：

bool myCompare(int v1, int v2)        //仿函数
{
	//降序 就让第一个数 > 第二个数
	return v1 > rv2;
}
//所有不支持随机访问迭代器的容器，不可以用标准算法
//不支持随机访问迭代器的容器，内部会提供对应一些算法

sort(L1.begin(), L1.end());              //错误
L.sort();                                //正确，调用成员函数，默认排序规则 从小到大， 升序
L.sort(myCompare);                       //降序

总结;
反转 — reverse
排序 — sort(成员函数)

• 对于自定义数据类型，必须要 指定排序规则 （仿函数），否则编译器不知道如何进行排序
• 高级排序只是在排序规则上再进行一次逻辑规则制定，并不复杂。

set/ multiset 容器

set基本概念

简介:

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

本质:

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

set和multiset区别:

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

1. set 构造和赋值

功能描述:

• 创建set容器以及赋值

构造:

#include<set>        			  //只需包含set头文件即可，multiset 在set 头文件内

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

赋值: (插入数据只有insert方式)

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

2. set 大小和变换

功能描述:

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

函数原型:

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

总结:
统计大小 — size
判断是哲为空 — empty
交换容器 — swap

3. set 插入和删除

功能描述:

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

函数原型：

insert(elem);		             //在容器中插入元素。
clear();      					 //清除所有元素

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

总结:
插入 — insert
删除 — erase
清空 — clear

4. set 查找和统计

功能描述:

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

函数原型:

find(key);          		     //查找key是否存在,若存在，返回该键的元素的迭代器;若不存在，返回迭代器set.end();
count(key);                      //统计key的元素个数, set要么是0 ，要么是1；multiset可能大于1

使用 迭代器 接收

set<int>::iterator pos = s.find(30);

总结:
查找 — find (返回的是迭代器)
统计 — count (对于set，结果为0或者1)

5. set 和multiset区别

学习目标:

• 掌握set和multiset的区别

区别:

• set不可以插入重复数据，而multiset可以
• set插入数据的同时会返回插入结果，表示插入是否成功，如果已有数据，则会返回失败
• multiset 不会检测数据，因此可以插入重复数据

set 返回对组的类型

set<int> s;
pair<set<int>::iterator, bool> ret = s.insert(10);

if (ret.second) {
	cout <<"第一次插入成功!”"<<endl;
}
else {
	cout <<"第—次插入失败!”<<endl;
}

总结:
如果不允许插入重复数据可以利用set
如果需要插入重复数据利用multiset

6. pair对组创建

功能描述:

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

两种创建方式: （用的时候不用包含头文件）

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

使用：

void test(
	//第一种方式
	pair<string, int>p("Tom", 20);
	cout << "姓名:" << p.first << "年龄:" << p.second << endl;

	//第二种方式
	pair<string, int>p2 = make_pair("Jerry", 30);
	cout << "姓名:" << p2.first << "年龄:" << p2.second << endl;
}

总结:
两种方式都可以创建对组，记住—种即可

7. set 容器排序

学习目标:

• set容器默认排序规则为从小到大，掌握如何改变排序规则

主要技术点:

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

使用：

//指定排序规则为从大到小

//set容器排序
class MyCompare{ //仿函数，就是一种类
public:
	bool operator()(int v1, int v2) const
	{
		return v1 > v2;
	}
};


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

总结:利用仿函数可以指定 set 容器的排序规则

map/ multimap 容器

map基本概念

简介:

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

本质:

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

优点:

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

map和multimap 区别:

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

只是key值有区别，value可以重复

1. map 构造和赋值

功能描述:

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

函数原型:
构造:

#include<map>        			 			 //包含头文件

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

赋值:

map& operator=(const map &mp);				//重载等号操作符

例如：

//map容器构造和赋值
void test01()
{
	//创建map容器
	map<int, int> m;                                 //键值对

	//第一种插入
	m.insert(pair<int，int>(1, 10));                 //使用对组pair赋值，插入的时候按key值自动排序
	//第二种插入(常用)
	m.insert(make_pair(2, 20));  
	//第三种
	m.insert(map<int, int>::value_type(3,30)) ;
	//第四种
	m[4] = 40;
	//[]不建议插入，用途可以利用key访问到value
	cout << m[4] << endl;
}

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

2. map 大小和交换

功能描述:

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

函数原型:(和 set 容器差不多！)

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

总结:
统计大小 — size
判断是否为空 — empty
交换容器 — swap

3. map 插入和删除

功能描述;

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

函数原型:

insert(elem);                             //在容器中插入元素,(见上面四种)。
clear();                                  //清除所有元素

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

总结: map插入方式很多记住其一即可
插入— insert
制除 — erase
清空— clear

4. map 查找和统计

功能描述:

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

函数原型:

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

总结:
查找 — find(返回的是迭代器)
统计 — count(对于map，结果为0或者1)

5. map 容器排序

学习目标:

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

主要技术点:

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

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

void test01()
{
	map<int, int, MyCompare>m;
	m.insert(make_pair(1, 10));
	m.insert(make_pair(2, 20));
	m.insert(make_pair(5, 50));
	m.insert(make_pair(3, 30));
	m.insert(make_pair(4, 40));

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

总结:
利用仿函数可以指定map容器的排序规则
对于自定义数据类型，map必须要指定排序规则,同set容器

注：仅供学习参考，如有不足，欢迎指正！