学习笔记｜STL

本文最后更新于：4 个月前

一、函数模版

1.基本语法

编写代码时，可以忽略类型。

// template<class T>
template<typename T1, typename T2>
int MySwap(T1 &a, T2 &b){
  //...
}

可以定义多个虚拟类型，T1，T2…
为了让编译器区分函数模版、普通函数，需要在函数模版前面写 template<class T> 。

2.自动类型推导和显式指定类型

调用函数模版时，函数模版自动推导类型和显式指定类型。

int main() {
	int a = 0, b = 0;
  // 自动类型推导
  MySwap(a, b);
  // 显式指定类型
  MySwap<int>(a, b);
}

3.函数模版和普通函数的区别

函数模版不提供隐式转换
普通函数会进行隐式转换，

情境一：当普通函数和函数模版重载，优先调用普通函数。

情境二：当需要发生隐式转换时，只能调用普通函数。

template<class T>
void Fun(T a, T b) {
    cout << a << " <T, T> " << b << endl;
    return;
}

void Fun(int a, int b) {
    cout << a << " <int, int> " << b << endl;
    return;
}

int main() {
    int a = 97, b =98;
    char c = 'a';
    Fun(a, b);     // <int, int> 存在满足要求的普通函数，优先调用普通函数。
    Fun(c, a);    // <char, int> 需要隐式转换的，必须调用普通函数。
    return 0 ;
}

情境三：若要显式调用函数模版时，加 <> 。

Fun<>(a, b);

4.模版函数的实现原理

过程：

2020-06-19-l0ZhlS

注意：

编译器不能直接调用函数模版。编译器不是把函数模板处理成能够处理任意类的函数。
编译器根据具体的函数类型，生成模版函数。
编译器对函数模版进行两次编译：
1. 在声明函数模版的地方，对函数模版本身进行编译。
2. 在调用模版函数的地方，替换参数后，进行编译。

二、类模版

1.基本格式

定义类时，要写 template<class T> 。
实例化对象时，必须显式提供所泛化的具体类型。

template<class T>
class A {
public:
    A(T id, T age){
        this->id_ = id;
    }
    void Show(){
        cout << "id = " << this->id_ << endl;
    }

private:
    T id_;           // 类中成员变量可用 T 表示。
};

int main(){
    A<char> a(97, 98);    // 实例化对象时，必须显式提供所泛化的具体类型。
    a.Show();
    return 0;
}

2.类模版的派生

（1）模版类派生普通类

若派生类是普通类，需要显式提供基类的类型。

派生类从基类继承，需要让编译器知道，父类的数据类型具体是什么。（数据类型的本质：固定大小内存块的别名。）

template<class T>
class Animal {
public:
    T age_;
    Animal(T age){
        this->age_ = age;
    }
    void Print(){
        cout << "age = " << age_ << endl;
    }
};

class Cat : public Animal<int>{    // 【显式地提供参数类型】
public:
    Cat(int age) : Animal(age){ }
    void Print(){
        cout << "I am Cat!" << endl;
        Animal::Print();
    }
};

int main(){
    Cat cat(10);
    cat.Print();
    return 0;
}

（2）模版类派生模版类

// 若子类是类模版，父类类型可以用 T 表示。
template<class T>
class Animal {
public:
    T age_;
    Animal(T age){
        this->age_ = age;
    }
    void Print(){
        cout << "age = " << age_ << endl;
    }
};

template<class T>      // 【派生类也需要写明 "template<class T> "】
class Cat : public Animal<T>{
public:
    Cat(T age) : Animal<T>(age){ }   // 【调用基类构造时，需要写明 泛型<T>】
    void Print(){
        cout << "I am Cat!" << endl;
      Animal<T>::Print();          // 【使用类的限定符时，需要写明泛型<T>】
    }
};

int main(){
    Cat<int> cat(10);
    cat.Print();
    return 0;
}

3.类模版+友元函数

（1）类模版+普通/友元+类内定义

和 普通类+普通/友元 相比，没有什么特殊的，一切正常。

template <class T>
class Person {
public:
    Person(string name, T age){
        this->name_ = name;
        this->age_ = age;
    }
    void Print(){                                            // 普通函数的类内定义
        cout << "name = " << this->name_ << endl;
        cout << "age = " << this->age_ << endl;
        return;
    }
    friend ostream &operator<<(ostream &os, Person<T> &person){    // 友元函数的类内定义
        os << "name = " << person.name_ << endl;
        os << "age = " << person.age_ << endl;
        return os;
    }

public:
    string name_;
    T age_;
};

int main(){
    Person<int> person_01("Tom", 13);
    person_01.Print();
    cout << person_01;
}

（2）类模版+普通函数+类外定义

类模版+普通函数+类外定义时，需要注意一下两点：

类外实现类成员函数时，需要写明 template <class T> 。
使用 类作用域符 时，需要写明泛型。

person.h

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

template <class T>
class Person {
public:
    Person(string name, T age);
    void Print();

public:
    string name_;
    T age_;
};

person.cc

#include "person.h"

template <class T>          // 类成员函数，类外实现时，需要用 template <class T>
Person<T>::Person(string name, T age){    // 使用 类作用域符 时，需要写明泛型<T>
    this->name_ = name;
    this->age_ = age;
}

template <class T>
void Person<T>::Print(){
    cout << "name = " << this->name_ << endl;
    cout << "age = " << this->age_ << endl;
}

main.cc

#include "person.h"

int main(){
    Person p_01("Tom", 11);
    p_01.Print();
    return 0;
}

（3）分文件编程报错

按照 类模版+普通函数+类外定义 的方式，会报错如下，原因是无法正确链接文件。

Undefined symbols for architecture x86_64:
  "Person<int>::Print()", referenced from:
      _main in main-02af6c.o
  "Person<int>::Person(std::__1::basic_string<char, std::__1::char_traits<char>, std::__1::allocator<char> >, int)", referenced from:
      _main in main-02af6c.o
ld: symbol(s) not found for architecture x86_64
clang: error: linker command failed with exit code 1 (use -v to see invocation)

解决方案：

将 person.cc 改为 person.hpp ，并在 main.cc 中引用 #include "person.hpp" 。

person.h

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

template <class T>
class Person {
public:
    Person(string name, T age);
    void Print();

public:
    string name_;
    T age_;
};

person.hpp

将 person.cc 改为 person.hpp 。

#include "person.h"

template <class T>          // 类成员函数，类外实现时，需要用 template <class T>
Person<T>::Person(string name, T age){    // 使用 类作用域符 时，需要写明泛型<T>
    this->name_ = name;
    this->age_ = age;
}

template <class T>
void Person<T>::Print(){
    cout << "name = " << this->name_ << endl;
    cout << "age = " << this->age_ << endl;
}

main.cc

#include "person.hpp"   // 由 #include "person.h" 改为  #include "person.hpp"

int main(){
    Person p_01("Tom", 11);
    p_01.Print();
    return 0;
}

（4）C++编译机制

独立编译：当分文件编程时，每个文件都是单独编译，生成若干个 .o 文件，并用链接器寻找相关文件，完成运行。

二次编译：类模版先编译一次，检测语法错误，分析语义，再根据实际的类型，生成模版函数，进行第二次编译。

冲突：独立编译后，才进行二次编译，所以链接器找不到类外定义的函数模版所生成的模版函数。容易发生的错误如下：

"operator<<(std::__1::basic_ostream<char, std::__1::char_traits<char> >&, Person<int>&)", referenced from:
      _main in 友元+类模版+友元+重载左移动-c601b9.o
ld: symbol(s) not found for architecture x86_64
clang: error: linker command failed with exit code 1 (use -v to see invocation)

（5）类模版+友元函数+类外定义

第一种格式：二重模版

定义友元函数时，使用一个新的泛型 T2 表示。

person.h

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

template <class T>
class Person {
public:
    Person(string name, T age);
    void Print();
    template<class T2>                    // 定义一个泛型 T2
    friend ostream &operator<<(ostream &os, Person<T2> &person);

public:
    string name_;
    T age_;
};

person.hpp

#include "person.h"

template <class T>
Person<T>::Person(string name, T age){
    this->name_ = name;
    this->age_ = age;
}

template <class T>
void Person<T>::Print(){
    cout << "name = " << this->name_ << endl;
    cout << "age = " << this->age_ << endl;
    return;
}

template <class T2>           // 函数实现时，也需要声明泛型 T2
ostream &operator<<(ostream &os, Person<T2> &person){
    os << "name = " << person.name_ << endl;
    os << "age = " << person.age_ << endl;
    return os;
}

main.cc

#include "person.hpp"

int main(){
    Person<int> person_01("Tom", 13);
    person_01.Print();
    cout << person_01;
}

第二种格式：声明前置

在类的定义和友元函数的定义前面，加上二者的声明。

person.h

// 前置声明 类
template <class T>
class Person;

// 前置声明 友元函数
template <class T>
ostream &operator<<(ostream &os, Person<T> &person);

template <class T>
class Person {
public:
    Person(string name, T age);
    void Print();
    // 在 函数名和参数列表之间 声明泛型 <T>
    friend ostream &operator<< <T> (ostream &os, Person<T> &person);

public:
    string name_;
    T age_;
};

person.hpp

#include "person.h"

template <class T>
Person<T>::Person(string name, T age){
    this->name_ = name;
    this->age_ = age;
}

template <class T>
void Person<T>::Print(){
    cout << "name = " << this->name_ << endl;
    cout << "age = " << this->age_ << endl;
    return;
}

template <class T>
ostream &operator<<(ostream &os, Person<T> &person){   // 函数实现时，无需添加 泛型<T>
    os << "name = " << person.name_ << endl;
    os << "age = " << person.age_ << endl;
    return os;
}

main.cc

#include "person.hpp"

int main(){
    Person<int> person_01("Tom", 13);
    person_01.Print();
    cout << person_01;
}

4.类模版+static成员

static 变量属于 实际的类，而不属于类模版。

实际的类 由实际的 泛型 <T> 最后的值决定。

template<class T>
class Person {
public:
    static int a;
};

template<class T>
int Person<T>::a = 0;       // 类外初始化 static 变量。

int main(){
    Person<int> p1, p2;    // 类模版为 int 的类，共用 static 变量。
  	Person<int> p3, p4;
  
  	Person<char> c1, c2;   // 类模版为 char 的类，共用 static 变量。
  	
    p2.a = 10;
    cout << p4.a;         // 10
  	cout << c1.a;         // 0
}

5.实例：MyArray

自定义一个数组的模版类。

<T> 对象元素必须能够被拷贝。
容器都是值寓意，而非引用寓意，放入容器的元素，都是拷贝份。
元素成员有指针，注意深拷贝。

template<class T>
class MyArray {
public:
    MyArray(const int max_size);
    MyArray(const MyArray<T> &another);
    T &operator[](const int &index);
    MyArray<T> &operator=(const MyArray<T> &another);
    void Print();
    void PushBack(const T &data);    // 用 const 引用，来接收 变量、常量。
    ~MyArray();

public:
    // 数组大小
    int max_size_;
    // 数组当前元素个数
    int size_;
    // 数组头指针
    T *arr_ptr_;
};

template<class T>
MyArray<T>::MyArray(const int max_size){       // 使用 类作用域符 时，需要写 泛型<T>
    this->max_size_ = max_size;
    this->arr_ptr_ = new T[this->max_size_];
    this->size_ = 0;
}

template<class T>
MyArray<T>::MyArray(const MyArray<T> &another){
    //【拷贝构造】，不需要判断指针是否为空，【等号操作符】需要。
    this->max_size_ = another.max_size_;
    this->size_ = another.size_;
    this->arr_ptr_ = new T[this->max_size_];
    for (int i = 0; i < this->size_; i++) {
        this->arr_ptr_[i] = another.arr_ptr_[i];
    }
}

template<class T>
T &MyArray<T>::operator[](const int &index){
    if (this->size_ <= index){
        cout << "索引越界！" << endl;
        return this->arr_ptr_[0];
    }
    return this->arr_ptr_[index];
}

template<class T>
MyArray<T> &MyArray<T>::operator=(const MyArray<T> &another){
    // 【等号操作符】，需要先判断数组指针是否为空，而不是判断 size 大小。
    //【拷贝构造】，不需要判断指针是否为空。
    if (this->arr_ptr_ != nullptr) {
        delete[] this->arr_ptr_;
        this->arr_ptr_ = nullptr;
    }
    this->max_size_ = another.max_size_;    // 类的三个成员变量 都需要考虑到，不要只拷贝数组。
    this->size_ = another.size_;
    this->arr_ptr_ = new T[this->max_size_];
    for (int i = 0; i < this->size_; i++) {
        this->arr_ptr_[i] = another.arr_ptr_[i]; 
    }
    return *this;
}

template<class T>
void MyArray<T>::Print(){
    for (int i = 0; i < this->size_; i++) {
        cout << this->arr_ptr_[i] << " ";
    }
    cout << endl;
    return;
}

template<class T>
void MyArray<T>::PushBack(const T &data){
    if (this->size_ == this->max_size_) {
        cout << "数组已满！" << endl;
        return;
    }
    this->arr_ptr_[this->size_] = data;
    this->size_ ++;
    return;
}

template<class T>
MyArray<T>::~MyArray(){
    if (this->arr_ptr_ != nullptr) {
        delete[] this->arr_ptr_;
        this->arr_ptr_ = nullptr;
    }
}

int main(){
    MyArray<int> arr1(3), arr2(5);
    arr1.PushBack(10);
    arr1.PushBack(9);
    arr1.PushBack(8);
    arr1.PushBack(7);
    arr1.PushBack(6);
    arr2 = arr1;
    MyArray<int> arr4 = arr2;
    arr4.Print();
}

三、类型转换

static_cast	内置的数据类型转换，以及具有继承关系的指针和引用的转换。【父类转换为子类时，不安全】	不会进行安全检查。
dynamic_cast	具有继承关系的指针和引用的转换。【只能从子类转换为父类】	转换之前，进行对象类型的安全检查
const_cas	增加或去除 const 。
reinterpret_cast	无关的指针类型的转换，或者函数指针之间的转换。

1.static_cast

static_cast<目的类型>(待转换变量)

// 基础类型
int a = 100;
char c = static_cast<char>(a);

// 基础数据类型指针【报错！】
// int *p1 = nullptr;
// char *p2 = static_cast<char *>(p1);

// 非继承关系的指针和引用【报错！】
// class ObjA {};
// class ObjB {};
// ObjA *p1 = nullptr;
// ObjB *p2 = static_cast<ObjB *>(p1);

// 具有继承关系的指针和引用
class ObjA {};
class ObjB : public ObjA {};
		// 1.父类指针转化为子类指针
ObjA *p1 = nullptr;
ObjB *p2 = static_cast<ObjB *>(p1);
		// 2.子类指针转化为父类指针
ObjB *p3 = nullptr;
ObjA *p4 = static_cast<ObjA *>(p3);
		// 3.父类引用转化为子类引用
ObjA obj_a_1;
ObjA &obj_aaa_1 = obj_a_1;
ObjB &obj_bbb_1 = static_cast<ObjB &>(obj_aaa_1);
		// 4.子类引用转化为父类引用
ObjB obj_b_2;
ObjB &obj_bbb_2 = obj_b_2;
ObjA &obj_aaa_2 = static_cast<ObjA &>(obj_bbb_2);

2.dynamic_cast

转换之前，进行对象类型的安全检查，所以只能从子类转换到父类。避免父类指针转化为子类指针，操作安全区域之外的内存。

// 基础数据类型【报错！】
// int a = 100;
// char c = dynamic_cast<char>(a);

// 非继承关系的指针和引用【报错！】
// class ObjA {};
// class ObjB {};
// ObjA *p1 = nullptr;
// ObjB *p2 = dynamic_cast<ObjB *>(p1);

// 具有继承关系的指针和引用
class ObjA {};
class ObjB : public ObjA {};
		// 1.父类指针转化为子类指针【报错！】
// ObjA *p1 = nullptr;
// ObjB *p2 = dynamic_cast<ObjB *>(p1);
		// 2.子类指针转化为父类指针
ObjB *p3 = nullptr;
ObjA *p4 = dynamic_cast<ObjA *>(p3);
		// 3.父类引用转化为子类引用【报错！】
// ObjA obj_a_1;
// ObjA &obj_aa_1 = obj_a_1;
// ObjB &obj_bb_1 = dynamic_cast<ObjB &>(obj_aa_1);
		// 4.子类引用转化为父类引用
ObjB obj_b_2;
ObjB &obj_bb_2 = obj_b_2;
ObjA &obj_aa_2 = dynamic_cast<ObjA &>(obj_bb_2);

3.const_cast

// 基础数据类型的引用
int a = 10;
const int &b = a;
int &c = const_cast<int &>(b);

// 普通指针类型
		// 去 const
const int *p1 = nullptr;
int *p2 = const_cast<int *>(p1);
		// 加 const
int *p3 = nullptr;
const int *p4 = const_cast<const int *>(p3);
const int *p5 = p3;

4.reinterpret_cast

typedef int (*FUN_P_1)(int);
typedef int (*FUN_P_2)(int, char);

int main(){
    // 无关的指针类型
    class ObjA {};
    class ObjB {};
    ObjA *p_a = nullptr;
    ObjB *p_b = reinterpret_cast<ObjB *>(p_a);

    // 函数指针的转换
    FUN_P_1 fun01;
    FUN_P_2 fun02 = reinterpret_cast<FUN_P_2>(fun01);
}

5.建议

转换前应该知道，转换前后的类型是什么，后果是什么。（尤其是，指针转换前后，可操作的内存区域的变化）。
不建议使用。

四、异常

1.异常的好处

在c语言中，我们使用函数返回值来表示异常。

例如以下程序：当发生异常（b 等于 0），返回 -1 表示错误。

double division(int a, int b){
    if (b == 0) { 
        return -1;    // 返回 -1 表示错误
    }
    return (double)a/b;
}

函数返回值可以忽略；但异常不能忽略。如果程序出现异常，但未被捕获，程序就会终止。
整型返回值没有任何语义；而异常可以包含语义（比如类名）。
整型返回值没有上下文；而异常作为一个类，可以拥有自己的成员，传递足够完整的信息。
对于函数的多级调用，使用整型返回值，需要每一级函数都进行处理；而异常是跨函数的，使用异常处理的栈展开机制，只需在其中一级函数中处理就可以。

2.基础语法

int Division(int a, int b){
    if (b == 0) {
        throw b;          // 抛出异常
    }
    return a / b;
}

int main(){
    try {                  // 尝试捕获异常
        Division(10, 0);
    }
    catch (int e) {        // 捕获异常
        cout << "除数为" << e << endl;
    }
  	return 0;
}

3.跨函数和不可忽略

【跨函数性】

执行（入栈）顺序：main -> Fun01 -> Fun02 -> divison。

divison 抛出异常，Fun02 没处理，往顶层抛，抛给 Fun01，Fun01 处理异常。

【不可忽略，必须处理】

若在顶层也没有处理异常，程序就会终止。

int Division(int a, int b){         // 抛出异常
    if (b == 0) {
        throw b;
    }
    return a / b;
}

int Fun02(int a, int b){            // 没有处理异常
    return Division(a, b);
}

int Fun01(){                        // 处理异常
    int res = 0;
    try { 
        res = Fun02(10, 0);
    }
    catch (int e) {
        cout << "除数为" << e << endl;
    }
    return res;
}

int main(){
    Fun01();
    return 0;
}

4.栈解旋（unwinding）

异常抛出后，从进入 try 块，到异常被抛出之前，此期间，栈上构造的所有对象，都会被自动析构。

跑异常的过程中，注意两个不执行：

throw 后的代码并不执行。
try中，抛出异常后的代码并不执行。

class Obj {
public:
    Obj(const int &num){
        this->num = num;
        cout << num << " 正在构造.." << endl;
    }
    ~Obj(){
        cout << num << " 正在析构..." << endl;
    }

public:
    int num;
};

int Devision(int a, int b){
    Obj obj_1(1);      // 栈解旋
    if (b == 0) {
        throw b;
        Obj obj_2(2);  // throw 后的代码并不执行。 
    }
    Obj obj_2_1(21);
    return a / b;
}

int main(){
    try {
        Obj obj_3(3);       // 栈解旋
        Devision(10, 0);    // 抛出异常
        Obj obj_4(4);       // try中，抛出异常后，代码并不执行。
    }
    catch (int e) {
        cout << "捕获异常" << endl;
    }
    return 0;
}

5.异常接口的声明

只能抛出 int, float, char 三种类型异常。

int Fun01() throw(int, float, char){
  throw "abc";      // 抛出不是以上三种类型时，【程序报错】。
}

不能抛出任何类型的异常

int Fun02() throw(){
  throw -1;      // 抛出了异常，【程序报错】。
}

可以抛出所有类型异常

int Fun03() throw(){
  
}

捕获多种类型的方式

int main(){
  try {
    Fun01();
  }
  catch (int e) {           // 捕获 int，没捕获到继续执行
    cout << e << endl;
  }
  catch (char e) {          // 捕获 char，没捕获到继续执行
    cout << e << endl;
  }
  catch (...) {             // 省略号，可以捕获所有类型异常。
    cout << “未知类型异常”  << endl;
  }
}

6.对象做异常类型

抛对象异常throw Exception("此处出现异象的原因是......");和捕捉对象异常catch (Exception e)的中间，有一个拷贝构构造存在。（如果 e 是引用，见异常对象的生命周期）

抛出的对象，不适用于拷贝省略。

所以，如果对象中有指向堆区的指针，类中要写清楚拷贝构造函数（深拷贝），不能使用默认的拷贝构造（浅拷贝）。浅拷贝导致两个指针指向一个堆区空间，析构时会产生错误。

// 异常类
class Exception {
public:
    Exception(const char *str){
        cout << "开始构造！" << endl;
        this->error = new char[strlen(str) + 1];
        strcpy(error, str);
    }
    // 必须写拷贝构造，不可以用默认拷贝构造（浅拷贝）
    Exception(const Exception &e){
        cout << "开始拷贝！" << endl;
        this->error = new char[strlen(e.error) + 1];
        strcpy(this->error, e.error);
    }
    void Show(){
        cout << this->error << endl;
    }
    ~Exception(){
        if (this->error != nullptr) {
            delete[] this->error;
            this->error = nullptr;
            cout << "开始析构!" << endl;
        }
    }
public:
    char *error;
};

void Fun(){
    throw Exception("此处出现异象的原因是......");
};

int main(){
    try {
        Fun();
    }
    catch (Exception e) {    // 捕捉异常后，调用类中函数。
        e.Show();
        e.~Exception();
    }
}

/*
开始构造！                  // throw Exception("此处出现异象的原因是......");
开始拷贝！                  // catch (Exception e)
此处出现异象的原因是......    // e.Show();
开始析构!                   // e.~Exception();
开始析构!                   // Exception().~Exception()  //  catch 处理完异常对象，析构。
*/

7.异常对象的生命周期

普通类型

普通类型，异常对象，在 catch 大括号处理完之后，析构。

class Exception {
public:
    Exception(){ cout << "开始构造！" << endl; }
    Exception(const Exception &e){ cout << "开始拷贝！" << endl; }
    ~Exception(){ cout << "开始析构!" << endl; }
};

void Fun(){
    throw Exception();
};

int main(){
    try {
        Fun();
    }
    catch (Exception e /*【此处普通类型】*/) {         // e 的生命周期：catch 大括号结束。
        cout << "捕获异常" << endl;
    }
}

/*
开始构造！                  // throw Exception();
开始拷贝！                  // catch (Exception e)
此处出现异象的原因是......    // cout << "捕获异常" << endl;
开始析构!                   // e.~Exception();
开始析构!                   // Exception().~Exception()  //  catch 处理完异常对象，析构。
*/

引用

引用，不用调用拷贝构造，异常对象 catch 处理完之后，析构。

class Exception {
public:
    Exception(){ cout << "开始构造！" << endl; }
    Exception(const Exception &e){ cout << "开始拷贝！" << endl; }
    ~Exception(){ cout << "开始析构!" << endl; }
};

void Fun(){
    throw Exception();
};

int main(){
    try {
        Fun();
    }
    catch (Exception &e/*【此处引用】*/) {         // e 的生命周期：catch 大括号结束。
        cout << "捕获异常" << endl;
    }
}

/*
开始构造！    // throw Exception();
捕获异常      // cout << "捕获异常" << endl;
开始析构!     //  Exception().~Exception()   //  catch 处理完异常对象，析构。
*/

指针

传递完指针，还未进入 catch 大括号，就会被立刻析构掉，但是异常类对象还在栈上（还可以调用函数，但是不能使用堆区空间）。

class Exception {
public:
    Exception(){ cout << "开始构造！" << endl; }
    Exception(const Exception &e){ cout << "开始拷贝！" << endl; }
    ~Exception(){ cout << "开始析构!" << endl; }
};

void Fun(){
    Exception tmp;
    throw &tmp;
};

int main(){
    try {
        Fun();
    }
    catch (Exception *e) {
        cout << "捕获异常" << endl;
        e->~Exception();
    }
}

/*
开始构造！    // Exception tmp;
开始析构!     // catch (Exception *e);   // 执行完 Exception *e，还没进入 catch 大括号，就被析构。
捕获异常      // cout << "捕获异常" << endl;
开始析构!     // e->~Exception(); 析构堆区的空间，若无堆区空间，可多次析构。
*/

五、输入输出流

1.流的概念和流类库

键盘输入数据到程序：标准输入 input

程序输出到显示器：标准输出 output

标准输入 + 标准输出 = 标准I/O

文件的输入输出 = 文件I/O

cout：全局的流对象（ostream类），默认与屏幕关联。

cin：全局的流对象（istream类），默认与键盘关联。

cerr：标准错误，无缓冲区。

clog：标准日志，有缓冲区。

2.缓冲区

缓冲区：一块内存。

程序从输入缓冲区读数据，发现输入缓冲区没有数据，程序阻塞，等待键盘输入。

输出时，输出缓冲区满，或者刷新输出缓冲区，才可以输出到屏幕上。

PS：在 windos 下，cout << "hello world"; 会立即从缓冲区打印到屏幕上。

在 Linux 下，cout << "hello world"; 不会立刻打印在屏幕，而是输出到输出缓冲区。

cout << "hello world << endl;" 会立刻打印在屏幕上。endl 的作用：输出换行符，并刷新缓冲区。

用以下代码验证：（注意 “有endl的cout”，“有endl的cout” 的打印时间）

#include <iostream>
using namespace std;

int main(){
	cout << "请输入";
	int a;
	cin >> a;
	cout << "有endl的cout" << endl;     // 从缓冲区立即打印到屏幕。
  cout << "没有endl的cout";   					// 不会立即打印到屏幕，for循环运行结束才会打印。 
	for (int i  = 0; i < 100000000; i++) {
  		int num = i + i - i;	
  }
	cout << a;
	return 0; 
}

3.cin的特点

遇到 Tab、空格space、回车Enter时结束，并且空格换行符会留在缓冲区。

4.cin.get()

（1）无参数

从输入缓冲区读取一个字符，返回值为读取到的字符。

可以读空格、读回车。

while((ch = cin.get()) != EOF){  // 判断是否是结束
		cout << ch << endl;
}

（2）一个参数

读取一个字符，给变量赋值。

可以读空格、读回车。

char ch；
cin.get(ch);    // 参数为：字符变量

（3）两个参数

读取一个字符串，并给变量赋值。

字符串中可以包含空格，不可以包含回车。

遇到回车结束，并将回车键保留在缓冲区（和 cin 一样）。(所以不能连续使用 cin.get() )

注意最后有结束符，所以 cin.get(chars, 5); 最多只能读取 4 个字符。

char chars[10] = {0};
cin.get(chars, 5);       // 参数为：字符串变量名， 获取字符串的长度为5

char* p = new char[10];
cin.get(p, 10);					// 参数为：字符串首地址， 获取字符串的长度为10

5.cin.getline()

读取一行字符串。

字符串中可以包含空格，不可以包含回车。

【重要】遇到回车结束，并删除该回车键，不在缓冲区保留。（和 cin、cin.get(buf, 10) 的区别）。

cin.getline(buf, 10); 减去字符串结束符，最多只能读取 9 个字符，若越界，后面其他的 cin语句不会执行。

char ch;
char buf[5] = {0};
cin.getline(buf, 5);   // 读取一个字符串。并去除回车键，以免下一行的 cin.get() 读到回车键。
cin.get(ch);
cout << "==" << ch << "==";

PS：遇到特定字符结束：

加入第三个参数，表示遇到该字符时，结束读取，并且该字符不在缓冲区保留。

char buf[5] = {0};
cin.getline(buf, 5, '9');  
// 当输入 “19” 时，buf = “1”;
// ‘9’既不保存在 buf 中，也不保存在 缓冲区 中。

6.cin.ignore()

忽略缓冲区当前的字符。

比如 cin 之后，碰到空格结束，但是空格还在缓冲区，就可以使用 cin.ignore() 删除缓冲区当前字符。

char a[10], b;
cin.get(a, 10);
cin.ignore()
cin.get(b);
// 当输入 “xxx\ny” 时，变量 b 不是回车，而是 ‘y’，因为 ‘\n’ 被忽略了。

PS：无参数和有参数

// 表示忽略 1 个字符
cin.ignore();

//表示忽略 10 个字符
cin.ignore(10);

// 表示忽略 10 个字符，如果碰到 ‘\n’,停止忽略。
cin.ignore(10, '\n');

7.cin.peek()

看一看缓冲区的第一个字符，但是不取走。返回值为缓冲区的第一个字符。

char ch = cin.peek();

举个例子：实现功能：识别输入的是字符串还是数字。

char ch = cin.peek;              // 看一看缓冲区的第一个字符是什么。
if (ch >= '0' && ch <='9') {     // 对第一个字符进行判断。
	int number;
	cin >> number;                 // 真正读取缓冲区数据。
  cout << "输入的是数字：" << number << endl;
} else {
  char buf[100];
  cin >> buf;                    // 真正读取缓冲区数据。
  cout << "输入的是字符串：" << buf << endl;
}

8.cin.putback()

把字符放回缓冲区。

char ch = ‘a’;
cin.putback(ch);

举个例子：实现和上面相同的功能：识别输入的是字符串还是数字。

char ch = cin.get();             // 读取缓冲区第一个字符。
cin.putback(ch);                 // 将第一个字符放回缓冲区。
if (ch >= '0' && ch <='9') {     // 对第一个字符进行判断。
  int number;
	cin >> number;                 // 读取缓冲区数据。
  cout << "输入的是数字：" << number << endl;
} else {
  char buf[100];
  cin >> buf;                    // 读取缓冲区数据。
  cout << "输入的是字符串：" << buf << endl;
}

9.getline()

cin.getline() 是 istream 类的成员函数，在头文件 <istream> 中。
getline() 是普通函数，在头文件 <string> 中。
区别在于 getline() 可以读取 string 字符串。

先看一下函数声明：

// 类的成员函数
istream& getline (char* s, streamsize n );
istream& getline (char* s, streamsize n, char delim );

// 普通函数（需要将类对象传递进去）
istream& getline (istream&  is, string& str, char delim);
istream& getline (istream&& is, string& str, char delim);
istream& getline (istream&  is, string& str);

与 cin.getline() 一样，可以读取空格，不可以读取回车。

string s;
getline(cin, s);

10.cout.flush()

刷新缓冲区

如果缓冲区没满，或者程序没有结束，cout 是不会输出的，必须刷新缓冲区才可以。

cout.flush();
// 类似的函数：int fflush(FILE *stream);

11.cout.put()

向输出缓冲区写入一个字符。

char c = 'c';
cout.put(c);

// 支持链式编程
cout.put(c).put(c).put(c) << endl;

12.cout.write()

按长度向输出缓冲区写入字符串。

第一个参数为字符串地址，第二个参数为输出字符的个数（不算结束符’\0’）

char s[] = "abcdef";
cout.write(s, strlen(s)) << endl;
cout.write(s, 3) << endl;

13.cout.width()、cout.fill()、cout.setf()

输出格式控制

通过成员方法的方式：

int number = 10;

// 控制进制
cout.unsetf(ios::dec);     // 卸载当前默认的 10 进制输出方式。
cout.setf(ios::oct);       // 设置成八进制输出
cout.setf(ios::showbase);  // 显示八进制数字前的0，十六进制数字前的0x
cout << number << endl;    // 此时，打印为：012

// 控制宽度
cout.width(5);            // 设置为宽度为 5
cout.fill('*');           // 默认右对齐，多余的位置使用 * 填充
cout << number << endl;   // 此时，打印为：**012

// 设置左对齐
cout.setf(ios::left);      // 设置左对齐
cout << number << endl;    // 此时，打印为：012**

通过控制符的方式：

需要引入头文件 #include <iomanip>

int number = 10;
cout << oct  	//八进制输出
  	 << setiosflags(ios::showbase)		// 显示八进制数字前的0，十六进制数字前的0x
     << setw(5)		// 设置为宽度为 5
     << setfill('*')		// 多余的位置使用 * 填充
     << setiosflags(ios::left)	// 设置左对齐
     << number
     << endl;

六、文件操作

继承关系：

iostream 多继承于 istream 和 ostream。
fstream 继承于 iostream。

graph TD
A(istream) --> B(ifstream) 
A --> E(iostream)
C(ostream) --> E
C --> D(ofstream)
E --> F(fstream)

1.文本文件

（1）文件读写的头文件

#include <fstream>

（2）打开文件

通过 ifstream 类的构造函数打开文件。

string source_file_name = "/test_source/STL/todo.txt";   // 文件路径。
ifstream ism(source_file_name, ios::in);  // 只读的方式打开。

string target_file_name = "/test_source/STL/todo_copy.txt";
ofstream osm(target_file_name, ios::out | ios::app);

通过 ifstream 类的成员函数打开文件。

ifstream osm;
osm.open(source_file_name, ios::in);

标志含义：

标志	含义
ios::app	所有写入的字符追加在文件末尾。
ios::in	只读的方式打开。
ios::out	写入的方式打开。
ios::trunc	如果文件存在，清空文件。
ios::binary	二进制的方式打开。

可以多个标志结合使用：

// 写入的方式打开，并将写入的内容追加在文件末尾。
osm.open(target_file_name, ios::out | ios:: app);

（3）判断是否为空

fstream 重载了 ! 符号。

if (!ism || !osm) {
  cout << "文件打开失败！" << endl;
}

（4）读写文件

因为 fstream 是多继承于 iostream 的，所以 cin、cout 的成员函数：get()，getline()，ignore() 等等都可以使用。

// 读文件 & 写文件
char ch;
while(ism.get(ch)) {
  cout << ch;
  osm.put(ch);
}

（5）关闭文件

依旧是类的成员函数。

ism.close();
osm.close();

实例：拷贝文件

/*
实现拷贝文本文件的功能。
*/

#include <fstream>

int main() {

    // 打开读文件
    string source_file_name = "/test_source/STL/todo.txt";
    ifstream ism(source_file_name, ios::in);
    // ifstream ism;
    // ism.open(source_file_name, ios::in);

    // 打开写文件
    string target_file_name = "/test_source/STL/todo_copy.txt";
    ofstream osm(target_file_name, ios::out | ios::app);

    if (!ism || !osm) {
        cout << "文件打开失败！" << endl;
    }

    // 读文件 & 写文件
    char ch;
    while(ism.get(ch)) {
        cout << ch;
        osm.put(ch);
    }


    // 关闭文件
    ism.close();
    osm.close();

    return 0;
}

2.二进制文件

与文本文件不一样的地方是：打开文件的时候，使用 ios::binary 标签。

ofstream osm(target_file_name, ios::out | ios::binary);

实例：对象序列化

值得注意的地方，写文件时，对对象取地址，并强转为 char* 类型。

osm.write((char*)&p1, sizeof(Person));

完整如下：

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

class Person {
public:
    Person(int age, int id) : age(age), id(id){}
    void Show() {
        cout << "age = " << age << endl;
        cout << "id = " << id << endl;
    }
private:
    int age;
    int id;
};

int main(){
    
    // 创建类对象
    Person p1(10, 20), p2(30, 40);

    // 1.打开文件
    string target_file_name = "/Users/STL/todo";
    ofstream osm(target_file_name, ios::out | ios::binary);  // 二进制的方式打开。

    // 2.检查是否打开
    if (!osm) {
        cout << "打开文件失败" << endl;
    }

    // 3.写文件
    osm.write((char*)&p1, sizeof(Person));   // 【取地址后强转为 char*】
    osm.write((char*)&p2, sizeof(Person));

    // 4.关闭文件
    osm.close();

    return 0;
}

实例：对象反序列化

值得注意的是，读文件时，对对象取地址，并强转为 char* 类型。

ism.read((char*)&p1, sizeof(Person));

完整如下：

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

class Person {
public:
    Person(int age, int id) : age(age), id(id){}
    Person(){}
    void Show() {
        cout << "age = " << age << endl;
        cout << "id = " << id << endl;
    }
private:
    int age;
    int id;
};

int main(){
    
    // 创建类对象
    Person p1, p2;

    // 1.打开文件
    string target_file_name = "/Users/STL/todo";
    ifstream ism(target_file_name, ios::in);

    // 2.检查是否打开
    if (!ism) {
        cout << "打开文件失败" << endl;
    }

    // 3.读文件
    ism.read((char*)&p1, sizeof(Person));
    ism.read((char*)&p2, sizeof(Person));

    // 4.关闭文件
    ism.close();

    p1.Show();
    p2.Show();

    return 0;
}

七、STL 概述

STL（Standard Template Library，标准模版库）

STL分为：容器（container）、算法（algorithm）、迭代器（iterator）

1.容器（container）

序列式容器：容器元素的位置，由进入的时机决定。比如 vector。

关联性容器：容器已有规则，与进入的时机有关。比如 set、map。

2.迭代器（iterator）

迭代器类似于指针，实际上迭代器是一个类，类中封装了指针，并重载了 ++、–、* 等等操作符。

其中 begin() 指向首地址，end() 指向最后一个元素的下一个地址。【但迭代器如begin() 不等于地址】

（1）为什么使用迭代器

迭代器是容器和算法之间的桥梁。实现算法时，传递的是容器的迭代器。

（2）迭代器类型

迭代器类型（以 vector 为例）：vector<int>::iterator 。

vector<int>::iterator p_begin = a.begin();

（3）容器算法分离案例

为了使容器和算法互相独立。

实现功能：统计数组中出现某元素个数。

基本思路：容器为数组，迭代器分别指向数组的首部和尾部，将迭代器传入算法。

// 算法
int MyCount(int* p_begin, int* p_end, int num) {   // 传入迭代器
    int count = 0;
    for (int* p = p_begin; p!= p_end; p++) {
        if (*p == num) {
            count++;
        }
    }
    return count;
}

int main() {
    // 容器
    int arr[] = {1, 2, 2, 3, 4, 2};

    // 迭代器
    int *p_begin = &arr[0];
    int *p_end = &arr[sizeof(arr) / sizeof(int)];

    cout << MyCount(p_begin, p_end, 2);
    return 0;
}

3.算法（algorithm）

注意头文件 #include <algorithm>

（1）for_ench()

第一个是 begin()，第二个是 end()，第三个是回调函数，比如 Print() 打印数据。

// 函数声明
for_each(_InputIterator __first, _InputIterator __last, _Function __f);

void Print(int val) {
  cout << val;
  return;
}

int main(){
    vector<int> a(5);
    for_each(a.begin(), a.end(), Print);
    return 0;
}

类似功能实现遍历（以类对象为例）：

<> 中是什么，*it 就代表什么。比如，vector<Person> ，*it 表示 Person 类对象。

class Person {
public:
    int age;
    int id;
    Person(int age, int id) : age(age), id(id) {}
};


int main(){
    vector<Person> v;
    Person p1(10, 20), p2(30, 40);
    v.push_back(p1);
    v.push_back(p2);
    for (vector<Person>::iterator it = v.begin(); it != v.end(); it++) {
      cout << (*it).age << endl;
    }
    return 0;
}

八、string

1.特性

char* 是指针，string 是类，并在类中封装了 char* ，string 是一个 char* 型容器。
封装了成员方法：查找find、拷贝copy、删除delete、替换replace、插入inset。
不用考虑内存释放和越界问题（string 类负责维护）。

2.初始化

// 无参构造
string s1;

// 有参构造
string s2(10, 'a');
string s3("abc");

// 拷贝构造。
string s4(s3);
string s5 = s3;
string s6 = "abc";

3.赋值

string s1("ab"), s2("cd");

// 等号操作符
s1 = "abc";
s1 = s2;
s1 = 'a';

// assign 成员函数
s1.assign("abc");

4.取值

[] at() 区别：如果索引越界，[] 直接报错，at() 抛异常 out_of_range。

string s1 = "abcd";

// 重载 [] 操作符
s1[0] = '0';

// at 成员函数
s1.at(0) = '0';

5.拼接

// 重载 += 操作符
string& operator+=(const string& str);
string& operator+=(const char* str);
string& operator+=(const char c);

// 重载 + 操作符
string operator+(const string& str);

// append 成员函数
string& append(const char* str);    // 字符串 str 连接到当前字符串结尾。
string& append(const string &str); 

// 参数 n 限定。
string& append(const char* str, int n);  // 字符串 str 前 n 个字符连接到当前字符串结尾。
string& append(const string &str, int pos, int n);  // 从 pos 开始的 n 个字符连接在当前字符串尾部。
string& append(int n, char c); // 在当前字符串结尾添加 n 个字符 c。

6.查找

// 从 pos 位置开始，查找字符串 str，返回第一次出现的位置。
int find(const string& str, int pos = 0) const;
int find(const char* str, int pos = 0) const;

// 从 pos 位置开始，查找字符 c，返回第一次出现的位置。
int find(const char c, int pos = 0) const;

// 从 pos 位置开始，查找字符串 str，返回最后一次出现的位置。  
// 如果没有找到，返回 npos。（npos是一个很大的数18446744073709551615UL，如果传递给int变量，= -1）
int rfind(const string& str, int pos = npos);
int rfind(const char* str, int pos = npos);

// 从 pos 位置开始，查找字符 c，返回最后一次出现的位置。
int rfind(const char c, int pos = 0);

例子：

string s = "abcfghfg";

// 查找第一个出现的位置
int frist = s.find("fg");

// 查找最后一个出现的位置
int last = s.rfind("fg");

7.替换

// 从 pos 位置开始的 n 个字符，替换为字符串 str。（被替换的字符，包括 pos 位置字符）
string& replace(int pos, int n, const string& str);
string& replace(int pos, int n, const char* str);

例子：

string s = "abccc";
s.replace(0,2,"xyz===");
cout << s;   // xyz===ccc

8.比较

compare 函数，比较 ascii 码，（大写A比小写a小。A：65，a：97）

对象 > s 时返回对象-s的值（正值）；
对象 < s 时返回对象-s的值（负值）；
对象 = s 时返回 0；

// 与字符串 s 比较大小。
int compare(const string& s) const;
int compare(const string& s) const;

例子：

string s1 = "abc", s2 = "aB";
cout << s1.compare(s2);   // 32（‘b’ - 'B' 的值）

9.截取

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

例子：

string s = “abcd”
cout << s.substr(1);   // "bcd"
cout << s.substr(2, 2) // "bd"

10.插入

【注意】

pos 位置可以用整型表示，并函数返回值为字符串本身。
pos 位置可以用迭代器表示，并返回插入后迭代器的位置或无返回值。（不返回字符串本身，所以不能直接打印。）
(vector、string 的迭代器可以加整型数字；list 的迭代器只能自加。（因为 list 不支持随机访问））

// 从 pos 位置开始，插入字符串 s。（原第 pos 位置字符的前面）
string& insert(int pos, const char* s);
string& insert(int pos, const string& s);

// 在 pos 位置处，插入 n 个字符 c。
string& insert(int pos, int n, char c);

// 用迭代器表示位置。————————————————————————————————————————————————————————
iterator insert(iterator it, char c);//在it处插入字符c，返回插入后迭代器的位置
void insert(iterator it, const_iterator first, const_iteratorlast);//在it处插入从first开始至last-1的所有字符
void insert(iterator it, int n, char c);//在it处插入n个字符c

例子：

string s = "abcde";
char p[] = "==gg==";
cout << s.insert(3, p);   // abc==gg==de
cout << s.insert(3, 5, '+');   // abc+++++==gg==de

//用迭代器表示位置。————————————————————————————————————————————————————————
// 从第 3 位开始插入 ‘A’（有第 0 位）
s.insert(s.begin()+3, 'A');    // 等同于 s.insert(3, 1, 'A');

// 从第 3 位开始插入 10 个‘A’（有第 0 位）
s.insert(s.begin()+3, 10, 'A');    // 等同于 s.insert(3, 10, 'A');

// 插入区间 [ s.begin()+1, s.end() ) 一段字符串。
s.insert(s.begin()+3, s.begin()+1, s.end());

11.删除

// 删除从 pos 开始的 n 个字符。
string& erase(int pos, int n = npos);

例子：

string s = "abcde";
cout << s.erase(1, 2);    // 从 1 号元素开始，删除两个元素。 // ade
cout << s.earse(1);       // 从 1 号元素开始，删到末尾。     // a

12.string 转 char*

接收的变量类型不能是 char * ，而是 const char* ，因为 c_str 返回的是 const char *。不能用安全性低的变量接受安全性高的数据。

string s = "hello";
const char* s_ptr = s.c_str();
cout << s_ptr << endl;  // hello

九、vector

动态数组，单口容器。

2020-08-07-fblvQf

1.动态增长原理与特性

当插入新元素时，若空间不足，

则重新申请更大的内存（两倍空间），
将原空间数据拷贝到新空间，
释放旧空间的数据，
再把新元素插入新空间中。

【注意：】将原空间数据拷贝到新空间时，会调用拷贝构造函数。

特性：

指定位置插入效率低，最坏情况要移动整个数组，时间复杂度 O(n)。
随机读取效率高，O(1)。

2.初始化

// 无参构造函数
vector<int> v1;

// 有参构造
vector<int> v2(v1.begin(), v1.end());  //用迭代器初始化。
vector<int> v3(5, 1);    // 五个元素，都为 1。
vector<int> v4(5);    // 五个元素，都为 0。

// 拷贝构造
vector<int> v5(v2);

// 用数组初始化
int arr[] = {1, 2, 3};
vector<int> v6(arr, arr + sizeof(arr) / sizeof(int));   // 类似于 begin() 和 end()。

3.赋值

vector<int> v1(5, 0);
vector<int> v2;

// 迭代器赋值
v2.assign(v1.begin(), v1.end());

// 用数组（类似于迭代器）
int arr[] = {1, 2, 3, 4, 5};
v2.assign(arr, arr + sizeof(arr) / sizeof(int));

// 赋值 n 个 num
v2.assign(5, 0);

// 重载 = 操作符
v2 = v1;

//交换整个容器
v2.swap(v1);   // v1变为v2，v2变为v1。

4.swap 函数交换原理

栈区有两个 vector 类对象，类成员变量中有一个指针，指向堆区的一块内存。

swap 函数，并非交换所有数据，只是交换指针。

对象地址为：&v；数据地址为：&(v[0]).

2020-08-07-YexN4W

5.大小操作

vector<int> v;

// 容器大小
v.size(); 

// 改变容器大小
// 若 n 比原来大，用 elem 填充新增的空间，无 elem 默认用 0 填充。
// 若 n 比原来小，删除愿容器中多余的数据。
v.resize(int n, elem);     // 【只能改变大小，不能改变容量。】 

// 容器是否为空
v.empty(); // 空返回 true，不空返回 false
if (v.empty()) {
  cout << "v 为空！";
}

// 容器的容量    // 只有string 和 vector 有 capacity 属性
v.capacity();  // 增加空间要拷贝内存，耗时，所以最好一开始申请足够的容量。

6.取值

vector v;

// 抛异常
v.at(0) = 0;

// 不抛异常，重载 [] 操作符
v[0] = 0;

// 返回容器第一个元素
v.front();

// 返回容器最后一个元素
v.back();

7.插入删除

【注意】：vector 的 insert函数 pos 位置，只能用迭代器，(vector、string 的迭代器可以加整型数字；list 的迭代器只能自加。（因为 list 不支持随机访问））

// 样例：
int a = 3;
v.insert(v.begin() + a, 5, 0);

// v.insert(a, 5, 0);  // error
// v.insert(2, 5, 0);  // error

vector v;
// 在 pos 位置插入 1 个元素 0。
v.insert(v.begin(), 0);

// 在 pos 位置插入 5 个元素 0。
v.insert(v.begin(), 5, 0);

// 在尾部插入 1；
v.push_back(1);

// 在尾部删除 1；
v.pop_back();

// 删除迭代器指向的元素
v.erase(const_iterator pos);

// 删除从迭代器 start 到 end 之间的元素。
v.erase(const_iterator start, const_iterator end);  //【左闭右开】

// 清空容器
v.clear();

8.用 swap 收缩空间

用 v 初始化匿名对象（按照 size 的大小初始化，而非 capacity ），并交换匿名对象和 v。

vector<int>(v).swap(v);

例如下面程序，虽然 size 是 10w，但是 capacity 是 13w。因为在扩大空间时，是默认按照两倍空间扩增的。

vector<int> a;
for (int i = 0; i < 100000; i++) {
    a.push_back(i);
}

cout << "a.size() = " << a.size() << endl;    // a.size() = 100000
cout << "a.capacity() = " << a.capacity() << endl;  // a.capacity() = 131072

// 当想要将 容量capacity 缩小成和 大小size 一致时，
vector<int>(v).swap(v);

9.reserve 预留空间

reserve 和 resize 区别：
reserve 是预留空间，不是创建真正的元素对象，未添加对象之前，不能引用容器内元素。
resize 是改变容器大小 size（不改变容量capacity ），调用此函数后，能引用容器内元素。

vector<int> v;
v.reserve(100000);

预留空间的作用： 减少容器扩容时的拷贝。

计算拷贝次数：

注意：&v 不是数据的地址，是栈中 v 对象的地址；而数据储存在堆区，可用 &(v[0]) 表示。
迭代器不是地址，是一个类对象，无法直接和地址比较。

// 方法一：判断 v.begin() 的值是否改变。
vector<int> v;
int count = 0;
vector<int>::iterator address = v.begin();
for (int i = 0; i < 100000; i++) {
    v.push_back(i);
    if (v.begin() != address) {
        address = v.begin();
        count++;
    }
}
cout << count << endl;   // 18次

// 方法二：判断 v[0] 的地址是否改变。
vector<int> v;
int count = 0;
int* address = nullptr;
for (int i = 0 ;i < 100000; i++) {
    v.push_back(i);
    if (address != &(v[0])) {
        address = &(v[0]);
        count++;
    }
}
cout << count << endl;   // 18次

若加入 v.reserve(100000) 则一次也不需要拷贝。

十、deque

double-ended queue 双端队列，（更像双端 vector）.
deque：[/‘di:ke/] queue：[/kju/]

2020-08-11-LFyZ9h

分片存储原理：

左边是一个 map 数组，节点中保存的是右边缓冲区内存片段的地址。
右边是缓冲区，有若干连续的内存片段，片段之间不连续，片段内部连续。

2020-08-11-2dDt8U

1.特性：

双端插入和删除元素效率高。
指定位置插入会导致数据元素移动，效率低。
随机存取效率高。
分块储存，排序效率非常低，【deque 特有的特点】。所以可以拷到 vector 容器中排序再拷回 deque容器。

总结：与其说是双端队列，不如说是双端vector，特性基本相同，API基本相同（差别在于：deque 可以双端插入和删除，vector 只能一端插入删除）。

2.初始化

API 和 vector 相同。

// 无参构造
deque<int> q1;

// 有参构造
deque<int> q2(q1.begin(), q2.end());  
deque<int> q3(5, 1);    // 初始化为 5 个 1；
deque<int> q4(5);       // 初始化为 5 个 0；

// 数组初始化
int arr[] = {1, 4, 3, 6, 3};
deque<int> q6(arr, arr + sizeof(arr)/sizeof(int));

//拷贝构造
deque<int> q5(q1);    // deque<int> q4(const deque &deq);

3.赋值

API 和 vector 相同。

deque<int> q1, q2(10, 1);

// 迭代器赋值
q1.assign(q2.begin(), q2.end());

// 用数组（类似于迭代器）
int arr[] = {1, 2, 3, 4};
q1.assign(arr, arr + sizeof(arr) / sizeof(arr[0]));

// 赋值 n 个 num
q1.assign(10, 2);

// 重载 = 操作符
q1 = q2;

// swap 函数交换
q1.swap(q2);

4.大小操作

API 和 vector 相同。
唯一不同：deque 没有容量capacity 属性（只有string 和 vector 有 capacity 属性）。

deque<int> q(10, 2);

// 返回元素个数
q.size();

// 改变容器大小
// 若 n 比原来大，用 elem 填充新增的空间，无 elem 默认用 0 填充。
// 若 n 比原来小，删除愿容器中多余的数据。
q.resize(int n, elem);

// 容器是否为空
q.empty(); // 空返回 true，不空返回 false
if (q.empty()) {
    cout << "q 为空！";
}

5.双端插入删除

deque<int> q；
// 从后面操作
q.push_back(1);
q.pop_back(1);

// 从前面操作
q.push_front(1);
q.pop_front(1);

6.取值

API 和 vector 相同。

deque<int> q(10, 5);

// 抛异常
q.at(0) = 0;

// 不抛异常，重载 [] 操作符
q[0] = 0;

// 返回容器第一个元素
q.front();

// 返回容器最后一个元素
q.back();

十一、stack

1.特性

不能遍历，不能随机读取；只能通过栈顶元素访问或删除。
不提供迭代器（意味着不能遍历）。

2.初始化

// 默认构造
stack<int> stk;

// 拷贝构造
stack<int> stk(const stack<int> &stk);

3.赋值

stack<int> stk1, stk2;

// 重载 = 操作符
stk1 = stk2;

4.大小操作

stack<int> stk;

// 元素个数 
stk.size();

// 是否为空
stk.empty();

5.插入删除

stack<int> stk;

// 插入
stk.push_back(10);

// 删除
stk.pop();

// 访问顶部元素
stk.top();

十二、queue

1.特性

不支持随机访问。
不提供迭代器，所以不能遍历。

2.初始化

// 默认构造
queue<int> q;

// 拷贝构造
queue<int> q(const queue<int> &another_q);

3.赋值

queue<int> q1, q2;

// 重载 = 号操作符
q1 = q2;

4.大小操作

queue<int> q;

// 元素个数
q.size();

// 是否为空
q.empty();

5.插入删除

queue<int> q;

// 队尾插入元素
q.push(10);

// 队首删除元素
q.pop();

6.取值

queue<int> q;

// 返回队首元素
q.back();

// 返回队尾元素
q.front();

十三、list

简要图：

2020-08-13-XlF1X8

实际上的图：

有头节点 head_node：data 是随机值，next 指向 begin() 位置节点。
首尾相连，end() 指向头节点位置。

验证：

int arr[] = {1, 4, 3, 6, 3};
list<int> l(arr, arr + sizeof(arr)/sizeof(int));

cout << *l.end();    // 随机值
cout << *(++l.end());  // begin() 位置的节点的 data。

2020-08-16-7j0SBg

1.特性

节点包括两个域：数据域、指针域；
不需要连续的内存空间；
添加和删除元素效率高；
链表需要的时候，才分配内存；
链表需要额外的空间保存节点关系（前驱后继）。

2.初始化

 // 默认构造 
list<int> l1;

// 有参构造
list<int> l2(l1.begin(), l1.end());  // 用迭代器
list<int> l3(10, 5);   // 初始化为 10 个 5

// 用数组初始化
int arr[] = {1, 4, 3, 6, 3};
list<int> l(arr, arr + sizeof(arr)/sizeof(int));

// 拷贝构造
list<int> l4(l3);

3.赋值

list<int> l1, l2(5, 0);

// 用区间 [l2.begin() + 1, l2.end())    // list 的迭代器不可以加整型，只能自加。
l1.assign(++l2.begin(), l2.end());

l1.assign(5, 1);  // 将 l1 赋值为 5 个 1。

// 重载 = 操作符
l1 = l2;

// 交换链表
l1.swap(l2);

4.大小操作

list<int> l(10, 5);

// 节点个数
l.size();

// 是否为空
l.empty();

// 重新指定大小
l.resize(num);
// 若容器变长，以 elem 填充，否则以 0 填充。
l.resize(num, elem);

5.取值

list<int> l(10, 1);
// 返回第一个元素
l.front();
// 返回最后一个元素
l.back();

// 迭代器取星
*l.begin() = 10;

6.插入删除

insert 函数只能使用迭代器。
list 的迭代器，不可以加整数，只能自加（因为 list 不支持随机访问）。

list<int> l(10, 5);

l.push_back(0);
l.pop_back();
l.push_front(1);
l.pop_front();

// 使用迭代器。
l.insert(l.begin(), 8);
l.insert(++l.begin(), 2, 8);

list<int>::iterator it = l.begin();
it++;
it++;
it++;
l.insert(it, 2, 8);   // 迭代器只能自加。

// l.insert(l.begin() + 3, 2, 8); // error，只能自加。
l.insert(l.end(), l.begin(), l.end());

// 清空
l.clear();

// 删除区间 [it, l.end()) 的内容。
list<int>::iterator it = l.begin();
it++;
l.erase(it, l.end());

// 删除匹配的所有值
l.remove(5);  // 删除所有 5；

7.链表反转和排序

list<int> l(10, 5);

// 翻转链表
l.reverse();

// 链表元素排序
bool compare(int a, int b) {
  return a > b;
}

l.sort(compare); // 调用回调函数 compare， 若无参数，默认按从小到大。

8.为什么有成员函数 sort？

list 不支持随机访问，如果使用算法中的 sort 函数，效率不稳定。

十四、set/multiset

基于红黑树（平衡二叉树的一种）实现的。

1.特性

属于关联容器：元素位置由容器规则实现的；
查找效率非常高（元素自动排序）；
set 不可以有重复元素，multiset 可以有重复元素。
提供迭代器，但是不能通过迭代器改变数的值（如何改变元素数值，删除旧数据，添加新数据）。
和 map 一样，不可以修改 key，因为 key 关系到容器元素的顺序。

2.初始化

// 默认构造函数
set<int> s1;
multiset<int> s2;

// 用数组初始化
int arr[] = {1, 4, 3, 5, 2};
set<int> s4(arr, arr + sizeof(arr)/sizeof(int));

// 用迭代器初始化
set<int> s5(s4.begin(), s4.end());

// 拷贝构造函数
set<int> s2 = s1;
set<int> s6(s1);

3.赋值

set<int> s1, s2;

// 重载 = 操作符
s1 = s2;

// 交换两个容器
s1.swap(s2);

4.大小操作

set<int> s1;

// 返回元素个数
s1.size();

// 判断容器是否为空
s1.empty();

5.插入删除

erase 的位置参数只能使用迭代器（只有 string 可以使用数字代表位置 pos ），迭代器不能加常量，只能自加。（因为 set 不支持随机访问）

set<int> s;

// 插入元素
s.insert(elem);

// 清空数组
s.clear();

// 删除迭代器所指元素，返回下一个元素的迭代器。
s.erase(s.begin());

set<int>::iterator it = s.begin();
it++;
it++;
s.erase(it);

// 删除迭代器区间的元素，返回下一个元素的迭代器。
s.erase(++s.begin(), s.end());

// 删除 值为 elem 的全部元素（set 无重复，multiset 有重复）。
s.erase(elem);

6.查找

如果 set 存储的是对象，那么按照什么变量排序，find 函数查找时，就是把什么变量当作 key。

见：如果排序对象呢？

// 1.找到，则返回当前位置的迭代器；2.未找到，返回 s.end() 迭代器。
s.find(3);

// 返回第一个 key >= keyElem 元素的迭代器。(lower_bound：下界)
lower_bound(keyElem);

// 返回第一个 key > keyElem 元素的迭代器。 (upper_bound：上界)
upper_bound(keyElem);

// 返回 lower_bound、upper_bound 函数的两个迭代器。
equal_range(keyElem);

例子：

int arr[] = {1, 7, 3, 5, 2};
set<int> s(arr, arr + sizeof(arr)/sizeof(int));

// s.find(3);  1.找到，则返回当前位置的迭代器；2.未找到，返回 s.end() 迭代器。
set<int>::iterator res = s.find(3);
if (res == s.end()) {
    cout << "Not found" << endl;
} else {
    cout << "Got it:" << *res << endl;  // Got it:3
}

// lower_bound(3);  返回第一个 key >= keyElem 元素的迭代器。
res = s.lower_bound(3);
if (res == s.end()) {
    cout << "Not found" << endl;
} else {
    cout << "Got it:" << *res << endl;  // Got it:3
}

// upper_bound(3);   返回第一个 key > keyElem 元素的迭代器。
res = s.upper_bound(3);
if (res == s.end()) {
    cout << "Not found" << endl;
} else {
    cout << "Got it:" << *res << endl;  // Got it:5
}

// equal_range(3);   返回 lower_bound、upper_bound 函数的两个迭代器。pair 对组。
pair<set<int>::iterator, set<int>::iterator> pair_res = s.equal_range(3);

if (pair_res.first == s.end()) {
    cout << "lower_bound:  Not found" << endl;
} else {
    cout << "lower_bound:  Got it:" << *pair_res.first << endl;  // Got it:3
}

if (pair_res.second == s.end()) {
    cout << "upper_bound:  Not found" << endl;
} else {
    cout << "upper_bound:  Got it:" << *pair_res.second << endl;  // Got it:5
}

7.pair 对组

对组 pair 将一对值组合成一个值，这一对值可以具有不同的数据类型，两个值分别用 pair 的两个公有函数 first 和 second 访问。

类模版：

template<class T1, class T2> struct pair.

如何创建对组？

// 第一种构造
pair<string, int> pair_01(string("name"), 20);
pair<string, int> pair_02("name", 20);

pair<string, int> pair_03 = make_pair("name", 20);

// 拷贝构造
pair<string, int> pair_04 = pair_03;
pair<string, int> pair_05(pair_04);

// 重载 = 操作符
pair_04 = pair_02;

// 取值
cout << pair_03.first << endl;;
cout << pair_03.second << endl;

8.仿函数（函数对象）

函数对象也叫仿函数。
函数对象是类，不是函数，只是重载了 () 操作符。
行为类似于函数的对象。

// 以下代码用于更改 set 排序顺序

template<class T>
class Compare {
public:
    bool operator()(const T &a, const T &b) {   // 重载了 () 操作符，并且传入参数。
        return a > b;
    }
};

/*  // 第二种写法：
template<class T>
struct Compare {
  	bool operator()(const T &a, const T &b) {
      	return a > b;
    }
};
*/

int main() {
    Compare<int> com;
    cout << com(1, 2);
}

仿函数的另外一个作用：函数对象超出函数的概念，函数对象可以保存函数调用的状态。

当统计函数调用次数时，就可以使用函数对象。函数对象可以用成员变量保存次数。
如果使用普通函数，就需要用全局变量保存次数，开发中，应少用全局变量。

class MyPrint {
public:
    MyPrint(){
        num = 0;
    }
    MyPrint& operator()(int number) {
        cout << number << endl;
        num++;              // 调用一次，num 就 ++。
        return *this;
    }
    int getNum() {
        return this->num;
    }
private:
    int num;    // 记录函数调用多少次
};

int main() {
    vector<int> v(10, 5);
    MyPrint print_01;
  	// 将对象 print_01 传入，for_each 会拷贝该对象，执行完后会将拷贝的对象作为返回值返回。
    // 1.print_01 中的 num = 0; 
    // 2.for_each 实际调用的是 print_01 的拷贝对象，并将拷贝对象返回；
    // 3.实例化一个新的对象来接收返回值。
    MyPrint print_02 = for_each(v.begin(), v.end(), print_01);  
    cout << print_01.getNum();  // 0
    cout << print_02.getNum();  // 10
}

9.更改默认排序

写一个仿函数 Compare，并把 Compare 当错参数传入 set 中。

// 仿函数
template<class T>
class Compare {
public:
    bool operator()(const T &a, const T &b) {
        return a > b;       // 从大到小
    }
};


int main() {
    int arr[] = {1, 7, 3, 5, 2};
  
  	// 添加仿函数为参数。
    set<int, Compare<int> > s(arr, arr + sizeof(arr)/sizeof(int));

    // for (set<int>::iterator it = s.begin(); it != s.end(); it++) {
    //    cout << *it << " ";
    }
}

如果排序对象呢？

以下面代码为例，如果以 Person 的 id 进行排序，find 函数查找时，就是按照 id 为key 进行查找，并且查找过程中不关心 age 的值。

// 定义一个类
class Person {
public:
    Person(int id, int age) {
        this->id = id;
        this->age = age;
    }
    int id;
    int age;
};

// 排序规则：以 Person 类的 id 进行大小排序
class Compare {
public:
    bool operator()(const Person &a, const Person &b) {
        return a.id > b.id;
    }
};

int main() {
    Person p1(10, 20), p2(20, 30), p3(30, 40);
  
    // 初始化容器时，将仿函数传入。将是按照 id 的大小排序，并且 id 成为 key。 
    set<Person, Compare> s;
    s.insert(p1);
    s.insert(p2);
    s.insert(p3);

    for (set<Person>::iterator it = s.begin(); it != s.end(); it++) {
        cout << it->id << " ";
    }
  
  	// find 函数以 id 为 key 进行查找。
  	Person p4(10, 11);
    cout << "id: " << s.find(p4)->id << " age: " << s.find(p4)->age;	
}

十五、map/multimap

基于红黑树（平衡二叉树的一种）实现的。

map 把数据封装成一个 pair 键值对，有键值 key、实值 value，（pair 第一个值是键值，第二个值是实值），所有元素根据键值自动排序。（相比于 set，区别在于 set 键值实值是一个值）

1.特性

属于关联容器：元素位置由容器规则实现的；
map 中 key 不能重复，multimap 中 key 可以重复。
可以通过迭代器改变 map 的 key 吗？
不能！和 set 容器一样，key 关系到容器内的元素的排列规则，任意改变键值会破坏容器的排列规则。（set 和 map 只能删了旧 key，再添加新的。）

2.初始化

map<int, int> m;

3.插入

【map】

插入的一个 pair 对组，并且 key 不能重复。
insert 有返回值 pair<iterator, bool>。
[] 访问，不存在则创建（有值则为所的赋值，无值则为默认值），存在则修改实值。

【multimap】

insert 有返回值 iterator，标记插入位置的迭代器。
不能用 [] 访问。

// insert 返回值是 pair<iterator, bool>，第一个值标记着插入位置的迭代器，第二个值标记着是否插入成功。
pair<map<int, int>::iterator, bool> res = m.insert(map<int, int>::value_type(0, 10));
if (res.second) {
  	cout << "插入成功!" << endl;
} else {
  	cout << "插入失败!" << endl;
}
m.insert(pair<int, int>(10, 10));
m.insert(make_pair(20, 10));

// 如果 m[30] 不存在，创建 m[30]；
// 如果 m[30] 存在，修改实值。
m[30] = 10;
m[40];      // 只要访问，默认创建 m[40] = 0;（int 的默认值是 0，string 的默认值是 “”）

4.遍历

for (map<int, int>::iterator it = m.begin(); it != m.end(); it++) {
    cout << “key:” << it->first << endl;  // it 指向的是一个对组
}

5.删除

erase 的位置参数只能使用迭代器（只有 string 可以使用数字代表位置 pos ），迭代器不能加常量，只能自加。（因为 map 不支持随机访问）

// 清空元素。
m.clear();

// 删除迭代器 pos 位置 的元素，返回下一个元素的迭代器。
map<int, int>::iterator pos = m.begin();
pos++;
pos++;
m.erase(pos);

// 删除迭代器区间 [++m.begin(), m.end()] 的元素。
m.erase(++m.begin(), m.end());

// 删除容器中 key = key_elem 的对组。
m.erase(key_elem);

6.查找

// 查找键值 key 是否存在，存在返回该键迭代器，不存在，则返回 m.end()。
m.find(key);

// 返回键值 key 的个数。
m.count(key);

// 返回第一个 >= key 的元素的迭代器。
m.lower_bound(key);

// 返回第一个 > key 的元素的迭代器。
m.upper_bound(key);

// 返回 lower_bound 和 upper_bound 的两个迭代器
m.equal_range(key);

7.更改排序规则

加入规则时，可以使用 class 和 struct 。
bool operator() 函数必须限定返回值为 const 修饰。
以对象为 key，必须有规则。

// 规则写法一：
struct Compare {
    bool operator()(const MyKey &a, const MyKey &b) const {  // const 修饰返回值
        return a.index > b.index;
    }
};

// 规则写法二：
// class Compare {
// public:
//     bool operator()(const MyKey& a, const MyKey& b) const {  // const 修饰返回值
//         return a.index > b.index;
//     }
// };

int main() {
    // 带上规则初始化
    map<MyKey, int, Compare> m;

    // 插入元素（对组）
    m.insert(pair<MyKey, int>(MyKey(1, 2), 10));
    m.insert(make_pair(MyKey(2, 3), 10));
    m.insert(map<MyKey, int, Compare>::value_type(MyKey(3, 4), 10));

    // 遍历，打印对象
    for (map<MyKey, int, Compare>::iterator it = m.begin(); it != m.end(); it++) {
        cout << it->first.index << ":" << it->first.id << "  " << it->second << endl;
    }
}

十六、STL

1.容器的共性机制

【拷贝】：

STL 容器提供的都是值（value）寓意，而非引用（reference）寓意。
当我们插入元素时，容器内部实施了拷贝动作：拷贝值到容器，而不是将原数据放入容器。
【提供给容器的元素必须能被拷贝。】

【迭代器】：

除 queue 和 stack 外，每个容器都有迭代器。
string、vector、deque 的迭代器可以加常数，list、set、map 只能迭代器自加（不空随机访问）。

【异常】

一般不会抛异常，需要传入正确的参数。

【大小的函数】

size、empty 所有容器都有。

2.容器深拷贝和浅拷贝

当元素插入容器时，容器将拷贝该元素，而且应该是深拷贝。

因为程序结束时，p 调用一次析构函数，v 中的元素也会调用一次析构函数，对堆区同一内存进行析构，报错！

【如果容器元素为对象，类中必须有拷贝构造函数（深拷贝）、重载等号操作符（深拷贝）】

class Person {
public:
    Person(const char *name) {
        this->name = new char[strlen(name) + 1];
        strcpy(this->name, name);
    }
    
   /*  // 如果没有拷贝构造函数，将会报错。 
    Person(const Person& another) {
        this->name = new char[strlen(another.name) + 1];
        strcpy(this->name, another.name);
    }
    
    // 等号操作符，也要注意深拷贝。
    Person& operator=(const Person& another) {
        if (this->name != nullptr) {
            delete this->name;
        }
        this->name = new char[strlen(another.name) + 1];
        strcpy(name, another.name);
        return *this;
    }
    */

    ~Person() {
        if (this->name != nullptr) {
            delete this->name;
        }
    }

private:
    char* name;
};

int main(){
    Person p("Tom");
    vector<Person> v;
    v.push_back(p);
    return 0;
}

3.谓词

谓词：返回值为 bool 类型的普通函数或者返回值为 bool 类型的重载 operator() 的仿函数。

如果 operator() 接收一个参数，叫一元谓词。
接收两个参数，叫二元谓词。

4.内建函数对象

什么是函数对象：仿函数（函数对象）

STL 内建了一些函数对象：算术类函数对象、关系运算类函数对象，逻辑运算类函数对象。

使用需要引用头文件：#include <functional>

举个例子：list 的自己的成员函数，sort 中的关于排序规则的参数，默认使用自己的内建函数对象。

list<int> l;
l.sort();   // 无参数，默认调用内建函数对象，排序从小到大

// 链表元素排序
bool compare(int a, int b) {
  return a > b;
}
l.sort(compare); // 有回调函数

算术类函数对象：

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<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>    //小于等于

逻辑运算类函数对象：

template<class T> bool logical_and<T> //逻辑与
template<class T> bool logical_or<T>  //逻辑或
template<class T> bool logical_not<T> //逻辑非

5.函数对象适配器

需要头文件 #include <functional>

（1）绑定适配器 bind1st、bind2nd

将一个二元的函数对象转变为一元的函数对象。

【需求】：for_each 调用仿函数 MyPrint，想打印 val + 100 的数值，并不修改 MyPrint。

【问题】：for_each 调用仿函数，只能调用一个一元函数对象。如何将 100 当作参数传入一元函数对象？

// for_each 的定义
for_each(_InputIterator __first, _InputIterator __last, _Function __f)
{
    for (; __first != __last; ++__first)
        __f(*__first);   // 只能传入一个参数，为一元函数或者一元函数对象。
    return __f;
}

【解决】：使用 bind2nd，将一个二元的函数对象转变为一元的函数对象。

MyPrint 要继承 binary_function<T> 类，类型中写 <参数类型, 参数类型, 返回值类型>。
operator() 函数要用 const 修饰，因为 bind2nd 参数是 const 修饰的。

bind2nd(const __Operation& __op, const _Tp& __x)
    {return binder2nd<__Operation>(__op, __x);}

完整代码：

class MyPrint : public binary_function<int, int, void> {   // 继承 + 类型
public:
    void operator()(int val, int number) const {   // const 修饰
        cout << val + number << endl;
    }
};

int main() {
    vector<int> v(10, 5);
    MyPrint print;
    for_each(v.begin(), v.end(), bind2nd(print, 100));   // 使用 bind2nd
}

bind1st 和 bind2nd 有什么区别？

bind1st 将 100 绑定为函数对象的第一个参数。
bind2nd 将 100 绑定为函数对象的第二个参数。

（2）取反适配器 not1、not2

not1：一元谓词取反。
not2：二元谓词取反。

【需求】：sort 排序时，需要传入规则 Compare，（否则默认按照从小到大排序），不过不想更改规则，如何将从大到小变成从小到大排序？

【解决】：使用取反适配器，因为比较两个值大小，所有使用 not2（二元仿函数）。

Compare 要继承 binary_function<T> 类，类型中写 <参数类型, 参数类型, 返回值类型>。
operator() 函数要用 const 修饰。
【注意】一元仿函数继承 unary_function，二元仿函数继承 binary_function。

完整代码：

struct Compare : public binary_function<int, int, bool> {   // 继承 binary_function，类型为 <参数类型，参数类型，返回值类型>
    bool operator()(const int &a, const int &b) const {   // 返回值用 const 修饰
        return a > b;
    }
};

int main() {
    vector<int> v;
    // 生成随机数
    srand((unsigned)time(NULL));
    for (int i = 0; i < 10; i++) {
        v.push_back(rand() % 100);
    }
		
  	// 遍历
    for (int i = 0; i  < 10; i++) {
        cout << v[i] << "  ";
    }
    cout << endl << "=====================================" << endl;

  	// 排序
    sort(v.begin(), v.end(), not2(Compare()));  // 使用取反适配器
		
  	// 遍历
    for (int i = 0; i  < 10; i++) {
        cout << v[i] << "  ";
    }
}

/*
71  0  97  44  92  37  75  25  41  20  
=====================================
0  20  25  37  41  44  71  75  92  97 
*/

（3）函数对象适配器

将普通函数修饰为函数对象。

ptr_fun：普通函数无法使用 bind2st 适配器，所以需要先将普通函数修饰为函数对象。

// 普通函数
void Print(int val, int tmp) {
    cout << val + tmp << endl;
    return;
}

int main() {
    vector<int> v(10, 5);
    // 【ptr_fun(Print)】  将普通函数 修饰为 函数对象。
    for_each(v.begin(), v.end(), bind2nd(ptr_fun(Print), 100));
}

mem_fun_ref、mem_fun：将类的成员函数修饰为函数对象。

调用方式比较特殊：mem_fun_ref(&Person::Show) 取类的地址 :: 对象名。

mem_fun、mem_fun的区别：

如果存放的是对象，使用 mem_fun_ref。
如果存放的是对象指针，使用 mem_fun。

class Person {
public:
    Person(int age, int id) {
        this->age = age;
        this->id = id;
    }
    void Show() {
        cout << "id:" << id << " age:" << age << endl;
    }
    void NewID(int val) {
        cout << "new_id:" << id + val << endl;
    }
private:
    int age;
    int id;
};

int main() {
    Person p1(10, 20), p2(30, 40);
    vector<Person> v;
    v.push_back(p1);
    v.push_back(p2);
  
  	
    // 【mem_fun_ref(&Person::Show)】  将类中的函数修饰成函数对象。
    for_each(v.begin(), v.end(), mem_fun_ref(&Person::Show));
    // 【bind2nd(mem_fun_ref(&Person::NewID), 1999)】  使用 bind2nd，使二元的函数对象，修饰为 一元的函数对象。
    for_each(v.begin(), v.end(), bind2nd(mem_fun_ref(&Person::NewID), 1999));
  
  
  	vector<Person*> v_ptr;
    v_ptr.push_back(&p1);
    v_ptr.push_back(&p2);
    // 【mem_fun(&Person::Show)】  将类中的函数修饰成函数对象。
    for_each(v_ptr.begin(), v_ptr.end(), mem_fun(&Person::Show));
  
    return 0;
}

6.常用的查找算法

（1）find

find(v.begin(), v.end(), 5)

若找到，返回迭代器；没找到，返回 end 迭代器。

【打印之前需要判断是否等于 end() 】
【若是储存元素为对象，应写重载 == 操作符】

// 源码
find(_InputIterator __first, _InputIterator __last, const _Tp& __value_)
{
    for (; __first != __last; ++__first)
        if (*__first == __value_)   // 此处用 == 判断，所以类要重载 == 操作符。
            break;
    return __first;
}

样例代码：

// 普通元素
vector<int> v(10);
for (int i = 0; i < 10; i++) {
    int tmp = rand() % 10;
    v[i] = tmp;
}

// find 函数：找到，返回迭代器；没找到，返回 end 迭代器。
vector<int>::iterator it  = find(v.begin(), v.end(), 5);
if (it != v.end()) {
    cout << "找到啦！" << endl;
} else {
    cout << "没有找到！" << endl;
}

// 元素为对象
class Person {
public:
    Person(int id) {
        this->id = id;
    }
    // 重载 == 操作符
    bool operator==(const Person& another) const {
        if (this->id == another.id) {
            return true;
        }
        return false;
    }
private:
    int id;
};

int main() {
    Person p1(10), p2(20);
    vector<Person> v;
    v.push_back(p1);
    v.push_back(p2);

    vector<Person>::iterator it  = find(v.begin(), v.end(), p1);
    if (it != v.end()) {
        cout << "找到啦！" << endl;
    } else {
        cout << "没有找到！" << endl;
    }
}

（2）binary_search

二分查找，只能用于有序序列。

返回值为 bool，若找到返回 true，没找到返回 false。

int main() {
    vector<int> v;
    for (int i = 0; i < 10; i++) {
        v.push_back(i);
    }
    // 二分查找
    bool res  = binary_search(v.begin(), v.end(),5);
    if (res) {
        cout << "找到啦！" << endl;
    } else {
        cout << "没有找到！" << endl;
    }
}

（3）adjacent_find

查找重复相邻的元素。

返回值：相邻元素的第一个位置的迭代器。
若无相邻重复的元素，返回 end()。

vector<int> v;
for (int i = 0; i < 10; i++) {
    v.push_back(i);
}
v.push_back(9);

vector<int>:: iterator it = adjacent_find(v.begin(), v.end());
if (it == v.end()) {
    cout << "没有找到！" << endl;
} else {
    cout << "找到：" << *it << endl;
}

（4）find_if

调用回调函数，判断是否找到。

_InputIterator find_if(_InputIterator __first, _InputIterator __last, _Predicate __pred)
{
    for (; __first != __last; ++__first)
        if (__pred(*__first))
            break;
    return __first;
}

举个列子：找到第一个大于 6 的数。

// find_if 调用回调函数 MySearch，把 *it 传入 MySearch，如果得到 true 则找到。
bool MySearch(int val) {
    if (val > 5) {
        return true;
    }
    return false;
}

int main() {
    vector<int> v;
    for (int i = 0; i < 10; i++) {
        v.push_back(i);
    }
    v.push_back(9);
     
    vector<int>:: iterator it  = find_if(v.begin(), v.end(), MySearch);  // 回调函数,也可以是 仿函数。
    if (it == v.end()) {
        cout << "没有找到！" << endl;
    } else {
        cout << "找到！" << *it << endl;
    }
		return 0;
}

（5）count、count_if

count：元素出现次数

count_if：根据回调函数，统计元素符合条件的个数。

// count
int main() {
    vector<int> v;
    for (int i = 0; i < 10; i++) {
        v.push_back(i);
    }
    v.push_back(9);

    int num = count(v.begin(), v.end(), 9);  // 查找元素 9 出现的次数。
    cout << "num: " << num << endl;
    return 0;
}

// count_if
struct MySearch {
    bool operator()(int val) {
        if (val > 5) {                 // 大于 5 出现的元素个数。
            return true;
        }
        return false;
    }
};


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

    MySearch m;
    int num = count_if(v.begin(), v.end(), m);  // 调用回调函数
    cout << "num: " << num << endl;
    return 0;
}

7.常用的遍历

（1）for_each

见：遍历容器

for_each(iterator begin, iterator end, _callback);

（2）transform

将一个容器的元素搬运到另一个容器中。

参数：原容器的begin()，原容器的end()，新容器的begin()，回调函数。

transform(iterator begin1, iterator end, iterator begin2, _callback);

实例：

int CallBack(int val) {
    return val;
}

int main() {
    vector<int> v1, v2;
    for (int i = 0; i < 10; i++) {
        v1.push_back(rand() % 100);
    }
		
  	// 1.先初始化足够的空间。
    v2.resize(v1.size());
    // 2.搬运元素。
    transform(v1.begin(), v1.end(), v2.begin(), CallBack);
    return 0;
}

Mark

C/C++ STL

本博客所有文章均个人原创，除特别声明外均采用 CC BY-SA 4.0协议，转载请注明出处！

Gtihub Action｜一行命令解决 LeanCloud 流控问题上一篇

用废旧手机搭建一个 Linux 服务器下一篇

学习笔记｜STL

一、函数模版

1.基本语法

2.自动类型推导和显式指定类型

3.函数模版和普通函数的区别

4.模版函数的实现原理

二、类模版

1.基本格式

2.类模版的派生

（1）模版类派生普通类

（2）模版类派生模版类

3.类模版+友元函数

（1）类模版+普通/友元+类内定义

（2）类模版+普通函数+类外定义

（3）分文件编程报错

（4）C++编译机制

（5）类模版+友元函数+类外定义

第一种格式：二重模版

第二种格式：声明前置

4.类模版+static成员

5.实例：MyArray

三、类型转换

1.static_cast

2.dynamic_cast

3.const_cast

4.reinterpret_cast

5.建议

四、异常

1.异常的好处

2.基础语法

3.跨函数 和 不可忽略

4.栈解旋（unwinding）

5.异常接口的声明

6.对象做异常类型

7.异常对象的生命周期

五、输入输出流

1.流的概念和流类库

2.缓冲区

3.cin的特点

4.cin.get()

5.cin.getline()

6.cin.ignore()

7.cin.peek()

8.cin.putback()

9.getline()

10.cout.flush()

11.cout.put()

12.cout.write()

13.cout.width()、cout.fill()、cout.setf()

六、文件操作

1.文本文件

实例：拷贝文件

2.二进制文件

实例：对象序列化

实例：对象反序列化

七、STL 概述

1.容器（container）

2.迭代器（iterator）

（1）为什么使用迭代器

（2）迭代器类型

（3）容器算法分离案例

3.算法（algorithm）

（1）for_ench()

八、string

1.特性

2.初始化

3.赋值

4.取值

5.拼接

6.查找

7.替换

8.比较

9.截取

10.插入

11.删除

12.string 转 char*

九、vector

1.动态增长原理与特性

2.初始化

3.赋值

3.跨函数和不可忽略

（1）for_ench()