黑马程序员C++提高编程

---

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

文章目录

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

一、模板

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

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

1.1 函数模板

1.1.1 函数模板基础知识

​ 语法：

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

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

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

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

🔴注意：

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

//自动类型推导必须推出一致的类型
template<typename T>
void MySwap(T& a, T& b)
{T temp = a;a = b;b = temp;
}
int main()
{int a = 10;double b = 20;MySwap(a, b);//errcout << "a=" << a << "b=" << b << endl;return 0;
}//模板必须要确定出T的数据类型，才可以使用
template<typename T>
void MySwap( )
{cout << "MySwap的调用";
}
int main()
{MySwap( );//err 自动类型推导推导不出数据类型MySwap<int>();//显示指定类型强制推导数据类型return 0;
}

案例一： 数组排序

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

//交换模板
template <typename T>
void MySwap(T& a, T& b)
{T temp = a;a = b;b = temp;
}
//打印模板
template<typename T>
void MyPrint(T arr[], int sz)
{for (int i = 0; i < sz; i++){cout << arr[i];}
}
//排序模板
template<typename T>
void MySort(T arr[], int sz)
{for (int i = 0; i < sz; i++){T max = arr[i];for (int j = i + 1; j < sz; j++){if (arr[j] > arr[i]){MySwap(arr[j], arr[i]);}}}MyPrint(arr,sz);
}int main()
{//字符数组测试char arr1[] = "badcfeg";MySort(arr1, sizeof(arr1) / sizeof(char));//整形数组测试int arr2[] = { 1,3,4,5,2,6,7,9 };MySort(arr2, sizeof(arr2) / sizeof(int));
}

1.2.1 普通函数与函数模板

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

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

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

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

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

void print(int a)
{cout << "普通函数调用" << endl;
}
template <typename T>
void print(T a)
{cout << "函数模板调用" << endl;
}
template <typename T>
void print(T a, T b)
{cout << "重载调用" << endl;
}
int main()
{int a = 10;//1.同名普通函数与函数模板，优先调用普通函数。print(a);//输出：普通函数调用//2.可以通过空模板参数列表来强制调用函数模板。print<>(a);//输出：函数模板调用//3.如果函数模板可以产生更好的匹配,优先调用函数模板char c = a;print(c);//输出：函数模板调用//4.函数模板可以函数重载print(a, 1);//输出：重载调用
}

1.2.2 函数模板的局限性

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

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

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

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

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

1.2 类模板

1.2.1 类模板的基础知识

​ 语法：

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

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

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

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

1.2.2 类模板与函数模板

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

1. 类模板无法进行自动类型推导。（函数模板可以进行自动类型推导）
2. 类模板在模板的参数列表中可以有默认参数，如果自己传了就用自己传的，没有传就用默认的即等于号后面的。（函数模板不可以用）

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

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

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

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

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

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

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

类模板：

person::person(T name)

void person::print()

普通类：

person::person(string name)

void person::print()

类模板多了一个模板的参数列表

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

学习目标：类模板实例化出的对象，向函数传参的方式

有三种方式：

1. 指定传入的类型 — 直接显示对象的数据类型（使用比较广泛，比较常用）
2. 参数模板化 — 将对象中的参数变为模板进行传递
3. 整个类模板化 — 将这个对象类型 模板化进行传递

template <class NameType,class AgeType>
class person
{
public:person(NameType name,AgeType age){this->name = name;this->age = age;}void print(){cout << this->name  << this->age;}NameType name;AgeType age;
};void print1(person <string, int>& p)
{p.print();
}template <class T1,class T2>
void print2(person <T1 , T2>&p)
{p.print();cout << "T1的类型:" << typeid(T1).name() << endl;//模板推出的数据类型cout << "T2的类型:" << typeid(T2).name() << endl;
}template <class T>
void print3(T& p)
{p.print();cout << "T的数据类型：" << typeid(T).name() << endl;
}
int main()
{person <string, int>p("xiyang", 18);// 1.指定传入的类型print1(p);// 2.参数模板化print2(p);// 3.整个类模板化print3(p);
}

1.2.6 类模板与继承

🔴注意：

1. 当子类继承的父类是一个类模板时，子类在声明的时候，要指定出父类中T的类型（否则会报错）

   class Son :public Base{};（报错）

   class Son1 :public Base {};（正确）

2. 如果不指定，编译器无法给子类分配内存

3. 如果想灵活指定出父类中T的类型，子类也需变为类模板

   class Son2 :public Base{};

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

1.2.7 类模板分文件编写

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

解决：

1.直接包含.cpp源文件

2.将声明和实现写在同一个文件中，并更改后缀名为.hpp,hpp是约定的名称，并不是强制

//person.h
#pragma once
#include <iostream>
#include <string>
using namespace std;
template<class NameType,class AgeType>
class person
{
public:person(NameType name,AgeType age);void print();NameType name;AgeType age;
};//person.cpp
#include "person.h"
template<class NameType, class AgeType>
person<NameType, AgeType>::person(NameType name, AgeType age)
{this->name = name;this->age = age;
}
template<class NameType, class AgeType>
void person<NameType, AgeType>::print()
{cout << this->age << this->name << endl;
}//test.cpp
#include "person.h"
int main()
{person<string, int>p("xiyang", 18);p.print();return 0;
}
12345678910111213141516171819202122232425262728293031323334353637

✅ 解决方案：
① 在test.cpp中，将 person.h 改为 person.cpp
② 直接将 person.h 和 person.cpp 合并，后缀为.hpp

//person.hpp
#pragma once
#include <iostream>
#include <string>
using namespace std;
template<class NameType,class AgeType>
class person
{
public:person(NameType name,AgeType age);void print();NameType name;AgeType age;
};
template<class NameType, class AgeType>
person<NameType, AgeType>::person(NameType name, AgeType age)
{this->name = name;this->age = age;
}
template<class NameType, class AgeType>
void person<NameType, AgeType>::print()
{cout << this->age << this->name << endl;
}
12345678910111213141516171819202122232425
//test.cpp
#include "person.hpp"
int main()
{person<string, int>p("xiyang", 18);p.print();return 0;
}
12345678

1.2.8 类模板与友元

掌握类模板配合友元函数的类内和类外实现

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

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

  建议：全局函数做类内实现，用法简单，而且编译器可以直接识别

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

案例二： 通用的数组类

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

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

//MyArray.hpp
#pragma once
#include <iostream>
#include <string>
using namespace std;
template <class T>
class MyArray
{
public://构造函数MyArray(int capacity){this->capacity = capacity;this->size = 0;this->arr = new T[this->capacity];}// 拷贝构造——为了解决浅拷贝带来的问题MyArray(MyArray& ma){this->capacity = ma.capacity;this->size = ma.size;this->arr = new	T[ma.capacity];for (int i = 0; i < ma.size; i++){this->arr[i] = ma.arr[i];}}// operator= ——解决浅拷贝带来的问题MyArray& operator=(MyArray& ma){//赋值前有内容则需要清空if (this->capacity != 0){this->size = 0;this->capacity = 0;delete[] this->arr;this->arr = NULL;}this->size = ma.size;this->capacity = capacity;this->arr = new T[ma.capacity];for (int i = 0; i < ma.size; i++){this->arr[i] = ma.arr[i];}return *this;}//通过下标访问数据T& operator[ ](int idex){//越界if (idex<0 || idex>size)exit(0);//强制退出return this->arr[idex];}//尾插void PushBack(T val){//判断是否满了if (this->capacity == this->size){return;}this->arr[this->size] = val;this->size++;}//尾删void PopBack(){//判断是否是空的if (this->size == 0){return;}this->size--;}//获取数组容量int GetCapacity(){return this->capacity;}//获取数组大小int	GetSize(){return this->size;}//析构函数~MyArray(){if (this->arr != NULL){this->capacity = 0;this->size = 0;delete[] this->arr;this->arr = NULL;}}
private:T* arr; //指向数组int capacity; //容量int size;  //数组大小
};
//test.cpp
#include "MyArray.hpp"
//测试内置数据类型
void printIntArray(MyArray<int>& arr) {for (int i = 0; i < arr.GetSize(); i++) {cout << arr[i] << " ";}cout << endl;
}
void test01()
{MyArray<int> array1(10);for (int i = 0; i < 10; i++){array1.PushBack(i);}cout << "array1打印输出：" << endl;printIntArray(array1);cout << "array1的大小：" << array1.GetSize() << endl;cout << "array1的容量：" << array1.GetCapacity() << endl;cout << "--------------------------" << endl;
}//测试自定义数据类型
class Person {
public:Person() {}Person(string name, int age) {this->name = name;this->age = age;}
public:string name;int age;
};void printPersonArray(MyArray<Person>& personArr)
{for (int i = 0; i < personArr.GetSize(); i++) {cout << "姓名：" << personArr[i].name << " 年龄： " << personArr[i].age << endl;}
}void test02()
{//创建数组MyArray<Person> pArray(10);Person p1("孙悟空", 30);Person p2("韩信", 20);Person p3("妲己", 18);Person p4("王昭君", 15);Person p5("赵云", 24);//插入数据pArray.PushBack(p1);pArray.PushBack(p2);pArray.PushBack(p3);pArray.PushBack(p4);pArray.PushBack(p5);printPersonArray(pArray);cout << "pArray的大小：" << pArray.GetSize() << endl;cout << "pArray的容量：" << pArray.GetCapacity() << endl;}int main() 
{test01();test02();
}

二、STL

2.1 STL的基础知识

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

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

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

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

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

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

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

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

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

1. vector存放内置数据类型

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

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

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

// vector存放自定义数据类型
using namespace std;
class person
{
public:person(string name, int age){this->age = age;this->name = name;}int age;string name;
};int main()
{//person类vector <person> v;//创建person p1("a", 18);person p2("b", 18);person p3("c", 18);person p4("d", 18);//向容器中添加数据v.push_back(p1);v.push_back(p2);v.push_back(p3);v.push_back(p4);//遍历for (vector<person>::iterator it = v.begin(); it != v.end(); it++){cout << "姓名：" << (*it).age << endl;//it->agecout << "年龄：" << (*it).name << endl;//it->name}//指针类vector <person*> v1;//向容器中添加数据v1.push_back(&p1);v1.push_back(&p2);v1.push_back(&p3);v1.push_back(&p4);//遍历for (vector<person*>::iterator it = v1.begin(); it != v1.end(); it++){cout << "姓名：" << (*it)->age << endl;cout << "年龄：" << (*it)->name << endl;}
}

3. vector容器嵌套容器

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

2.3 常用容器

2.3.1 string

2.3.1.1 string基础知识

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

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

2.3.1.2 接口

​ 1. 构造函数原型

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

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

​ 2. 赋值操作

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

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

​ 3. 字符存取

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

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

​ 4.字符串查找、替换

​ ① int find(const char c, int pos = 0) const ：查找字符c第一次出现位置
​ ② int find(const char* s, int pos = 0) const：查找s第一次出现位置,从pos开始查找
​ ③ int find(const char* s, int pos, int n) const：从pos位置查找s的前n个字符第一次位置
​ ④ int find(const string& str, int pos = 0) const：查找str第一次出现位置,从pos开始查找
​ ⑤ int rfind(const char c, int pos = 0) const:查找字符c最后一次出现位置
​ ⑥ int rfind(const char* s, int pos = npos) const：查找s最后一次出现位置,从pos开始查找
​ ⑦ int rfind(const char* s, int pos, int n) const:从pos查找s的前n个字符最后一次位置
​ ⑧ int rfind(const string& str, int pos = npos) const:查找str最后一次位置,从pos开始查找
​ ⑨ string& replace(int pos, int n, const string& str)：替换从pos开始n个字符为字符串str
​ ⑩ string& replace(int pos, int n,const char* s)：替换从pos开始的n个字符为字符串s

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

​ 5. 插入和删除
​ ① string& insert(int pos, const char* s)
​ ② string& insert(int pos, const string& str)
​ ③ string& insert(int pos, int n, char c)：在指定位置插入n个字符c
​ ④ string& erase(int pos, int n = npos)：删除从Pos开始的n个字符

int main()
{//字符串插入和删除string str = "hello";str.insert(1, "111");cout << str << endl;str.erase(1, 3);  //从1号位置开始3个字符cout << str << endl;
}
12345678910

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

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

​ 但大小比较很有缺陷，ehllo和hello结果过是1小于2，ehllo和h还是1小于2，其实没啥用，基本只用于两字符串是否相等上面

​ 7. 字符串拼接

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

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

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

int main()
{string str = "abcdefg";string subStr = str.substr(1, 3);cout << "subStr = " << subStr << endl;string email = "hello@sina.com";int pos = email.find("@");string username = email.substr(0, pos);cout << "username: " << username << endl;}
123456789101112

2.3.2 vector

2.3.2.1 vector基础知识

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

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

2.3.2.2 接口

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

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

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

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

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

	vector<int>v1;for (int i = 0; i < 10; i++){v1.push_back(i);}//1.at(int idx)cout << v1.at(0) << endl;//2.operator[]cout << v1[0] << endl;//3.front()cout << v1.front() << endl;//4.back()cout << v1.back() << endl;
12345678910111213141516

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

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

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

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

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

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

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

//swap的收缩内存作用
int main()
{vector <int> v;for (int i = 0; i < 999999; i++){v.push_back(i);}cout << "v的容量为：" << v.capacity() << endl;cout << "v的大小为：" << v.size() << endl;v.resize(3);cout << "v的容量为：" << v.capacity() << endl;cout << "v的大小为：" << v.size() << endl;//收缩内存vector<int>(v).swap(v); //匿名对象，指针交换后，系统执行完这行代码后匿名对象指向空间立即释放，不会造成内存泄漏cout << "v的容量为：" << v.capacity() << endl;cout << "v的大小为：" << v.size() << endl;
}

2.3.3 deque

2.3.3.1 deque基础知识

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

与vector区别：

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

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

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

🔵特点：
① deque对头部的插入删除速度比vector快
② deque容器的迭代器是支持随机访问的迭代器。

内部工作原理
deque中有一个中控器，维护每段缓冲区中的内容，缓冲区里面存放真实数据。

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

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

2.3.3.2 接口

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

//构造函数和赋值操作部分的基础内容，基本和vector没有什么区别
//遍历
void printfde(deque<int>& v)
{for (deque<int>::iterator it = v.begin(); it != v.end(); it++){cout << *it << "  ";}cout << endl;
}
//如果要防止修改的话则需要一个只读的迭代器，即const_iterator和const deque<int>& v
//只读迭代器就是加个const
void printfde(const deque<int>& v)
{for (deque<int>::const_iterator it = v.begin(); it != v.end(); it++){cout << *it << "  ";}cout << endl;
}
//1.deque<T> deqTdeque<int> d1;for (int i = 0; i < 10; i++){d1.push_front(i);//头插}//2.deque(beg, end)deque<int> d2(d1.begin(), d1.end());//3.deque(n, elem)deque<int> d3(10, 100);//4.deque(const deque &deq)deque<int> d4(d1);

案例三： 评委打分

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

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

2.3.4 stack

2.3.4.1 stack基础知识

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

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

2.3.4.2 接口

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

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

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

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

//eg.
#include <stack>
//栈容器常用接口
void test01()
{//创建栈容器 栈容器必须符合先进后出stack<int> s;//向栈中添加元素，叫做 压栈 入栈s.push(10);s.push(20);s.push(30);while (!s.empty()) {//输出栈顶元素cout << "栈顶元素为： " << s.top() << endl;//弹出栈顶元素s.pop();}cout << "栈的大小为：" << s.size() << endl;}int main() {test01();system("pause");return 0;
}
12345678910111213141516171819202122232425262728293031

2.3.5 queue

2.3.5.1 queue基础知识

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

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

2.3.5.2 接口

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

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

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

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

#include <queue>
#include <string>
class Person
{
public:Person(string name, int age){this->m_Name = name;this->m_Age = age;}string m_Name;int m_Age;
};void test01() {//创建队列queue<Person> q;//准备数据Person p1("唐僧", 30);Person p2("孙悟空", 1000);Person p3("猪八戒", 900);Person p4("沙僧", 800);//向队列中添加元素  入队操作q.push(p1);q.push(p2);q.push(p3);q.push(p4);//队列不提供迭代器，更不支持随机访问	while (!q.empty()) {//输出队头元素cout << "队头元素-- 姓名： " << q.front().m_Name<< " 年龄： " << q.front().m_Age << endl;cout << "队尾元素-- 姓名： " << q.back().m_Name<< " 年龄： " << q.back().m_Age << endl;cout << endl;//弹出队头元素q.pop();}cout << "队列大小为：" << q.size() << endl;
}int main() {test01();system("pause");return 0;
}

2.3.6 list

2.3.6.1 list基础知识

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

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

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

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

2.3.6.2 接口

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

#include <list>
void printList(const list<int>& L) 
{for (list<int>::const_iterator it = L.begin(); it != L.end(); it++) {cout << *it << " ";}cout << endl;
}
void test01()
{list<int>L1;L1.push_back(10);L1.push_back(20);L1.push_back(30);L1.push_back(40);printList(L1);list<int>L2(L1.begin(),L1.end());printList(L2);list<int>L3(L2);printList(L3);list<int>L4(10, 1000);printList(L4);
}
int main() 
{test01();system("pause");return 0;
}
123456789101112131415161718192021222324252627282930

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

#include <list>void printList(const list<int>& L) 
{for (list<int>::const_iterator it = L.begin(); it != L.end(); it++) {cout << *it << " ";}cout << endl;
}//赋值和交换
void test01()
{list<int>L1;L1.push_back(10);L1.push_back(20);L1.push_back(30);L1.push_back(40);printList(L1);//赋值list<int>L2;L2 = L1;printList(L2);list<int>L3;L3.assign(L2.begin(), L2.end());printList(L3);list<int>L4;L4.assign(10, 100);printList(L4);}//交换
void test02()
{list<int>L1;L1.push_back(10);L1.push_back(20);L1.push_back(30);L1.push_back(40);list<int>L2;L2.assign(10, 100);cout << "交换前： " << endl;printList(L1);printList(L2);cout << endl;L1.swap(L2);cout << "交换后： " << endl;printList(L1);printList(L2);}int main(){//test01();test02();system("pause");return 0;
}
12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970

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

#include <list>void printList(const list<int>& L) 
{for (list<int>::const_iterator it = L.begin(); it != L.end(); it++) {cout << *it << " ";}cout << endl;
}//大小操作
void test01()
{list<int>L1;L1.push_back(10);L1.push_back(20);L1.push_back(30);L1.push_back(40);if (L1.empty()){cout << "L1为空" << endl;}else{cout << "L1不为空" << endl;cout << "L1的大小为： " << L1.size() << endl;}//重新指定大小L1.resize(10);printList(L1);L1.resize(2);printList(L1);
}int main() {test01();system("pause");return 0;
}
12345678910111213141516171819202122232425262728293031323334353637383940414243

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

#include <list>//数据存取
void test01()
{list<int>L1;L1.push_back(10);L1.push_back(20);L1.push_back(30);L1.push_back(40);//cout << L1.at(0) << endl;//错误 不支持at访问数据//cout << L1[0] << endl; //错误  不支持[]方式访问数据cout << "第一个元素为： " << L1.front() << endl;cout << "最后一个元素为： " << L1.back() << endl;//list容器的迭代器是双向迭代器，不支持随机访问list<int>::iterator it = L1.begin();//it = it + 1;//错误，不可以跳跃访问，即使是+1
}int main() {test01();system("pause");return 0;
}
123456789101112131415161718192021222324252627282930

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

#include <list>void printList(const list<int>& L) {for (list<int>::const_iterator it = L.begin(); it != L.end(); it++) {cout << *it << " ";}cout << endl;
}//插入和删除
void test01()
{list<int> L;//尾插L.push_back(10);L.push_back(20);L.push_back(30);//头插L.push_front(100);L.push_front(200);L.push_front(300);printList(L);//尾删L.pop_back();printList(L);//头删L.pop_front();printList(L);//插入list<int>::iterator it = L.begin();L.insert(++it, 1000);printList(L);//删除it = L.begin();L.erase(++it);printList(L);//移除L.push_back(10000);L.push_back(10000);L.push_back(10000);printList(L);L.remove(10000);printList(L);//清空L.clear();printList(L);
}int main() {test01();system("pause");return 0;
}
12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364

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

void printList(const list<int>& L) {for (list<int>::const_iterator it = L.begin(); it != L.end(); it++) {cout << *it << " ";}cout << endl;
}bool myCompare(int val1 , int val2)
{return val1 > val2;
}//反转和排序
void test01()
{list<int> L;L.push_back(90);L.push_back(30);L.push_back(20);L.push_back(70);printList(L);//反转容器的元素L.reverse();printList(L);//排序L.sort(); //默认的排序规则 从小到大printList(L);L.sort(myCompare); //指定规则，从大到小printList(L);
}int main() {test01();system("pause");return 0;
}
12345678910111213141516171819202122232425262728293031323334353637383940414243

2.3.7 set/ multiset

2.3.7.1 set/ multiset 基础知识

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

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

2.3.7.2 接口

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

#include <set>void printSet(set<int> & s)
{for (set<int>::iterator it = s.begin(); it != s.end(); it++){cout << *it << " ";}cout << endl;
}//构造和赋值
void test01()
{set<int> s1;s1.insert(10);s1.insert(30);s1.insert(20);s1.insert(40);printSet(s1);//拷贝构造set<int>s2(s1);printSet(s2);//赋值set<int>s3;s3 = s2;printSet(s3);
}int main() {test01();system("pause");return 0;
}
12345678910111213141516171819202122232425262728293031323334353637383940

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

#include <set>void printSet(set<int> & s)
{for (set<int>::iterator it = s.begin(); it != s.end(); it++){cout << *it << " ";}cout << endl;
}//大小
void test01()
{set<int> s1;s1.insert(10);s1.insert(30);s1.insert(20);s1.insert(40);if (s1.empty()){cout << "s1为空" << endl;}else{cout << "s1不为空" << endl;cout << "s1的大小为： " << s1.size() << endl;}}//交换
void test02()
{set<int> s1;s1.insert(10);s1.insert(30);s1.insert(20);s1.insert(40);set<int> s2;s2.insert(100);s2.insert(300);s2.insert(200);s2.insert(400);cout << "交换前" << endl;printSet(s1);printSet(s2);cout << endl;cout << "交换后" << endl;s1.swap(s2);printSet(s1);printSet(s2);
}int main() {//test01();test02();system("pause");return 0;
}
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172

​ 3. 插入和删除

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

#include <set>void printSet(set<int> & s)
{for (set<int>::iterator it = s.begin(); it != s.end(); it++){cout << *it << " ";}cout << endl;
}//插入和删除
void test01()
{set<int> s1;//插入s1.insert(10);s1.insert(30);s1.insert(20);s1.insert(40);printSet(s1);//删除s1.erase(s1.begin());printSet(s1);s1.erase(30);printSet(s1);//清空//s1.erase(s1.begin(), s1.end());s1.clear();printSet(s1);
}int main() {test01();system("pause");return 0;
}
12345678910111213141516171819202122232425262728293031323334353637383940414243

​ 4. 查找和统计

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

#include <set>//查找和统计
void test01()
{set<int> s1;//插入s1.insert(10);s1.insert(30);s1.insert(20);s1.insert(40);//查找set<int>::iterator pos = s1.find(30);if (pos != s1.end()){cout << "找到了元素 ： " << *pos << endl;}else{cout << "未找到元素" << endl;}//统计int num = s1.count(30);cout << "num = " << num << endl;
}int main() {test01();system("pause");return 0;
}
12345678910111213141516171819202122232425262728293031323334353637

​ 5. set和multiset区别

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

#include <set>//set和multiset区别
void test01()
{set<int> s;pair<set<int>::iterator, bool>  ret = s.insert(10);if (ret.second) {cout << "第一次插入成功!" << endl;}else {cout << "第一次插入失败!" << endl;}ret = s.insert(10);if (ret.second) {cout << "第二次插入成功!" << endl;}else {cout << "第二次插入失败!" << endl;}//multisetmultiset<int> ms;ms.insert(10);ms.insert(10);for (multiset<int>::iterator it = ms.begin(); it != ms.end(); it++) {cout << *it << " ";}cout << endl;
}int main() {test01();system("pause");return 0;
}
1234567891011121314151617181920212223242526272829303132333435363738394041

​ 6. pair对组创建

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

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

#include <string>//对组创建
void test01()
{pair<string, int> p(string("Tom"), 20);cout << "姓名： " <<  p.first << " 年龄： " << p.second << endl;pair<string, int> p2 = make_pair("Jerry", 10);cout << "姓名： " << p2.first << " 年龄： " << p2.second << endl;
}int main() {test01();system("pause");return 0;
}
1234567891011121314151617181920

​ 7. 容器排序

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

//示例一：内置数据类型
#include <set>class MyCompare 
{
public:bool operator()(int v1, int v2) {return v1 > v2;}
};
void test01() 
{    set<int> s1;s1.insert(10);s1.insert(40);s1.insert(20);s1.insert(30);s1.insert(50);//默认从小到大for (set<int>::iterator it = s1.begin(); it != s1.end(); it++) {cout << *it << " ";}cout << endl;//指定排序规则set<int,MyCompare> s2;s2.insert(10);s2.insert(40);s2.insert(20);s2.insert(30);s2.insert(50);for (set<int, MyCompare>::iterator it = s2.begin(); it != s2.end(); it++) {cout << *it << " ";}cout << endl;
}int main() {test01();system("pause");return 0;
}
1234567891011121314151617181920212223242526272829303132333435363738394041424344454647
//示例二 set存放自定义数据类型
#include <set>
#include <string>class Person
{
public:Person(string name, int age){this->m_Name = name;this->m_Age = age;}string m_Name;int m_Age;};
class comparePerson
{
public:bool operator()(const Person& p1, const Person &p2){//按照年龄进行排序  降序return p1.m_Age > p2.m_Age;}
};void test01()
{set<Person, comparePerson> s;Person p1("刘备", 23);Person p2("关羽", 27);Person p3("张飞", 25);Person p4("赵云", 21);s.insert(p1);s.insert(p2);s.insert(p3);s.insert(p4);for (set<Person, comparePerson>::iterator it = s.begin(); it != s.end(); it++){cout << "姓名： " << it->m_Name << " 年龄： " << it->m_Age << endl;}
}
int main() {test01();system("pause");return 0;
}
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354

2.3.8 map/ multimap

2.3.8.1 map/ multimap基础知识

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

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

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

2.3.8.2 接口

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

#include <map>void printMap(map<int,int>&m)
{for (map<int, int>::iterator it = m.begin(); it != m.end(); it++){cout << "key = " << it->first << " value = " << it->second << endl;}cout << endl;
}void test01()
{map<int,int>m; //默认构造m.insert(pair<int, int>(1, 10));m.insert(pair<int, int>(2, 20));m.insert(pair<int, int>(3, 30));printMap(m);map<int, int>m2(m); //拷贝构造printMap(m2);map<int, int>m3;m3 = m2; //赋值printMap(m3);
}int main() {test01();system("pause");return 0;
}
1234567891011121314151617181920212223242526272829303132333435

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

#include <map>void printMap(map<int,int>&m)
{for (map<int, int>::iterator it = m.begin(); it != m.end(); it++){cout << "key = " << it->first << " value = " << it->second << endl;}cout << endl;
}void test01()
{map<int, int>m;m.insert(pair<int, int>(1, 10));m.insert(pair<int, int>(2, 20));m.insert(pair<int, int>(3, 30));if (m.empty()){cout << "m为空" << endl;}else{cout << "m不为空" << endl;cout << "m的大小为： " << m.size() << endl;}
}//交换
void test02()
{map<int, int>m;m.insert(pair<int, int>(1, 10));m.insert(pair<int, int>(2, 20));m.insert(pair<int, int>(3, 30));map<int, int>m2;m2.insert(pair<int, int>(4, 100));m2.insert(pair<int, int>(5, 200));m2.insert(pair<int, int>(6, 300));cout << "交换前" << endl;printMap(m);printMap(m2);cout << "交换后" << endl;m.swap(m2);printMap(m);printMap(m2);
}int main() {test01();test02();system("pause");return 0;
}123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263

​ 3. 插入和删除

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

#include <map>void printMap(map<int,int>&m)
{for (map<int, int>::iterator it = m.begin(); it != m.end(); it++){cout << "key = " << it->first << " value = " << it->second << endl;}cout << endl;
}void test01()
{//插入map<int, int> m;//第一种插入方式m.insert(pair<int, int>(1, 10));//第二种插入方式m.insert(make_pair(2, 20));//第三种插入方式m.insert(map<int, int>::value_type(3, 30));//第四种插入方式m[4] = 40; printMap(m);//删除m.erase(m.begin());printMap(m);m.erase(3);printMap(m);//清空m.erase(m.begin(),m.end());m.clear();printMap(m);
}int main() {test01();system("pause");return 0;
}
12345678910111213141516171819202122232425262728293031323334353637383940414243444546

​ 4. 查找和统计

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

#include <map>//查找和统计
void test01()
{map<int, int>m; m.insert(pair<int, int>(1, 10));m.insert(pair<int, int>(2, 20));m.insert(pair<int, int>(3, 30));//查找map<int, int>::iterator pos = m.find(3);if (pos != m.end()){cout << "找到了元素 key = " << (*pos).first << " value = " << (*pos).second << endl;}else{cout << "未找到元素" << endl;}//统计int num = m.count(3);cout << "num = " << num << endl;
}int main() {test01();system("pause");return 0;
}
1234567891011121314151617181920212223242526272829303132333435

​ 7. 容器排序

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

#include <map>class MyCompare {
public:bool operator()(int v1, int v2) {return v1 > v2;}
};void test01() 
{//默认从小到大排序//利用仿函数实现从大到小排序map<int, int, MyCompare> m;m.insert(make_pair(1, 10));m.insert(make_pair(2, 20));m.insert(make_pair(3, 30));m.insert(make_pair(4, 40));m.insert(make_pair(5, 50));for (map<int, int, MyCompare>::iterator it = m.begin(); it != m.end(); it++) {cout << "key:" << it->first << " value:" << it->second << endl;}
}
int main() {test01();system("pause");return 0;
}
123456789101112131415161718192021222324252627282930313233

案例四：员工分组

案例描述：

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

#include <string> 
#include <vector>
#include <map>
#include <ctime>
#include <iostream>
//部门的编号
#define CEHUA 0   //策划
#define MEISHU 1  //美术
#define YANFA 2   //研发
using namespace std;
//员工类
class Worker
{
public:Worker(string name,int salary){this->name = name;this->salary = salary;}string name;//姓名int salary;//工资
};
//创建员工
void CreatWorker(vector<Worker>& w,int n)
{string name;int salary;for (int i = 0; i < n; i++){name= "员工";char temp = (char)('A' + i);name = name + temp;//员工 ABCDEFG...salary = rand() % 1000 + 1000;//salary：1000-1999Worker worker(name, salary);//用name和salary实例化类w.push_back(worker);//将实例化的类放入vector容器中}}
void ClassifyWorker(multimap<int, Worker>& m, vector <Worker> &w,int n)
{for (int i = 0;i < n; i++){int id = rand() % 3;//0 1 2m.insert(make_pair(id, w.at(i)));}
}
void ShowWorkerByGourp(multimap<int, Worker>& m)
{cout << "策划部门：" << endl;multimap<int, Worker>::iterator pos = m.find(CEHUA);int count = m.count(CEHUA); // 统计具体人数int index = 0;for (; pos != m.end() && index < count; pos++, index++){cout << "姓名： " << pos->second.name << " 工资： " << pos->second.salary << endl;}cout << "----------------------" << endl;cout << "美术部门： " << endl;pos = m.find(MEISHU);count = m.count(MEISHU); // 统计具体人数index = 0;for (; pos != m.end() && index < count; pos++, index++){cout << "姓名： " << pos->second.name << " 工资： " << pos->second.salary << endl;}cout << "----------------------" << endl;cout << "研发部门： " << endl;pos = m.find(YANFA);count = m.count(YANFA); // 统计具体人数index = 0;for (; pos != m.end() && index < count; pos++, index++){cout << "姓名： " << pos->second.name << " 工资： " << pos->second.salary << endl;}}
int main()
{srand((unsigned int)time(NULL));//随机数种子，为了产生随机工资和部门编号vector <Worker> w;              //员工信息multimap<int, Worker> m;        //部门编号 + 员工信息int number;                     //员工数目cout << "please input the number of employees:";cin >> number;//创建员工CreatWorker(w,number);//员工分部门ClassifyWorker(m,w, number);//按部门输出ShowWorkerByGourp(m);return 0;
}
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596

三、STL- 函数对象

3.1 函数对象

3.1.1 函数对象的基础知识

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

3.1.2 函数对象使用

🔵特点：

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

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

3.2 谓词

3.2.1 谓词的基础知识

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

3.2.2 一元谓词

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

find_if函数原型：

3.2.3 二元谓词

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

3.3 内建函数对象

3.3.1 内建函数对象意义

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

3.3.2 算术仿函数

​ 作用：实现四则运算

​ 仿函数原型：
​ template<class T> T plus<T>//加法仿函数
​ template<class T> T minus<T> //减法仿函数
​ template<class T> T multiplies<T>//乘法仿函数
​ template<class T> T divides<T> //除法仿函数
​ template<class T> T modulus<T> //取模仿函数
​ template<class T> T negate<T> //取反仿函数

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

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

3.3.3 关系仿函数

​ 仿函数原型：
​ template<class T> bool equal_to<T>//等于
​ template<class T> bool not_equal_to<T> emplate<class T> T minus<T> //不等于
​ template<class T> bool greater<T>//大于
​ template<class T> bool greater_equal<T> //大于等于
​ template<class T> bool less<T> //小于
​ template<class T> bool less_equal<T> //小于等于

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

3.3.4 逻辑仿函数

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

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

四、STL- 常用算法

4.1 常用遍历算法

4.1.1 for_each

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

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

4.1.2 transform

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

目标容器需要提前开辟空间

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

4.2 常用查找算法

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

4.2.1 find

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

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

4.2.2 find_if

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

#include <algorithm>
#include <vector>
#include <string>//内置数据类型
class GreaterFive
{
public:bool operator()(int val){return val > 5;}
};void test01() {vector<int> v;for (int i = 0; i < 10; i++) {v.push_back(i + 1);}vector<int>::iterator it = find_if(v.begin(), v.end(), GreaterFive());if (it == v.end()) {cout << "没有找到!" << endl;}else {cout << "找到大于5的数字:" << *it << endl;}
}//自定义数据类型
class Person {
public:Person(string name, int age){this->m_Name = name;this->m_Age = age;}
public:string m_Name;int m_Age;
};class Greater20
{
public:bool operator()(Person &p){return p.m_Age > 20;}};void test02() {vector<Person> v;//创建数据Person p1("aaa", 10);Person p2("bbb", 20);Person p3("ccc", 30);Person p4("ddd", 40);v.push_back(p1);v.push_back(p2);v.push_back(p3);v.push_back(p4);vector<Person>::iterator it = find_if(v.begin(), v.end(), Greater20());if (it == v.end()){cout << "没有找到!" << endl;}else{cout << "找到姓名:" << it->m_Name << " 年龄: " << it->m_Age << endl;}
}int main() {//test01();test02();system("pause");return 0;
}123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990

4.2.3 adjacent_find

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

#include <algorithm>
#include <vector>void test01()
{vector<int> v;v.push_back(1);v.push_back(2);v.push_back(5);v.push_back(2);v.push_back(4);v.push_back(4);v.push_back(3);//查找相邻重复元素vector<int>::iterator it = adjacent_find(v.begin(), v.end());if (it == v.end()) {cout << "找不到!" << endl;}else {cout << "找到相邻重复元素为:" << *it << endl;}
12345678910111213141516171819202122

4.2.4 binary_search

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

#include <algorithm>
#include <vector>void test01()
{vector<int>v;for (int i = 0; i < 10; i++){v.push_back(i);}//二分查找bool ret = binary_search(v.begin(), v.end(),2);if (ret){cout << "找到了" << endl;}else{cout << "未找到" << endl;}
}int main() {test01();system("pause");return 0;
}
12345678910111213141516171819202122232425262728293031

4.2.5 count

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

#include <algorithm>
#include <vector>//内置数据类型
void test01()
{vector<int> v;v.push_back(1);v.push_back(2);v.push_back(4);v.push_back(5);v.push_back(3);v.push_back(4);v.push_back(4);int num = count(v.begin(), v.end(), 4);cout << "4的个数为： " << num << endl;
}//自定义数据类型
class Person
{
public:Person(string name, int age){this->m_Name = name;this->m_Age = age;}bool operator==(const Person & p){if (this->m_Age == p.m_Age){return true;}else{return false;}}string m_Name;int m_Age;
};void test02()
{vector<Person> v;Person p1("刘备", 35);Person p2("关羽", 35);Person p3("张飞", 35);Person p4("赵云", 30);Person p5("曹操", 25);v.push_back(p1);v.push_back(p2);v.push_back(p3);v.push_back(p4);v.push_back(p5);Person p("诸葛亮",35);int num = count(v.begin(), v.end(), p);cout << "num = " << num << endl;
}
int main() {//test01();test02();system("pause");return 0;
}
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475

4.2.6 count_if

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

#include <algorithm>
#include <vector>class Greater4
{
public:bool operator()(int val){return val >= 4;}
};//内置数据类型
void test01()
{vector<int> v;v.push_back(1);v.push_back(2);v.push_back(4);v.push_back(5);v.push_back(3);v.push_back(4);v.push_back(4);int num = count_if(v.begin(), v.end(), Greater4());cout << "大于4的个数为： " << num << endl;
}//自定义数据类型
class Person
{
public:Person(string name, int age){this->m_Name = name;this->m_Age = age;}string m_Name;int m_Age;
};class AgeLess35
{
public:bool operator()(const Person &p){return p.m_Age < 35;}
};
void test02()
{vector<Person> v;Person p1("刘备", 35);Person p2("关羽", 35);Person p3("张飞", 35);Person p4("赵云", 30);Person p5("曹操", 25);v.push_back(p1);v.push_back(p2);v.push_back(p3);v.push_back(p4);v.push_back(p5);int num = count_if(v.begin(), v.end(), AgeLess35());cout << "小于35岁的个数：" << num << endl;
}int main() {//test01();test02();system("pause");return 0;
}
12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182

4.3 常用排序算法

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

4.3.1 sort

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

#include <algorithm>
#include <vector>void myPrint(int val)
{cout << val << " ";
}void test01() {vector<int> v;v.push_back(10);v.push_back(30);v.push_back(50);v.push_back(20);v.push_back(40);//sort默认从小到大排序sort(v.begin(), v.end());for_each(v.begin(), v.end(), myPrint);cout << endl;//从大到小排序sort(v.begin(), v.end(), greater<int>());for_each(v.begin(), v.end(), myPrint);cout << endl;
}int main() {test01();system("pause");return 0;
}
1234567891011121314151617181920212223242526272829303132333435

4.3.2 random_shuffle

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

#include <algorithm>
#include <vector>
#include <ctime>class myPrint
{
public:void operator()(int val){cout << val << " ";}
};void test01()
{srand((unsigned int)time(NULL));vector<int> v;for(int i = 0 ; i < 10;i++){v.push_back(i);}for_each(v.begin(), v.end(), myPrint());cout << endl;//打乱顺序random_shuffle(v.begin(), v.end());for_each(v.begin(), v.end(), myPrint());cout << endl;
}int main() {test01();system("pause");return 0;
}
1234567891011121314151617181920212223242526272829303132333435363738

4.3.3 merge

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

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

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

#include <algorithm>
#include <vector>class myPrint
{
public:void operator()(int val){cout << val << " ";}
};void test01()
{vector<int> v1;vector<int> v2;for (int i = 0; i < 10 ; i++) {v1.push_back(i);v2.push_back(i + 1);}vector<int> vtarget;//目标容器需要提前开辟空间vtarget.resize(v1.size() + v2.size());//合并  需要两个有序序列merge(v1.begin(), v1.end(), v2.begin(), v2.end(), vtarget.begin());for_each(vtarget.begin(), vtarget.end(), myPrint());cout << endl;
}int main() {test01();system("pause");return 0;
}
123456789101112131415161718192021222324252627282930313233343536373839

4.3.4 reverse

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

#include <algorithm>
#include <vector>class myPrint
{
public:void operator()(int val){cout << val << " ";}
};void test01()
{vector<int> v;v.push_back(10);v.push_back(30);v.push_back(50);v.push_back(20);v.push_back(40);cout << "反转前： " << endl;for_each(v.begin(), v.end(), myPrint());cout << endl;cout << "反转后： " << endl;reverse(v.begin(), v.end());for_each(v.begin(), v.end(), myPrint());cout << endl;
}int main() {test01();system("pause");return 0;
}
12345678910111213141516171819202122232425262728293031323334353637383940

4.4 常用拷贝和替换算法

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

4.4.1 copy

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

#include <algorithm>
#include <vector>class myPrint
{
public:void operator()(int val){cout << val << " ";}
};void test01()
{vector<int> v1;for (int i = 0; i < 10; i++) {v1.push_back(i + 1);}vector<int> v2;v2.resize(v1.size());copy(v1.begin(), v1.end(), v2.begin());for_each(v2.begin(), v2.end(), myPrint());cout << endl;
}int main() {test01();system("pause");return 0;
}
12345678910111213141516171819202122232425262728293031323334

4.4.2 replace

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

#include <algorithm>
#include <vector>class myPrint
{
public:void operator()(int val){cout << val << " ";}
};void test01()
{vector<int> v;v.push_back(20);v.push_back(30);v.push_back(20);v.push_back(40);v.push_back(50);v.push_back(10);v.push_back(20);cout << "替换前：" << endl;for_each(v.begin(), v.end(), myPrint());cout << endl;//将容器中的20 替换成 2000cout << "替换后：" << endl;replace(v.begin(), v.end(), 20,2000);for_each(v.begin(), v.end(), myPrint());cout << endl;
}int main() {test01();system("pause");return 0;
}
123456789101112131415161718192021222324252627282930313233343536373839404142

4.4.3 replace_if

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

#include <algorithm>
#include <vector>class myPrint
{
public:void operator()(int val){cout << val << " ";}
};class ReplaceGreater30
{
public:bool operator()(int val){return val >= 30;}};void test01()
{vector<int> v;v.push_back(20);v.push_back(30);v.push_back(20);v.push_back(40);v.push_back(50);v.push_back(10);v.push_back(20);cout << "替换前：" << endl;for_each(v.begin(), v.end(), myPrint());cout << endl;//将容器中大于等于的30 替换成 3000cout << "替换后：" << endl;replace_if(v.begin(), v.end(), ReplaceGreater30(), 3000);for_each(v.begin(), v.end(), myPrint());cout << endl;
}int main() {test01();system("pause");return 0;
}
12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152

4.4.4 swap

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

#include <algorithm>
#include <vector>class myPrint
{
public:void operator()(int val){cout << val << " ";}
};void test01()
{vector<int> v1;vector<int> v2;for (int i = 0; i < 10; i++) {v1.push_back(i);v2.push_back(i+100);}cout << "交换前： " << endl;for_each(v1.begin(), v1.end(), myPrint());cout << endl;for_each(v2.begin(), v2.end(), myPrint());cout << endl;cout << "交换后： " << endl;swap(v1, v2);for_each(v1.begin(), v1.end(), myPrint());cout << endl;for_each(v2.begin(), v2.end(), myPrint());cout << endl;
}int main() {test01();system("pause");return 0;
}1234567891011121314151617181920212223242526272829303132333435363738394041424344

4.5 常用算术生成算法

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

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

4.5.1 accumulate

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

#include <numeric>
#include <vector>
void test01()
{vector<int> v;for (int i = 0; i <= 100; i++) {v.push_back(i);}int total = accumulate(v.begin(), v.end(), 0);cout << "total = " << total << endl;
}int main() {test01();system("pause");return 0;
}
12345678910111213141516171819202122

4.5.2 fill

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

#include <numeric>
#include <vector>
#include <algorithm>class myPrint
{
public:void operator()(int val){cout << val << " ";}
};void test01()
{vector<int> v;v.resize(10);//填充fill(v.begin(), v.end(), 100);for_each(v.begin(), v.end(), myPrint());cout << endl;
}int main() {test01();system("pause");return 0;
}
123456789101112131415161718192021222324252627282930313233

4.6 常用集合算法

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

4.6.1 set_intersection

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

#include <vector>
#include <algorithm>class myPrint
{
public:void operator()(int val){cout << val << " ";}
};void test01()
{vector<int> v1;vector<int> v2;for (int i = 0; i < 10; i++){v1.push_back(i);v2.push_back(i+5);}vector<int> vTarget;//取两个里面较小的值给目标容器开辟空间vTarget.resize(min(v1.size(), v2.size()));//返回目标容器的最后一个元素的迭代器地址vector<int>::iterator itEnd = set_intersection(v1.begin(), v1.end(), v2.begin(), v2.end(), vTarget.begin());for_each(vTarget.begin(), itEnd, myPrint());cout << endl;
}int main() {test01();system("pause");return 0;
}
123456789101112131415161718192021222324252627282930313233343536373839404142

4.6.2 set_union

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

#include <vector>
#include <algorithm>class myPrint
{
public:void operator()(int val){cout << val << " ";}
};void test01()
{vector<int> v1;vector<int> v2;for (int i = 0; i < 10; i++) {v1.push_back(i);v2.push_back(i+5);}vector<int> vTarget;//取两个容器的和给目标容器开辟空间vTarget.resize(v1.size() + v2.size());//返回目标容器的最后一个元素的迭代器地址vector<int>::iterator itEnd = set_union(v1.begin(), v1.end(), v2.begin(), v2.end(), vTarget.begin());for_each(vTarget.begin(), itEnd, myPrint());cout << endl;
}int main() {test01();system("pause");return 0;
}
1234567891011121314151617181920212223242526272829303132333435363738394041

4.6.3 set_difference

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

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

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

#include <vector>
#include <algorithm>class myPrint
{
public:void operator()(int val){cout << val << " ";}
};void test01()
{vector<int> v1;vector<int> v2;for (int i = 0; i < 10; i++) {v1.push_back(i);v2.push_back(i+5);}vector<int> vTarget;//取两个里面较大的值给目标容器开辟空间vTarget.resize( max(v1.size() , v2.size()));//返回目标容器的最后一个元素的迭代器地址cout << "v1与v2的差集为： " << endl;vector<int>::iterator itEnd = set_difference(v1.begin(), v1.end(), v2.begin(), v2.end(), vTarget.begin());for_each(vTarget.begin(), itEnd, myPrint());cout << endl;cout << "v2与v1的差集为： " << endl;itEnd = set_difference(v2.begin(), v2.end(), v1.begin(), v1.end(), vTarget.begin());for_each(vTarget.begin(), itEnd, myPrint());cout << endl;
}int main() {test01();system("pause");return 0;
}

完结散花🎉🎉🎉

文章知识点与官方知识档案匹配，可进一步学习相关知识