C基础

运算符优先级

C语言运算符优先级从高到低大致可分为:

  1. 单目运算符(如 !)
  2. 算术运算符(如 %)
  3. 移位运算符(如 >>)
  4. 关系运算符(如 ==)
  5. 逻辑运算符
  6. 赋值运算符

位运算

符号 描述 运算规则
& 与 两个位都为1时，结果才为1
| 或 两个位都为0时，结果才为0
^ 异或 两个位相同为0，相异为1
~ 取反 0变1，1变0
<< 左移 各二进位全部左移若干位，高位丢弃，低位补0
>> 右移 各二进位全部右移若干位，高位补0或符号位补齐

排序

排序次数 = 数组size - 1

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

在数值上相同

定义交换函数

1
2
3
4
5
6
template <typename T>
void Swap(T &a, T &b) {
    T temp = a;
    a = b;
    b = temp;
}

冒泡法：

  • 重复遍历数组，比较相邻元素
  • 如果顺序错误（前 > 后），则交换它们
  • 每轮遍历将最大元素”冒泡”到正确位置
1
2
3
4
5
6
7
8
9
10
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]);
            }
        }
    }
}

选择法：

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

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

1
2
3
4
5
6
7
8
9
10
11
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

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

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

引用

数据类型 &别名 = 原名

别名可以和原名相同

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

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

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

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

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

结构体

结构体定义由关键字 struct 和结构体名组成，结构体名可以根据需要自行定义

1
2
3
4
5
6
struct tag {
    member-list
    member-list
    member-list  
    ...
} variable-list ;

tag 是结构体标签；member-list 是标准的变量定义； variable-list 结构变量

程序内存

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

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

不在全局区的数据：

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

全局区的数据：

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

栈区：

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

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

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

堆区：

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

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

空类占1字节的内存

随机数

伪随机数：

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

真随机数产生：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#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个字节空间，是为了区分空对象占用内存的位置

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

一般形式为： 

1
2
3
4
5
6
7
8
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相同区域，报错

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
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 关键字来把类成员定义为静态的

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

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

1
2
3
4
5
class Base {
public:
    static int m_A;
};
int Base::m_A = 10;

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

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

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

const修饰

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

在C++中，const成员函数的声明语法要求将const关键字放在函数参数列表的后面、函数体的前面,表示该成员函数不会修改类的数据成员

1
void fun_name() const;

常函数不可修改成员属性

友元函数

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

友元的三种实现：

  • 全局函数做友元

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

  • 类做友元

  • 成员函数做友元

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
#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 
1
class Dog : public Animal {}; // 语法

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

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

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

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

1
2
s.m_A; // 子类成员
s.Base::m_A;	// 父类成员
1
2
Son::m_A; //静态直接调用
Son::Base::m_A;

多继承：

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

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

类允许被继承的话，析构函数需要加virtual修饰

类的多态

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

多态分为两类

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

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

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

虚函数：

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

纯虚函数：

  • 一个包含纯虚函数的类被称为抽象类，它不能被直接实例化
  • 纯虚函数没有函数体，声明时使用= 0
  • 它强制派生类提供具体的实现
  • 虽然纯虚函数通常需要子类实现，但这不是强制性的。如果子类也声明为抽象类,则可以不实现父类的纯虚函数,而是将实现推迟到其子类

多态满足条件：

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

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

常常先创建一个父类空指针，在后续过程再让其指向new开辟子类的区域

1
2
3
4
5
6
7
8
Worker * worker = nullptr;
if (DeptId == 1) {
	worker = new Staff(id,name,DeptId);
} else if (DeptId == 2) {
	worker = new Manager(id,name,DeptId);
} else if (DeptId == 3) {
	worker = new Boss(id,name,DeptId);
}

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

虚析构：

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

运算符优先级

运算符优先级从高到低的排序:

  1. ()、[]、->、. (最高优先级)
  2. ++ – (单目运算符)
  3. *、/、% (算术运算符)
  4. +、- (算术运算符)
  5. 其他 (如比较运算符、逻辑运算符等)

重载运算符

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

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

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

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

不能重载的运算符：

  • sizeof() 在编译时就需要确定大小,而运算符重载是在运行时进行的
  • 成员访问运算符 .
  • 作用域运算符 ::
  • 条件运算符 ?

常见重载

左移右移运算符

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
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;
}

递增递减运算符

1
2
3
4
5
6
7
8
9
10
11
12
13
class Myint {
public:
    int num = 0;
    Myint& operator++() {
        num++;
        return *this;
    }
    Myint operator++(int) {
        Myint temp = *this;
        num++;
        return temp;
    }
};

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

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

赋值运算符

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
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;
}

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

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

函数调用运算符

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

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

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

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
#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函数

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

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

1
2
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();

1
2
3
4
5
6
7
char buf[1024] = {0};
// 方法1:
while (ifs>>buf) 
    cout << buf << endl;
// 方法2:
while (ifs.getline(buf, sizeof(buf)))
    cout << buf << endl;

二进制方式：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
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是一个通用的数据类型，通常用大写字母表示

1
2
template <typename T>
ret-type func-name(parameter list)
  • template → 声明创建模板
  • typename → 表面其后面的符号是一种数据类型，可以用class代替

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

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

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

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

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

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

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

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

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

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

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
#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;
}

类模板语法

1
2
3
template <class type> 
class class-name {
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#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的类型

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

    1
    2
    3
    4
    5
    6
    template<class T>
    class Base {
        T data;
    };
    class Son : public Base<int>{
    };

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

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    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{};
    }

构造函数的类外实现：

1
2
3
4
5
6
7
8
9
10
11
12
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;
}

成员函数的类外实现：

1
2
3
4
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文件

全局函数的实现：

建议采用类内实现，简单

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#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) 用于遍历容器中的元素，允许以统一的方式访问容器中的元素

STL中一级容器是指, 容器元素本身是基本类型, 非组合类型

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

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

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

    举例，一个数组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()

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

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

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

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

几种遍历方式：

1
2
3
4
5
6
7
8
9
10
11
12
   // 第一种遍历
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

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

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

Data_stack

实例：子弹射出；挤地铁

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

常用操作：

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

queue

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

它遵循以下规则：

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

实例：排队买东西

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

常用操作：

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

emplace可以替代push;

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

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

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

list

list 是一种序列容器，允许在容器的任意位置快速插入和删除元素

成员函数at()访问

单向链表：

Singly-linked-list

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

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

双向链表：

Doubly-linked-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)

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

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

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

1
2
it++;
it--;

不支持下标运算符”[]”的容器：set、stack、queue、list

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

优缺点：

容器 优点 缺点
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的两个值

1
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);
length不写默认到最后位置
find()/rfind() 查找子字符串在字符串中的位置(正方向/从末尾)
str.find(“sub”)
replace() 替换字符串中的部分内容
str.replace(pos, length, “new_substring”);
insert() 在指定位置插入内容
erase() 删除指定位置指定长度的字符
compare() 比较两个字符串，相等返回0
std::cout << (str.empty() ? “Yes” : “No”);

string 转 int：

利用.c_str()转const char *再 利用atoi()转int

内建函数对象

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

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

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

算术仿函数

实现四则运算

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

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

使用举例：

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

关系仿函数

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

使用举例：

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

逻辑仿函数

  • logical_not return !a 属于一元谓词

    1
    2
    3
    4
    5
    6
    std::transform(
           input.begin(), 
           input.end(),
           output.begin(),
           std::logical_not<bool>()  
       );

常用算法

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

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

遍历算法

  • for_each 遍历容器

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

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

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    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()

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

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

    1
    2
    3
    4
    5
    6
    bool operator==(const T & class-name){
        if(x==x&&y==y&&...)
            return true;
        else
            return false;
    }

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

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

    谓词举例：

    1
    2
    3
    4
    5
    6
    class Compare {
    public:
        bool operator()(int v) {
            return v>1;
        }
    };

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

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

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

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

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

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

    1
    count(iterator beg, iterator end, value);

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

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

排序算法

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

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

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

    降序：

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

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

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

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

    1
    random_shuffle(iterator beg, iterator end);

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

    random_shuffle已被弃用，用shuffle取代

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

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

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

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

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

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

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

    1
    reverse(iterator beg, iterator end);

拷贝替换

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

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

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

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

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

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

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

    1
    swap(container c1, container c2);

算术生成算法

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

  • accumulate 计算容器内累加和

    1
    accumulate(iterator beg, iterator end, init_val)

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

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

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

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

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

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

    1
    fill(iterator beg, iterator end, val)

集合算法

以下算法都要求容器有序

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

    1
    2
    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 计算两个容器的并集，返回并集的结束迭代器位置

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

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

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

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

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

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