学习笔记|STL

本文最后更新于:2 个月前

一、函数模版

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)类模版+普通函数+类外定义

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

  1. 类外实现类成员函数时,需要写明 template <class T>

  2. 使用 类作用域符 时,需要写明泛型。

  • 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.动态增长原理与特性

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

  1. 则重新申请更大的内存(两倍空间),
  2. 将原空间数据拷贝到新空间,
  3. 释放旧空间的数据,
  4. 再把新元素插入新空间中。

特性:

  • 指定位置插入效率低,最坏情况要移动整个数组,时间复杂度 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;
    }
}

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

  • 返回值为 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;
}

 目录

致敬李文亮及各路英雄好汉!