12、C++模板和标准模板库 STL_c++不可以使用标准模板是什么意思-CSDN博客

本文链接：https://blog.csdn.net/mzpmzk/article/details/57416462

一、C++ 模版

模板用于表达逻辑结构相同，但具体数据元素类型不同的数据对象的通用行为，属于泛型程序设计，优势在于能够减少重复代码的编写
模板把函数或类要处理的数据类型参数化（用一个虚拟的类型来代表），表现为参数的多态性
在调用函数或类时系统会根据实参的类型来取代模板中的虚拟类型，从而实现不同函数的功能，避免创建多个类型的函数或类
一般模板的 声明和定义 都放到头文件中

1、类型别名模板

// 类型别名模板，std::unique_ptr 定义一个带有自定义删除器 samplesCommon::InferDeleter 的类型别名
template <typename T>   // T 是一个模板参数
using SampleUniquePtr = std::unique_ptr<T, samplesCommon::InferDeleter>;

2、函数模板

所谓函数模板，实际上是建立一个通用函数，它所用到的数据的类型（包括返回值类型、形参类型、局部变量类型）可以不具体指定，而是用一个虚拟的类型来代替（实际上是用一个标识符来占位），等发生函数调用时再根据传入的实参来逆推出真正的类型。这个通用函数就称为函数模板（Function Template）

// 一、函数模板定义及使用
#include <iostream>
using namespace std;

// 告诉编译器紧跟的代码里出现虚拟类型 T（也可以是其它名字） 不要报错，T 是一个通用的类型
// template<class/typename T1, class/typename T2 ....> ，可定义多个 class/typename
template<class/typename T>  // class 和 typename 效果一样，但为了跟类区分，一般用 typename 好点
void MySwap(T &a, T &b) {   // void mySort(T arr[], int len)，可以部分参数使用通用类型 T，部分使用普通类型
    T temp = a;             
    a = b;
    b = temp;
}

int main() {
    int a = 10;
    int b = 20;
    cout << "a:" << a << " b:" << b << endl;  // a:10 b:20
    MySwap(a, b);  // 函数模板可以自动推导参数的类型，按照 a、b 的类型来替换 T
    cout << "a:" << a << " b:" << b << endl;  // a:20 b:10

    char c1 = 'a';
    char c2 = 'b';
    cout << "c1:" << c1 << " c2:" << c2 << endl;  // c1:a c2:b
    MySwap<char>(c1, c2);  // 函数模板可以自动推导参数的类型，也可以显式指定类型
    cout << "c1:" << c1 << " c2:" << c2 << endl;  // c1:b c2:a
    return 0;
}

-------------------------------------------------------------------------------------
// 二、 函数模板与普通函数的区别以及调用规则
#include<iostream>
using namespace std;

// 1、普通函数与函数模板区别：普通函数可以进行隐式类型转换，函数模版不可以
template<class T>
T myPlus(T a, T b) {
    return a + b;
}

int myPlus(int a, int b) {
    return a + b;
}

void test01() {
    int a = 10;
    int b = 20;
    char c = 'c';     // a = 97
    // myPlus(a, c);  // 类型推导不出来，函数模板不可以进行隐式类型转换
    cout << myPlus(a, c) << endl; // 10+99=109，普通函数可以进行隐式类型转换
}


// 2、普通函数和函数模板的调用规则
template<class T>
void myPrint(T a, T b) {
    cout << "模板调用 myPrint" << endl;
}

// 函数模板重载
template<class T>
void myPrint(T a, T b, T c) {
    cout << "模板调用 myPrint(a,b,c)" << endl;
}

// 普通函数
void myPrint(int a, int b) {
    cout << "普通函数调用 myPrint" << endl;
}

void test02() {
    int a = 10;
    int b = 20;

    // 2.1 如果出现重载优先使用普通函数调用
    myPrint(a, b);     // 普通函数调用 myPrint

    // 2.2 如果想强制调用模板，可以使用空模板实参列表限定编译器只能通过模板匹配
    myPrint<>(a, b);   // 模板调用 myPrint

    // 2.3 函数模板可以发生重载
    int c = 30;
    myPrint(a, b, c);  // 模板调用 myPrint(a,b,c)

    // 2.4 如果函数模板可以产生更好的匹配，那么优先调用函数模板
    char d = 'd';
    char e = 'e';
    myPrint(d, e);     // 模板调用 myPrint

}

int main() {
    test01();
    test02();
    return 0;
}

-------------------------------------------------------------------------------------
// 三、模板的局限性及机制
// 3.1 模板并不是万能的，不能通用所有的数据类型
// 3.2 模板不能直接调用，通过具体类型生成的模板函数才可以调用
// 3.2 编译器会对函数模板进行两次编译，第一次在声明的地方对模板代码本身进行编译，
//     第二次在调用时对替换 T 类型后的代码进行编译
#include<iostream>
#include <string>
using namespace std;

class Person {
public:
    Person(string name, int age) {
        this->m_Name = name;
        this->m_Age = age;
    }

    string m_Name;
    int m_Age;
};


template<class T>
bool myCompare(T &a, T &b) {
    if (a == b) {
        return true;
    }
    return false;
}

// 通过第三代具体化自定义数据类型，解决类的类型匹配问题，具体化优先于常规模板
// 语法： template<> 返回值 函数名<具体类型>(参数)
template<>
bool myCompare<Person>(Person &a, Person &b) {
    if (a.m_Age == b.m_Age) {
        return true;
    }

    return false;
}

int main() {
    int a = 10;
    int b = 20;
    int ret1 = myCompare(a, b);
    cout << "ret1 = " << ret1 << endl;  // ret1 = 0

    Person p1("Tom", 10);
    Person p2("Jerry", 10);
    int ret2 = myCompare(p1, p2);
    cout << "ret2 = " << ret2 << endl;  // ret2 = 1
    
    return 0;
}

3、类模板

类模板和函数模板的定义和使用类似，主要区别如下：
类模板可以有默认类型参数，而函数模板不可以（C++11 及以后的标准支持为函数模板中的参数设置默认值）
类模板不可以进行自动类型推导（需要显示指定参数类型），而函数模板可以

// 一、类模板定义及使用
#include <iostream>
#include <string>
using namespace std;

// 类模板声明：template<class/typename T1， class/typename T2 ....> ，可定义多个 class/typename
template<class NameType, class AgeType=int>  // 类模板可以有默认参数类型
class Person {
public:
    Person(NameType name, AgeType age) {
        this->m_Name = name;
        this->m_Age = age;
    }

    void showPerson() {
        cout << "姓名：" << this->m_Name << " 年龄：" << this->m_Age << endl;
    }

    NameType m_Name;
    AgeType m_Age;
};

int main() {
    // Person p("孙悟空", 100);            // 类模板不支持类型自动推导
    Person<string, int> p("孙悟空", 100);  // 需要显示指定参数类型
    p.showPerson();                       // 姓名：孙悟空 年龄：100
    return 0;
}

-------------------------------------------------------------------------------------
// 二、 类模板做函数参数
// 1、类模板做函数参数：显式指定类型
void doWork1(Person<string, int> &p) {
    p.showPerson();
}

// 2、类模板做函数参数：参数模板化
template<class T1, class T2>
void doWork2(Person<T1, T2> &p) {
    p.showPerson();
}

// 3、类模板做函数参数：整体模板化
template<class T>
void doWork3(T &p) {
    p.showPerson();
}

int main() {
    Person<string, int> p1("小学生", 12);
    doWork1(p1);  // 姓名：小学生 年龄： 12

    Person<string, int> p2("中学生", 18);
    doWork2(p2);  // 姓名：中学生 年龄： 18

    Person<string, int> p3("大学生", 22);
    doWork3(p3);  // 姓名：大学生 年龄： 22
    return 0;
}

-------------------------------------------------------------------------------------
// 三、 类模板派生普通类
template<class T>  // 父类模板
class MyClass {
public:
    MyClass(T property) {
        this->mProperty = property;
    }

public:
    T mProperty;
};


// 普通派生类
class SubClass : public MyClass<int> {   // 子类实例化的时候需要知道父类的具体类型(自动调用父类的构造函数)，
public:                                  // 这样编译器才能知道给子类分配多少内存
    SubClass(int b) : MyClass<int>(20) {
        this->mB = b;
    }

public:
    int mB;
};

-------------------------------------------------------------------------------------
// 四、 类模板派生类模板
template<class T>  // 父类类模板
class Base {
public:
    T m;
};

template<class T>  // 派生类模板
class Child : public Base<double> {
public:
    T mParam;
};

Child<int> ch;    // 派生类实例化

-------------------------------------------------------------------------------------
// 五、 类模板类内和类外实现
#include <iostream>
#include <string>

using namespace std;

template<class T1, class T2>
class Person {
public:
    Person(T1 name, T2 age);  // 声明处加上分号
//    {
//    	this->m_Name = name;  // 类内实现
//    	this->m_Age = age;
//    }

    void showPerson();  // 声明处加上分号
//    {
//    	cout << "姓名：" << this->m_Name << " 年龄：" << this->m_Age << endl;  // 类内实现
//    }

    T1 m_Name;
    T2 m_Age;
};

// 类外实现构造函数 Person：在类外定义成员函数时仍然需要带上模板头
template<class T1, class T2>
Person<T1, T2>::Person(T1 name, T2 age) {
    this->m_Name = name;
    this->m_Age = age;
}

// 类外实现成员函数 showPerson：在类外定义成员函数时仍然需要带上模板头
template<class T1, class T2>
void Person<T1, T2>::showPerson() {
    cout << "姓名：" << this->m_Name << " 年龄：" << this->m_Age << endl;  
}

int main() {
    Person<string, int> p("Han", 18);
    Person<string, int> *p1 = new Person<string, int>("Man", 18);  // 使用对象指针的方式来实例化
    p.showPerson();    // 姓名：Han 年龄：18
    p1->showPerson();  // 姓名：Man 年龄：18
    return 0;
}

-------------------------------------------------------------------------------------
// 六、 类模板头文件和源文件分离问题
// 问题：主程序中只包含类模板头文件(.h)会导致无法解析外部命令
// 原因：类模板需要二次编译，在出现模板的地方编译一次，在调用模板的地方再次编译（即：类模板的成员函数运行阶段才去创建）
//      C++ 编译规则为独立编译(.h 和 .cpp 独立编译)，包含.h 头文件，不会创建函数的实现
// 解决：类模板的声明和实现放到一个文件中，并把这个文件命名为 .hpp（文件头部加入 #pragma once，防止被重复包含)

-------------------------------------------------------------------------------------
// 七、 模板类碰到友元函数
template<class T1 ,class T2>
class Person
{
	// 友元函数类内实现
	friend void printPerson(Person<T1 ,T2> & p)
	{
		cout << "姓名：" << p.m_Name << " 年龄：" << p.m_Age << endl;
	}
public: 
	Person(T1 name, T2 age)
	{
		this->m_Name = name;
		this->m_Age = age;
	}

private:
	T1 m_Name;
	T2 m_Age;
};

二、标准模板库 STL(Standard Template Library)

STL 基本概念：

STL 是为了建立数据结构和算法的一套标准
降低他们之间的耦合关系(数据和操作分离)，数据由容器加以管理，操作则由可定制的算法定义
提升各自的独立性、弹性、交互操作性（迭代器在容器和算法之间充当“粘合剂”，以使它们交互运作）

STL 提供了 6 大组件，分别为：容器(container)、算法(algorithm)、迭代器(iterator)、仿函数、适配器、空间配置器；
容器通过 空间配置器 取得数据存储空间
算法通过 迭代器 存储容器中的内容
仿函数 可以协助算法完成不同的策略的变化
适配器 可以修饰 仿函数

STL 几乎所有的代码都采用了函数模板或类模板，相比传统的由函数和类组成的库提供了更好的代码重用机会，且一般支持 C++ 的编译器都带了 STL 的支持

STL 使用注意事项：

STL的头文件一般都是不带 .h 后缀的，eg: #include <vector> // 不是vector.h
STL 使用命名空间 std, 因此要把此前缀去掉的话，要使用using namespace std;

1、容器

用来存放特定排列方式的数据（以利于搜索或排序等），包含各种数据结构，如 vector、deque、string、stack、queue、list、pair、map、set 等
从实现角度来看，STL 容器是一种类模板(class template)
set / map / multiset / multimap 底层使用红黑树实现, unordered_xxx 底层使用 hash 表实现

在这里插入图片描述

a、vector

vector 是数组(连续存储)和链表(跳跃存储)的结合体：
- vector 设计之初即是为了改善 C 语言原生数组的种种缺失与不便（可复制、可在运行期动态改变元素个数），提供一种更有效、更安全的数组
- vector 的使用接口刻意模拟 C 语言原生数组，较明显的差异在于存储器管理，原生数组必须在声明数组的时候明确指定数组长度(例如 int a[5])，但是 vector 不需要指定，而是会在运行期依据状况自我调整长度，动态增大容量（capacity），本质是一个动态数组
- vector 在数据量不大的情况下，非常方便存储和访问操作；在数据量大的情况下，查找效率低，删除操作还会导致大量的数组移动操作
- vector 使用时，最好给它一个初始化大小，避免更多的内存申请动作和移动操作
vector 的定义：
- #include <vector> std::vector<T> arr; ，声明一个 vector 容器对象，这个容器中存放的是 T 类型的数据，对象的名称是 arr
- T* c_arr = arr.data() 或 auto c_arr= arr.data()：转换为 C 类型的指针
vector 成员函数概览：
vector 的使用：

#include<iostream>
#include <vector>
using namespace std;


// 1、vector 初始化
vector<int> v = {1, 2, 3, 4, 5};  // C++ 11 以后支持此种初始化方式
vector<int> v{1, 2, 3, 4, 5};  // C++ 11 以后支持此种初始化方式
vector<int> v1(5, 3);  // 指定值 3 进行初始化（5 个 3），若第二个参数不指定，默认为 0
vector<int> v1(5);  // 默认初始化（5 个 0）
vector<int> v1(v); // 拷贝构造进行初始化，等价于 vector<int> v1 = v; v1 是 v 的引用
vector<int> v1(v.begin() + 1, v.end() - 1); // 将 v[begin()-1, end()-1) 区间中的元素拷贝给本身
vector<int> v1(arr, arr + sizeof(arr) / sizeof(int));  // int arr[] = {2, 3, 4, 1, 9};

// 2、巧用 shrink_to_fit 方法收缩空间
void test() {
    vector<int> v;
    for (int i = 0; i < 100; i++) {
        v.push_back(i);
    }

    cout << "v 的容量 " << v.capacity() << endl;  // v 的容量 128
    cout << "v 的大小 " << v.size() << endl;  // v 的大小 100
    
    // 重置 vector 的大小
    v.resize(3);
    cout << "v 的容量 " << v.capacity() << endl;  // v 的容量 128
    cout << "v 的大小 " << v.size() << endl;  // v 的大小 3

    // 巧用 shrink_to_fit() 方法收缩空间
    v.shrink_to_fit();
    cout << "v 的容量 " << v.capacity() << endl;  // v 的容量 3
    cout << "v 的大小 " << v.size() << endl;  // v 的大小 3
}


// 3、使用 reserve 方法提前预留空间，减少内存开辟次数
void test() {
    vector<int> v;
    v.reserve(100000);  // 提前预留出空间

    int *p = NULL;
    int num = 0;
    for (int i = 0; i < 100000; i++) {
        v.push_back(i);
        if (p != &v[0]) {
            p = &v[0];
            num++;
        }
    }
    cout << num << endl;  // 开辟 100000 数据用了多少次：不提前预留空间，大概 18 次；提前预留空间后只需 1 次
}

// 4、vector 插入和删除操作
void test() {
    vector<int> v;
    v.push_back(10);
    v.push_back(30);
    v.push_back(20);
    v.push_back(50);
    cout << "v front " << v.front() << endl;  // v front 10
    cout << "v back " << v.back() << endl;  // v back 50

    // insert(const_iterator pos, int count,ele); 向迭代器指向位置 pos 插入 count 个元素 ele
    v.insert(v.begin(), 2, 100); // 参数 1：迭代器，插入的位置；参数2：N个数；参数3：具体插入的内容(100 100 10 30 20 50)
    v.insert(v.begin(), 100); // 参数 1：迭代器，插入的位置  参数2：具体插入的内容(100 10 30 20 50)
    v.pop_back(); // 尾删(100 100 10 30 20)

    // erase(const_iterator pos);// 删除迭代器指向位置 pos 处的元素
    v.erase(v.begin()); // 删除(100 10 30 20)
    
    // erase(const_iterator start, const_iterator end);// 删除迭代器指向位置 start 到 end 之间的元素
    v.erase(v.begin()+1, v.end()-1);  // 100 20
    
    // 清空所有数据
    v.clear();
}


// 5、顺序和逆序迭代器：iterator 和 reverse_iterator
// 取值范围：左闭右开 [ )
for (vector<int>::iterator it = v.begin(); it != v.end(); it++) {
    cout << *it << " ";
}
// 取值范围：左开右闭 ( ]
for (vector<int>::reverse_iterator it = v.rbegin(); it != v.rend(); it++) {
    cout << *it << " ";
}
// 简化版本
for (auto it = v.begin(); it != v.end(); it++) {
    cout << *it << " ";
}
for (auto it = v.rbegin(); it != v.rend(); it++) {
    cout << *it << " ";
}

// 极简版本：使用 range for 循环遍历容器中的元素
for (auto& each_element: v) {
    cout << each_element << " ";
}


vector<int>::iterator it1;  // it1 的类型其实就相当于 int* 指针（实际为 vector<int, allocator>::iterator）
vector<Teacher>::iterator it2;  // it2 的类型其实就相当于 Teacher* 指针

// 6、vector 元素互换
v1.swap(v2);   // v2 的元素与 v1 互换

b、deque

deque 和 vector 用法基本相同，不同点主要有：
增加了头部插入和删除
没有容量的概念（它是动态的以分段连续空间组合而成,随时可以增加一段新的空间并链接起来），换句话说：像 vector 那样（旧空间不足而重新配置一块更大空间，然后复制元素，再释放旧空间）这样的事情在 deque 身上是不会发生的。也因此，deque 没有必须要提供所谓的空间保留(reserve) 功能
缓冲区才是 deque 的存储空间的主体

在这里插入图片描述

#include <iostream>
#include <deque>
using namespace std;

// 1、deque 构造函数
deque<T> v{};  
deque<T> v = {};          
deque(beg, end);          // 构造函数将[beg, end)区间中的元素拷贝给本身
deque(n, elem);           // 构造函数将 n 个 elem 拷贝给本身
deque(const deque &deq);  // 拷贝构造函数

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

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

// 4、deque 双端插入和删除操作
push_back(elem);   // 在容器尾部添加一个数据
push_front(elem);  // 在容器头部插入一个数据
pop_back();        // 删除容器最后一个数据
pop_front();       // 删除容器第一个数据

// 5、deque 数据存取
at(idx);     // 返回索引 idx 所指的数据,如果 idx 越界,抛出 out_of_range。
operator[];  // 返回索引 idx 所指的数据,如果 idx 越界,不抛出异常,直接出错。
front();     // 返回第一个数据
back();      // 返回最后一个数据

// 6、deque 插入操作(其中 pos 为一个迭代器)
insert(pos, elem);     // 在 pos 位置插入一个 elem 元素的拷贝,返回新数据的位置。
insert(pos, n, elem);   // 在 pos 位置插入 n 个 elem 数据,无返回值。
insert(pos, beg, end);  // 在 pos 位置插入[beg,end)区间的数据,无返回值。

// 7、deque 删除操作(其中 pos 为一个迭代器)
clear();           // 移除容器的所有数据
erase(beg, end);   // 删除[beg,end)区间的数据,返回下一个数据的位置
erase(pos);        // 删除 pos 位置的数据,返回下一个数据的位置

c、string

string本质上是以字符作为元素的vector特化版本；不存在 0 字符结尾这个概念，能装入 '\0' 这种数据
string 和 C 风格字符串对比：
string 是一个类，char* 是一个指针，string 封装了 char*，管理这个字符串，是一个 char* 型的容器
string 封装了很多实用的成员方法，如查找(find)、拷贝(copy)、删除(delete) 、替换(replace)、插入(insert)
string 不用考虑内存释放和越界，它管理 char* 所分配的内存（由 string 类负责维护）

可以用c_str()函数来获取 string 内部的字符串指针，返回 const char*

#include<iostream>
#include <string>
using namespace std;

// 1、string 构造函数
string();                   // 创建一个空的字符串，eg: string str()/str{}/str=" "/str; 
string(const string& str);  // 使用一个 string 对象初始化另一个 string 对象，eg: string str1(str); 
string(const char* s);      // 使用字符串 s 初始化，eg: string str = "hello";
string(int n, char c);      // 使用 n 个字符 c 初始化，eg: string str(10, 'a'); 
std::string sEncryptKey;   // 默认会创建一个空的字符串, 不加大括号初始化也可以
std::vector<std::string> vsInputNames;  // 会默认初始化为一个空的 std::vector，{length 0, capacity 0}

// 2、string 基本赋值操作
string& operator=(const char* s);      // char* 类型字符串 赋值给当前的字符串
string& operator=(const string &s);    // 把字符串 s 赋给当前的字符串
string& operator=(char c);             // 字符赋值给当前的字符串
string& assign(const char *s);         // 把字符串 s 赋给当前的字符串
string& assign(const char *s, int n);  // 把字符串 s 的前 n 个字符赋给当前的字符串
string& assign(const string &s);       // 把字符串 s 赋给当前字符串
string& assign(int n, char c);         // 用 n 个字符 c 赋给当前字符串
string& assign(const string &s, int start, int n);  // 将 s 从 start 开始 n 个字符赋值给字符串


// 3、sring 存取字符及大小操作
char& operator[](int n);  // 通过 [] 方式取字符
char& at(int n);          // 通过 at 方法获取字符
front();  // 返回第一个数据
back();   // 返回最后一个数据
size()/length();             // 返回容器中元素的个数
empty();            // 判断容器是否为空
resize(num);        // 重新指定容器的长度为 num,若容器变长,则以默认值填充新位置。如果容器变短,则末尾超出容器长度的元素被删除
resize(num, elem);  // 重新指定容器的长度为 num,若容器变长,则以 elem 值填充新位置,如果容器变短,则末尾超出容器长度的元素被删除
shrink_to_fit()   // 巧用 shrink_to_fit() 方法收缩空间
reserve()   // 使用 reserve 方法提前预留空间，减少内存开辟次数

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


// 5、string 查找和替换(找到返回第一次出现的位置，找不到返回 -1), int pos = s.find("str");
int find(const string& str, int pos = 0) const;  // 查找 str 第一次出现位置,从 pos 开始查找
int find(const char* s, int pos = 0) const;      // 查找 s 第一次出现位置,从 pos 开始查找
int find(const char* s, int pos, int n) const;   // 从 pos 位置查找 s 的前 n 个字符第一次位置
int find(const char c, int pos = 0) const;       // 查找字符 c 第一次出现位置
int rfind(const string& str, int pos = npos) const;  // 查找 str 最后一次位置,从 pos 开始查找
int rfind(const char* s, int pos = npos) const;      // 查找 s 最后一次出现位置,从 pos 开始查找
int rfind(const char* s, int pos, int n) const;      // 从 pos 查找 s 的前 n 个字符最后一次位置
int rfind(const char c, int pos = 0) const;          // 查找字符 c 最后一次出现位置
string& replace(int pos, int n, const string& str);  // 替换从 pos 开始 n 个字符为字符串 str（str 中字符个数可以大于 n）
string& replace(int pos, int n, const char* s);      // 替换从 pos 开始的 n 个字符为字符串 s


// 6、string 比较操作
int compare(const string &s) const; // 与字符串 s 比较，函数在 > 时返回 1, < 时返回 -1, == 时返回 0
int compare(const char *s) const;   // 与字符串 s 比较，比较区分大小写，比较时参考字典顺序，排越前面的越小


// 7、string 子串(可结合 find 使用，实现特定功能)
// Return：string containing the substring [pos, pos+count) or [pos, size())
string substr(int pos = 0, int n) const;  // 返回由 pos 开始的 n 个字符组成的字符串
string email = "zhangxia@qq.com";
int pos = email.find("@"); // 8
string userName = email.substr(0, pos);  // the part till @
string domainName = email.substr(pos + 1); // the part after @  

// 8、string 插入和删除操作(其中 pos 为一个迭代器)
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);       // 删除从 pos 开始的 n 个字符
pop_back();        // 删除容器最后一个数据
push_back();       // 在容器尾部添加一个数据

// 9、string 和 c-style 字符串转换
string s1 = "itcast";
const char* cstr = s1.c_str();  // string 转 const char*，不可进行隐式类型转换
char* s = "hello"; 
string s2(s);       // char* 转 string，可进行隐式类型转换
string s2(cstr);    // const char* 转 string，可进行隐式类型转换


// 10、使用 empty() 方法判断字符串是否为空
std::string str;
if (str.empty()) {
    std::cout << "字符串为空。" << std::endl;
} else {
    std::cout << "字符串非空。" << std::endl;
}

d、stack

stack 是一种 后进先出 的数据结构，如下图所示
stack 容器允许新增(push)、移除(pop)、取得(top)栈顶元素
Stack 不提供遍历功能，也不提供迭代器

在这里插入图片描述

//  stack 采用模板类实现，常用 api 如下：
stack<T> stkT;                       // stack 对象的默认构造形式，不能使用 stack<int> s = {10, 20}; 这种方式初始化
stack(const stack &stk);             // 拷贝构造函数
stack& operator=(const stack &stk);  // 重载等号操作符
push(elem);  // 向栈顶添加元素
pop();       // 从栈顶移除第一个元素
top();       // 返回栈顶元素
empty();     // 判断堆栈是否为空
size();      // 返回堆栈的大小

e、queue

queue 是一种 先进先出 的数据结构，如下图所示
queue 容器允许从队尾新增元素(push)，从队头移除元素(pop)
queue 不提供遍历功能，也不提供迭代器

在这里插入图片描述

//  queue 采用模板类实现，常用 api 如下：
queue<T> queT;                       // queue 对象的默认构造形式，不能使用 queue<int>q = {10, 20}; 这种方式初始化
queue(const queue &que);             // 拷贝构造函数
queue& operator=(const queue &que);  // 重载等号操作符
push(elem);  // 往队尾添加元素
pop();       // 从队头移除第一个元素
back();      // 返回最后一个元素
front();     // 返回第一个元素
empty();     // 判断队列是否为空
size();      // 返回队列的大小

f、list

list 内部用循环的双向链表来实现，内部元素内存各处，互相以 link串接起来，每个元素都只知道其前一个元素以及下一个元素的位置。故要遍历整个list，必须从第一个元素开始逐个往下寻访(顺序链式访问，所以只能使用迭代器进行遍历)不支持随机存取(Random Access)。
list 的强项是高效的插入以及删除，list插入或删除时只需要改动元素的link字段，不需要搬动元素，相对vector等要高效
list 在经常需要于集合内部任意位置(即除了头尾以外的其他位置) 频繁增删元素的工作上表现优秀。若仅需要于集合尾端增删元素，那应该优先考虑vector容器，若仅于头尾二端增删元素，那应该优先考虑deque容器。
list的使用：std::list<T> mylist;
list链表中插入/删除一个节点
- 遍历 list，找到目标位置
- 调用insert/erase，插入/删除一个节点

// list 的遍历及删除值为 3 的节点
for (list<int>::iterator iter = lst.begin(); iter != lst.end(); iter++)
{
	int& value = *iter;
	cout << value << endl;
	
	if (value == 3)  // 若为中间节点，则后面数据的不能访问
	{
		lst.erase(iter);
	}
}

// list 构造函数：采用采用模板类实现
list<T> lstT;   // list 对象的默认构造形式，可使用 list<int> lst = {1, 2}; 这种方式初始化
list(beg,end);  // 构造函数将[beg, end)区间中的元素拷贝给本身。
list(n,elem);   // 构造函数将 n 个 elem 拷贝给本身。
list(const list &lst);  // 拷贝构造函数

// list 数据元素插入和删除操作(其中 pos 为一个迭代器)
push_back(elem);      // 在容器尾部加入一个元素
push_front(elem);     // 在容器开头插入一个元素
pop_back();           // 删除容器中最后一个元素
pop_front();          // 从容器开头移除第一个元素
insert(pos,elem);     // 在 pos 位置插 elem 元素的拷贝,返回新数据的位置
insert(pos,n,elem);   // 在 pos 位置插入 n 个 elem 数据,无返回值
insert(pos,beg,end);  // 在 pos 位置插入[beg,end)区间的数据,无返回值
clear();              // 移除容器的所有数据
erase(beg,end);       // 删除[beg,end)区间的数据,返回下一个数据的位置
erase(pos);           // 删除 pos 位置的数据,返回下一个数据的位置
remove(elem);         // 删除容器中所有与 elem 值匹配的元素


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

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

// list 数据的存取
front();  // 返回第一个元素
back();   // 返回最后一个元素


// list 反转排序
reverse();  // 逆序排列 1, 5, 3 --> 3, 5, 1
sort();     // 从小到大排序 1, 3, 5

bool myCompare(int v1, int v2) {
    return v1 > v2; // 从大到小排序
}

list<int> L = {1, 5, 3};
L.reverse();               // 3 5 1
L.sort();                  // 1 3 5：从小到大排序 
L.sort(myCompare);         // 5 3 1：传入自定义函数实现从大到小排序

g、pair

对组(pair)将一对值组合成一个值，这一对值可以具有不同的数据类型，类似于 python 中的元组(tuple)
两个值可以分别用 pair 对象的两个公有属性 first 和 second 访问

// 创建对组(不需要额外引入头文件)
pair<string, int> p1("man", 20);
pair<string, int> p2 = make_pair("man", 20);

// 访问对组
cout << p1.first << endl;   // 访问 pair 第一个值
cout << p1.second << endl;  // 访问 pair 第二个值

h、map/multimap

在 map 存储中，是按照键值对来存储的 key-value，不允许两个元素有相同的 key
list使用遍历查找，但需要从头到尾，挨个对比，速度较慢；而 map 使用映射查找，速度很快（无论存储了多少数据，总是可以通过key值，直接检索到value的值）
multimap 和 map 的操作类似，唯一区别 multimap 键值可重复，底层实现均为红黑树，树中的每个结点是一个 std::pair，键 (pair.first) 需要支持使用 < 比较大小

在这里插入图片描述

// map 构造函数
map<T1, T2> mapTT;   // map 默认构造函数，eg: map<int, string> mapStu{{1, "man"}, {2, "han"}}; 
map(const map &mp);  // 拷贝构造函数

// map 赋值操作
map& operator=(const map &mp);  // 重载等号操作符
swap(mp);                       // 交换两个集合容器

// map 大小操作
size();   // 返回容器中元素的数目
empty();  // 判断容器是否为空

// map 插入数据元素操作
map.insert(...);  // 往容器插入元素,返回 pair<iterator,bool>
map<int, string> mapStu;
mapStu.insert(make_pair(-1, "校长"));   // 第一种，通过 make_pair 的方式插入，推荐                    
mapStu.insert(pair<int, string>(3, "小张"));  // 第二种，通过 pair 的方式插入
mapStu.insert(map<int, string>::value_type(1, "小李"));  // 第三种，通过 value_type 的方式插入对象
mapStu[2] = "小刘";  // 第四种，通过数组的方式插入值，推荐使用 
mapStu[5] = "小王";
// 打印 map 中的 key 和 value 值
for (map<int, string>::iterator it = mapStu.begin(); it != mapStu.end(); it++) {
    cout << "key=" << it->first << " value=" << it->second << endl;
}

// map 删除操作
clear();         // 删除所有元素
erase(pos);      // 删除 pos 迭代器所指的元素,返回下一个元素的迭代器
erase(beg,end);  // 删除区间[beg,end)的所有元素 ,返回下一个元素的迭代器
erase(keyElem);  // 删除容器中 key 为 keyElem 的对组

// map 查找操作
find(key);       // 查找键 key 是否存在,若存在,返回该键的元素的迭代器;若不存在,返回 map.end();
count(keyElem);  // 返回容器中 key 为 keyElem 的对组个数。对 map 来说,要么是 0,要么是 1;对multimap 来说,值可能大于 1
lower_bound(keyElem);  // 返回第一个 key>=keyElem 元素的迭代器
upper_bound(keyElem);  // 返回第一个 key>keyElem 元素的迭代器
equal_range(keyElem);  // 返回容器中 key 与 keyElem 相等的上下限的两个迭代器

// 查找 key 是否存在
map<int, string>::iterator pos = mapStu.find(2);
if (pos != mapStu.end()) {
    cout << "找到：key" << pos->first << " value:" << pos->second << endl;
} else {
    cout << "未找到" << endl;
}

i、set/multiset

set 中所有元素都会根据其值进行自动被排序，且不允许有两个相同元素存在，底层实现为红黑树
multiset 特性及用法和 set 完全相同，唯一的差别在于它允许相同元素的存在，底层实现为红黑树

在这里插入图片描述

// set 构造函数
set<T> st;           // set 默认构造函数，可使用 set<int> s = {5, 3, 1}; 此种方式初始化
mulitset<T> mst;     // multiset 默认构造函数， 
set(const set &st);  // 拷贝构造函数

// set 赋值操作
set& operator=(const set &st);  // 重载等号操作符
swap(st);                       // 交换两个集合容器

// set 大小操作
size();   // 返回容器中元素的数目
empty();  // 判断容器是否为空

// set 插入和删除操作
insert(elem);     // 在容器中插入元素，返回值类型为 pair<set<int>::iterator, bool>
clear();          // 清除所有元素
erase(pos);       // 删除 pos 迭代器所指的元素,返回下一个元素的迭代器
erase(beg, end);  // 删除区间[beg,end)的所有元素 ,返回下一个元素的迭代器
erase(elem);      // 删除容器中值为 elem 的元素

// set 查找操作
find(key);             // 查找键 key 是否存在,若存在,返回该键的元素的迭代器;若不存在,返回 set.end()
count(key);            // 查找键 key 的元素个数
lower_bound(keyElem);  // 返回第一个 key>=keyElem 元素的迭代器；未找到，返回 set.end()
upper_bound(keyElem);  // 返回第一个 key>keyElem 元素的迭代器；未找到，返回 set.end()
equal_range(keyElem);  // 返回容器中 key 与 keyElem 相等的上下限两个迭代器（lower_bound&upper_bound）

void test() {
    set<int> s1 = {1, 3, 5, 7, 9};
    set<int>::iterator pos = s1.find(3);

    // 判断是否找到
    if (pos != s1.end()) {
        cout << "找到了，值为：" << *pos << endl;  // 找到了，值为：3
    } else {
        cout << "未找到" << endl;
    }

    // 返回第一个 key>keyElem 元素的迭代器；未找到，返回 set.end()
    set<int>::iterator it = s1.lower_bound(3); // 未找到，返回 set.end()
    if (it != s1.end()) {
        cout << "找到了 lower_bound(3)的值为：" << *it << endl; // 3
    } else {
        cout << "未找到" << endl;
    }

    // 返回第一个 key>keyElem 元素的迭代器；未找到，返回 set.end()
    set<int>::iterator it2 = s1.upper_bound(3);
    if (it2 != s1.end()) {
        cout << "找到了 upper_bound(3) 的值为：" << *it2 << endl;  // 5
    } else {
        cout << "未找到" << endl;
    }

    // 返回容器中 key 与 keyElem 相等的上下限两个迭代器（lower_bound&upper_bound）
    pair<set<int>::iterator, set<int>::iterator> ret = s1.equal_range(3);

    // 获取第一个值(lower_bound)
    if (ret.first != s1.end()) {
        cout << "找到equal_range中 lower_bound 的值 ：" << *(ret.first) << endl;  // 3
    } else {
        cout << "未找到" << endl;
    }

    // 获取第二个值(upper_bound)
    if (ret.second != s1.end()) {
        cout << "找到equal_range中 upper_bound 的值 ：" << *(ret.second) << endl;  // 5
    } else {
        cout << "未找到" << endl;
    }

}

// set 容器，不允许插入重复的键值
void test() {
    set<int> s1;
    pair<set<int>::iterator, bool> ret = s1.insert(10);

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

    ret = s1.insert(10);
    if (ret.second) {
        cout << "第二次插入成功" << endl;
    } else {
        cout << "第二次插入失败" << endl;  // 第二次插入失败
    }
}


// set 的返回值：指定 set 排序规则

2、算法

以算法是以有限的步骤，解决逻辑或数学上的问题；从实现的角度来看，STL 算法是一种函数模板(function tempalte)
算法主要是由头文件<algorithm> <functional> <numeric>组成
<algorithm> 是所有 STL 头文件中最大的一个，常用算法如：比较、交换、查找、遍历、排序、复制、修改、反转、合并等等
<numeric> 体积很小，只包括在几个序列容器上进行的简单运算的模板函数
<functional> 定义了一些模板类，用以声明函数对象

a、常用遍历算法

/*
for_each(iterator beg, iterator end, _callback); 遍历容器元素 [beg, end)
@param beg 开始迭代器
@param end 结束迭代器
@param _callback 函数回调或者函数对象
@return 函数对象
*/

// 源码实现如下：
template<typename _InputIterator, typename _Function>
_Function for_each(_InputIterator __first, _InputIterator __last, _Function __f)
{
  for (; __first != __last; ++__first)
		__f(*__first);
  return _GLIBCXX_MOVE(__f);  // 返回函数对象
}

// 普通打印函数
void myPrintf(int v)
{
	cout << v <<  " ";
}

// 函数对象打印：跟类(class)的方式定义相比，省去了其中的 public 声明，效果一样
struct myPrint {
    void operator()(int v) {
        cout << v << " ";
        m_Count++;
    }

    int m_Count;
};

void test01() {
    vector<int> v = {0, 1, 2, 3, 4};
	for_each(v.begin() + 2, v.end() - 1, myPrintf);  // 传入普通函数名，输出 2, 3
    cout << endl;
    
	// 返回函数对象
    myPrint p = for_each(v.begin() + 2, v.end() - 1, myPrint());  // 传入函数对象，输出 2, 3
    cout << endl;
    cout << p.m_Count << endl;  // 输出 2，可以保持 m_Count 的状态
}


/*
transform(__first1, __last1, __result, __unary_op) 将一个容器中的值搬运到另一个容器中 
transform(__first1, __last1, __first2, __result, __binary_op) 将容器 1 和容器 2 中的元素相加放入到第三个容器中
@param __first1   源容器1开始迭代器
@param __last1    源容器1结束迭代器
@param __first2   源容器2开始迭代器
@param __result   目标容器开始迭代器
@param __callback 回调函数或者函数对象
@return           返回目标容器迭代器
Note: transform 不会给目标容器分配内存，所以需要我们提前分配好内存
*/

// 将一个容器中的值搬运到另一个容器中
class TransForm {
public:
    int operator()(int val) {
        return val + 10;
    }
};

void test02() {
    vector<int> v = {0, 1, 2, 3, 4};  // 原容器
    vector<int> vTarget;              // 目标容器
    vTarget.resize(v.size());         // 给 vTarget 开辟空间
    transform(v.begin(), v.end(), vTarget.begin(), TransForm());  // 将 v 中的元素搬运到 vTarget
    for_each(vTarget.begin(), vTarget.end(), [](int val) { cout << val << " "; });  // 输出 10 11 12 13 14
}

// 将容器 1 和容器 2 中的元素相加放入到第三个容器中
class TransForm2 {
public:
    int operator()(int val1, int val2) {
        return val1 + val2;
    }
};

void test03() {
    vector<int> v1 = {0, 1, 2, 3, 4};       // 原容器 1
    vector<int> v2 = {10, 11, 12, 13, 14};  // 原容器 2
    vector<int> vTarget;                    // 目标容器
    vTarget.resize(v1.size());              // 给 vTarget 开辟空间
    transform(v1.begin(), v1.end(), v2.begin(), vTarget.begin(), TransForm2());  // 将容器 1 和容器 2 中的元素相加放入到第三个容器中
    for_each(vTarget.begin(), vTarget.end(), [](int val) { cout << val << " "; });  // 输出 10 12 14 16 18
}

b、常用查找算法

/*
find(iterator beg, iterator end, value) 查找第一个匹配的元素
@param beg 容器开始迭代器
@param end 容器结束迭代器
@param value 需查找元素的值
@return 返回第一个匹配元素位置的迭代器，使用 distance(v.begin(), pos) 算法可获取 index（返回值类型 long）
*/
void test01() {
    vector<int> v = {0, 1, 2, 3, 4};
    vector<int>::iterator pos = find(v.begin(), v.end(), 2);
    if (pos != v.end()) {
        // find it index is：2; value is: 2
        cout << "find it index is：" << distance(v.begin(), pos) << "; value is: " << *pos << endl;
    } else {
        cout << "not find" << endl;
    }
}


/*
find_if(iterator beg, iterator end, _callback) 查找第一个满足条件的元素
@param beg 容器开始迭代器
@param end 容器结束迭代器
@param  _callback 回调函数或者谓词(返回bool类型的函数对象)
@return 返回第一个满足条件元素位置的迭代器
*/
class GreaterThenTwo {
public:
    bool operator()(int v) {
        return v > 2;
    }

};

void test02() {
    vector<int> v = {0, 1, 2, 3, 4};
    vector<int>::iterator pos = find_if(v.begin(), v.end(), GreaterThenTwo());
    if (pos != v.end()) {
        cout << "找到了数据：" << *pos << endl;  // 找到了数据：3
    } else {
        cout << "未找到" << endl;
    }
}


/*
adjacent_find(iterator beg, iterator end) 查找相邻重复元素
@param beg 容器开始迭代器
@param end 容器结束迭代器
@return 返回相邻元素的第一个位置的迭代器
*/
void test03() {
    vector<int> v = {0, 2, 2, 3, 4};
    vector<int>::iterator pos = adjacent_find(v.begin(), v.end());
    if (pos != v.end()) {
        cout << "找到了相邻重复元素为： " << *pos << endl;  // 找到了相邻重复元素为： 2
    } else {
        cout << "未找到" << endl;
    }
}


/*
binary_search(iterator beg, iterator end, value) 二分查找法
@param beg   容器开始迭代器
@param end   容器结束迭代器
@param value 查找的元素
@return bool 查找返回 true 否则 false
Note: 一般在排好序的容器中使用
*/
void test04() {
    vector<int> v = {0, 1, 2, 3, 4};
    bool ret = binary_search(v.begin(), v.end(), 4);
    if (ret) {
        cout << "找到了 4" << endl;  // 找到了 4
    } else {
        cout << "未找到" << endl;
    }
}



/*
count(iterator beg, iterator end, value) 统计元素出现次数
@param beg 容器开始迭代器
@param end 容器结束迭代器
@param  value
@return 返回元素个数(int)

count_if(iterator beg, iterator end, _callback) 按条件统计元素出现次数
@param beg 容器开始迭代器
@param end 容器结束迭代器
@param  _callback 回调函数或者谓词(返回 bool 类型的函数对象)
@return 返回元素个数(int)
*/
void test05() {
    vector<int> v = {0, 2, 2, 2, 4};
    int num = count(v.begin(), v.end(), 2);  // 2 的个数为 3
    cout << "2 的个数为 " << num << endl;

    num = count_if(v.begin(), v.end(), GreaterThenTwo());  // 大于 2 的个数为 1
    cout << "大于 2 的个数为 " << num << endl;
}

c、常用排序算法

/*
merge(iterator beg1, iterator end1, iterator beg2, iterator end2, iterator dest)  容器元素合并，并存储到另一容器中，源容器,必须是有序的
@param beg1  容器1开始迭代器
@param end1  容器1结束迭代器
@param beg2  容器2开始迭代器
@param end2  容器2结束迭代器
@param dest  目标容器开始迭代器
*/
void test01() {
    vector<int> v1 = {0, 1, 2};
    vector<int> v2 = {3, 4};
    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(), [](int v) { cout << v << " "; });  // 输出 0 1 2 3 4
}


/*
sort(iterator beg, iterator end, _callback)  容器元素从小到大进行排序
@param beg 容器开始迭代器
@param end 容器结束迭代器
@param _callback 回调函数或者谓词(返回 bool 类型的函数对象)，若不提供则默认从小到大排序
*/
bool myCompare(int v1, int v2) {
    return v1 > v2;  // 排序规则：从大到小排序
}

void test02() {
    vector<int> v1 = {5, 15, 3, 40, 7};

    sort(v1.begin(), v1.end());  // 从小到大排序
    for_each(v1.begin(), v1.end(), [](int val) { cout << val << " "; });  // 3 5 7 15 40
    cout << endl;

    sort(v1.begin(), v1.end(), greater<int>());  // 从大到小排序
    sort(v1.begin(), v1.end(), myCompare);       // 从大到小排序
    for_each(v1.begin(), v1.end(), [](int val) { cout << val << " "; });  // 40 15 7 5 3
    cout << endl;
}


/* 
random_shuffle(iterator beg, iterator end) 对指定范围内的元素随机调整次序
@param beg 容器开始迭代器
@param end 容器结束迭代器
Note: 
- 需要引入 ctime 头文件，在主程序中加入随机种子 srand((unsigned int) time(NULL));
- C++17 以后函数 random_shuffle 变为 shuffle
*/
void test03() {
    vector<int> v = {0, 1, 5, 8, 2};
    random_shuffle(v.begin(), v.end());
    for_each(v.begin(), v.end(), [](int val) { cout << val << " "; });
}


/* 
reverse(iterator beg, iterator end)  对指定范围内的元素进行逆序排列
@param beg 容器开始迭代器
@param end 容器结束迭代器
*/
void test04() {
    vector<int> v = {0, 1, 5, 8, 2};
    reverse(v.begin(), v.end());
    for_each(v.begin(), v.end(), [](int val) { cout << val << " "; });  // 输出 2 8 5 1 0 
}

d、常用拷贝和替换算法

/*
copy(iterator beg, iterator end, iterator dest) 将容器内指定范围的元素拷贝到另一容器中
@param beg  容器开始迭代器
@param end  容器结束迭代器
@param dest 目标起始迭代器
*/
void test01() {
    vector<int> v = {0, 1, 2, 3, 4};
    vector<int> vTarget;
    vTarget.resize(v.size());  // 为目标容器开辟空间，默认 0 填充

    copy(v.begin(), v.end(), vTarget.begin());
    for_each(vTarget.begin(), vTarget.end(), [](int val) { cout << val << " "; });  // 输出 0 1 2 3 4 
}


/*
replace(iterator beg, iterator end, oldvalue, newvalue) 将容器内指定的旧元素修改为新元素
@param beg 容器开始迭代器
@param end 容器结束迭代器
@param oldvalue 旧元素
@param oldvalue 新元素

replace_if(iterator beg, iterator end, _callback, newvalue) 将容器内满足条件的元素替换为新元素
@param beg 容器开始迭代器
@param end 容器结束迭代器
@param _callback函数回调或者谓词(返回 bool 类型的函数对象)
@param newvalue 新元素
*/
class GreatThanTwo {
public:
    bool operator()(int v) {
        return v > 2;
    }
};

void test02() {
    vector<int> v = {0, 1, 2, 3, 4};

    // 把容器中的 2 替换成 -1
    replace(v.begin(), v.end(), 2, -1);
    for_each(v.begin(), v.end(), [](int val) { cout << val << " "; });  // 输出 0 1 -1 3 4 
    cout << endl;

    // 把容器中所有大于 2 的数字都替换成 10
    replace_if(v.begin(), v.end(), GreatThanTwo(), 10);
    for_each(v.begin(), v.end(), [](int val) { cout << val << " "; });  // 输出 0 1 -1 10 10 
}


/*
swap(container c1, container c2) 互换两个容器中的所有元素
@param c1 容器 1
@param c2 容器 2
*/
void test03() {
    vector<int> v1 = {0, 1, 2};
    vector<int> v2 = {3, 4};
    swap(v1, v2); // v1 和 v2 互换
}

e、常用算数生成算法

/*
accumulate(iterator beg, iterator end, value)
@param beg   容器开始迭代器
@param end   容器结束迭代器
@param value 总和累加起始值
Note: 需包含 numeric 头文件
*/
void test01() {
    vector<int> v = {0, 1, 2, 3, 4};
    int sum = accumulate(v.begin(), v.end(), 90);  // 默认提供累加起始值为 0 即可
    cout << "总和为：" << sum << endl;  // 总和为：100
}

/*
fill(iterator beg, iterator end, value)  将容器指定范围的元素替换为填充元素
@param beg   容器开始迭代器
@param end   容器结束迭代器
@param value 填充元素
*/
void test02() {
    vector<int> v = {0, 1, 2, 3, 4};
    fill(v.begin() + 2, v.end(), -1);
    for_each(v.begin(), v.end(), [](int val) { cout << val << " "; });  // 输出 0 1 -1 -1 -1

}

f、常用集合算法

/*
set_intersection(iterator beg1, iterator end1, iterator beg2, iterator end2, iterator dest)  求两个集合的交集
@param beg1  容器1开始迭代器
@param end1  容器1结束迭代器
@param beg2  容器2开始迭代器
@param end2  容器2结束迭代器
@param dest  目标容器开始迭代器
@return 目标容器的最后一个元素的迭代器地址
Note：两个集合一般需要是有序序列
*/
void test01() {
    vector<int> v1 = {0, 1, 2};
    vector<int> v2 = {2, 3, 4};
    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, [](int val) { cout << val << " "; });  // 输出 2
    cout << endl;

}

/*
set_union(iterator beg1, iterator end1, iterator beg2, iterator end2, iterator dest) 求两个集合的并集
@param beg1  容器1开始迭代器
@param end1  容器1结束迭代器
@param beg2  容器2开始迭代器
@param end2  容器2结束迭代器
@param dest  目标容器开始迭代器
@return 目标容器的最后一个元素的迭代器地址
Note：两个集合一般需要是有序序列
*/
void test02() {
    vector<int> v1 = {0, 1, 2};
    vector<int> v2 = {2, 3, 4};
    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, [](int val) { cout << val << " "; });  // 输出 0 1 2 3 4
    cout << endl;

}


/*
set_difference(iterator beg1, iterator end1, iterator beg2, iterator end2, iterator dest) 求两个集合的差集
@param beg1  容器1开始迭代器
@param end1  容器1结束迭代器
@param beg2  容器2开始迭代器
@param end2  容器2结束迭代器
@param dest  目标容器开始迭代器
@return 目标容器的最后一个元素的迭代器地址
Note：两个集合一般需要是有序序列
*/
void test03() {
    vector<int> v1 = {0, 1, 2};
    vector<int> v2 = {2, 3, 4};
    vector<int> vTarget;
    vTarget.resize(max(v1.size(), v2.size()));  // 为目标容器分配空间

    // v1 差 v2
    vector<int>::iterator itEnd = set_difference(v1.begin(), v1.end(), v2.begin(), v2.end(), vTarget.begin());
    for_each(vTarget.begin(), itEnd, [](int val) { cout << val << " "; });  // 输出 0 1
    cout << endl;

    // v2 差 v1
    itEnd = set_difference(v2.begin(), v2.end(), v1.begin(), v1.end(), vTarget.begin());
    for_each(vTarget.begin(), itEnd, [](int val) { cout << val << " "; }); // 输出 3 4
}

g、常用大小写转换算法

string s = "abCdEfg";
for (int i = 0; i < s.size();i++)
{
	// s[i] = toupper(s[i]);  // 全变大写
	s[i] = tolower(s[i]);     // 全变小写
}

3、迭代器

迭代器提供一种方法，可指定容器中的 一段区间，以执行 遍历、删除 等操作，它扮演了容器与算法之间的胶合剂，共有五种类型（最常用的是最后两种）
从实现角度来看，迭代器是一种类模板 (class template)，所有 STL 容器都附带有自己专属的迭代器
每一个容器都有其对应的迭代器：如 vector<int>::iterator

在这里插入图片描述

// 1、普通指针(p)也算一种迭代器（通过 ++ 操作可以依次遍历其中元素）
void test() {
    int arr[5] = {1, 3, 5, 6, 8};
    int *p = arr;  // 指针指向数组首地址，等价于 int *p = &arr[0]

    for (int i = 0; i < 5; i++) {
        cout << *(p++) << ' ';  // 支持 ++ 操作
    }
    cout << endl;
}

// 2、迭代器的基本用法
vector<int> v; // 声明一个容器，这个容器中存放 int 类型数据，对象名称 v

// 2.1 利用迭代器遍历容器中的内容（左闭右开），vector<int>::iterator 可用 auto 替换来简化代码
for (vector<int>::iterator it = v.begin(); it != v.end();it++)
{
	cout << *it << endl;
}
// 使用 auto 简化代码，去除首尾元素
for (auto it = v.begin()+1; it < v.end()-1;it++)
{
	cout << *it << endl;
}


// 2.2 利用逆序迭代器遍历容器中的内容（左开右闭），vector<int>::reverse_iterator 可用 auto 替换来简化代码
for (vector<int>::reverse_iterator it = v.rbegin(); it != v.rend(); it++)
{
    cout << *it << endl;
}

// 2.3 利用数组遍历容器中的内容
for (int i = 0; i < 4; i++)
{
	cout << v[i] << endl;
}

// 3、迭代器的种类
vector<int>::iterator
vector<int>::reverse_iterator
vector<int>::const_iterator

vector<int>::iterator it1;  // it1 的类型其实就相当于 int* 指针（实际为 vector<int, allocator>::iterator）
vector<Teacher>::iterator it2;  // it2 的类型其实就相当于 teacher* 指针

4、仿函数

从实现角度来看，仿函数是一种重载了 operator() 的 class 或者 class template，所以又叫函数对象，使得类对象可以像函数一样调用
函数对象通常不定义构造函数和析构函数,所以在构造和析构时不会发生任何问题,避免了函数调用的运行时问题
函数对象超出普通函数的概念，函数对象可以有自己的状态

// 1、仿函数：二元谓词
class myCompare {
public:
    // 重载 ()，返回值为 bool 类型，且有两个参数，又叫二元谓词
    bool operator()(int v1, int v2) {
        return v1 > v2;
    }
};

myCompare p;
bool ret = p(3, 2);
cout << ret << endl;  // 1

// 2、匿名函数对象可以做函数的参数
void doBusiness(myCompare compare,int num1, int num2)
{
	int ret = compare(num1, num2);
	cout << ret << endl;
}
doBusiness(myCompare(), 3, 2);

// 3、内建函数对象
#include <functional>  // 内建函数对象头文件

// 3.1 算数类函数对象，除了 negate 是一元运算，其他都是二元运算
template<class T> T plus<T>        // 加法仿函数
template<class T> T minus<T>       // 减法仿函数
template<class T> T multiplies<T>  // 乘法仿函数
template<class T> T divides<T>     // 除法仿函数
template<class T> T modulus<T>     // 取模仿函数
template<class T> T negate<T>      // 取反仿函数
// 加法仿函数的具体实现
template<typename _Tp>
struct plus : public binary_function<_Tp, _Tp, _Tp>
{
  _GLIBCXX14_CONSTEXPR
  _Tp operator()(const _Tp& __x, const _Tp& __y) const
  { return __x + __y; }
};
plus<int> p;
cout << p(1, 1) << endl;  // 2


// 3.2 关系运算类函数对象，每一种都是二元运算
template<class T> bool equal_to<T>       // 等于
template<class T> bool not_equal_to<T>   // 不等于
template<class T> bool greater<T>        // 大于
template<class T> bool greater_equal<T>  // 大于等于
template<class T> bool less<T>           // 小于
template<class T> bool less_equal<T>     // 小于等于
// 大于仿函数使用示例：
vector<int> v = {10, 30, 50, 20, 40};
sort(v.begin(), v.end(), greater<int>());  // 传入匿名仿函数对象
for_each(v.begin(), v.end(), [](int val) { cout << val << " "; });  // 50 40 30 20 10


// 3.3 逻辑运算类运算函数，not 为一元运算，其余为二元运算
template<class T> bool logical_and<T>  // 逻辑与
template<class T> bool logical_or<T>   // 逻辑或
template<class T> bool logical_not<T>  // 逻辑非

5、适配器

一种用来修饰容器或者仿函数或迭代器接口的东西
可调整原有容器的行为，使得其对外展现出新的类型、接口或返回新的元素

// 函数适配器 bind1st bind2nd(直接给函数对象绑定参数，此参数可由用户输入)
// 函数对象要：继承类 binary_function<参数类型1 ，参数类型2 ，返回值类型>
// 加 const 修饰 operator()
class MyPrint : public binary_function<int, int, void> {
public:
    void operator()(int v, int start) const {
        cout << "v = " << v << " start = " << start << " v+start = " << v + start << endl;
    }

};

void test01() {
    vector<int> v;
    for (int i = 0; i < 3; i++) {
        v.push_back(i);
    }
    cout << "请输入起始值" << endl;
    int num;
    cin >> num;  // 输入 10
    
    // for_each(v.begin(), v.end(), bind1st(MyPrint(), num));
    for_each(v.begin(), v.end(), bind2nd(MyPrint(),num));
    // v = 0 start = 10 v+start = 10
    // v = 1 start = 10 v+start = 11
    // v = 2 start = 10 v+start = 12
}


// 一元取反适配器 not1，二元取反适配器 not2
// 函数对象要：继承类 unary_function <参数类型1，返回值类型>
// 加 const 修饰 operator()
class GreaterThenTwo : public unary_function<int, bool> {
public:
    bool operator()(int v) const {
        return v >= 2;
    }
};

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

    // 查找小于 2 的数字
    vector<int>::iterator pos = find_if(v.begin(), v.end(), not1(bind2nd(greater_equal<int>(), 2)));
    // vector<int>::iterator pos = find_if(v.begin(), v.end(), GreaterThenTwo());  // 查找大于等于 2 的数字
    if (pos != v.end()) {
        cout << "找到小于 2 的数字为： " << *pos << endl;  // 找到小于 2 的数字为： 0
    } else {
        cout << "未找到" << endl;
    }
}

// 函数指针适配器 ptr_fun，将函数指针适配为函数对象
void MyPrint03(int v, int start) {
    cout << v + start << endl;
}

void test03() {
    vector<int> v;
    for (int i = 0; i < 3; i++) {
        v.push_back(i);
    }
    // ptr_fun：将函数指针适配为函数对象
    for_each(v.begin(), v.end(), bind2nd(ptr_fun(MyPrint03), 10));  // 10 11 12
}

// 成员函数适配器 mem_fun&mem_fun_ref
// 如果容器中存放的是对象指针，那么用 mem_fun
// 如果容器中存放的是对象实体, 那么用 mem_fun_ref
class Person {
public:
    Person(string name, int age) {
        this->m_Name = name;
        this->m_Age = age;
    }

    void showPerson() {
        cout << "成员函数中：姓名： " << m_Name << " 年龄：" << m_Age << endl;
    }

    void plusAge() {
        this->m_Age = this->m_Age + 100;
    }

    string m_Name;
    int m_Age;
};

void test04() {
    vector<Person> v;      // 如果容器中存放的是对象实体, 那么用 mem_fun_ref 
    // vector<Person*> v;  // 如果容器中存放的是对象指针，那么用 mem_fun

    Person p1("aaa", 10);
    Person p2("bbb", 15);

    v.push_back(p1);
    v.push_back(p2);
    // v.push_back(&p1);
    // v.push_back(&p2);

    // 成员函数适配器 mem_fun_ref
    // 成员函数中：姓名： aaa 年龄：10
    // 成员函数中：姓名： bbb 年龄：15
    for_each(v.begin(), v.end(), mem_fun_ref(&Person::plusAge));
    for_each(v.begin(), v.end(), mem_fun_ref(&Person::showPerson));
    // for_each(v.begin(), v.end(), mem_fun(&Person::plusAge));
    // for_each(v.begin(), v.end(), mem_fun(&Person::showPerson));
    // 成员函数中：姓名： aaa 年龄：110
    // 成员函数中：姓名： bbb 年龄：115
}

6、空间配置器

负责空间的配置与管理；从实现角度看,配置器是一个实现了动态空间配置、空间管理、空间释放的 class tempalte

三、thrust

thrust 是一个基于 CUDA 的高级并行编程库，提供了一组易于使用的算法和数据结构，用于在 GPU 上进行并行计算。
thrust 提供了类似于标准 C++ 模板库（STL）的接口和语法，使开发者能够以一种简单直观的方式利用 GPU 的并行计算能力。它提供了丰富的算法，如排序、归约、扫描、变换等，并支持向量、数组和键值对等多种数据结构。
需要注意的是，thrust 并不是 CUDA 的一部分，而是一个由 NVIDIA 提供的独立库。要使用 thrust，需要将其包含在项目中，并确保正确链接和配置相关的编译器和构建系统

// 对于 thrust 中的 lambda 表达式，需要增加 __device__ 标记表明函数可以被核函数调用，此时需要在 makefile 中增加--extended-lambda 标记
// 由于使用到了 device vector，因此编译环境需要修改为 nvcc 编译，因此 main.cpp 改成了 main.cu
#include <stdio.h>
#include <thrust/host_vector.h>
#include <thrust/device_vector.h>
#include <thrust/sort.h>
#include <iostream>
using namespace std;

__host__ __device__
int sort_func(int a, int b){
    return a > b;
}

int main(){

    int data[] = {5, 3, 1, 5, 2, 0};
    int ndata  = sizeof(data) / sizeof(data[0]);
    thrust::host_vector<int> array1(data, data + ndata);
    thrust::sort(array1.begin(), array1.end(), sort_func);

    thrust::device_vector<int> array2 = thrust::host_vector<int>(data, data + ndata);
    thrust::sort(array2.begin(), array2.end(), []__device__(int a, int b){return a < b;});

    printf("array1------------------------\n");
    for(int i = 0; i < array1.size(); ++i)
        cout << array1[i] << endl;

    printf("array2------------------------\n");
    for(int i = 0; i < array2.size(); ++i)
        cout << array2[i] << endl;
    return 0;
}