C++理论学习

C基础

排序

排序次数 = 数组size - 1

比较次数 = 数组size - 1 - 排序轮次

在数值上相同

定义交换函数

template <typename T>
void Swap(T &a, T &b) {
    T temp = a;
    a = b;
    b = temp;
}

冒泡法：

• 重复遍历数组，比较相邻元素
• 如果顺序错误（前 > 后），则交换它们
• 每轮遍历将最大元素”冒泡”到正确位置

template <typename T>
void MSort(T arr[], const auto len) {
    for (int i = 0; i < len - 1; i++) {
        for (int j = 0; j < len - i - 1; j++) {
            if (arr[j] > arr[j + 1]) {
                Swap(arr[j], arr[j + 1]);
            }
        }
    }
}

选择法：

• 每次从未排序部分选出最大/小元素

• 将其放到已排序序列的末尾

template <typename T>
void XSort(T arr[], const auto len) {
    for (int i = 0; i < len-1; i++) {
        int min = i;
        for (int j = i+1; j < len; j++)
            if (arr[j] < arr[min])
                min = j;
        if (min!=i)
            swap(arr[i], arr[min]);
    }
}

指针

空指针NULL不能访问

常量指针const int * p = &a

指针的指向(地址)可以改，但指针指向的值不可修改

指针常量int * const p = &a

指针的指向(地址)不可以改，但指针指向的值可以改

const int * const p = &a

指针的指向(地址)不可以改，指针指向的值也不可修改

无论什么指针都占四个字节

引用

数据类型 &别名 = 原名

别名可以和原名相同

对引用的操作会直接作用于原变量

通过引用参数产生的效果同按地址传递是一样的，引用的语法更清楚简单

引用很容易与指针混淆，它们之间有三个主要的不同：

• 不存在空引用，引用必须连接到一块合法的内存
• 一旦引用被初始化为一个对象，就不能被指向到另一个对象；指针可以在任何时候指向到另一个对象
• 引用必须在创建时被初始化，指针可以在任何时间被初始化。
• 引用的对象必须是一个变量，而指针必须是一个地址

引用的本质是一个指针常量

程序内存

c++ 在程序运行之前分为全局区和代码区

全局区的数据在程序结束后由操作系统释放

不在全局区的数据：

• 局部变量
• const修饰的局部变量(局部常量)

全局区的数据：

• 全局变量
• 静态变量(static 关键字)
• 常量(const修饰的全局常量和字符串常量)

栈区：

由编译器自动分配释放，存放函数的参数值，局部变量等，在函数内部声明的所有变量都将占用栈内存

如果想保留需要加上static关键字放入全局区

注意事项：不要返回局部变量的地址，栈区开辟的数据由编译器动释放

堆区：

这是程序中未使用的内存，在程序运行时可用于动态分配内存

在C++中主要利用new在堆区开辟内存，在程序结束最好delete释放内存

空类占1字节的内存

随机数

伪随机数：

#include <ctime>
int main(){
	srand(time(nullptr));
	rand()%100 // 0-99
}

真随机数产生：

#include <iostream>
#include <random>  // C++11 随机数库
int main() {
    // 1. 创建真随机种子源（基于硬件熵）
    std::random_device rd;
    
    // 2. 选择高质量的随机引擎（Mersenne Twister）
    std::mt19937 gen(rd());
    
    // 3. 定义随机数分布（例如：0-99的均匀分布）
    std::uniform_int_distribution<int> dist(0, 99);
    // 3. 定义浮点随机数分布（60.0 - 100.0）
    //std::uniform_real_distribution<double> dist(60.0, 100.0);
    
    // 生成随机数
    for (int i = 0; i < 10; ++i) {
        std::cout << dist(gen) << " ";
    }
}

类和对象

C++面向对象的三大特性为：封装、继承、多态

定义一个类需要使用关键字 class，然后指定类的名称

类的主体包含在一对花括号中，主体包含类的成员变量和成员函数

类可以被看作是一种模板，可以用来创建具有相同属性和行为的多个对象

声明类的对象，就像声明基本类型的变量一样，格式为：<类名> <对象名表>

空对象也占用1个字节空间，是为了区分空对象占用内存的位置

定义类的过程就是对问题进行抽象和封装的过程

一般形式为：

class 类名{
	public：
		<公有数据和函数>
	protected：
		<保护数据和函数>
	private：
		<私有数据和函数>
};

对象公共数据成员的访问方式：

1. 圆点访问方式

   对象名.成员名 或 (*指向对象的指针).成员名

2. 指针访问方式

   对象指针变量名->成员名 或 (&对象名)->成员名

struct和class的区别：struct默认权限为公共，class默认权限为私有

一般来说会将类单独写到头文件中，在主函数中include

在类的.h文件中将类的内容复制过去，但是具体实现删去，只保留语句和函数，分号结尾；

在类的.cpp文件中定义那些函数，这时候不需要再用Class框起来，而且在函数前带上类名::声明函数的所属(以成员函数的形式)

类的访问权限

类成员的访问限制是通过在类主体内部对各个区域标记public、private、protected来指定的

默认情况下，类的所有成员都是私有的，如果没有使用任何访问修饰符，类的成员将被假定为私有成员

实际操作中一般会在私有区域定义数据，在公有区域定义相关的函数，以便在类的外部也可以调用这些函数

类的公有部分(public)只暴露必要的接口，私有部分(private)隐藏具体实现

• public(公共)成员在类的外部是可访问的，可以不使用任何成员函数来设置和获取公有变量的值

• private(私有)成员变量或函数在类的外部是不可访问的，只有类和友元函数可以访问私有成员，不能被派生类访问

  儿子不可以访问父亲的私有内容

• protected(受保护)成员变量或函数与私有成员十分相似，但protected成员在派生类(即子类)中是可访问的

  儿子可以访问父亲的保护内容

构造函数

类的构造函数是类的一种特殊的成员函数，它会在每次创建类的新对象时执行

在顺序上，类内子类先构造

构造函数的名称与类的名称是完全相同的，并且不会返回任何类型，也不会返回 void

一般构造函数分为默认构造函数(没有任何参数也没有任何内容)，有参构造函数，拷贝构造函数(一般用来复制类)

如果提供了有参构造函数，编译器不再提供默认构造函数，但仍然提供拷贝构造函数

如果提供了拷贝构造函数，就不再提供其它普通构造函数

初始化列表：构造函数(): 属性1(值1), 属性2(值2)…{}

C++中拷贝构造函数调用时机通常有三种情况：

• 使用一个已经创建完毕的对象来初始化一个新对象
• 值传递的方式给函数参数传值
• 以值方式返回局部对象

浅拷贝：简单的赋值拷贝操作(=操作) -> 带来的问题是内存的重复释放

先进后出，释放的时候拷贝的析构函数已经把new出来的区域delete，但是原类释放析构函数又delete相同区域，报错

深拷贝：在堆区重新申请空间，进行拷贝操作

class Person {
public:
    Person(const int age, const int height) {
        this->age = age;
        this->height = new int(height);
    }
    Person(const Person &p) {
        this->age = p.age;
        this->height = new int(*p.height);
    }
    int age{};
    int *height{};
    ~Person() {
        delete this->height;
    }
};

析构函数

类的析构函数是类的一种特殊的成员函数，它会在每次删除所创建的对象时执行；在顺序上，类内子类后析构，与构造顺序相反

同理父子类，先构造父类然后子类，析构时先子类后父类

析构函数的名称与类的名称是完全相同的，只是在前面加了个波浪号（~）作为前缀，它不会返回任何值，也不能带有任何参数，默认析构函数没有任何内容

析构函数的主要作用是将堆区开辟的数据做释放操作

成员函数

类的成员函数是指那些把定义和原型写在类定义内部的函数，就像类定义中的其他变量一样

可以在类的外部使用范围解析运算符 :: 定义该函数

成员变量和成员函数是分开存储的，只有非静态成员变量内存上属于类的对象

this指针

this指针是一个特殊的指针，它指向当前对象的实例，每一个对象都能通过 this指针来访问自己的地址

this是一个隐藏的指针，可以在类的成员函数中使用，它可以用来指向调用对象

使用 this 指针来引用当前对象的成员变量 value，并将传入的值赋给它，这样可以明确地告诉编译器想要访问当前对象的成员变量，而不是函数参数或局部变量

this指针的用途：

• 当形参和成员变量同名时，可用this指针来区分

• 在类的非静态成员函数中返回对象本身，可使用return *this

  return *this 这种情况下如果要返回本体需要函数的返回类型为类的引用

  如果是函数类型不是引用相当于拷贝类对象，函数的效果无法叠加！

类允许空指针，但是如果空指针传入后调用类对象(this)，程序会崩溃

静态成员

可以使用 static 关键字来把类成员定义为静态的

当声明类的成员为静态时，这意味着无论创建多少个类的对象，静态成员都只有一个副本，静态成员在类的所有对象中是共享的

静态成员需要类内声明，但类外初始化操作

class Base {
public:
    static int m_A;
};
int Base::m_A = 10;

静态成员函数即使在类对象不存在的情况下也能被调用，只要使用类名加范围解析运算符 :: 就可以访问

静态成员函数与普通成员函数的区别：

• 静态成员函数没有 this 指针，只能访问静态成员（包括静态成员变量和静态成员函数）
• 普通成员函数有 this 指针，可以访问类中的任意成员；而静态成员函数没有 this 指针

const修饰

在对象前加const变为常对象，只能调用常函数

常函数是在函数定义完的括号后加上const

常函数不可修改成员属性

友元函数

在类内定义时在前加上friend(不写具体内容)，友元有权访问类的所有私有（private）成员和保护（protected）成员

友元的三种实现：

• 全局函数做友元

  尽管友元函数的原型有在类的定义中出现过，但是友元函数并不是成员函数

• 类做友元

• 成员函数做友元

如果出现定义类内类的情况，最好用上指针，这样可以使用前向声明，不用完整定义

#include <iostream>
using namespace std;
class Building;
class Goodgay {
public:
    Goodgay();
    void visit1();
    void visit2();
    ~Goodgay();
private:
    Building *building;
};
class Building{
    // friend class Goodgay;
    friend void Goodgay::visit2();
public:
    Building();
    string kitchen;
private:
    string bedroom;
};
Building::Building() {
    this->kitchen = "kitchen";
    this->bedroom = "bedroom";
}
Goodgay::Goodgay() {
    building = new Building();
}
void Goodgay::visit1() {
    cout <<"GoodGay is visiting " <<building->kitchen << endl;
}
void Goodgay::visit2() {
    cout << "GoodGay is visiting " << building->bedroom << endl;
}
Goodgay::~Goodgay() {
    delete building;
}
int main(){
    Goodgay g;
    g.visit1();
    g.visit2();
}

类的继承

有public, protected, private三种继承方式，它们相应地改变了基类成员的访问属性

继承方式	public 成员	protected 成员	private 成员
public 继承	public	protected	private
protected 继承	protected	protected	private
private 继承	private	private	private

class Dog : public Animal {}; // 语法

但无论哪种继承方式，下面两点都没有改变：

• private 成员只能被本类成员和友元访问，不能被派生类访问
• protected 成员可以被派生类访问

父类中所有非静态成员属性都会被子类继承下去，私有成员是被编译器给隐藏了，因此访问不到，但是被继承下去了

如果出现类内对象同名的情况，需要加作用域，同理静态成员

s.m_A; // 子类成员
s.Base::m_A;	// 父类成员

Son::m_A; //静态直接调用
Son::Base::m_A; 

多继承：

class <派生类名>:<继承方式1><基类名1>,<继承方式2><基类名2>,…

如果出现菱形继承，需要在继承时加上virtual变为虚继承，父类称为虚基类

类的多态

当类之间存在层次结构，并且类之间是通过继承关联时，就会用到多态

多态分为两类

• 静态多态：函数重载和运算符重载属于静态多态，复用函数名
• 动态多态：派生类和虚函数实现运行时多态

静态多态和动态多态区别：

• 静态多态的函数地址早绑定－编译阶段确定函数地址
• 动态多态的函数地址晚绑定－运行阶段确定通数地址

虚函数：

• 在基类中声明一个函数为虚函数，使用关键字virtual
• 派生类可以重写这个虚函数
• 调用虚函数时，会根据对象的实际类型来决定调用哪个版本的函数

纯虚函数：

• 一个包含纯虚函数的类被称为抽象类，它不能被直接实例化
• 纯虚函数没有函数体，声明时使用= 0
• 它强制派生类提供具体的实现

#include <iostream>
using namespace std;
class BaseCalculator{
public:
    virtual float getResult() = 0;
    float in_Num1;
    float in_Num2;
};
class Add: public BaseCalculator {
public:
    float getResult() {
        return in_Num1 + in_Num2;
    }
};
class Substract: public BaseCalculator {
public:
    float getResult() {
        return in_Num1 - in_Num2;
    }
};
class Multiply: public BaseCalculator {
public:
    float getResult() {
        return in_Num1 * in_Num2;
    }
};
class Divide: public BaseCalculator {
public:
    float getResult() {
        return in_Num1 / in_Num2;
    }
};
void test01() {
    BaseCalculator *base = new Add;
    base->in_Num1 = 10;
    base->in_Num2 = 20;
    cout << base->getResult() << endl;
    delete base;
    base = new Substract;
    base->in_Num1 = 10;
    base->in_Num2 = 20;
    cout << base->getResult() << endl;
    delete base;
    base = new Multiply;
    base->in_Num1 = 10;
    base->in_Num2 = 20;
    cout << base->getResult() << endl;
    delete base;
    base = new Divide;
    base->in_Num1 = 10;
    base->in_Num2 = 20;
    cout << base->getResult() << endl;
    delete base;
}
int main() {
    test01();
}

多态满足条件：

• 有继承关系
• 子类重写父类中的虚函数

多态使用条件：父类指针或引用指向子类对象

使用virtual后产生一个虚函数指针vfptr

c++开发提倡用多态，方便拓展和修复功能

虚析构：

1. 虚析构或纯虚析构就是用来解决通过父类指针释放子类对象
2. 如果子类中没有堆区数据，可以不写为虚析构或纯虚析构
3. 拥有纯虚析构函数的类也属于抽象类

重载运算符

在同一个作用域内，可以声明几个功能类似的同名函数，但是这些同名函数的形式参数（指参数的个数、类型或者顺序）必须不同

最主要就是区分输入的参数能够唯一地满足某个函数

函数名是由关键字 operator 和其后要重载的运算符符号构成的

Box operator+(const Box&); // 成员函数
Box operator+(const Box&, const Box&); // 全局函数

可以重载多种，输入不同类型

左移右移运算符

对于一个类，不能写为成员函数去重载，会出现一些问题

class Person {
    friend ostream & operator<<(ostream &, const Person &); // 避免无法访问私有内容
    string name = "张三";
    int age = 12;
};
// 这里返回ostream &是为了避免后续追加内容报错，链式规则，返回void就无法再加内容
ostream & operator<<(ostream& cout, const Person& person) {
    cout << "name:" <<person.name << "\tage:" << person.age;
    return cout;
}
int main(){
    Person person;
    cout << person << endl;
}

递增递减运算符

class Myint {
public:
    int num = 0;
    Myint& operator++() {
        num++;
        return *this;
    }
    Myint operator++(int) {
        Myint temp = *this;
        num++;
        return temp;
    }
};

对于前++和后++区别在于在参数框中加入占位符int，只能int

而且对于前++使用&引用，后++使用值返回

赋值运算符

class Person {
public:
    Person(int age);
    Person(const Person& p);
    Person& operator=(const Person &p);
    ~Person();
    int *age;
};
Person& Person::operator=(const Person &p) {
    // 要先判断自身堆区有无内容
    if (this->age != nullptr) {
        delete this->age;
    }
    age = new int (*p.age);
    return *this;
}

为了像原来等号可以连等，需要重载时返回引用

为了避免默认拷贝函数的影响，需要定义拷贝函数，避免浅拷贝

函数调用运算符

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

行为和函数调用类似，称为仿函数

仿函数的优势是非常灵活，没有固定写法

类后面直接带()称为匿名函数对象，适用于只需要一下的结果

#include <iostream>
#include <string>
using namespace std;
class Print {
public:
    void operator()(const string& test) const {
        cout << test << endl;
    }
};
class Add {
public:
    int operator()(const int& x, const int& y) const {
        return x + y;
    }
};
class Compare {
public:
    bool operator()(int v) {
        return v>1;
    }
};

int main() {
    Print myprint;
    myprint("hello world");
    cout << Add()(1, 2) <<endl;
}

• 函数对象在使用时，可以像普通函数那样调用，可以有参数，可以有返回值
• 函数对象超出普通函数的概念，函数对象可以有自己的状态
• 函数对象也可以作为参数传递，比如修改关联式容器的compare规则

返回bool类型的仿函数称为谓词，谓词不应修改元素

如果operator()接受一个参数，那么叫做一元谓词

如果operator()接受两个参数，那么叫做二元谓词

文件操作

iostream 标准库，它提供了 cin 和 cout 方法分别用于从标准输入读取流和向标准输出写入流

从文件读取流和向文件写入流需要用到 C++ 中另一个标准库 fstream

数据类型	描述
ofstream	该数据类型表示输出文件流，用于创建文件并向文件写入信息
ifstream	该数据类型表示输入文件流，用于从文件读取信息
fstream	该数据类型通常表示文件流，且同时具有 ofstream 和 ifstream 两种功能

输出文件流过程：

1. 创建流对象：ofstream ofs;
2. 打开文件：ofs.open(“文件路径”,打开方式);
3. 写数据：ofs << “写入的数据”;
4. 关闭文件：ofs.close();

open函数

void open(const char *filename, ios::openmode mode);

模式标志	描述
ios::app	追加模式，所有写入都追加到文件末尾
ios::ate	文件打开后定位到文件末尾
ios::in	打开文件用于读取
ios::out	打开文件用于写入
ios::trunc	如果该文件已经存在，先删除再创建
ios::binary	二进制模式

可以把以上两种或两种以上的模式结合使用

ofstream outfile;
outfile.open("file.dat", ios::out | ios::trunc );

输入文件流过程：

1. 创建流对象：ifstream ifs;

2. 打开文件并判断文件是否打开成功

   ifs.open(“文件路径”,打开方式);

   if(!ifs.is_open()) ：文件不存在

   char ch; ifs >> ch; if (ifs.eof()) ：判断文件是否为空

3. 读数据：四种方式读取

4. 关闭文件：ifs.close();

char buf[1024] = {0};
// 方法1:
/*
while (ifs>>buf) 
    cout << buf << endl;
*/
// 方法2:
/*
while (ifs.getline(buf, sizeof(buf)))
    cout << buf << endl;
*/
// 方法3:
/*string str;
while (getline(ifs, str)) 
    cout << str << endl;
*/
// 方法4:
/*char ch;
while ((ch = ifs.get())!= EOF) 
    cout << ch;
*/
ifs.close();

二进制方式：

#include <fstream>
#include <iostream>
using namespace std;
class Person {
public:
    char name[64];
    int age;
};
void test01() {
    ofstream ofs("person.txt", ios::out | ios::binary);
    Person p = {"张三", 18};
    ofs.write((const char*)&p, sizeof(Person));
    ofs.close();
}
void test02() {
    ifstream ifs("person.txt", ios::in | ios::binary);
    if (!ifs.is_open()) {
        cerr << "Can't open person.txt" << endl;
        return;
    }
    Person p{};
    ifs.read((char*)&p, sizeof(Person));
    cout << p.name << endl;
    cout << p.age << endl;
}
int main() {
    test01();
    test02();
}

模板

主要为STL服务

模板的特点：

• 模板不可以直接使用，它只是一个框架
• 模板的通用并不是万能的

函数模板语法

使用模板时必须确定出通用数据类型T，并且能够推导出一致的类型

T是一个通用的数据类型，通常用大写字母表示

template <typename T>
ret-type func-name(parameter list)

• template → 声明创建模板
• typename → 表面其后面的符号是一种数据类型，可以用class代替

使用函数模板有两种方式：自动类型推导、显式指定类型

func<int>() // 显式指定

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

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

如果函数复杂尽量显式指定类型

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

1. 如果函数模板和普通函数都可以调用，优先调用普通函数
2. 可以通过空模板参数列表强制调用函数模板 func<>()
3. 函数模板可以发生函数重载
4. 如果函数模板可以产生更好的匹配，优先调用函数模板

所以如果已经有函数模板尽量不要写同名的普通函数

如果碰到不通用的类型，需要写专门针对某个类型的模板

template<> ret-type func-name(parameter list) 

在这个示例中两种解决方案，一种重载运算符(对于复杂函数来说不现实)，另一种就是写专门的模板

#include <iostream>
using namespace std;
class Person {
public:
    Person(const string &name, const int age) {
        this->name = name;
        this->age = age;
    }
    /*bool operator==(const Person& person) const {
        if (this->name == person.name&&this->age == person.age) {
            return true;
        }
        return false;
    }*/
    string name;
    int age;
};
template <typename T>
bool equal(T &a, T &b) {
    if (a == b)
        return true;
    return false;
}
template <> bool equal(Person &a, Person &b) {
    if (a.name == b.name && a.age==b.age)
        return true;
    return false;
}
int main() {
    Person p1("Ben",10);
    Person p2("Ben",20);
    if (equal(p1,p2))
        cout << "equal" << endl;
    else
        cout << "not equal" << endl;
}

类模板语法

template <class type> 
class class-name {
}

#include <iostream>
using namespace std;
template <class NameType, class AgeType = int>
class Person {
public:
    Person(NameType name, AgeType age) {
        this->name = name;
        this->age = age;
    }
    NameType name;
    AgeType age;
};

int main() {
    Person<string> p("ben",11);
}

类模板与函数模板区别主要有两点：

1. 类模板没有自动类型推导的使用方式，只能显式指定
2. 类模板在模板参数列表中可以有默认参数

类模板的成员函数只有在调用的时候才会去创建

通过类模板创建的对象向函数传参时建议直接指定传入的类型

当类模板碰到继承时，需要注意一下几点：

• 当子类继承的父类是一个类模板时，子类在声明的时候，要指定出父类中T的类型

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

  template<class T>
  class Base {
      T data;
  };
  class Son : public Base<int>{
  };

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

  template<class T>
  class Base {
      T data;
  };
  template<class T1,class T2>
  class Son : public Base<T2>{
      T1 obj;
  };
  int main() {
      Son<int,char> s1{};
  }

构造函数的类外实现：

class Person {
public:
    Person(T1 name,T2 age);
    T1 name;
    T2 age;
    void display();
};
template<class T1, class T2>
Person<T1, T2>::Person(T1 name, T2 age) {
    this->name = name;
    this->age = age;
}

成员函数的类外实现：

template<class T1, class T2>
void Person<T1, T2>::display() {
    cout << this->name << " " << this->age << endl;
}

类模板中成员函数类外实现时，需要加上模板参数列表<T1,T2,…>

如果把类模板写成头文件，使用时会发生错误，解决方案：

1. 把导入的.h头文件改为导入.cpp文件
2. 把两个文件写成一个文件，.h文件后缀改为.hpp，不需要.cpp文件

全局函数的实现：

建议采用类内实现，简单

#include <iostream>
using namespace std;
template<class T1, class T2>
class Person {
    // 全局函数类内实现
    // friend void display(Person<T1,T2> p) {
    //     cout << p.name << endl;
    //     cout << p.age;
    // }
    // 全局函数类外实现,需要加空模板参数列表
    friend void display<>(Person<T1,T2> p);
public:
    Person(T1 name,T2 age);
private:
    T1 name;
    T2 age;
};
template<class T1, class T2>
Person<T1, T2>::Person(T1 name, T2 age) {
    this->name = name;
    this->age = age;
}
// 全局函数类外实现
template<class T1, class T2>
void display(Person<T1,T2> p) {
    cout << p.name << endl;
    cout << p.age;
}

int main() {
    Person<string,int>p1("tom",10);
    display(p1);
}

如果在friend void display<>(Person<T1,T2> p)这里不加<> 会被编译器解释为声明一个普通函数的友元，使用<>明确告诉编译器这是针对模板实例的友元声明

STL

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

STL几乎所有代码都采用了模板

STL 分为多个组件，包括容器、算法、迭代器、函数对象和适配器等

容器和算法通过迭代器无缝连接

组件	描述
容器(Containers)	各种数据结构，包括向量(vector)、链表(list)、队列(queue)、栈(stack)、集合(set)、映射(map)等，用于存放数据
算法(Algorithms)	各种常见算法，如sort, find, copy, move, for_each等
迭代器(iterators)	用于遍历容器中的元素，允许以统一的方式访问容器中的元素

容器分为序列式容器和关联式容器两种：

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

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

  举例，一个数组13542，序列式容器内就是13542，在关联式容器内是12345

容器的构造函数：

构造函数：(以vector为例)

• vector<T> v; 采用模板，默认构造函数
• vector(v.begin(), v.end()); 将[begin,end)区间中的元素拷贝给本身
• vector(const vector &vec); 拷贝构造函数

算法分为：质变算法和非质变算法

• 质变算法：运算过程中会更改区间内的元素的内容。例如拷贝，替换，删除等等
• 非质变算法：是指运算过程中不会更改区间内的元素内容，例如查找、计数、遍历、寻找极值等等

序列式容器

vector

vector 是一种序列容器，用于存储动态大小的数组，允许用户在容器的末尾快速地添加或删除元素

vector与普通数组区别：

• 数组是静态空间，而vector可以动态扩展

• 动态扩展：并不是在原空间之后续接新空间，而是找更大的内存空间，然后将原数据拷贝新空间，释放原空间

  如果一开始大概知道要开辟多少空间，可以.reserve(num)预留容量，避免频繁分配内存

需要包含头文件 <vector>

常用操作：

函数	说明
push_back(elem);	在末尾添加一个元素
pop_back();	删除末尾元素
front();	返回容器中第一个元素
back();	返回容器中最后一个元素
swap(vec);	互换两个容器
capacity();	返回容器容量
empty();	判断是否为空
size();	返回容器中存储元素个数
resize(int num, (elem));	size变为num，变多填充默认/(elem)值 变小则超出部分删除，容量不变
insert(pos, (count), ele);	指向位置插入(count个)ele
erase(pos);	删除指向位置的元素
erase(start, end);	删除区间内的元素
clear();	删除容器内元素

vector容器capacity比size大(自适应)，但在resize后capacity不变，为了节省内存，c++11之前可以自交换，c++11以上建议使用shrink_to_fit()

起始迭代器，指向容器中第一个元素

vector<T> v;
vector<T>::iterator itBegin = v.begin();

结束迭代器，指向容器中最后一个元素的下一个位置

vector<T>::iterator itEnd = v.end();

几种遍历方式：

   // 第一种遍历
while (itBegin != itEnd) {
       cout << *itBegin << endl;
       ++itBegin;
   }
   // 第二种遍历
   for (vector<T>::iterator it = v.begin(); it != v.end(); ++it) {
       // (*it)的类型就是vector<>内的类型
       cout << *it << endl;
   }
   // 第三种遍历
   for_each(v.begin(), v.end(), [](T i){cout << i << endl;});

在写的过程中像vector<T>::iterator这种可以auto

注意(*it)的类型就是<>内的类型

deque

双端数组：允许在两端进行高效的插入和删除操作，适用于需要频繁插入和删除元素的场景

deque与vector区别:

• vector对于头部的插入删除效率低，数据量越大，效率越低
• deque相对而言，对头部的插入删除速度回比vector快
• vector访问元素时的速度会比deque快，这和两者内部实现有关

deque的构造和赋值操作和vector基本一样

插入删除增加头部操作，其它和vector相同

函数	说明
push_front(elem);	在头部添加一个元素
pop_front();	删除容器第一个元素

stack

堆栈是一种后进先出的数据结构，默认基于deque

非常适合于需要”最后添加的元素最先被移除”的场景

栈的元素是线性排列的，但只允许在一端(栈顶)进行添加和移除操作，另一端是封闭的(栈底)

实例：子弹射出；挤地铁

只能访问栈顶元素，因此栈不允许有遍历的行为

常用操作：

函数	说明
push()	在栈顶添加一个元素(入栈)
pop()	移除栈顶元素(出栈)
top()	返回栈顶元素的引用，但不移除它
empty()	检查栈是否为空
size()	返回栈中元素的数量

queue

队列是一种先进先出的数据结构

它遵循以下规则：

• 元素只能从队尾添加
• 元素只能从队首移除

实例：排队买东西

只有队头和队尾可以访问，因此不允许有遍历行为

常用操作：

函数	说明
push()	在队尾添加一个元素
pop()	移除队首元素
front()	返回队首元素的引用
back()	返回队尾元素的引用
empty()	检查队列是否为空
size()	返回队列中的元素数量

emplace可以替代push;

push()先产生一个副本，然后将该副本移动到容器中；

emplace()直接在内存上构造对象，省去移动的过程

emplace(args) args: 用于构造新元素的参数

list

list 是一种序列容器

允许在容器的任意位置快速插入和删除元素

单向链表：

包含两个域，一个信息域和一个指针域

第一个部分保存关于节点的信息，第二个部分存储下一个节点的地址，单向链表只可向一个方向遍历

双向链表：

双向链表中不仅有指向后一个节点的指针，还有指向前一个节点的指针

由于链表的存储方式并不是连续的内存空间，迭代器只支持前移和后移，属于双向迭代器(支持++与–，不支持+n)

常用操作：

函数	说明
push_back(const T& val)	在链表末尾添加元素
push_front(const T& val)	在链表头部添加元素
pop_back()	删除链表末尾的元素
pop_front()	删除链表头部的元素
front()	返回链表第一个元素
back()	返回链表最后一个元素
empty()	检查链表是否为空
size()	返回链表中的元素数量
remove(const T& val)	删除所有等于指定值的元素
reverse()	反转链表
merge(list& other)	合并另一个链表(置于链头)
sort()	排序链表

对list来说，merge和sort需要使用自己的成员函数

序列容器对比

对比复杂度：

容器	随机访问	头部操作	尾部操作	中间操作
vector	O(1)	O(n)	O(1)*	O(n)
deque	O(1)	O(1)	O(1)	O(n)
stack	不支持	-	O(1)	不支持
queue	不支持	O(1)	O(1)	不支持
list	不支持	O(1)	O(1)	O(1)

验证迭代器支持随机访问的方法：

auto it = container.begin();
it = it + n;

如果不报错代表支持随机访问

it++;
it--;

如果不报错代表属于双向迭代器

优缺点：

容器	优点	缺点
vector	随机访问高效 尾部操作快	中间/头部操作慢 扩容成本高
deque	双端操作高效 扩容时无需拷贝全部元素	中间操作慢 内存非完全连续
stack	专为LIFO(后进先出)设计	仅能访问栈顶元素 不支持遍历/随机访问
queue	专为FIFO(先进先出)设计	仅能访问首尾元素 不支持遍历/随机访问
list	任意位置操作高效 无扩容开销	访问元素需遍历 内存开销大

• 需随机访问 + 尾部操作 → vector
• 需高效头尾操作 + 随机访问 → deque
• 需频繁任意位置插入/删除 → list

vector和list是最常用的容器

关联式容器

set

set是一种关联容器，它存储了一组唯一的元素，所有元素在插入时自动被排序(默认小→大)，底层结构是用二叉树实现

set容器中存储的元素类型必须满足以下条件：

• 元素类型必须可以比较大小
• 元素类型必须可以被复制和赋值

常用操作：

函数	说明
insert()	插入一个元素
erase()	删除一个元素
empty()	检查容器是否为空
size()	返回容器中元素的数量

在set中元素不允许重复插入，但multiset允许重复插入

如果我需要创建set是从大到小排序的，需要在创建时再输入一个比较类，比如greater<T>()

map

map是一种关联容器，所有元素都是键值对(pair)

在创建pair对象时，必须提供两个类型名，两个类型不必相同

pair中第一个元素为key(键值)起到索引作用，第二个元素为value(实值)

map的指针指向first和second分别对应pair的两个值

pair<T1, T2> p = make_pair(T1 val, T2 val);

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

所以在创建时要关注最后排序的是什么

可以通过key值快速找到value值

map不允许容器有重复的key值，multimap允许

map的sort和set类似，不再重复

string

string和char *区别：

• char *是—个指针
• string是一个类，类内部封装了char*，是一个char*型的容器

构造函数：

• string(); 创建一个空的字符串
• string(const char* s); 使用字符串s初始化
• string(const string& str); 拷贝str
• string(int n, char c): 使用n个字符c初始化

常用操作：

函数名	描述
size()	返回字符串的长度(字符数) [同length()函数]
empty()	判断字符串是否为空
operator[]	访问字符串中指定位置的字符
substr()	返回从pos开始的length长度字符串 (常配合find使用) string sub = str.substr(pos, length);
find()/rfind()	查找子字符串在字符串中的位置(正方向/从末尾) str.find(“sub”)
replace()	替换字符串中的部分内容 str.replace(pos, length, “new_substring”);
insert()	在指定位置插入内容
erase()	删除指定位置指定长度的字符
compare()	比较两个字符串，相等返回0 std::cout << (str.empty() ? “Yes” : “No”);

内建函数对象

函数对象是那些重载了 operator() 的对象，它们可以像普通函数一样被调用

<functional> 头文件提供了一些函数对象

主要分为算术仿函数、关系仿函数、逻辑仿函数

算术仿函数

实现四则运算

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

• plus<T> 加法仿函数
• minus<T> 减法仿函数
• multiplies<T> 乘法仿函数
• divides<T> 除法仿函数
• modulus<T> 取模%仿函数(只能整型(int,long,char))
• negate<T> 取反仿函数

使用举例：

plus<int> p;
cout << p(10,20) << endl;
// 类模板需要先实例化对象才能用，所以要多一个()
cout << plus<int>()(10,20) << endl;

关系仿函数

• greater<T> return a > b
• less<T> return a < b

使用举例：

sort(iterator beg, iterator end, greater<int>());

逻辑仿函数

• logical_not return !a 属于一元谓词

  std::transform(
         input.begin(), 
         input.end(),
         output.begin(),
         std::logical_not<bool>()  
     );

常用算法

算法主要由由头文件<algorithm>, <functional>, <numeric>组成

• algorithm是所有STL头文件中最大的一个，范围涉及到比较、交换、查找、遍历操作、复制、修改等等
• numeric体积很小，只包括几个在序列上面进行简单数学运算的模板函数
• functional定义了一些模板类用以声明函数对象

遍历算法

• for_each 遍历容器

  std::for_each(iterator beg, iterator end, _func())
  std::for_each(vec.begin(), vec.end(), [](T i){cout << i << endl;}); // 遍历显示

• transform 搬运容器到另一个容器

  class Transform {
  public:
      int operator()(int v) {
          return (v+10);
      }
  };
  vector<int> v;
  vector<int> v2;
  v2.resize(v.size()); // 必须要提前开辟空间，不然程序崩溃
  transform(v.begin(), v.end(), v2.begin(), Transform());

查找算法

• find 在容器中查找与给定值匹配的第一个元素

  如果找到 it 将指向匹配的元素；否则 it 将等于 container.end()

  auto it = find(iterator beg, iterator end, value)

  如果是自定义类，需要重载==

  bool operator==(const T & class-name){
      if(x==x&&y==y&&...)
          return true;
      else
          return false;
  }

• find_if 根据bool型仿函数(也叫谓词)的条件返回第一个满足的迭代器位置

  auto it = find_if(iterator beg, iterator end, _Pred())

  谓词举例：

  class Compare {
  public:
      bool operator()(int v) {
          return v>1;
      }
  };

• adjacent_find 在容器中寻找相邻重复元素，返回前一个的迭代器位置

  auto it = adjacent_find(iterator beg, iterator end);

• binary_search 查找指定的元素，查到返回true否则false

  bool binary_search(iterator beg,iterator end,value);

  在无序序列中不可用 使用前先sort

• count 查找元素个数，自定义类需要重载==

  count(iterator beg, iterator end, value);

• count_if 查找满足bool型仿函数的条件的元素个数

  int n = count_if(iterator beg, iterator end, _Pred());

排序算法

• sort 对容器内的元素进行排序

  sort(iterator beg, iterator end, _Pred());

  谓词非必须，默认less(也就是升序)

  降序：

  sort(iterator beg, iterator end, greater<T>());

  对于支持随机访问的迭代器的容器(vector,deque)，都可以用sort算法直接进行排序

  如果是自定义类的排序，需要补充一个比较函数(list的sort同理)

• random_shuffle 对指定范围内的元素随机调整次序

  random_shuffle(iterator beg, iterator end);

  这个随机和rand一样是伪随机，如果需要每次结果不一样需要加上随机种子srand(time(nullptr));

  random_shuffle已被弃用，用shuffle取代

  shuffle(iterator beg, iterator end,
              mt19937(random_device()()));

• merge 将两个容器的元素合并存储到另一个容器

  注意，两个容器必须有序(同升/同降)

  merge(iterator beg1, iterator end1, iterator beg2, iterator end2, iterator dest);

  dest是目标容器开始迭代器，合并后还是一个有序容器

  注意：和transform相同，在合并前需要给目标容器开辟一定的空间，否则程序崩溃

• reverse 对容器内元素进行反转，颠倒其顺序

  reverse(iterator beg, iterator end);

拷贝替换

• copy 容器内指定范围的元素拷贝到另一容器中

  copy(iterator beg, iterator end, iterator dest);

• replace 将容器内指定范围的元素修改为新元素

  replace(iterator beg, iterator end, oldvalue, newvalue);

• replace_if 将区间内满足条件的元素，替换成指定元素

  replace_if(iterator beg, iterator end, _Pred(), newvalue);

• swap 互换两个同种类型的容器

  swap(container c1, container c2);

算术生成算法

属于小型算法，需要包含<numeric>

• accumulate 计算容器内累加和

  accumulate(iterator beg, iterator end, init_val)

  min_element和 max_element 用于找到区间内的最大值和最小值

• inner_product 计算两个容器中对应元素乘积的总和

  inner_product(iterator beg1, iterator end1, iterator beg2, iterator end2, init_val)

• adjacent_difference 计算容器中相邻元素的差值，并将结果存储在另一个容器中

  adjacent_difference(iterator beg, iterator end, iterator dest);

• fill 向容器中填充指定元素

  fill(iterator beg, iterator end, val)

集合算法

以下算法都要求容器有序

• set_intersection 计算两个容器的交集，返回交集的结束迭代器位置

  dest.resize(min(container1.size(),container2.size()));
  auto itend = set_intersection(iterator beg1, iterator end1, iterator beg2, iterator end2, iterator dest);

  开辟目标容器时size设为两个容器size 的较小值

• set_union 计算两个容器的并集，返回并集的结束迭代器位置

  dest.resize(container1.size() + container2.size());
  auto itend = set_union(iterator beg1, iterator end1, iterator beg2, iterator end2, iterator dest);

  开辟目标容器时size设为两个容器size 的和

• set_difference 计算两个容器的差集，返回差集的结束迭代器位置

  dest.resize(max(container1.size(),container2.size()));
  auto itend = set_difference(iterator beg1, iterator end1, iterator beg2, iterator end2, iterator dest);

  谁在前就是找后一个没有的元素

  开辟目标容器时size设为两个容器size 的较大值