博客

1.1 STL诞生

目的：提升复用性，建立数据结构和算法的标准

1.2 STL基本概念

• Standard Template Libraary,标准模板库。

• STL广义上分为：容器（container）算法（algorithm）迭代器（iterator）。

• 容器和算法之间通过迭代器进行无缝连接。

• STL几乎所有的代码都采用了模板类或者模板函数。

1.3 STL六大组件

容器，算法，迭代器，仿函数，适配器（配接器），空间配置器

1. 容器：各种数据结构，如：vector、list、deque、set、map等，用来存放数据。

2. 算法：各种常用的算法，如sort、find、copy、for_each等。

3. 迭代器：扮演容器与算法之间的胶合剂。

4. 仿函数：行为类似函数，可作为算法的某种策略。

5. 适配器：一种用来修饰容器或仿函数或迭代器接口的东西。

6. 空间配置器：负责空间的配置与管理。

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

容器∶置物之所也

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

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

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

序列式容器∶强调值的排序，序列式容器中的每个元素均有固定的位置。

关联式容器∶二叉树结构，各元素之间没有严格的物理上的顺序关系

算法∶问题之解法也

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

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

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

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

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

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

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

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

迭代器种类：

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

2. vector容器

2.1 vector存放内置数据类型

容器：

vector

算法：

for_each

迭代器：

vector<int>::iterator

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
void myPrint(int val)
{
    cout<<val<<endl;
}
void test01(）
{
    vector<int> v;      //创建一个vector容器 ，数组
    
    v.push_back(10);    //向容器中插入数据
    v.push_back(20);
    v.push_back(30);
    v.push_back(40);
    //第一种遍历方式
    vector<int>::iterator itBegin = v.begin();  //起始迭代器 指向容器中的第一个元素
    vector<int>::iterator itEnd = v.end();      //结束迭代器
    while(itBegin!=itEnd)
    {
        cout<<*itBegin<<endl;
        itBegin++;
    }
    //第二种遍历方式
    for(vector<int>::iterator it= v.begin();it!=v.end();it++)
        cout<<*it<<endl;
    //第三种遍历方式
    for_each(v.begin(),v.end(),myPrint)
}

2.2 vector存放自定义数据类型

#include <iostream>
#include <vector>
#include <string.h>
#include <algorithm>
using namespace std;
class Person
{
    public:
    Person(string name,int age):m_Name(name),m_Age(age){}
    string m_Name;
    int m_Age;
}
void test01()
{
    vector<Person> v;   //创建一个vector容器
    
    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);
​
    for(vector<Person>::iterator it= v.begin();it!=v.end();it++)    //遍历容器
        cout<<"姓名"<<(*it).m_Name<<"年龄"<<it->m_Age<<endl;
}
void test02()
{
    vector<Person> v;   //创建一个vector容器
    
    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);
    for(vector<Person*>::iterator it= v.begin();it!=v.end();it++)   //遍历容器
        cout<<"姓名"<<(*it)->m_Name<<"年龄"<<(*it)->m_Age<<endl;
}

2.3 vector容器嵌套容器

#include <iostream>
#include <vector>
using namespace std;
void test01()
{
    vector<vector<int>> v;      
    //创建vector小容器
    vector<int> v1;             
    vector<int> v2; 
    vector<int> v3; 
    vector<int> v4; 
    //向小容器中添加数据
    for(int i=0;i<4;i++)
    {
        v1.push_back(i+1); 
        v2.push_back(i+2); 
        v3.push_back(i+3); 
        v4.push_back(i+4); 
    }
    //将小容器插入到大容器中
    v.push_back(v1);
    v.push_back(v2);
    v.push_back(v3);
    v.push_back(v4);
    //通过大容器，把所有的数据遍历一次
    for(vector<vector<int>>::iterator it=v.begin();it!=v.end();it++)
        for(vector<int>::iterator vit=(*it).begin();vit!=(*it).end();vit++)
            cout<<*vit<<"";
}

2.4 基本概念

vector与普通数组的区别在于：数组是静态空间，vector可以动态扩展。

2.5 vector构造函数

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

2.6 vector赋值操作

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

2.7 vector容量和大小

容量>=大小

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

2.8 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 pos，const_iterator end);   //删除迭代器从start到end之间的元素
clear(); =erase(begin，end);                     //删除容器中的所有元素

2.9 vector数据存取

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

2.10 vector互换容器

1.容器互换 
v1.swap(v2); 
2.巧用swap可以收缩内存空间
vector<int>(v).swap(v);
匿名对象执行完当前行会被自动回收

2.11 vector预留空间

v.reserve(int len);

3. string容器

3.1 基本概念

本质：char*是一个指针

string是c++风格的字符串，本质的一个类，类内部分装了char,管理这个字符串是一个char型容器

特点：

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

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

3.2 string构造函数

string(); //创建一个空是字符串 例如string str；
string(const char* s);  //使用字符串s初始化
string(const string& str);  //使用一个string对象初始化另一个string对象
string(int n,char c);   //使n个字符c初始化
​
示例：灵活使用
#include <iostream>
#include <string.h>
using namespace std;
void test01()
{
    string s1; //默认构造
    
    const char* str="hello world";
    string s2(str);
​
    string s3(s2);
    
    string s4(10,'a');
}

3.3 string的赋值操作

一般来说=赋值实用

#include <iostream>
#include <string.h>
using namespace std;
​
string& operator=(const char* s);       //char*类型的字符串赋值给当前字符串
eg:str1="hello world";
string& operator=(const string &s);     //把字符串s赋值给当前字符串
eg:str2=str1;
string& operator=(char c);              //把字符s赋值给当前字符串
eg:str3='a';
string& assign(const char* s);          //char*类型的字符串赋值给当前字符串
eg:str4.assign("hello c++");
string& assign(const char* s,int n);    //char*类型的字符串的前n个字符赋值给当前字符串
eg:str5.assign("hello c++",5);
string& assign(const string &s);        //把字符串s赋值给当前字符串
eg:str6.assign(str5);
string& assign(int n, char c);          //把n个字符s赋值给当前字符串
eg:str7.assign(5,'a');

3.4 string字符串拼接

#include <iostream>
#include <string.h>
using namespace std;
​
string& operator+=(const char* str);        //重载+=操作符
eg:str1+="hello world";
string& operator+=(const char c);           //重载+=操作符
eg:str2+='c';
string& operator+=(const string& str);      //重载+=操作符
eg:str3+=str2;
string& append(const char* s);              //char*类型的字符串拼接到当前字符串
eg:str4.append("hello c++");
string& append(const char* s,int n);        //char*类型的字符串的前n个字符拼接到当前字符串
eg:str5.append("hello c++",5);
string& append(const string &s);            //把字符串s拼接到当前字符串
eg:str6.append(str5);
string& append(const string &s,int pos,int n);  //字符s中从pos开始的n个字符拼接到当前字符串
eg:str7.append(str5,2,3);                       //0开始

3.5 string查找和替换

• 查找：查找指定字符串是否存在

• 替换：在指定位置替换字符串

//find没有查找到的情况下返回-1
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第一次出现的位置
​
//rfind 从右往左查找，find从左往右
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.6 string字符串比较

按照ASCII码进行对比

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

int compare(const string &s)const;  //与字符串s比较
int compare(const char *s)const;    //与字符串s比较
eg:str1.compare(str2);

3.7 string的字符存取

string中单个字符存取

char& operator[](int n);    //通过[]方式读取
for(int i=0;i<str.size();i++)
    cout<<str[i]<<"";
char& at(int n);            //通过at方法读取
for(int i=0;i<str.size();i++)
    cout<<str.at(i)<<"";

3.8 string子串

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

4.deque容器

4.1 deque容器的基本概念

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

deque与vector区别

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

• deque相对而言，对于头部的插入删除速度比vector快

• vector访问元素时的速度会比deque快，这和两者的内部实现有关

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

deque<T> deqT;                  //默认构造函数
deque(d.begin(),d.end());       //将[beg,end]区间中的元素拷贝给本身
eg:deque<int> d2(d1.begin(),d1.end());
deque(n,elem);                  //构造函数将n个elem拷贝给本身
eg:deque<int> d3(10,100);
deque(const deque &vec);        //拷贝构造函数
eg:deque<int> d4(d3);
​
void printDeque(const deque<int>& d)
    for(deque<int>::const_iterator it=d.begin();it!=d.end();it++)
        cout<<*it<<" ";

4.2 deque容器赋值

deque& operator=(const deque &deq);     //重载等号操作符
assign(beg,end);                        //将[beg,end]区间中的数据拷贝赋值给本身
eg:d2.assign(d1.begin(),d1.end());      //前闭后开
assign(n,elem);                         //将n个elem拷贝赋值给本身

4.3 deque大小操作

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

4.4 deque插入和删除

两端插入操作：
push_back(ele);                             //尾部插入元素ele
push_front(ele);                            //头部插入元素ele
pop_back();                                 //删除最后一个元素
pop_front();                                //删除第一个元素
指定位置操作：
insert(const_iterator pos, elem);           //迭代器指向位置POS插入元素elem
insert(const_iterator pos,int n, elem);     //迭代器指向位置POS插入n个元素elem
insert(const_iterator pos,beg,end); //迭代器指向位置POS插入[beg,end]区间数据，无返回值
eg:d.insert(d.begin,d2.begin(),d2.end());
erase(const_iterator pos);                       //删除迭代器指向的元素
erase(const_iterator start，const_iterator end); //删除迭代器从start到end之间的元素
clear();                                         //清空容器中的所有元素

4.5 deque数据存取

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

4.6 deque排序

#include <deque>
#include <algorithm>
//排序 默认排序规则 从小到大 升序
//对于支持随机访问的迭代器的容器，都可以利用sort算法直接对其进行排序，vector亦可
sort(iterator beg,iterator end);        //对beg和end区间内元素进行排序
eg:sort(d.begin(),d.end());

5. stack容器

5.1 stack基本概念

概念：stack是一种先进后出的数据结构，它只有一个出口

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

可以返回元素的个数，可以判断容器是否为空。

5.2 stack常用接口

6.queue容器

6.1 queue基本概念

概念：Queue是一种先进先出的数据结构，它有两个出口

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

6.2 queue常用接口

7.list容器

7.1 list基本概念

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

• 链表由一系列结点组成，一个是存储数据元素的数据域，另一个是存储下一个结点地址的指针域

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

• 优点：可以对任意位置进行快速插入或删除操作，只需要修改指针，不需移动大量元素

  采用动态存储分配，不会造成内存浪费和溢出

• 缺点：容器遍历速度没有数组快，占用空间较大

重点：list的插入和删除操作都不会造成原有的list迭代器失效，但在vector中不成立

7.2 list构造函数

list<T> lst;                    //采用模板实现类实现，默认构造函数
list(lst.begin(),lst.end());    //将lst[begin(),end()]区间中的元素拷贝给本身
eg:list<int> lst3(lst1.begin(),lst1.end());
list(n,elem);                   //构造函数将n个elem拷贝给本身
eg:list<int> lst3(10,100);
list(const list &lst);          //拷贝构造函数
eg:list<int> lst4(lst3);

7.3 list赋值和交换

list& operator=(const list &lst);               //重载等号操作符
assign(beg,end);                                //将[beg,end]区间中的数据拷贝赋值给本身
eg:lst2.assign(lst1.begin(),lst1.end());        //前闭后开
assign(n,elem); 
swap(lst);                                      //将lst与本身的元素互换

7.4 list大小操作

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

7.5 list插入和删除

两端插入操作：
push_back(ele);                             //尾部插入元素ele
push_front(ele);                            //头部插入元素ele
pop_back();                                 //删除最后一个元素
pop_front();                                //删除第一个元素
指定位置操作：
insert(const_iterator pos, elem);           //迭代器指向位置POS插入元素elem
insert(const_iterator pos,int n, elem);     //迭代器指向位置POS插入n个元素elem
insert(const_iterator pos,beg,end); //迭代器指向位置POS插入[beg,end]区间数据，无返回值
eg:lst2.insert(lst2.begin,lst1.begin(),lst1.end());
erase(const_iterator pos);                  //删除迭代器指向的数据
erase(const_iterator begin，const_iterator end); //删除迭代器从start到end之间的数据
clear();                                    //清空容器中的所有数据
remove(elem);                               //删除容器中所有与elem值匹配的元素

7.6 list数据存取

front();    //返回第一个元素
back();     //返回最后一个元素
//注意：
//L1[0] 不可以用访问list容器中的元素
//L1.at(0) 不可以用at方式访问list容器中的元素
//原因是list本质链表，不是用连续线性空间存取数据，迭代器也不是随机访问的
//验证迭代器是不支持随机访问
list<int>::iterator it = L1.begin();
it++，it--;
//it = it + 1    //不支持随机访问

7.7 list反转和排序

reverse();          //反转链表
sort();             //链表排序
//所有不支持随机访问迭代器的容器，不可以用标准算法，内部会提供对应一些算法
eg:lst1.sort();     //默认排序规则，从小到大 升序
仿函数：//变换排序规则
bool myCompare(int v1,int v2)
{
    //降序  就让第一个数>第二个数
    return v1>v2;
}
lst1.sort(myCompare);   

总结：

• 对于自定义数据类型，必须要指定排序顺序，否则编译器不知道如何进行排序。

• 高级排序只是在排序规则上再进行一次逻辑规则制定，并不复杂。

8. set/multiset容器

8.1 set基本概念

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

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

set和multiset区别：

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

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

8.2 set构造和赋值

构造：

set<T> st;                      //默认构造函数
set(const set &st);             //拷贝构造函数
赋值：
set& operator=(const set &st);  //重载等号操作

8.3 set大小和交换

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

8.4 set插入和删除

insert(elem);                           //在容器中插入元素elem
erase(const_iterator pos);              //删除迭代器指向的数据，返回下一个元素的迭代器
erase(const_iterator begin，const_iterator end); //删除区间begin到end之间的元素，返回下一个元素的迭代器
erase(elem);                            //删除迭代器中值为elem的元素
clear();                                //清空容器中的所有元素

8.5 set查找和统计

find(key);       //查找key是否存在，若存在，返回该键的元素的迭代器；若不存在，返回set.end();
eg:set<T>::iterator pos = s.find(key);  //重点：返回的是迭代器！！！
if(pos!=s.end())
    cout<<"找到元素："<<*pos<<endl;
else
    cout<<"未找到元素"<<endl;
count(key);                             //统计key的元素个数，对于set，结果为0或者1
eg:int num = s.count(key);
cout<<"num="<<num<<endl;

8.6 set和multiset区别：

• set插入数据的同时会返回插入结果，表示插入是否成功

• multiset不会检测数据，因此可以插入重复数据

pair<set<T>::iterator,bool> ret=s.insert(key);
if(ret.second)
    cout<<"插入成功"<<endl;
else
    cout<<"插入失败"<<endl;

8.7 pair对组创建

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

//两种创建方式
pair<type,type> p (value1,value2);
pair<type,type> p = make_pair (value1,value2);
p.first   p.second   //分别代表第一个第二个数据

8.8 set容器排序

set容器默认排序规则为从小到大，利用仿函数可以改变规则

示例一：set存放内置数据类型
class MyCompare				//仿函数
{
    public:
    	bool operator()(T v1,T v2)
        {
            return v1>v2;
        }
};
set<T,MyCompare> s1;     //创建时用仿函数指定规则
for(set<T>::iterator it = s1.begin();it !=s1.end();it++)
    cout<<*it<<" ";
示例二：set存放自定义数据类型
//自定义数据类型排序必须指定排序规则
#include <iostream>
#include <set>
#include <string>
class Person
{
    public:
    	Person(string name,int age)
        {
            this->m_Name = name;
            this->m_Age = age;
        }
    	string m_Name;
    	int m_Age;
}
class comparePerson
{
    public:
    	bool operator()(const Person& p1,const Person& p2)
        {
            //按照年龄进行排序 降序
            return p1.m_Age > p2.m_Age;
        }
}
void test01()
{
    set<Person,comparePerson> s;
    Person p1("刘备",23);
    Person p2("关羽",27);
    Person p3("张飞",25);
    
    s.insert(p1);
    s.insert(p2);
    s.insert(p3);
    for(set<Person,comparePerson>::iterator it = s.begin();it !=s.end();it++)
    	cout << "姓名：" << it->m_Name << "年龄：" << it->m_Age << endl;
    
}
int main()
{
    test01();
    system("pause");
    return 0;
}

9.map/multimap容器

9.1 map基本概念

简介:

• map中所有元素都是pair

• pair中的第一个元素为key（键值），起索引作用，第二个元素为value（实值）

• 所有元素都会根据元素的键值自动排序

本质：

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

优点：

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

map/multimap容器区别：

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

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

9.2 map构造和赋值

//构造：
map<T1,T2> mp;                  //默认构造函数
map(const map &mp);             //拷贝构造函数
eg:map<T,T> mp1(mp2);
赋值：
map& operator=(const map &mp);  //重载等号操作

9.3 map大小和交换

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

9.4 map插入和删除

//插入：
insert(elem);                       //在容器中插入元素elem
map<T,T> m;
第一种：m.insert(pair<T,T>(key,value));
第二种：m.insert(make_pair(key,value));
第三种：m.insert(map<T,T>::value_type(key,value));
第四种：m[key]=value;                 //不建议用[]进行插入,但可以利用key访问value
//删除：
erase(const_iterator pos);          //删除迭代器指向的数据，返回下一个元素的迭代器
erase(key);                         //删除迭代器中first为key的元素
eg:m.erase(m.begin());
erase(const_iterator begin，const_iterator end); //删除区间begin到end之间的元素，返回下一个元素的迭代器
eg:m.erase(m.begin(),m.end());      //等同于clear();
clear();                            //清空容器中的所有元素

9.5 map查找和统计

//查找:
find(key);       //查找first为key是否存在，若存在，返回该键的元素的迭代器；若不存在，返回map.end();
eg:map<T,T>::iterator pos = mp.find(key);   //重点：返回的是迭代器！！！
if(pos!=mp.end())
    cout<<"找到了元素，key="<<(*pos).first<<"value="<<(*pos).second<<endl;
else
    cout<<"未找到元素"<<endl;
//统计:
                    //map不允许容器中有重复的key值元素，multimap允许
count(key);         //对于count统计而言，first为key的元素个数结果为0或者1,而multimap可以大于1
eg:int num = mp.count(key);
cout<<"num="<<num<<endl;

9.6 map容器排序

• map容器默认的排序规则为按照key值进行从小到大排序

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

class MyCompare             //仿函数
{
    public:
        bool operator()(T v1,T v2)
        {
            //降序
            return v1>v2;
        }
};
map<T,T,MyCompare> mp;     //创建时用仿函数指定规则
for(map<int,int,MyCompare>::iterator it = mp.begin();it !=mp.end();it++)
    cout<<"key:"<<it->first<<"value:"<<it->second<<endl;
//对于自定义数据类型，示例同set容器排序

10.STL函数对象

10.1 函数对象

10.1.1 函数对象概念

概念：

• 重载函数调用操作符的类，其对象常称为函数对象

• 函数对象使用重载的()时，行为类似于函数调用，也叫仿函数

本质：

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

10.1.2 函数对象使用

特点：

• 函数对象在使用时，可以像普通函数那样调用，可以有参数和返回值

• 函数对象超出普通函数的概念，函数对象可以有自己的状态

• 函数对象可以作为参数传递

#include <iostream>
#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++");
}

10.2 谓词

10.2.1 谓词概念

概念：

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

• 如果operator()接受一个参数，一元谓词，接受两个参数，二元谓词

10.2.2 一元谓词

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
class GreaterFive
{
    public:
        bool operator()(int val)
        {
            return val>5;
        }
};
void test01()
{
    vector<int> v;
    for(int i=0;i<10;i++)
        v.push_back(i);
    //查找容器中有没有大于5的数字
    //GreaterFive()匿名的函数对象
    //find_if返回对象为迭代器，未找到返回到end()
    vector<int>::iterator it = find_if(v.begin(),v.end(),GreaterFive());
    if(it==v.end())
        cout<<"未找到"<<endl;
    else
        cout<<"找到了大于5的数字:"<<*it<<endl;       
}
int main()
{
    test01();
    system("pause");
    return 0;
}

10.2.3 二元谓词

class MyCompare             //仿函数
{
    public:
        bool operator()(int val1,int val2)
        {
            return val1>val2;
        }
}
vector<int> v;
//sort，默认从小到大
sort(v.begin(),v.end());
//使用函数对象，改变默认排序规则
sort(v,begin(),v.end(),MyCompare());

10.3 内建函数对象

10.3.1 内建函数对象意义

分类：

• 算术仿函数

• 关系仿函数

• 逻辑仿函数

用法：

• 这些仿函数所产生的对象，用法和一般函数完全相同

• 使用内建函数对象，需要引入头文件

  #include <functional>

10.3.2 算术仿函数

• 实现四则运算

• 其中negate是一元运算，其他的都是二元运算

#include <functional>               //内建函数对象头文件  
//仿函数原型
template<class T> T plus<T>         //加法仿函数
eg:
plus<int> p;
p(10,20);
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>       //取反仿函数  
eg:
negate<int> n;
n(50);

10.3.3 关系仿函数

• 实现关系对比

#include <functional>               //内建函数对象头文件  
//仿函数原型
template<class T> bool equal_to<T>          //等于
template<class T> bool not_equal_to<T>      //不等于
template<class T> bool greater<T>           //大于
//greater<T>()内建
eg:sort(v.begin(),v.end(),greater<T>());
template<class T> bool greater_equal<T>     //大于等于
template<class T> bool less<T>              //小于  
template<class T> bool less_equal<T>        //小于等于

10.3.4 逻辑仿函数

• 实现逻辑运算

template<class T> bool logical_and<T>       //逻辑与
template<class T> bool logical_or<T>        //逻辑或 
template<class T> bool logical_not<T>       //逻辑非
    
#include <iostream>
#include <vector>
#include <algorithm>
#include <functional>
using namespace std;
void test01()
{
    vector<bool> v;
    v.push_back(true);
    //利用逻辑非 将容器V搬运
    vector<bool> v2;
    v2.resize(v.size());        //必须先开辟足够大小的空间
    transfrom(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;
}

11.STL-常用算法

概述：

• 算法主要是由头文件 <algorithm> <functional> <numeric>

• <algorithm> 是所有STL头文件中最大的一个，范围涉及到比较、交换、查找、遍历操作、复制、修改等等

• <numeric>体积很小，只包括几个在序列上进行简单数学运算的模板函数

• <functional> 定义了一些模板类，用以声明函数对象

11.1 常用遍历算法

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

11.1.1 for_each

for_each(iterator beg,iterator end,_func);
//_func可以是普通函数或仿函数（匿名函数对象）

11.1.2 transform

transform(iterator beg1,iterator end1,iterator beg2,_func)
//beg1 源容器开始迭代器 end1 源容器结束迭代器  beg2 目标容器开始迭代器
//_func 函数或函数对象  
//注意：目标容器需要提前开辟空间

11.2 常用查找算法

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

11.2.1 find

• 按值查找元素

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

特殊的，如果是查找自定义数据类型，则需要重载==号

eg:

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
class Person
{
    public:
        Person(string name,int age)
        {
            this->m_Name = name;
            this->m_Age = age;
        }
    //重载 == 底层find知道如何对比person数据类型
        bool operator==(const Person &p)
        {
            if(this->m_Name == p.m_Name && this->m_Age == p.m_Age)
                return true;
            else
                return false;
        }
        string m_Name;
        int m_Age;
};
void test01()
{
    vector<Person> v;
    Person p1("刘备",23);
    Person p2("关羽",27);
    Person p3("张飞",25);
    v.push_back(p1);
    v.push_back(p2);
    v.push_back(p3);
    
    Person p4("关羽",27);
    vector<Person>::iterator it = find(v.begin(),v.end(),p4);
    if(it == v.end())
        cout << "没有找到" << endl;
    else
        cout << "找到元素 姓名：" << it->m_Name << "年龄：" << it->m_Age << endl;
}
int main()
{
    test01();
    system("pause");
    return 0;
}

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

11.2.2 find_if

• 按条件查找元素

find_if(iterator beg,iterator end,_Pred);
//按条件查找元素，找到返回指定位置迭代器，找不到返回结束迭代器
//beg 开始迭代器 end 结束迭代器 _Pred函数或者谓词（返回bool类型的仿函数）
//自定义数据类型，其余同上
class Greater           
{
    public:
        bool operator()(Person &p)
        {
            return p.m_Age > 20;
        }
};
vector<Person>::iterator it = find_if(v.begin(),v.end(),Greater());

11.2.3 adjacent_find

• 查找相邻重复元素

adjacent_find(iterator beg,iterator end);
//查找相邻重复元素，返回相邻元素的第一个位置的迭代器
//beg 开始迭代器 end 结束迭代器
eg:vector<T>::iterator pos = adjacent_find(v.begin(),v.end());

11.2.4 binary_search

• 查找指定元素是否存在

bool binary_search(iterator beg,iterator end,value);
//查找指定的元素，查到返回true 否则false
//注意：在无序序列中不可用
//beg 开始迭代器 end 结束迭代器 value 查找的元素
eg:
vector<int> v;
for(int i=0;i<10;i++)
    v.posh_back(i);
//注意：容器必须是有序的容器！！！
bool ret = binary_search(v.begin(),v.end(),9);
if(ret)
    cout<<"找到！"<<endl;
else
    cout<<"未找到！"<<endl;

11.2.5 count

• 统计元素的个数

int num = count(iterator beg,iterator end,value);
//统计元素出现的次数
//beg 开始迭代器 end 结束迭代器 value 查找的元素
//注意：统计自定义数据类型时候，需要配合重载operator==  ！！！（方式同上）

11.2.6 count_if

int num = count_if(iterator beg,iterator end,_Pred);
//按照条件统计元素出现次数
//beg 开始迭代器 end 结束迭代器 _Pred 谓词

11.3 常用排序算法

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

11.3.1 sort

sort(iterator beg,iterator end,_Pred);
//默认从小到大
//beg 开始迭代器 end 结束迭代器 _Pred 谓词（自建或内建函数对象）

11.3.2 random_shuffle

random_shuffle(iterator beg,iterator end);
//打乱顺序：!!!使用时记得加随机数种子
#include <ctime>
srand((unsigned int)time(NULL));

11.3.3 merge

merge(iterator beg1,iterator end1,iterator beg2,iterator end2,iterator dest);
//容器元素合并，并存储到另一容器中
//注意：两个元素必须是有序的,且排序方式必须相同（同升或者同降等等）
//beg1 容器1开始迭代器 end1 容器1结束迭代器 beg2 容器2开始迭代器 end2 容器2结束迭代器
//dest 目标容器开始迭代器
//!!!目标容器需要提前开辟空间
eg:vTarget.resize(v1.size()+v2.size());
merge(v1.begin(),v1.end(),v2.begin(),v2.end(),vTarget.begin());

11.3.4 reverse

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

11.4 常用拷贝函数和替换函数

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

11.4.1 copy

copy(iterator beg,iterator end,iterator dest)
//beg 开始迭代器 end 结束迭代器  dest 目标容器开始迭代器
//!!!目标容器需要提前开辟空间
eg:v2.resize(v1.size);
copy(v1.begin(),v1.end(),v2.begin());

11.4.2 replace

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

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

11.4.3 replace_if

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

11.4.4 swap

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

11.5 常用算术生成算法

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

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

11.5.1 accumulate

accumulate(iterator beg,iterator end,value);
//计算区间内容器元素累计总和
//beg 开始迭代器 end 结束迭代器  value 起始值累加值（一般设置为0）
eg:int total = accmulate(v.begin(),v.end(),0)

11.5.2 fill

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

11.6 常用集合算法

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

11.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 目标容器开始迭代器
//！！!目标容器需要提前开辟空间 最特殊情况：大容器包含小容器 开辟空间取小容器的size即可
eg:#include <algorithm>
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);

总结：

• 求交集的两个集合必须是有序序列

• 目标容器开辟空间需要从两个容器的大小中取小值

• set_intersection返回值是交集中最后一个元素的位置

11.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 目标容器开始迭代器
//！！!目标容器需要提前开辟空间 最特殊情况：两个容器没有交集，并集就是两个容器的size相加
eg: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);

总结：

• 求并集的两个集合必须是有序序列

• 目标容器开辟空间需要从两个容器的大小相加

• set_union返回值是并集中最后一个元素的位置

11.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 目标容器开始迭代器
//！！!最特殊情况：两个容器没有交集，取两个容器中大的size作为目标容器开辟空间
eg:#include <algorithm>
vTarget.resize(max(v1.size()，v2.size());
//返回目标容器的最后一个元素的迭代器的地址
vector<int>::iterator itEnd = set_difference(v1.begin(),v1.end(),v2.begin(),v2.end(),vTarget.begin());
//基于最大容器开辟的空间仍然有可能偏大，遍历容器时应该使用返回的结束迭代器
for_each(vTarget.begin(),itEnd,myPrint);

总结：

• 求差集的两个集合必须是有序序列

• 目标容器开辟空间需要从两个容器的大小取较大值

• set_difference返回值是差集中最后一个元素的位置

致谢：以上资料均总结翻录于

黑马程序员匠心之作|C++教程从0到1入门编程,学习编程不再难_哔哩哔哩_bilibili

受益匪浅，推荐大家学习观看！！！