C++

text::数据结构与算法

一、C语言

0 基础

单行注释：//

多行注释：/**/

// 引用头文件
#include <stdio.h>

// 宏定义常量（）
#define 常量名 常量值
#define PI 3.14

// #define性质
#define x 5
#define a x+x
cout << a * a << endl;
// 输出35，因为实际上是表达式拼接，所以是输出x+x*x+x的值。

1 变量

// 整形（整数类型）
int a = 10;
short b = 5;
long c = 20;
long long d = 12;

// 浮点型（小数类型）
float a = 10.12;
double b = 12.24;

// 布尔型（真或假）
bool a = true;

// 字符型（直接表示出字符，注意字符是单引号）
char a = 'a';

// 字符串（实则是字符数组，注意是双引号）
char str[] = "123";

// 数组（一堆数的集合）
int arr[] = {1,2,3,4};
char arr[] = {'a','b','c'};

// 常量限定
const 数据类型 name = value;

// 无符号整形
unsigned int a = 10;

2 运算符

数据运算

算术运算符	术语	示例	结果
+	正号	+3	3
-	负号	-3	-3
+	加	10 + 5	15
-	减	10 - 5	5
*	乘	10 * 5	50
/	除	10 / 5	2
%	取模(取余)	10 % 3	1
++	前置递增	a=2; b=++a;	a=3; b=3;
++	后置递增	a=2; b=a++;	a=3; b=2;
—	前置递减	a=2; b=—a;	a=1; b=1;
—	后置递减	a=2; b=a—;	a=1; b=2;

赋值运算符	术语	示例	结果
=	赋值	a=2; b=3;	a=2; b=3;
+=	加等于	a=0; a+=2;	a=2;
-=	减等于	a=5; a-=3;	a=2;
*=	乘等于	a=2; a*=2;	a=4;
/=	除等于	a=4; a/=2;	a=2;
%=	模等于	a=3; a%2;	a=1;

比较运算符	术语	示例	结果
==	相等于	4 == 3	0
!=	不等于	4 != 3	1
<	小于	4 < 3	0
>	大于	4 > 3	1
<=	小于等于	4 <= 3	0
>=	大于等于	4 >= 1	1

逻辑运算符	术语	示例	结果
`!`	非	`!a`	如果a为假，则!a为真；如果a为真，则!a为假。
`&&`	与	`a && b`	如果a和b都为真，则结果为真，否则为假。
`		`	或	`a		b`	如果a和b有一个为真，则结果为真，二者都为假时，结果为假。
`&`	按位与	`a & b`	a和b每一位做与运算，全真为1，否则为0
`	`	按位或	`a	b`	a和b每一位做或运算，全假为0，否则为1
`^`	按位异或	`a ^ b`	a和b每一位做异或运算，相同为1，相反为0

3 输入输出

格式化输出

转义字符	含义	ASCII码值（十进制）
`\a`	警报	007
`\b`	退格(BS) ，将当前位置移到前一列	008
`\f`	换页(FF)，将当前位置移到下页开头	012
`\n`	换行(LF) ，将当前位置移到下一行开头	010
`\r`	回车(CR) ，将当前位置移到本行开头	013
`\t`	水平制表(HT) （跳到下一个TAB位置）	009
`\v`	垂直制表(VT)	011
`\\`	代表一个反斜线字符”\”	092
`'`	代表一个单引号（撇号）字符	039
`"`	代表一个双引号字符	034
`\?`	代表一个问号	063
`\0`	数字0	000
`\ddd`	8进制转义字符，d范围0~7	3位8进制
`\xhh`	16进制转义字符，h范围`0~9，a~f，A~F`	3位16进制

// 输入
scanf("");
scanf("%d",&a);

// 输出
printf("");
printf("%d",a);
printf("%d %d",a,b);

4 判断

执行满足条件的语句

// if判断
if() {}
else if() {}
else{]
    
// switch判断
switch()
{
    case 1:break;
    case 2:break;
    default:
}
     
// 三目运算符，真返回t值，假返回f值
c = a > b ? t : f;

5 循环

多次重复执行同一段语句

for(){}

while(){}

do{} while()
    
// 立刻结束循环
break;
// 跳过后续语句继续循环
continue;

6 数组

存放相同数据元素的集合

索引从0开始

// 一维数组
int nums[10];
char strs[10];
int score[10] = { 0,1,2,3,4,5,6,7,8,9 };

// 二维数组
int arr[2][3] = { {1,2,3},{4,5,6} };

// 多维数组
int lst[1][2][3];

// 省略长度
int score[] = { 0,1,2,3,4 };

// 省略行数（列数不可省略）
int arr[][3] = {{1, 2, 3}, {4, 5, 6}};

// 访问数组
nums[i];
nums[i][j];

7 函数

实现代码复用

形参：函数内部新建的参数。

实参：函数外传入的参数。

exit 函数：链接

// 函数定义
void func(){}

// 函数声明（可以多次声明但是不能多次定义）
void func();

// 函数返回
int func(){ return num; }

// 函数调用
func();

// 值传递（不改变实参值）
void swap(int num1, int num2);
swap(a, b);

// 地址传递（改变实参值）
void swap2(int * p1, int *p2);
swap2(&a, &b); // 传入地址

8 文件

持久化存储

// mode:r,w,a,b,+
FILE *fp = fopen("path",mode);

// 读
fscanf(fp,"%d",&num);
// 读一行
fgets(buf,size(buf),fp);

// 写
fprintf(fp,"%d",num);
// 写字符串
fputs(buf,fp);

// 关闭文件
fclose(fp);

9 指针

可以通过指针间接访问内存

指针所占地址：所有数据类型的指针，x86是4B，x64是8B

空指针：指针变量指向内存中编号为0的空间

野指针：指针变量指向非法的内存空间

// 定义指针
int* p;

// 指针赋值
p = &a;

// 使用值（*p是指针值，p是指针地址）
*p;

// 空指针
int* p = NULL;

// 指向数组首个元素
int *p = arr;

// 指针遍历数组
for (int i = 0; i < 10; i++)
{
   	printf("%d", *p);
    p++;
}

10 结构体

将一组数据组合成一个整体

结构体指针使用：先要指向一个结构体

// 结构体定义
struct student
{
	//成员列表
	string name;  //姓名
	int age;      //年龄
	int score;    //分数
}stu3; // 结构体变量创建方式3

int main() {

	//结构体变量创建方式1
	struct student stu1; // struct关键字可以省略
    
	//结构体变量创建方式2
	struct student stu2 = { "李四",19,60 };
    
    // 结构体值赋值
	stu1.name = "张三";
	stu1.age = 18;
	stu1.score = 100;
	
    // 输出
	printf("%d",stu1.age);
}

// 结构体数组
struct student arr[3]=
{
    {"张三",18,80 },
    {"李四",19,60 },
    {"王五",20,70 }
};

// 结构体指针
struct student stu = { "张三",18,100, };
struct student * p = &stu;
p->score = 80; // 指针通过 -> 操作符访问成员

// 结构体嵌套
struct student
{
	string name;
	int age;
	int score;
};
struct teacher
{
	int id;
	string name;
	int age;
	struct student stu; // 子结构体
};

// 嵌套结构体的调用
struct teacher t1;
t1.stu.name = "张三";

// const限定值不能被修改
void printStudent(const student *stu);

11 内存

malloc申请内存：

需要给定空间大小。并且malloc返回的是(void*)，需要将指针强制转换成对应指针类型。

// 某类型所占空间
sizeof(int);
cout << "short 类型所占内存空间为： " << sizeof(short) << endl;

// 申请内存
int *arr;
arr = (int*)malloc(size * sizeof(int));

// 释放内存
free(arr);

二、C++基础

0 工程包含

多个cpp包含同一个头文件。

头文件中有#pragma once且只有声明，不能有定义，否则会多次包含。

extern int a：全局声明。

int a：定义。

// example.h（声明类、结构体、函数）
#ifndef EXAMPLE_H
#define EXAMPLE_H

#include<iostream>
using namespace std;

// 声明一个结构体
struct Point {
    int x;
    int y;
};

// 声明一个类
class Rectangle {
private:
    int width;
    int height;

public:
    Rectangle(int w, int h);  // 声明构造函数
    int getArea();            // 声明成员函数
};

// 声明一个全局函数
int add(int a, int b);

#endif

// example.cpp（实现类、函数）
#include "example.h"

// 类的构造函数的定义
Rectangle::Rectangle(int w, int h) {
    width = w;
    height = h;
}

// 类的成员函数的定义
int Rectangle::getArea() {
    return width * height;
}

// 全局函数的定义
int add(int a, int b) {
    return a + b;
}

// main.cpp（实例化类、结构体，调用函数）
#include "example.h"

int main() {
    // 实例化一个类对象
    Rectangle rect(5, 3);
    
    // 调用类的成员函数
    int area = rect.getArea();
    std::cout << "Area: " << area << std::endl;
    
    // 使用结构体
    Point p;
    p.x = 10;
    p.y = 20;
    std::cout << "Point: (" << p.x << ", " << p.y << ")" << std::endl;
    
    // 调用全局函数
    int sum = add(2, 3);
    std::cout << "Sum: " << sum << std::endl;
    
    return 0;
}

1 基本使用

#include <iostream>
using namespace std;    // stdio.h

int main()
{
    cout << "Hello C++" << endl;
    //std::cout << "Hello World!\n";
}
// 引用命名空间，否则就是 namespace::function 使用
// 命名空间主要用于区分同名的函数

// 引用命名空间中的一个函数
using std::endl;
int main()
{
	std::cout << "!" << endl;
}

// 查看版本（C++98:199711L，C++11:201103L，C++14:201402L）
#include <iostream>
using namespace std;

int main()
{
    cout << __cplusplus << endl;
}

2 变量

大部分同C语言。

//必须带 f ，否则会变成 double 类型
float f1 = 3.14f;
//字符串类型 使用前应包含<string>头文件（VS2022不用）
std::string str2 = "";

// 宽字符。Windows中通常是16位无符号整数，采用UTF-16编码。Linux和Unix中通常是32位整数，采用UTF-32编码。L是宽字节常量。
wchar_t unichar = L"Hello World!";

// string字符串操作
// string -> int
int num = stoi(str);

// 构造字符串
string str = stirng("123");
string space = string(10,' '); // 依照数量构造

// int -> string
string str = to_string(num);

// 获取子串（pos：起始位置，n：个数）
s.substr(int pos = 0,int n);

// 寻找子串（str：子串，position：起始位置）
s.find(str,position);

// 字符串拼接
str = a + b;
str.append(c);

// 获得长度（注：类型是无符号类型，需要做运算前应该赋给int类型的变量，再做运算）
unsigned int n = s.length();

// 读取float和double所有精度
#include <iostream>  
#include <iomanip>
using namespace std;

int main() {
	float f = 123.45678901234567894567890123456789f;
    // std::setprecision(7)：设置精度
	std::cout << "float: " << std::fixed << std::setprecision(7) << f << std::endl;

	double d = 123.45678901234567894567890123456789;
	std::cout << "double: " << std::fixed << std::setprecision(16) << d << std::endl;
	return 0;
}

3 运算符

同C。

4 输入输出

输入带空格

输入被跳过问题

using namespace std;

// 输入（同C：空格截断）
cin >> (scanf) ; 

// 输出
// (print)是输出结果，例：cout << "a="<< a << ",b=" << b << endl; 
// endl：以换行结束，ends：不以换行结束。
cout << (print) << endl;
cout << "Hello" << " " << "World" << endl;

//带空格输入（string中前一个函数是将cin的残留回车符清除。）
char[]带空格：cin.get(arr,len);
string带空格：cin.ignore(); getline(cin,str);

5 判断

同C。

6 循环

同C。

//goto语句（同汇编）：
label: 
goto label;

// 迭代获得str中的值给x，带了引用表示对x的操作会影响str值，不带则不会影响
for(auto x:str);
for(auto& x:str);

7 数组

同C。

8 函数

同C。

默认参数

不同于python，默认参数之后的参数都必须是默认参数，输入值时不可以指定参数的位置（例不可以：fun( b = 10); ）

函数在声明和实现中只能有一处有默认参数。

占位参数

传值时必须传值，但是该值不会被使用（暂时）（例：void fun ( int a , int )）

占位参数也可以是默认参数（例：void fun ( int a , int = 10 )）

函数重载

参数是( int& a) 和 ( const int& a )：func(a)是第一个，func(10)是第二个。

默认参数容易出现二义性。

// 默认参数
// 示例1：默认参数之后的参数都必须是默认参数
void myFunction(int a, int b = 5, int c = 10) {}

myFunction(1); // 正确，b和c将使用默认值
myFunction(1, 2); // 正确，c将使用默认值
myFunction(1, c = 15); // 错误，不可以指定参数的位置

// 示例2：函数声明中指定默认参数
void myFunction(int a, int b = 5); 
// 函数定义中不能再次指定默认参数
void myFunction(int a, int b) {}


// 占位参数
// 示例1：带有占位参数的函数
void myFunction(int a, int) {
    // a被使用，但第二个参数没有使用
    // 所以传递什么值给第二个参数并不重要
}
myFunction(5, 10); // 参数10会被忽略

// 示例2：占位参数也可以是默认参数
void myFunction(int a, int b = 10) {}
myFunction(5); // 正确，b将使用默认值


// 函数重载
// 示例1：参数是(int& a) 和 (const int& a)
// a是一个非常量引用
void myFunction(int& a) {}
// a是一个常量引用
void myFunction(const int& a) {}
int main() {
    int x = 5;
    const int y = 10;

    myFunction(x); // 调用第一个函数，x是一个非常量
    myFunction(y); // 调用第二个函数，y是一个常量

    myFunction(10); // 错误，编译器无法确定调用哪个函数
    return 0;
}

// 示例2：默认参数容易出现二义性
void myFunction(int a, int b = 5) {}
void myFunction(int a, int b) {}
myFunction(1); // 错误，出现了默认参数的二义性

9 文件

流对象	作用
ofstream	写文件
ifstream	读文件
fstream	读写文件

打开方式	解释
ios::in	读
ios::out	写
ios::ate	初始位置为文件尾
ios::app	追加
ios::trunc	文件存在则删除文件再创建
ios::binary	二进制打开

文件打开方式可以配合使用，如二进制写：ios::binary | ios::out

// 1.包含头文件
#include <fstream>

// 2.创建流对象
ifstream ifs;
ifstream ifs("path",mode);
ofstream ofs;
ofstream ofs("path",mode);

// 3.打开文件（也可以直接在上面构造对象）
ofs.open("path",mode);

// 4.读写数据
ifs >> buf;
ofs << "data" << endl;

// 5.关闭文件
ofs.close();

// 读数据
ifs.read(buf,sizeof(buf));
// 读取一行
ifs.getline(buf, sizeof(buf));
getline(ifs,buf);
// 读取一个字符
char c = ifs.get();

// 写数据
ofs.write(buf,sizeof(buf));

10 异常

链接

// 抛出异常
throw "tip";

// 捕获异常
try
{}
catch(ExceptionName e)
{}
// 写...表示捕获所有异常
catch(...)
{}

11 指针

同C

// 常量指针：指针的指向可以改，指针指向的值不能被修改。
const int* p = &a;
p1 = &b; // 正确
*p1 = 100;  // 报错

// 指针常量：指针的指向不可以改，指针指向的值可以改。
int* const p = &a;
p2 = &b; // 报错
*p2 = 100; // 正确

// const既修饰指针又修饰常量：都不可以改。
const int* const p = &a;
p3 = &b; // 报错
*p3 = 100; // 报错

12 结构体

同C

默认访问权限是公有。

13 内存

同C

内存区域	解释
代码区	存放函数体的二进制代码，由操作系统进行管理
全局区	存放全局变量全局常量和静态变量
栈区	由编译器自动分配释放，存放函数的参数值，局部变量，局部常量等（栈区函数使用完后返回的局部变量会保留一次，cout输出一次其他字符串后会被清空）
堆区	由程序员分配和释放，若程序员不释放，程序结束时由操作系统回收

//堆区开辟数据：（指针在栈区，数据在堆区）
//开辟地址，初值为 num
type *p = new type( num ) ;
//num 个 type 的地址
type *p = new type[ num ] ;

//堆区释放数据/数组
delete p; 
delete[] p;

三、引用

注意：

引用必须初始化，不能只有定义。（作为函数参数可以补初始化）

引用初始化后不能再修改指向对象，之后使用等于是赋值。（包括地址指向）

type &alias = name;
int& b = a;

//内部实现：指针常量（下面两个等价）
int& ref = a;  // ref = a;和下面注释等价
int* const ref = &a;  // *ref = a;

//函数引用传递（传原名，相当于取别名后传递，会影响原数据）
int add (int& a,int& b);
//返回值可以是引用
int& add();

//有趣案例：
int& fun()
{
    static int a = 10;
    return a;
}
int main()
{
    int& ref = fun();
    fun() = 1000;
    std::cout << ref << std::endl;
    return 0;
}
//打印值为1000。

四、类与对象

1 封装

class name { access : type / function }; ： class 类名 { 访问权限 : 属性 / 方法 } ;（不用于C#，一个访问权限会影响后面所有的属性和方法）

class_name::function：class_name.function，直接使用类的方法，不实例化。

类的拆分：

头文件：保留类名和函数名。

主文件：类的具体实现。（不用留下类名，而是在包含头文件后 class_name : : function 即可，相当于直接用类的属性或方法）

访问权限：（类内属性方法默认私有，结构体内属性方法默认公有）

public：类内可以访问，类外可以访问。

private：类内可以访问，类外不可以访问。不可以被继承。

protected：类内可以访问，类外不可以访问。可以被继承。

#include <iostream>
using namespace std;

class Person {
private:
    string name;
    int age;
    int high = 160;
};
public:
	// 类中可以定义引用类型
	int& age = high;
    // 构造函数
    Person(string n, int a) {
        name = n;
        age = a;
    }

    // 公有方法
    void say_hello() {
        cout << "Hello, my name is " << name << " and I am " << age << " years old." << endl;
    }

    // 公有方法
    void set_age(int a) {
        age = a;
    }

    // 公有方法
    int get_age() {
        return age;
    }
};

int main() {
    // 创建 Person 类的对象
    Person p("Bob", 30);

    // 调用公有方法
    p.say_hello();

    // 调用公有方法
    p.set_age(40);

    // 调用公有方法
    cout << "Bob's age is " << p.get_age() << endl;

    return 0;
}

2 对象特征

2.1 构造和析构

构造函数：class_name() {} ，实例化对象，可以有参数。

初始化列表： class_name() : type() , ... ;（同C#，自动调用构造函数）

初始化列表的执行顺序与成员变量在类定义中的声明顺序有关。

建议成员变量的初始化顺序应该与它们在类定义中的声明顺序一致，以避免潜在的问题。

初始化类：

括号法（无参直接不写括号，不然是声明函数）

显示法（不写实例是初始化一个匿名对象，不使用会立刻被释放。且不要匿名初始化拷贝函数，编译器会认为是对象声明（Person(p3)等价于Person p3 ））

析构函数：~class_name() {}，销毁对象，不可以有参数。

类嵌套，构造类先构造自身中的其他类再构造自身，析构则相反。

// 构造方法
// 括号法
Person p(10);
Person p;
// 显示法
Person p = Person();

// 隐式转换
Person p4 = 10; // 等价于Person p4 = Person(10);

// 释放内存
if (p != NULL) { 
    delete p; 
    p = NULL; 
};

// 初始化列表（初始化顺序是先1后2，因为1先声明）
class MyClass {
private:
    int m_value1;
    int m_value2;

public:
    MyClass(int value1, int value2) : m_value1(value1), m_value2(value2) {
        std::cout << "Hello World" << std::endl;
    }
};

#include <iostream>

class Person {
public:
    Person() {
        std::cout << "Person constructor called" << std::endl;
    }

    Person(const Person& other) {
        std::cout << "Person copy constructor called" << std::endl;
    }

    ~Person() {
        std::cout << "Person destructor called" << std::endl;
    }
};

int main() {
    // 匿名对象，立即被释放
    Person();
    
    // 匿名对象拷贝初始化，被解释为对象声明
    Person(p3);
    Person p4;

    return 0;
}

2.2 拷贝类

浅拷贝：简单的复制拷贝（指针则是复制地址）。

深拷贝：重新在堆区申请空间再进行拷贝。

类构造函数分类：有参和无参，普通和拷贝构造函数（Person ( const Person &p) ; ，传一个自己的引用）

拷贝构造函数使用场景：

函数传局部变量：当将一个对象作为参数传递给函数时，拷贝构造函数会在函数调用期间创建该对象的副本。

函数 return：当函数返回一个对象时，拷贝构造函数会在函数返回之前创建该对象的副本。

主动拷贝：有时候需要显式地创建一个对象的副本，而不是与现有对象共享数据。

注意：如果用户定义了拷贝构造函数，c++不会提供任何默认构造函数。

class MyClass {
private:
	char* m_data;
public:
	// 拷贝构造函数（浅拷贝）
	MyClass(const MyClass& other) : m_data(other.m_data) {}
}

class MyClass {
private:
	char* m_data;
public:
	// 拷贝构造函数（深拷贝）
	MyClass(const MyClass& other) {
		m_data = new char[strlen(other.m_data) + 1];
		strcpy(m_data, other.m_data);
	}
}

// 调用拷贝构造函数
MyClass obj2(obj1);
MyClass obj3 = obj1; // 和等号赋值运算符不同，此处是声明并赋值，等于调用了拷贝构造函数

// 1.函数传局部变量
#include <iostream>

class MyClass {
public:
    MyClass() {
        std::cout << "Constructor called" << std::endl;
    }

    MyClass(const MyClass& other) {
        std::cout << "Copy constructor called" << std::endl;
    }
};

void doSomething(MyClass obj) {
    // 在函数调用期间，会调用拷贝构造函数来创建 obj 的副本
}

int main() {
    MyClass obj;
    doSomething(obj);

    return 0;
}

// 2.函数 return
#include <iostream>

class MyClass {
public:
    MyClass() {
        std::cout << "Constructor called" << std::endl;
    }

    MyClass(const MyClass& other) {
        std::cout << "Copy constructor called" << std::endl;
    }
};

MyClass createObject() {
    MyClass obj;
    return obj;  // 在函数返回之前，会调用拷贝构造函数来创建 obj 的副本
}

int main() {
    MyClass newObj = createObject();

    return 0;
}

// 3.主动拷贝
#include <iostream>

class MyClass {
private:
    int m_value;

public:
    MyClass(int value) : m_value(value) {
        std::cout << "Constructor called" << std::endl;
    }

    MyClass(const MyClass& other) : m_value(other.m_value) {
        std::cout << "Copy constructor called" << std::endl;
    }
};

int main() {
    MyClass obj1(42);
    MyClass obj2 = obj1;  // 使用拷贝构造函数进行主动拷贝

    return 0;
}

2.3 静态类

静态成员变量：在类内定义（不可初始化），在类外全局处（不可以在函数中）初始化（不赋值默认0），初始化案例： int test::c ;

静态成员函数：只可以访问静态变量。

#include <iostream>
using namespace std;

class Test {
public:
    static int count; // 静态成员变量

    static void incrementCount() { // 静态成员函数
        count++;
    }
};

int Test::count = 0; // 静态成员变量初始化

int main() {
    cout << "Count: " << Test::count << endl; // 输出
    Test::incrementCount(); // 调用静态成员函数
    Test::incrementCount();
    cout << "Count: " << Test::count << endl; // 输出
    Test::incrementCount();
    cout << "Count: " << Test::count << endl; // 输出

    return 0;
}

2.4 类内存

内存：空对象为1B，非空对象成员变量和是多少内存就是多少。

空对象实例化为1B，空对象指针实例化为4B

有虚函数的类对象中都有一个虚函数表指针 __vptr，大小为4B(32位机器) / 8B(64位机器)

成员函数和静态成员不包含在其中（分开存储）。

this指针指向被调用的成员函数所属的对象。return *this; 可以返回自身（函数返回值是 class_name& ）。

空指针可以访问成员函数，但是下列情况会异常：

遇到 this会异常（因为指针为0）（可以添加代码来避免：if( this == NULL) { return ; }）。

遇到虚函数会直接异常（因为找不到虚函数表）

#include <iostream>

class MyClass {
private:
	string name = "123";
public:
	void printMessage() {
		// if (this == NULL){return;} // 加此代码可以避免异常
		cout << "Hello, I am MyClass!" << this->name << endl;
	}
    
    virtual void printMessage2() {
		cout << "Hello, I am MyClass!" << endl;
	}
};

int main() {
    MyClass* ptr = nullptr; // 空指针

    // 使用空指针调用成员函数
    ptr->printMessage();
    
    // 调用虚函数直接异常
    ptr->printMessage2();

    return 0;
}

2.5 常值类

常函数：void add() const {};。不可以在函数内修改类的值（相当于：const Class * const this），不会调用其他非const的成员函数。但若加上 mutable 的属性则可以在常函数中修改值。

常对象：const Class name;。只可以调用常函数。

#include <iostream>

class MyClass {
public:
    int value;

    void setValue(int newValue) {
        value = newValue;
    }

    void printValue() const {
        std::cout << "Value: " << value << std::endl;
    }
};

int main() {
    const MyClass obj; // 常对象

    // obj.setValue(10); // 错误，常对象不可调用非常函数
    obj.printValue(); // 可以调用常函数

    return 0;
}

2.6 友元

在类外访问类内的私有属性或方法。

友好函数：在类中用 friend type funtion();声明类外的全局函数即可。

友好类：在类中用friend class name; 声明类外的其他类即可。

友好类函数：在类中用 friend type class_name::function(); 声明类外的其他类中的函数即可。

#include <iostream>

class MyClass {
private:
    int privateData;

public:
    MyClass(int data) : privateData(data) {}

    // 友好函数声明
    friend void friendFunction(const MyClass& obj);

    // 友好类声明
    friend class FriendClass;
};

// 友好函数定义
void friendFunction(const MyClass& obj) {
    std::cout << "Friend function accessing private data: " << obj.privateData << std::endl;
}

// 友好类定义
class FriendClass {
public:
    void accessPrivateData(const MyClass& obj) {
        std::cout << "Friend class accessing private data: " << obj.privateData << std::endl;
    }
};

int main() {
    MyClass obj(42);
    
    // 通过友好函数访问私有数据
    friendFunction(obj);

    // 通过友好类访问私有数据
    FriendClass friendObj;
    friendObj.accessPrivateData(obj);

    return 0;
}

3 运算符重载

自定义的数据类型进行运算。

// 操作符重载（分成员函数重载和全局函数重载，同理，但调用方式不同）。
type operator+() {};
type operator-() {};
type operator*() {};
type operator/() {};

// 左移运算符（用在 cout 输出，只能全局定义，本质就是 cout << p ）
type operator<<( ostream& cout , class& p ) { ... }; 
// 无限追加（此操作可以实现 cout << p 后可以追加其他内容）
ostream& operator<<( ostream& cout , class& p ){ 
    return cout; 
}; 

// 递增运算符（前置/后置）（通过在括号中加 int 区分前置和后置，递减同理）
class& operator++() { 
    this.num ++; 
    return *this; 
}
class operator++( int ) { 
    class temp = *this;
    this.num++;
    return temp;
}

// 赋值运算符（用于深拷贝，之前类中数据存在应先释放再赋值）
class operator=( class& p ) { 
    return *this;
}

// 关系运算符
bool operator==( class& p ) { ... }
bool operator>( class& p ) { ... }
bool operator<( class& p ) { ... }

// 函数调用运算符（仿函数）（类名当函数名用）
type operator( ... ) { ... }

/* 
加法操作符重载案例
成员函数重载调用：double res = obj + 1.0;
全局函数重载调用：double res = 1.0 + 2.0;
*/
#include <iostream>

class MyClass {
private:
	double data;
public:
	MyClass(double val) : data(val) {}

	// 成员函数重载
	double operator+(double operand) const {
		return data + operand;
	}

	double getData() {
		return data;
	}
};

// 全局函数重载
double operator+(MyClass operand1, MyClass operand2) {
	return operand1.getData() + operand2.getData();
}

int main() {
	MyClass obj(2.0);

	// 成员函数重载调用
	double res1 = obj + 1.0;
	std::cout << "Member function overload result: " << res1 << std::endl;

	// 全局函数重载调用
	double res2 = 1.0 + 2.0;
	std::cout << "Global function overload result: " << res2 << std::endl;

	return 0;
}


// 无限追加案例



// 前置和后置



// 仿函数

4 继承

继承方式：

基础继承：class child: public father [ ,public father ...]（class 派生类 : 继承方式基类）

公共继承：public（可以访问父类公共的东西，且权限不变）

保护继承：protected（可以访问父类公共和受保护的东西，且权限变为受保护）

私有继承：private（可以访问父类公共和受保护的东西，且权限变为私有）

继承特性：

父类中所有非静态成员属性都会被继承（包括私有属性）

构造和析构：先构造父类，再构造子类。而析构相反。

子类和父类中出现同名成员：

访问子类：<obj>.<name>

访问父类：<obj>.<class>::<name>

注：同名参数在子类重写后父类中依旧存在。（用 sizeof 可以发现内存大小不变，参数只是隐藏了而已。和python不同，父类中写的函数中含有 this 的话会指向父类的属性而非子类重写的属性）

注：子类出现了与父类同名的函数，则会隐藏掉所有父类的同名函数（包括重载）

菱形继承问题定义：两个派生类继承了同一个基类，然后又有一个派生类继承了这两个派生类。

使用属性时通过作用域区分。

利用虚继承，在两个派生类继承方式之前加上关键字 virtual（class student : virtual public people），（此时继承下来的东西为 { vbptr }（virtual base pointer：虚基类指针），直接指向第一份数据，在第三个派生生继承时就不会产生二义性）

// 继承
#include <iostream>
using namespace std;

class Father {
public:
	int publicData;
	void publicFunction() {
		cout << "Father's public function" << endl;
	}

protected:
	int protectedData;
	void protectedFunction() {
		cout << "Father's protected function" << endl;
	}

private:
	int privateData;
	void privateFunction() {
		cout << "Father's private function" << endl;
	}
};

// 公共继承
class Child_Public : public Father {
public:
	void accessFatherData() {
		cout << "Accessing father's public data: " << publicData << endl;
	}
};

// 保护继承
class Child_Protected : protected Father {
public:
	void accessFatherData() {
		cout << "Accessing father's protected data: " << protectedData << endl;
	}
};

// 私有继承
class Child_Private : private Father {
public:
	void accessFatherData() {
		//cout << "Accessing father's private data: " << privateData << endl; // 错误：无法访问父类私有成员
	}
};

int main() {
	Child_Public child1;
	child1.publicData = 42;
	child1.accessFatherData();
	child1.publicFunction();

	Child_Protected child2;
	child2.accessFatherData(); // 错误数据：无法从外部访问受保护的成员
	//child2.publicFunction(); // 函数变成受保护权限，无法调用

	Child_Private child3;
	child3.accessFatherData(); // 错误：无法从外部访问私有成员
	//child3.publicFunction(); // 函数变成受私有权限，无法调用

	cout << "child publicData data:" << child1.publicData << endl;
	cout << "father publicData data:" << child1.Father::publicData << endl;

	return 0;
}

// 菱形继承问题
#include <iostream>

class Base {
public:
	int data;

	Base(int val) : data(val) {}
};

class Derived1 : virtual public Base {
public:
	Derived1(int val) : Base(val) {}
};

class Derived2 : virtual public Base {
public:
	Derived2(int val) : Base(val) {}
};

class Derived3 : public Derived1, public Derived2 {
public:
	Derived3(int val) : Base(val), Derived1(val), Derived2(val) {}
};

int main() {
	Derived3 obj(42);

	// 通过作用域区分属性
	std::cout << "Data from Derived1: " << obj.Derived1::data << std::endl;
	std::cout << "Data from Derived2: " << obj.Derived2::data << std::endl;

	// 使用虚继承解决菱形继承问题
	std::cout << "Data from Derived3: " << obj.data << std::endl;

	return 0;
}

5 多态

5.1 分类

静态多态：函数重载，运算符重载，复用函数名。

动态多态：派生类，虚函数。

静态多态的函数地址早绑定：编译阶段确定函数地址。

动态多态的函数地址晚绑定：运行阶段确定函数地址。

// 案例：cat:animal,speak(animal an)。传入cat 到 speak 中，输出的结果是 animal 的，因为是地址早绑定，编译阶段就确定了函数地址。（与 JAVA 和 C# 不同）
#include <iostream>
using namespace std;

class Animal {
public:
    void speak() {
        cout << "Animal speaks" << endl;
    }
};

class Cat : public Animal {
public:
    void speak() {
        cout << "Cat speaks" << endl;
    }
};

void speak(Animal* animal) {
    animal->speak();
}

int main() {
    Cat cat;
    speak(&cat); // 输出结果为 "Animal speaks"
    return 0;
}


// 解决方案：父类函数前加上 virtual 变成虚函数，使其变成动态函数，运行时才会确定地址，这样 speak 函数在调用时会先找子类。
#include <iostream>
using namespace std;

class Animal {
public:
    virtual void speak() {
        cout << "Animal speaks" << endl;
    }
};

class Cat : public Animal {
public:
    void speak() {
        cout << "Cat speaks" << endl;
    }
};

void speak(Animal* animal) {
    animal->speak();
}

int main() {
    Cat cat;
    speak(&cat); // 输出结果为 "Cat speaks"
    return 0;
}

5.2 动态多态条件

原理：存在虚函数表，虚函数起始位置存在虚函数表中。子类未重写则直接继承虚函数表，若重写了则虚函数表中对应函数地址要改成子类的。

有继承关系。

子类重写父类的虚函数。

...

5.3 纯虚函数与抽象类

纯虚函数：virtual void func() = 0;

抽象类：只要类中有一个纯虚函数就为抽象类。

抽象类特点：

无法实例化对象。

抽象类的子类必须重写父类的纯虚函数，也就是要有具体实现，否则子类也是抽象类。

#include <iostream>

// 抽象类
class Shape {
public:
    virtual void draw() = 0; // 纯虚函数，定义为抽象类

    void print() {
        std::cout << "Print shape." << std::endl;
    }
};

// 抽象类的子类
class Circle : public Shape {
public:
    void draw() override {
        std::cout << "Draw circle." << std::endl;
    }
};

int main() {
    // Shape shape; // 编译错误，无法实例化抽象类

    Circle circle;
    circle.draw();
    circle.print();

    return 0;
}

5.4 虚析构和纯虚析构

父类指针在析构时，不会调用子类中的析构函数，导致子类中堆区内容释放不干净。所以子类中有堆区内容时需要写虚析构或纯虚析构，没有可以不写。

利用虚析构可以解决父类指针释放时子类释放不干净的问题：virtual ~father(){}（写在父类中，要具体实现）

纯虚析构：

父类中声明：virtual ~father() = 0;

类外实现：father::~father(){}

有了纯虚析构之后，这个类也属于抽象类。

虚析构和纯虚析构只需要写一个即可。

...

6 VS 开发人员命令提示工具

:: x64 Native Tools Command Prompt for VS 2022
cd <path>
cl /d1 reportSingleclassLayout<name> <name>.cpp（cl ：l是字母，d1：1是数字）

五、模板

1 基本概念

建立通用的模具，大大提高复用性。

函数模版（T类型须一致，必须确定T才可以使用）：

template < typename T >

type function ( T a ) {} ;

使用：

自动推导；

显式指定 function<>() ;

与普通函数区别：

普通函数可以隐式转换（例：char -> int ）

函数模板自动类型推导不会隐式转换，用显式指定类型则会发生隐式转换

局限性：

无法简单地比较、赋值数组、类这样的数据类型。解决方法可以选择运算符重载（一般不选）、直接对模板函数进行重载，特殊处理指定的类。

// 简单案例
#include <iostream>

template <typename T>
T maximum(T a, T b) {
    return (a > b) ? a : b;
}

int main() {
    int num1 = 10;
    int num2 = 20;
    std::cout << "较大的数是：" << maximum(num1, num2) << std::endl;

    double num3 = 3.14;
    double num4 = 2.71;
    std::cout << "较大的数是：" << maximum(num3, num4) << std::endl;

    return 0;
}


// 局限性：特殊的模板处理
template <typename T>
T maximum(T a, T b) {
    return (a > b) ? a : b;
}

template<> Person& maximum(Person &a,Person &b){
    return (a.age > b.age) ? a : b;
}

2 与普通函数发生重载

如果函数模板和普通函数都可以调用，优先调用普通函数。

可以通过空模板参数列表强制调用函数模板。

函数模板可以发生函数重载。

如果函数模板可以产生更好的匹配，优先调用函数模板。

注：实际开发中不要同时出现函数模板和普通函数的重载。

// 简单案例
#include <iostream>
using namespace std;

void myPrint(int a, int b)
{
	cout << "Normal function called!" << endl;
}

template<typename T>
void myPrint(T a, T b)
{
	cout << "Template function called!" << endl;
}

template<typename T>
void myPrint(T a, T b, T c)
{
	cout << "Template overload function called!" << endl;
}

int main()
{
	int num1 = 10;
	int num2 = 20;
	char char1 = 'a';
	char char2 = 'b';
	char char3 = 'c';

	myPrint(num1, num2);  // 特点1
	myPrint<>(num1, num2);  // 特点2
	myPrint(char1, char2, char3);  // 特点3
	myPrint(char1, char2);  // 特点4
}

3 类模板

类模板与函数模板区别：

类模板没有自动类型推导的使用方式。

类模板在模板参数列表可以有默认参数。

类中成员函数创建时机：

普通类在一开始成员函数就会被创建。

模板类的成员函数只有在被调用时才会被创建（要知道 T 的值才会创建函数）。

// 简单案例
template<class NameType,class AgeType>
class Person
{
private:
    NameType m_Name;
    AgeType m_Age;
public:
	Person(NameType name,AgeType age)
    {
        this->m_Name = name;
        this->m_Age = age;
    }
};

// 类模板不会自动推导（不写<string, int>会报错）
Person<string, int> p("Ami", 123);
// 类模板的默认参数
template<class NameType, class AgeType = int>
class Person{}

/*类模板的成员函数传参*/
// 1.指定参数类型（常用）
void printPerson1(Person<string,int> &p){}
// 2.参数模板化
template<class T1,class T2>
void printPerson2(Person<T1,T2> &p){} 
// 3.整个类模板化
template<class T>
void printPerson3(T &p){}

4 类模板其他问题

类模板继承：

子类继承的父类是类模板时，子类在声明时要指明父类中T的类型。如果不指定编译器无法给子类分配内存。

如果想灵活指定父类T的类型，子类也需要变成类模板。

// 类模板继承
template<class T>
class Base{ T m; };

class Son:public Base<int>{}; // 1.不指明T将报错

template<class T1,class T2>
class Son2:public Base<T2>{ T1 obj;}; // 2.灵活指定T。父类的T是子类的T2。

六、 STL技术

1 基本概念

STL基础知识：

STL(Standard Template Library，标准模板库)

STL从广义上分为：容器(container)、算法(algorithm)、迭代器(iterator)。

容器和算法之间通过迭代器进行无缝连接。

STL几乎所有的代码都采用了模板类或者模板函数。

STL六大组件：

容器：各种数据结构，如vector、list、deque、set、map等，用来存放数据。

算法：各种常用的算法，如sort、find、copy、for_each等。

迭代器：扮演了容器与算法之间的胶合剂。

仿函数：行为类似函数，可作为算法的某种策略。

适配器：一种用来修饰容器或者仿函数或迭代器接口的东西。

空间配置器：负责空间的配置与管理。

容器：

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

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

算法：

质变算法：运算过程中会更改区间内的元素。

非质变算法：运算过程中不会更改区间内的元素。

迭代器：

算法需要靠迭代器才能访问容器中的元素。

每个容器有自己专属的地带器。功能类似指针。

常用的容器中的迭代器冲类为双向迭代器和随机访问迭代器

种类	功能	支持运算
输入迭代器	数据只读	只读，支持++、==、！=
输出迭代器	数据只写	只写，支持++
前向迭代器	读写，并向前推进迭代器	读写，支持++、==、！=
双向迭代器	读写，可前后推进迭代器	读写，支持++、—
随机访问迭代器	读写，可跳跃式访问任意数据	读写，支持++、—、[n]、-n、<、<=、>、>=

2 迭代器

// 迭代器
// 起始迭代器，指向容器第一个元素
vector<T>::iterator itBegin = v.begin();
// 结束迭代器，指向容器中最后一个元素的下一个位置
vector<T>::iterator itEnd = v.end();

// 迭代器访问数据
// 方法一
while(itBegin != itEnd)
{
    cout << *itBegin << endl;
    itBegin++;
}
// 方法二
for(vector<int>::iterator it = v.begin();it != v.end();it++)
{
    cout << *it << endl; 
}
// 方法三
#include <algorithm>
void func(int val){ cout << val << endl; }
void main(){ for_each(itBegin, itEnd, func); }

// 迭代器访问类中数据（假设容器为：vector<Person>）
(*it).name; // 对迭代器it解引用成容器中的参数后访问属性
it->name; // 直接访问对应属性

// 指针操作
vector<Person *> v; // 定义指针容器
Person p('Bob',12);
v.push_back(&p1); // 输入地址
for(vector<Person *>::iterator it = v.begin();it != v.end();it++)
{
    cout << (*it)->name << endl; // 解引用后指针操作
    cout << (**it).name << endl; // 两次解引用
}

// 常迭代器，迭代器中的值不可被修改
deque<int>const_iterator it;

// 案例
// 结果输出3，说明end不会一直更新
deque<int> dep;
dep.push_back(1);
dep.push_back(2);
deque<int>::iterator beg = dep.begin();
deque<int>::iterator end = dep.end();
dep.push_back(3);
dep.push_back(4);
dep.push_back(5);

cout << (*end) << endl;

3 vector容器

vector类似于数组，也成为单端数组。

数组空间是静态的，而vector可以动态扩展。扩展方式是找到更大的内存空间，然后将原数据拷贝新空间，释放原空间。

vector容器的迭代器是支持随机访问的迭代器。

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

// 创造容器
vector<T> v; // 默认无参构造
vector(v.begin(),v.end()); // 将区间内元素拷贝给本身
vector(n,elem); // 将n个elem拷贝给本身
vector(const vector &vec); // 拷贝构造函数

// 赋值
vector& operator = (const vector &vec); // 重载=
assign(beg,end); // 将[beg,end)区间的数据拷贝给本身
assign(n,elem); // n个elem拷贝给本身

// 大小
empty(); // 是否空
capacity(); // 容量
size(); // 元素个数
resize(int num); // 重设长度，变长填充默认值，变短删除尾部元素
resize(int num,elem); // 同理，但是变长填充的是elem

// 插入与删除
push_back(elem); // 尾部添加数据
pop_back(); // 尾部删除数据
insert(const_iterator pos,elem); // 迭代器指向的位置pos插入elem
insert(const_iterator pos,int count,elem); //同理，插入count个elem
erase(const_iterator pos); // 删除迭代器指向元素
erase(const_iterator start,const_iterator end); // 删除范围，左闭右开
clear(); // 删除容器中所有元素

// 存取
at(int idx); // 返回idx指向元素
operator[]; // 返回idx指向元素
front(); // 返回容器第一个元素
back(); // 返回容器最后一个元素

swap(vec); // 两个容器元素互换（常用于收缩内存）
reserve(int len); // 预留len个元素长度，但不可访问

// 容器嵌套（类似二维数组）
vector<vector<int>> v;
vector<int> v1;
vector<int> v2;
v.push_back(v1);
v.push_back(v2);

for(vector<vector<int>>::iterator it = v.begin(); it != v.end(); it++)
{
    for(vector<int>::iterator vit = (*it).begin(); vit != (*it).end(); vit++)
    {
        cout << *vit << " ";
	}
    cout << endl;
}

// 案例
// 收缩内存
int main()
{
	vector<int> v;
	for (int i = 0; i < 10000; i++)
	{
		v.push_back(i);
	}
    // 不交换前容器大小远大于实际大小
	cout << "before swap" << endl;
	cout << "capacity:" << v.capacity() << endl;
	cout << "size:" << v.size() << endl;
	// 重设大小后容器大小也不会变
    v.resize(3);
	cout << "after resize" << endl;
	cout << "capacity:" << v.capacity() << endl;
	cout << "size:" << v.size() << endl;
    // 子交换，缩小容器大小
    // 先利用v拷贝构造了一个匿名对象，然后交换，然后释放匿名对象的空间
	vector<int>(v).swap(v);
	cout << "after swap" << endl;
	cout << "capacity:" << v.capacity() << endl;
	cout << "size:" << v.size() << endl;
}

// 二维容器附加初值
vector<vector<int>> arr(rowLen, vector<int>(colLen, 0));

4 string容器

字符串。

string本质是一个类，内部封装了char*，有很多方法可以管理这个char*。

// 构造
string(); // 创建空字符串
string(const char* s); // 初始化常字符串
string(const string& str); // 用string对象初始化另一个string对象
string(int n,char c); // 用n个字符c进行初始化

//  赋值
string& operator=(const char* s); // char*类型字符串赋给当前字符串
string& operator=(const string &s); // 字符串s赋给当前字符串
string& operator=(char c); // 字符赋给当前字符串
string& assign(const char *s); // 字符串s赋给当前字符串
string& assign(const char *s,int n); // 字符串s的前n个字符赋给当前字符串
string& assign(const string &s); // 字符串s赋给当前字符串
string& assign(int n,char c); // 用n个字符c赋给当前字符串

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

// 查找（const表示不修改字符串，没找到返回-1）
int find(const string& str, int pos = 0) const; // 查找str第一次出现位置,从pos开始查找
int find(const char* s,int pos = 0) const; // 查找s第一次出现位置,从pos开始查找
int find(const char* s,int pos,int n) const; // 从pos位置查找s的前n个字符第一次位置
int find(const char c, int pos = 0) const; // 查找字符c第一次出现位置
int rfind(const string& str, int pos = npos ) const; // 查找str最后一次位置,从pos开始查找
int rfind(const char* s,int pos = npos ) const; // 查找s最后一次出现位置,从pos开始查找
int rfind( const char* s,int pos,int n) const; // 从pos查找s的前n个字符最后一次位置
int rfind(const char c,int pos = 0) const; // 查找字符c最后一次出现位置

// 替换
string& replace(int pos,int n,const string& str); // 替换从pos开始n个字符为字符串str
string& replace(int pos,int n,const char* s); // 替换从pos开始的n个字符为字符串s

// 字符串比较（ASCII码，=返回0，>返回1，<返回-1）
int compare(const string &s) const;
int compare(const char *s) const;

// 存取（可修改）
char& operator[](int n); // 直接索引
char& at(int n);

// 插入
string& insert(int pos,const char* s); // 插入字符串
string& insert(int pos,const string& str); // 插入字符串
string& insert(int pos,int n, char c); // 在指定位置插入n个字符c

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

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

5 deque容器

双端队列。

vector对于头部的插入删除效率低，因为插入要移动元素。

deque相对而言，对头部的插入删除速度比vector快。

vector访问元素时的速度会比deque快，这和两者内部实现有关。

内部工作原理：deque内部有个中控器，中控器中有多段缓冲区，缓冲区中存放数据。中控器维护每段缓冲区中的地址，使得deque使用时像一片连续的内存空间。

deque容器的迭代器是支持随机访问的迭代器。

#include <deque>

// 创建双端队列（类似vector）
deque<T> deqT;
deque(v.begin(),v.end());
deque(n,elem);
deque(const deque &deq);

// 赋值（类似vector）
deque& operator = (const deque &deq);
assign(beg,end);
assign(n,elem);

// 大小（类似vector,但是没有capacity，因为它可以无限扩展）
empty();
size();
resize(int num);
resize(int num,elem);

// 两端插入和删除
push_back(elem);
push_front(elem);
pop_back();
pop_front();

// 指定位置插入删除
insert(pos,elem);
insert(pos,n,elem);
insert(pos,beg,end);
erase(pos);
erase(beg,end);
clear();

// 存取
at(int idx);
operator[];
front();
back();

6 stack容器

栈。

#include <stack>

// 创建栈
stack<T> stk;
stack(const stack &stk);

// 赋值
stack& operator=(const stack &stk);

// 大小
empty();
size();

// 入栈出栈
push(elem);
pop(); // 出栈（返回值为空！）
top(); // 返回栈顶元素（不出栈）

7 queue容器

普通队列。

#include <queue>

// 创建队列
queue<T> que;
queue(const queue &que);

// 赋值
queue& operator=(const queue &que);

// 大小
empty();
size();

// 入队出队
push(elem);
pop();
front(); // 返回队头元素（不出队）
back(); // 返回队尾元素（不出队）


// 大小
empty();
size();
resize(int num);
resize(int num,elem);

// 优先队列（默认大根堆）
priority_queue<T> maxHeap;
priority_queue<T, vector<T>, less<T>> maxHeap;
priority_queue<T, vector<T>, greater<T>> minHeap; // 切换到小根堆

maxHeap.size();
maxHeap.empty();
maxHeap.push(val);
maxHeap.pop();
maxHeap.top();

8 list容器

双向循环链表。

list的优点：

采用动态存储分配，不会造成内存浪费和溢出。

链表增删时间为O(1)。

list的缺点：

空间（额外的指针指向下一节点）和时间（遍历）消费大。

List有一个重要的性质，插入操作和删除操作都不会造成原有list迭代器的失效，这在vector是不成立的。

list容器的迭代器是双向迭代器。

#include<list>

// 创建双向循环链表
list<T> lst;
list(beg,end);
list(n,elem);
list(const list &lst);

// 赋值
list& operator = (const list &list);
assign(beg,end);
assign(n,elem);

// 两端插入和删除
push_back(elem);
push_front(elem);
pop_back();
pop_front();

// 指定位置插入删除
insert(pos,elem);
insert(pos,n,elem);
insert(pos,beg,end);
erase(pos);
erase(beg,end);
clear();
remove(elem); // 删除所有与elem值匹配的元素

// 存取
front();
back();

reverse(); // 反转
sort([func]); // 排序（定义函数：bool func(a,b){ return;}）
swap(lst); // 两个容器元素互换

9 set/multiset容器

集合。

所有元素在插入时自动排序。

本质：关联式容器，底层是二叉树。

set不允许有重复元素，multiset允许有重复元素。

#include <set>

// 创建集合
set<T> st;
set(const set &st);
// 可重复集合
multiset<T> st;


// 赋值
set& operator=(const set &st);

// 大小
empty();
size();

// 插入删除
insert(elem);
erase(pos);
erase(beg,end);
erase(elem); // 删除值为elem的元素
clear();

// 查找
find(key); // 查找key是否存在，存在返回指定元素的迭代器，不存在返回set.end();
count(key); // 统计key的个数

swap(st);


// 创建重复集合
multiset<T> st;
multiset(const set &st);

// 创建对组
pair<type,type> p (val_1,val_2);
pair<type,type> p = make_pair(val_1,val_2);

// 取队组数
p.first;
p.second;

// set的insert有返回结果判断是否插入成功
pair<set<int>::iterator,bool> ret = s.insert(10);
if(ret.second) { cout << "success!" << endl;}
else { cout << "failed!" << endl;}

// set排序（默认从小到大，可以自定义仿函数改变排序规则，需要在插入数据前改变）
// 从大到小排序
class MyCompare
{
public:
    bool operator()(int v1,int v2)
    {
        return v1 > v2;
    }
}
void main()
{ set<int,MyCompare> s; }

// 自定义数据类型需要指定排序规则规则
#include <iostream>
#include <algorithm>
#include <set>
using namespace std;

class Person
{
public:
	string m_Name;
	int m_Age;
	Person(string name, int age)
	{
		this->m_Name = name;
		this->m_Age = age;
	}
};
class comparePerson
{
public:
    // 函数尾需要加const进行只读限制
	bool operator()(const Person& v1, const Person& v2)const
	{
		return v1.m_Age > v2.m_Age;
	}
};

int main()
{
	set<Person, comparePerson> s;

	s.insert(Person("lili", 16));
	s.insert(Person("muge", 12));
	s.insert(Person("sora", 15));

	for (set<Person, comparePerson>::iterator it = s.begin(); it != s.end(); it++)
	{
		cout << (*it).m_Name << " is " << (*it).m_Age << endl;
	}
	return 0;

}

10 map/multimap容器

字典。

元素都是pair，第一个是key，第二个是value。

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

本质：关联式容器，底层是二叉树。

map不允许有重复的键，multimap允许有重复的键。

自定义数据类型需要指定排序规则规则（同理set）

#include <map>

// 创建字典
map<T1,T2> mp;
map(const map &mp);
// 无序字典
unordered_map<T1,T2> mp;
// 可重复字典
multimap<T1,T2> mp;


// 赋值
map& operator=(const map &mp);

// 大小
empty();
size();

// 指定位置插入删除
insert(pair<key,value>);
erase(pos);
erase(beg,end);
erase(key); // 删除键为key的元素
clear();

// 查找
find(key); // 查找key是否存在，存在返回指定元素的迭代器，不存在返回set.end();
count(key); // 统计key的个数

swap(mp);

// map排序（默认从小到大，可以自定义仿函数改变排序规则，需要在插入数据前改变）
// 从大到小排序
class MyCompare
{
public:
    bool operator()(int v1,int v2)
    {
        return v1 > v2;
    }
}
void main()
{ map<int,int,MyCompare> mp; }

// 初始化值为0，可以直接++
map<int,int> mp;
mp[i]++;

// 遍历字典
for(map<int,int>::iterator iter = mp.begin(); iter != mp.end(); iter++)
{
    int key = iter->first;
    int second = iter->second;
}

// 判断键存在
if(mp.find(s[i]) != mp.end()){;}

11 函数对象

概念：

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

函数对象使用重载的()时，行为类似函数调用。也叫仿函数。

本质:

函数对象(仿函数)是一个类，不是一个函数。

特点：

函数对象在使用时，可以像普通函数那样调用，可以有参数，可以有返回值函数。

对象超出普通函数的概念，函数对象可以有自己的状态。

函数对象可以作为参数传递。

谓词概念：

返回bool类型的仿函数称为谓词。

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

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

// 1.函数对象在使用时，可以像普通函数那样调用，可以有参数，可以有返回值函数。
class MyAdd
{
public:
    int operator()(int v1,int v2)
    { return v1 + v2; }
};

void test01()
{
    MyAdd myAdd;
    cout << myAdd(10,10) << endl;
}

// 2.对象超出普通函数的概念，函数对象可以有自己的状态。
class MyPrint
{
public:
	int count = 0; // 记录函数被调用的次数
	void operator()(string test)
	{
		cout << test << endl;
		count++;
	}
};

void test02()
{
	MyPrint myPrint;
	for (int i = 0; i < 10; i++)
	{
		myPrint("Hello World!");
	}

	cout << "myPrint has been called " << myPrint.count << " times" << endl;
}

// 3.函数对象可以作为参数传递。
void doPrint(MyPrint &mp, string test)
{ mp(test); }

void test03()
{
    MyPrint myPrint;
    doPrint(myPrint,"Hello C++");
}

// STL内建仿函数
#include<functional>

// 算术仿函数
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> // 逻辑非

// greater案例
#include <iostream>
#include <functional>

int main() {
    std::greater<int> greaterThan; // 创建一个greater仿函数对象

    int a = 5;
    int b = 10;

    if (greaterThan(a, b)) {
        std::cout << "a is greater than b" << std::endl;
    } else {
        std::cout << "a is not greater than b" << std::endl;
    }

    return 0;
}

七、 STL中的算法

所有不支持随机访问迭代器的容器，不可以用标准算法。（例如：list）

1 遍历算法

#include <algorithm>

// 遍历容器（func是指遍历时的操作）
for_each(iterator beg,iterator end,_func);

for_each(v.begin(),v.end(),print01); // 普通函数放函数名，类调用放类名
for_each(v.begin(),v.end(),print02()); // 调用仿函数放函数名后要带括号


// 搬运容器到另一个容器中（func是指搬运时的额外操作）
// 注：目标容器要有空间（size），reserve不行。
transform(iterator ori_beg,iterator ori_end,iterator new_beg,_func);

class NewData {
private:
	static int i;
public:
	int operator()() {
		this->i++;
		return i * 10;
	}
};

int NewData::i = 0;

class AddFive {
public:
	int operator()(int value) const {
		return value + 5;
	}
};

class MyPrint {
public:
	void operator()(int value) const {
		std::cout << value << std::endl;
	}
};

int main()
{
	vector<int> v;
	v.resize(10);

	NewData newData;
	generate(v.begin(), v.end(), newData);

	vector<int> news;
	news.resize(v.size());
    // news.reverve(v.size()); // 仅预留空间，不会报错，但数据无法插入

	transform(v.begin(), v.end(), news.begin(), AddFive());
	for_each(news.begin(), news.end(), MyPrint());
	cout << news.capacity() << " " << news.size() << endl;

	return 0;
}

/* newData不用括号：在上述代码中，generate(v.begin(), v.end(), newData) 使用的是 newData 而不是 newData() 是因为 generate 函数期望传递一个可调用对象作为生成元素的函数。newData 是一个可调用对象，它是一个函数对象（仿函数）类型，并通过重载 operator() 实现了调用运算符。因此，将 newData 传递给 generate 函数时，这个函数对象会被调用来生成每个元素的值。如果使用 newData() 代替 newData，那么等价于调用了 operator() 并返回了结果。这并不是我们想要的效果，因为我们希望在每次调用 operator() 时，NewData 类中的静态成员变量 i 都会自增，而不是只调用一次。因此，正确的方式是直接将 newData 作为可调用对象传递给 generate 函数。这样，每次调用 newData 都会触发 operator() 的执行，从而实现按需生成序列的功能。 */

2 查找算法

#include <algorithm>

// 查找元素（自定义元素类型要重载==号来判断相等，找不到返回v.end()）
iterator find(iterator beg,iterator end,value);

// 按条件查找元素（_Pred函数或谓词，找不到返回v.end()）
iterator find_if(iterator beg,iterator end, _Pred);

// 查找相邻重复元素（找到返回第一个数的迭代器，否则返回v.end()）
iterator adjacent_find(iterator beg,iterator end);

// 二分查找（序列一定要升序排序）
bool binary_search(iterator beg,iterator end,value);

// 统计元素个数（自定义要重载==）
int count(iterator beg,iterator end,value);

// 按条件统计元素个数
int count_if(iterator beg,iterator end,_Pred);

3 排序算法

#include <algorithm>

// 排序（默认升序）
sort(iterator beg,iterator end[,_Pred]);
sort(v.begin(),v.end(),greater<int>()); // 降序

// 洗牌，指定范围内的元素随机调序
srand((unsigned int)time(NULL));
random_shuffle(iterator beg,iterator end);

// 容器元素合并并存储到新容器中（两个容器需要有序，dest是目标容器的开始迭代器）
merge(iterator beg_1,iterator end_1,iterator beg_2,iterator end_2,iterator dest);

// 反转元素
reverse(iterator beg,iterator end);

4 拷贝替换算法

#include <algorithm>

// 拷贝（dest：目标起始迭代器，目标容器需提前开辟空间）
copy(iterator beg,iterator end,iterator dest);

// 替换元素
repalce(iterator beg,iterator end,old_value,new_value);

// 按条件替换元素
replace_if(iterator beg,iterator end,_pred,new_value);

// 互换两个同类型容器的元素
swap(container c1,container c2);

5 算术生成算法

#include <numeric>

// 元素累计（value是初值）
int sum = accumulate(iterator beg,iterator end,value); // 累加
int sum = accumulate(vec.begin() ,vec.end() ,1 ,multiplies<int>()); // 累乘


// 将指定区间的值填充为目标值
fill(iterator beg,iterator end,value);

6 集合算法

#include <algorithm>

// 交集（dest：目标起始迭代器，目标容器需提前开辟空间）
iterator set_intersection(iterator beg_1,iterator end_1,iterator beg_2,iterator end_2,iterator dest);

// 并集（两个集合需有序）
iterator set_union(iterator beg_1,iterator end_1,iterator beg_2,iterator end_2,iterator dest);

// 差集（两个集合需有序）
iterator set_difference(iterator beg_1,iterator end_1,iterator beg_2,iterator end_2,iterator dest);

// 获取交集
vTarget.resize(min(v1.size(),v2.size()));
vector<int>::iterator itEnd = set_intersection(v1.begin(),v1.end(),v2.begin(),v2.end(),vTarget);

for_each(vTarget.begin(),itEnd,myPrint); // 此处要用itEnd而不是vTarget.end()，因为开辟的空间不一定全部都用到了

// 获取并集
vTarget.resize(v1.size() + v2.size());

// 获取差集
vTarget.resize(max(v1.size(),v2.size()));

八、C++库

库名	连接	功能
boost	安装	自定义命令行输入输出
Opencv	text::Opencv	视觉处理

C++

一、C语言

0 基础

1 变量

2 运算符

3 输入输出

4 判断

5 循环

6 数组

7 函数

8 文件

9 指针

10 结构体

11 内存

二、C++基础

0 工程包含

1 基本使用

2 变量

3 运算符

4 输入输出

5 判断

6 循环

7 数组

8 函数

9 文件

10 异常

11 指针

12 结构体

13 内存

三、 引用

四、 类与对象

1 封装

2 对象特征

2.1 构造和析构

2.2 拷贝类

2.3 静态类

2.4 类内存

2.5 常值类

2.6 友元

3 运算符重载

4 继承

5 多态

5.1 分类

5.2 动态多态条件

5.3 纯虚函数与抽象类

5.4 虚析构和纯虚析构

6 VS 开发人员命令提示工具

五、 模板

1 基本概念

2 与普通函数发生重载

3 类模板

4 类模板其他问题

六、 STL技术

1 基本概念

2 迭代器

3 vector容器

4 string容器

5 deque容器

6 stack容器

7 queue容器

8 list容器

9 set/multiset容器

10 map/multimap容器

11 函数对象

七、 STL中的算法

1 遍历算法

2 查找算法

3 排序算法

4 拷贝替换算法

5 算术生成算法

6 集合算法

八、C++库

九、C/C++应用

三、引用

四、类与对象

五、模板