C++基础

1. 技术路线

600

2. 链接

https://www.zhihu.com/question/587090539 ^a28e96

https://www.zhihu.com/tardis/zm/art/435927070?source_id=1005

https://interviewguide.cn/notes/03-hunting_job/02-interview/01-01-01-basic.html

3. 指针常量与常量指针

  • const修饰指针有三种情况
  1. const修饰指针 --- 常量指针
  2. const修饰常量 --- 指针常量
  3. const即修饰指针，又修饰常量
int main() {
	int a = 10;
	int b = 10;
	//const修饰的是指针，指针指向可以改，指针指向的值不可以更改
	const int * p1 = &a; 
	p1 = &b; //正确
	//*p1 = 100;  报错
	//const修饰的是常量，指针指向不可以改，指针指向的值可以更改
	int * const p2 = &a;
	//p2 = &b; //错误
	*p2 = 100; //正确
    //const既修饰指针又修饰常量
	const int * const p3 = &a;
	//p3 = &b; //错误
	//*p3 = 100; //错误
	system("pause");
	return 0;
}
  • 引用的本质是在内部实现一个指针常量.
int a = 10;
//自动转换为 int* const ref = &a; 指针常量是指针指向不可改，也说明为什么引用不可更改
int& ref = a; 
ref = 20; //内部发现ref是引用，自动转换为: *ref = 20;
  • 在函数形参列表中，可以加==const修饰形参==，防止形参改变实参
//int& ref = 10;  引用本身需要一个合法的内存空间，因此这行错误
//加入const就可以了，编译器优化代码，int temp = 10; const int& ref = temp;
const int& ref = 10;

//常用作类的拷贝构造函数
Person(const Person& p) {
	cout << "拷贝构造函数!" << endl;
}

4. 指针数组与数组指针

  • 指针
int a = 10;
//变量名是p
int* p = &a;//p是一个变量名，其值是int*类型

int array[5] = {1, 2, 3, 4, 5}; // 定义数组
int *intptr = array; // 定义指向数组元素的指针
cout << intptr << endl << intptr[2] << endl<< *intptr <<endl<< *(intptr+1)<< endl;
int (*arrayptr)[5] = &array; // 定义指向数组的指针
cout << arrayptr << endl << *arrayptr << endl<< **arrayptr << *(*arrayptr+1 )<< endl;
//输出
012FFC20
3
1
2
012FFC20
012FFC20
12
  • 指针数组：是一个数组，其每个元素是指针
//变量名是p[3]
int* p[3]; //定义一个指针数组,该数组长度为3，其内存放着三个指针变量分别是p[0]、p[1]、p[2]
int a[3][4];
for (int i = 0; i < 3; i++)
	p[i] = a[i]//要分别赋值。

int a = 10;
cout << &a << endl;
//变量名是p[3][4]
int* p[3][4] = { &a };//直接定义二维数组，其每个元素存放a的地址
cout << p[0][0] << endl;
  • 数组指针：是一个指针，其指向一个数组
int a[3][4] = { {1,2,3,4},{5,6,7,8},{9,10,11,12} };
//变量名是*p
int (*p)[4]; //定义一个数组指针
p=a; //将二维数组赋给一个指针，本质上将二维数组的首地址赋给p，即a[0]或&a[0][0]
p++; //该语句执行过后，也就是p=p+1;p跨过行a[0][]指向了行a[1][]

int(* pa)[3][4] = &a;
//变量名是*pa
cout << *(*(*pa)+1)+1)<<endl;

5. 指针函数与函数指针

  • 指针函数：是一个函数，返回值是指针
int  *fun(int x)
Data* f(int a,int b){
    Data * data = new Data;
    data->a = a;
    data->b = b;
    return data;
}
  • 函数指针：是一个指针，指向函数的入口
int test(int a){
    return a;
}
int main(int argc, const char * argv[]){
    int (*fp)(int a);
    fp = test;
    //或者
    int (*fp)(int a) = &test;
    cout<<fp(2)<<endl;
    return 0;
}

6. Lambda表达式

  • Lambda表达式是一种在被调用的位置或作为参数传递给函数的位置定义匿名函数对象（闭包） 的简便方法。
[capture list] (parameter list) mutable -> return type { function body }
  • [capture list] 是捕获列表，用于指定 Lambda表达式可以访问的外部变量，以及是按值还是按引用的方式访问。它标识一个Lambda的开始。函数对象参数是传递给编译器自动生成的函数对象类的构造函数的。函数对象参数只能使用那些到定义Lambda为止时Lambda所在作用范围内可见的局部变量（包括Lambda所在类的this）。
    1. 空：没有使用任何函数对象参数。
    2. =：使用Lambda所在作用范围内所有可见的局部变量（包括Lambda所在类的this），并且是值传递方式（相当于编译器自动为我们按值传递了所有局部变量）。
    3. &：使用Lambda所在作用范围内所有可见的局部变量（包括Lambda所在类的this），并且是引用传递方式（相当于编译器自动为我们按引用传递了所有局部变量）。
    4. this：函数体内可以使用Lambda所在类中的成员变量。此时是引用传递类的成员变量。
    5. a：将a按值进行传递。按值进行传递时，函数体内不能修改传递进来的a的拷贝，因为默认情况下函数是const的。要修改传递进来的a的拷贝，可以添加mutable修饰符。
    6. &a：将a按引用进行传递。
    7. a, &b：将a按值进行传递，b按引用进行传递。
    8. =，&a, &b。除a和b按引用进行传递外，其他参数都按值进行传递。
    9. &, a, b：除a和b按值进行传递外，其他参数都按引用进行传递。
int x = 10;
auto f = [x] (int y) -> int { return x + y; }; // 值捕获 x
x = 20; // 修改外部的 x
cout << f(5) << endl; // 输出 15，不受外部 x 的影响

int x = 10;
auto f = [&x] (int y) -> int { return x + y; }; // 引用捕获 x
x = 20; // 修改外部的 x
cout << f(5) << endl; // 输出 25，受外部 x 的影响

int x = 10;
int y = 20;
auto f = [=, &y] (int z) -> int { return x + y + z; }; // 隐式按值捕获 x，显式按引用捕获 y
x = 30; // 修改外部的 x
y = 40; // 修改外部的 y
cout << f(5) << endl; // 输出 55，不受外部 x 的影响，受外部 y 的影响

int x = 10;
auto f = [z = x + 5] (int y) -> int { return z + y; }; // 初始化捕获 z，相当于值捕获 x + 5
x = 20; // 修改外部的 x
cout << f(5) << endl; // 输出 20，不受外部 x 的影响
  • parameter list 是参数列表，用于表示 Lambda表达式的参数，没有参数时，可以为空。也可以省略。有参数时和普通函数一样指定参数的类型和名称，例如通过按值（如：(a,b)）和按引用（如：(&a,&b)）两种方式进行传递，还可以在 c++14 中使用 auto 关键字来实现泛型参数。
  • mutable是可修改标示符，按值传递函数对象参数时，加上mutable修饰符后，可以修改按值传递进来的拷贝（注意是能修改拷贝，而不是值本身）。不使用时可以省略。
  • return type 是返回值类型，用于指定 Lambda表达式的返回值类型，可以省略，表示由编译器根据函数体推导，也可以使用 -> 符号显式指定，还可以在 c++14 中使用 auto 关键字来实现泛型返回值。
  • function body 是函数体，用于表示 Lambda表达式的具体逻辑，可以是一条语句，也可以是多条语句，还可以在 c++14 中使用 constexpr 来实现编译期计算。

[!NOTE] 虽然=捕获列表是值传递，但是可以以值的形式传地址，在Lambda函数内部不修改该地址而修改该地址存放的数据以实现修改值

7. 字符大小写转换

  • 字母大写转换
#include <cctype> // 包含 toupper 和 tolower 函数
std::string str = "Hello World!";
// 转换为大写
for (char &c : str) {
	c = std::toupper(c);
}
std::cout << str << std::endl; // 输出: HELLO WORLD!
  • 字母小写转换
// 转换为小写
for (char &c : str) {
	c = std::tolower(c);
}
std::cout << str << std::endl; // 输出: hello world!
  • 字符自动识别转换
#include <cctype>
if (isupper(ch)) { // 如果输入的是大写字母  
        ch = tolower(ch); // 转换为小写字母并输出  
        cout << "转换后的字母为：" << ch << endl;  
} else if (islower(ch)) { // 如果输入的是小写字母  
	ch = toupper(ch); // 转换为大写字母并输出  
	cout << "转换后的字母为：" << ch << endl;  
} else {  
	cout << "输入的不是英文字母。" << endl;  
}
  • 字符串大小写转换
#include <algorithm>
cin>>str;
///转小写
transform(str.begin(),str.end(),str.begin(),::tolower);
cout<<"转化为小写后为："<<str<<endl;
transform(str.begin(),str.end(),str.begin(),::toupper);
cout<<"转化为大写后为："<<str<<endl;
return 0;

8. 字符-数字转换

  • 数字转字符
int num = 1; // 数字1
char ch = num + '0'; // 转换为字符'1'
cout << "转换后的字符是: " << ch << endl; // 输出: 转换后的字符是: 1

//以下方法只能用于整形/长整型转字符数组
int g = 45612;
char j[20];
itoa(g, j, 0);
ltoa(g, j, 0);
  • 字符转数字
char ch = '9';
int n = ch - '0';

//以下方法只能用于字符数组转int/float/long
char cstr[] = "1234.6";
int d = atoi(cstr);
float d = atof(cstr);
long d = atol(cstr);
  • 数字转字符串
string to_string(int val);
string to_string(long val);
string to_string(long long val);
string to_string(unsigned int val);
string to_string(unsigned long val);
string to_string(unsigned long long val);
string to_string(float val);
string to_string(double val);
string to_string(long double val);

string si = to_string(42); // si="42"
string sl = to_string(42L); // sl="42"
string su = to_string(42u); // su="42"
string sd = to_wstring(42.0); // sd="42.000000"
string sld = to_wstring(42.0L); // sld="42.000000"
  • 字符串转数字
int stoi(const string& str, size_t* idx = 0; int base = 10);
long stol(const string& str, size_t* idx = 0, int base = 10);
long long stoll(const string& str, size_t* idx = 0, int base = 10);

auto i1 = std::stoi("42");
auto i2 = std::stoi("101010", nullptr, 2); // i2 = 42
auto i3 = std::stoi("052", nullptr, 8); // i3 = 42
auto i4 = std::stoi("0x2A", nullptr, 16); // i4 = 42
auto f1 = std::stof("123.45");
auto d2 = std::stod("1.2345e+2");
auto ll3 = std::stod("-123456789");
  • toascii（将整型数转换成合法的ASCII 码字符）

#include<ctype.h>

int toascii(int c);

toascii()会将参数c转换成7位的unsigned char值，第八位则会被清除，此字符即会被转成ASCII码字符。返回值将转换成功的ASCI

9. string与const char*

[!NOTE] <string>是C++标准库头文件，包含了拟容器class std::string的声明（不过class string事实上只是basic_string<char>的typedef），用于字符串操作。

  • const char* 转换成string

在C++中存在着从const char*到string的隐式类型转换，换句话说，如果一个函数的参数类型是string类，直接传入const char*类型的参数是没问题的

const char* cstr = "demo";
string str(cstr);
  • string与const char*的转换

在传入参数时，有时我们传入string在编译时是会报错的，所以我们就需要传入const char*类型

我们可以使用成员函数c_str()，来返回string对应的char数组

string str = "demo";
const char* cstr = str.c_str();

并且，在进行文件读写的时候，使用const char* 比使用string更安全。因为，string是会自动分配内存的，其内部的存储方式是不可见的，而const char*类型是整存整取的，或者也可以自己手动存入每一部分

10. CString与const char*

[!NOTE] <cstring>是C标准库头文件<string.h>的C++标准库版本，包含了C风格字符串（NUL即'\0'结尾字符串）相关的一些类型和函数的声明，例如strcmp、strchr、strstr等。

2.1 多字节与宽字节

11. 字符串读取

  • cin>>

用法1：最基本，也是最常用的用法，输入一个数字：

#include <iostream>  
using namespace std;  
int main ()  
{  
	int a,b;  
	cin>>a>>b;  
	cout<<a+b<<endl;  
}
输入：2[回车]3[回车]  
输出：5
注意:>> 是会过滤掉不可见字符（如 空格 回车，TAB 等）

用法2：接受一个字符串，遇“空格”、“TAB”、“回车”都结束
int main ()  
{  
	char a[20];  
	cin>>a;  
	cout<<a<<endl;  
}

输入：jkljkljkl
输出：jkljkljkl

输入：jkljkl jkljkl       //遇空格结束  
输出：jkljkl
  • cin.get()
用法1： cin.get(字符变量名)可以用来接收字符
int main ()  
{  
	char ch;  
	ch=cin.get();               //或者cin.get(ch);  
	cout<<ch<<endl;  
}

输入：jljkljkl  
输出：j

用法2：cin.get(字符数组名,接收字符数目)用来接收一行字符串,可以接收空格
int main ()  
{  
	char a[20];  
	cin.get(a,20);  
	cout<<a<<endl;  
}

输入：jkl jkl jkl  
输出：jkl jkl jkl

输入：abcdeabcdeabcdeabcdeabcde （输入25个字符）  
输出：abcdeabcdeabcdeabcd              （接收19个字符+1个'\0'）
  • cin.getline()  // 接受一个字符串，可以接收空格并输出

int main ()  
{  
	char m[7];  
	cin.getline(m,5);  
	cout<<m<<endl;  
}

输入：jkljkljkl  
输出：jklj
接受5个字符到m中，其中最后一个为'\0'，所以只看到4个字符输出；

如果把5改成7：  
输入：jk jkajk  
输出：jk jkajk

//延伸：  
//cin.getline()实际上有三个参数，cin.getline(接受字符串的变量,接受个数,结束字符)  
//当第三个参数省略时，系统默认为'\0'  
//如果将例子中cin.getline()改为cin.getline(m,5,'a');当输入jk jkajk时输出jk jk
  • getline()     // 接受一个字符串，可以接收空格并输出

#include<string>  
int main ()  
{  
	string str;  
	getline(cin,str);  
	cout<<str<<endl;  
}

输入：jkljkljkl  
输出：jkljkljkl

输入：jkl jfksldfj jklsjfl  
输出：jkl jfksldfj jklsjfl

和cin.getline()类似，但是cin.getline()属于istream流，而getline()属于string流，是不一样的两个函数

12. explicit

  • explicit关键字用于修饰类的构造函数，特别是那些只有一个参数的构造函数。它的目的是要求在对象初始化或赋值时必须显式地使用构造函数，从而避免了编译器自动进行类型转换所可能引发的错误和歧义。

  • 例如，如果一个类有一个接受单个整数参数的构造函数，没有explicit关键字修饰，那么编译器允许使用单个整数值来隐式创建该类的对象。这可能导致代码的可读性降低，因为从代码表面上看不出实际发生了类型转换。

class MyClass {
	public:
		MyClass(int value) : _value(value) {}
	private:
		int _value;
};
MyClass obj = 10; // 隐式转换，没有使用explicit关键字

  • 在上述代码中，_MyClass obj = 10;_这行代码会隐式地调用_MyClass_的构造函数，将整数_10_转换为_MyClass_类型的对象。这种隐式转换可能不是程序员所期望的，尤其是在复杂的程序中，它可能导致难以追踪的错误。

  • 使用explicit关键字：为了避免这种隐式转换，可以在构造函数前加上explicit关键字。这样，编译器就会阻止隐式转换，除非显式地调用构造函数。

class MyClass {
	public:
		explicit MyClass(int value) : _value(value) {}
	private:
		int _value;
};
MyClass obj = 10; // 错误：不能隐式转换
MyClass obj(10); // 正确：显式调用构造函数
  • 在这个例子中，_=explicit关键字确保了MyClass对象的创建必须明确地调用构造函数。这样可以提高代码的清晰度和安全性。

13. 找最大值的索引

auto maxit = max_element(nums.begin() + i, nums.end());
int maxindex = distance(nums.begin(), maxit);

14. 单例模式

  • 单例模式可以分为 懒汉式 和 饿汉式 ，两者之间的区别在于创建实例的时间不同。

  • 懒汉式：系统运行中，实例并不存在，只有当需要使用该实例时，才会去创建并使用实例。这种方式要考虑线程安全。

  • 饿汉式：系统一运行，就初始化创建实例，当需要时，直接调用即可。这种方式本身就线程安全，没有多线程的线程安全问题。

单例类的特点

  • 构造函数和析构函数为私有类型，目的是禁止外部构造和析构。
  • 拷贝构造函数和赋值构造函数是私有类型，目的是禁止外部拷贝和赋值，确保实例的唯一性。
  • 类中有一个获取实例的静态方法，可以全局访问。

懒汉单例(静态局部变量)

//.h
class Single
{
public:
    static Single& GetInstance();// 获取单实例对象
    void Print();// 打印实例地址

private:
    Single()= default;// 禁止外部构造
    ~Single()= default;// 禁止外部析构
    Single(const Single &single) = delete;// 禁止外部拷贝构造
    const Single &operator=(const Single &single) = delete;// 禁止外部赋值操作
};

//.cpp
Single& Single::GetInstance()
{
    /**
     * 局部静态特性的方式实现单实例。
     * 静态局部变量只在当前函数内有效，其他函数无法访问。
     * 静态局部变量只在第一次被调用的时候初始化，也存储在静态存储区，生命周期从第一次被初始化起至程序结束止。
     */
    static Single single;// C++11 保证静态局部变量初始化的线程安全
    return single;
}

void Single::Print()
{
    std::cout << "我的实例内存地址是:" << this << std::endl;
}
Single::Single()
{
    std::cout << "构造函数" << std::endl;
}
Single::~Single()
{
    std::cout << "析构函数" << std::endl;
}

[!NOTE] 现代 C++（C++11 及更高版本）中，静态局部变量的初始化是线程安全的，编译器会自动处理同步问题，确保只有一个线程能初始化该变量。

  • 静态变量的生命周期：instance 的内存从程序启动到结束一直存在。
  • 初始化的唯一性：编译器确保 instance 仅在首次调用时初始化。
  • 线程安全（C++11+）：标准强制要求静态变量初始化的原子性，避免多线程冲突。

饿汉单例(类唯一静态成员变量)

class Single {
public:
    static Single& GetInstance();
private:
    Single() = default;
    ~Single() = default;
    Single(const Single& single) = delete;
    Single& operator=(const Single& single) = delete;
    // 静态成员变量（类加载时初始化）
    static Single instance;
};

//.cpp

Single Single::instance;// 全局初始化实例
Single& Single::GetInstance()
{
    return single;
}
void Single::Print()
{
    std::cout << "我的实例内存地址是:" << this << std::endl;
}

Single::Single()
{
    std::cout << "构造函数" << std::endl;
}
Single::~Single()
{
    std::cout << "析构函数" << std::endl;
}

[!NOTE] 静态成员变量的初始化发生在程序启动阶段（main 函数执行前）。具体时机由编译器和运行时环境决定，但保证在任何代码访问该类之前完成初始化。

  • 由于初始化发生在单线程环境（main 函数启动前），因此天然线程安全，无需加锁。

15. 静态成员

静态成员变量

  • 类的静态成员变量不能类内初始化，但是可以为静态成员提供const整数类型的类内初始值。不过要求静态成员必须是字面值常量类型的constexpr。

  • C++ 要求静态成员变量必须在类外显式定义（除非是 constexpr 常量）。

  • 类的声明只是类型定义，不分配实际内存，静态成员变量需要独立于类的实例存在。

//静态成员变量的声明与定义
static Singleton instance;//仅在类内声明变量，未分配内存。
Singleton Singleton::instance;//在类外定义变量，此时才分配内存并调用构造函数。

静态成员函数

  • 类的静态成员函数可以类内/类外实现

4.2.8 静态成员

16. 模板

函数模板

  • 定义：定义一个通用函数，允许参数或返回值的类型在调用时指定。
  • 语法：使用 template <typename T> 声明，后跟函数定义。
//交换的函数模板
template<typename T>
void mySwap(T &a, T&b)
{
	T temp = a;
	a = b;
	b = temp;
}

template<class T> // 也可以替换成typename
//利用选择排序，进行对数组从大到小的排序
void mySort(T arr[], int len)
{
	for (int i = 0; i < len; i++)
	{
		int max = i; //最大数的下标
		for (int j = i + 1; j < len; j++)
		{
			if (arr[max] < arr[j])
			{
				max = j;
			}
		}
		if (max != i) //如果最大数的下标不是i，交换两者
		{
			mySwap(arr[max], arr[i]);
		}
	}
}
template<typename T>
void printArray(T arr[], int len) {

	for (int i = 0; i < len; i++) {
		cout << arr[i] << " ";
	}
	cout << endl;
}
void test01()
{
	//测试char数组
	char charArr[] = "bdcfeagh";
	int num = sizeof(charArr) / sizeof(char);
	mySort(charArr, num);
	printArray(charArr, num);
}

void test02()
{
	//测试int数组
	int intArr[] = { 7, 5, 8, 1, 3, 9, 2, 4, 6 };
	int num = sizeof(intArr) / sizeof(int);
	mySort(intArr, num);
	printArray(intArr, num);
}

int main() {

	test01();
	test02();

	system("pause");

	return 0;
}

类模板

  • 定义：定义一个通用类，允许成员变量或成员函数的类型在实例化时指定。
  • 语法：使用 template <class T> 声明，后跟类定义。

[!NOTE] 头文件声明的作用，就是让编译器知道，这个函数的定义应该在其他文件中，就不会因为暂时找不到函数的定义而报错。至于找到对应的定义，就是链接器需要干的事情。

//.h文件
#pragma once
#include <iostream>
using namespace std;

template <class T>
class MyClass {
public:
    MyClass();
    MyClass(const T& val);
    void func(T a, T b);
    T value;
};

//.cpp文件
#include"SingleTon.h"
template<class T>
MyClass<T>::MyClass(){}

template <class T>
MyClass<T>::MyClass(const T&val):value(val) {}

template <class T>
void MyClass<T>::func(T a, T b)
{
	T temp = a;
	a = b;
	b = temp;
}

//main.cpp文件
#include "SingleTon.h"
int main()
{
	MyClass<int> myclass;
	myclass.func(10, 20);
	return 0;
}

  • SingleToncpp编译时，编译器没有看到任何具体的实例化类型（如 SingleTon<int>），因此不会生成 func() 函数的实际代码。

  • 模板代码（如 template <typename T> void MyClass<T>::func()）本身不会被编译成目标代码，只是 “蓝图”。

  • 链接阶段就会报错：main.cpp 中使用了 MyClass<int>::func()，但 SingleTon.o 中没有该函数的实现，导致链接器无法找到符号定义。

  • 所以写在同一个hpp文件中，就不存在上述问题了

//myclass.hpp
#pragma once
#include <iostream>
using namespace std;

template <class T>
class MyClass {
public:
    MyClass();
    MyClass(const T& val);
    void func(T a, T b);
    T value;
};

template<class T>
MyClass<T>::MyClass() {}

template <class T>
MyClass<T>::MyClass(const T& val) :value(val) {}

template <class T>
void MyClass<T>::func(T a, T b)
{
    T temp = a;
    a = b;
    b = temp;
}

//main.cpp
#include "myclass.hpp"
int main()
{
	MyClass<int> myclass;
	myclass.func(10, 20);
	return 0;
}

对比

  • 函数模板是为了实现与类型无关的通用函数，依赖调用时的类型推导；

  • 类模板是为了创建通用的类结构，需在实例化时显式指定类型参数。

  • 函数模板不能部分特化：函数模板只能全特化（如 template<> void swap<int>(int&, int&)），但类模板可以偏特化（如 template<typename T> class Vector<T*>）。

    • 全特化（Full Specialization）：为模板的所有模板参数指定具体类型，形成一个完全确定的版本。
    • 偏特化（Partial Specialization）：为模板的部分模板参数指定具体类型，保留其他参数作为模板参数（即 “部分特化，部分泛化”）。
    • C++ 标准明确禁止函数模板的偏特化，原因是 函数重载（Function Overloading）可以完美替代偏特化的需求，无需额外引入偏特化机制。
    • 类模板没有 “重载” 机制，因此需要偏特化来针对部分类型定制逻辑。偏特化的类模板与通用模板是不同的类，但共享模板名称。

  • 类模板实例化必须显式指定类型：函数调用可以自动推导类型，但类实例化必须显式指定（如 Vector<int>），除非使用 C++17 的类模板参数推导（如 std::pair p(1, "hello");）。

特性函数模板类模板
实例化触发方式函数调用时自动推导或显式指定必须显式指定模板参数（如 Vector<int>）
类型推导支持自动类型推导（如 max(1, 2)）不支持自动推导，需显式指定类型
特化（Specialization）支持全特化（如 template<> int max<int>(int, int)）支持全特化和偏特化（如 template<typename T> class Vector<T*>）
默认模板参数C++11 起支持（如 template<typename T = int>）支持，且更常见（如 template<typename T = int> class Stack）
用途通用算法（如 std::sort、std::swap）容器类（如 std::vector、std::map）、工具类

17. STL汇总

string

  • 构造
    • string(); //创建一个空的字符串 例如: string str;
    • string(const char* s); //使用字符串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 &s, int pos, int n);//字符串s中从pos开始的n个字符连接到字符串结尾
  • 查找替换
    • 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
  • 字符串比较
    • int compare(const string &s) const; //与字符串s比较
    • int compare(const char *s) const; //与字符串s比较
  • 字符存取
    • char& operator[](int n); //通过[]方式取字符
    • char& at(int n); //通过at方法获取字符
  • 插入删除
    • 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个字符组成的字符串

vector

  • 构造
    • vector<T> v; //采用模板实现类实现，默认构造函数
    • vector(v.begin(), v.end()); //将v[begin(), 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);//重新指定容器的长度为num，若容器变长，则以默认值填充新位置。如果容器变短，则末尾超出容器长度的元素被删除。这里改变的是size，不是capacity
    • resize(int num, elem); //重新指定容器的长度为num，若容器变长，则以elem值填充新位置。如果容器变短，则末尾超出容器长度的元素被删除
  • 插入和删除
    • push_back(ele); //尾部插入元素ele
    • pop_back(); //删除最后一个元素
    • insert(const_iterator pos, ele); //迭代器指向位置pos插入元素ele
    • insert(const_iterator pos, int count,ele);//迭代器指向位置pos插入count个元素ele
    • erase(const_iterator pos); //删除迭代器指向的元素
    • erase(const_iterator start, const_iterator end);//删除迭代器从start到end之间的元素
    • clear(); //删除容器中所有元素
  • 数据存取
    • at(int idx); //返回索引idx所指的数据
    • operator[]; //返回索引idx所指的数据
    • front(); //返回容器中第一个数据元素
    • back(); //返回容器中最后一个数据元素
  • 互换容器
    • swap(vec); // 将vec与本身的元素互换，swap可以使两个容器互换，可以达到实用的收缩内存效果
  • 预留空间
    • reserve(int len);//容器预留len个元素长度，预留位置不初始化，元素不可访问。减少vector在动态扩展容量时的扩展次数

deque

  • 构造
    • deque<T> deqT; //默认构造形式
    • deque(beg, end); //构造函数将[beg, end)区间中的元素拷贝给本身。
    • deque(n, elem); //构造函数将n个elem拷贝给本身。
    • deque(const deque &deq); //拷贝构造函数
  • 赋值
    • deque& operator=(const deque &deq);//重载等号操作符
    • assign(beg, end);//将[beg, end)区间中的数据拷贝赋值给本身。
    • assign(n, elem); //将n个elem拷贝赋值给本身。
  • 大小操作
    • deque.empty(); //判断容器是否为空
    • deque.size(); //返回容器中元素的个数
    • deque.resize(num); //重新指定容器的长度为num,若容器变长，则以默认值填充新位置。如果容器变短，则末尾超出容器长度的元素被删除。
    • deque.resize(num, elem); //重新指定容器的长度为num,若容器变长，则以elem值填充新位置。如果容器变短，则末尾超出容器长度的元素被删除。
  • 插入和删除 两端插入操作：
    • push_back(elem); //在容器尾部添加一个数据
    • push_front(elem); //在容器头部插入一个数据
    • pop_back(); //删除容器最后一个数据
    • pop_front(); //删除容器第一个数据 指定位置操作：
    • insert(pos,elem); //在pos位置插入一个elem元素的拷贝，返回新数据的位置。
    • insert(pos,n,elem); //在pos位置插入n个elem数据，无返回值。
    • insert(pos,beg,end); //在pos位置插入[beg,end)区间的数据，无返回值。
    • clear(); //清空容器的所有数据
    • erase(beg,end); //删除[beg,end)区间的数据，返回下一个数据的位置。
    • erase(pos); //删除pos位置的数据，返回下一个数据的位置。
  • 数据存取
    • at(int idx); //返回索引idx所指的数据
    • operator[]; //返回索引idx所指的数据
    • front(); //返回容器中第一个数据元素
    • back(); //返回容器中最后一个数据元素

stack

  • 构造
    • stack<T> stk; //stack采用模板类实现， stack对象的默认构造形式
    • stack(const stack &stk); //拷贝构造函数
  • 赋值
    • stack& operator=(const stack &stk); //重载等号操作符
  • 数据存取：
    • push(elem); //向栈顶添加元素
    • pop(); //从栈顶移除第一个元素
    • top(); //返回栈顶元素
  • 大小操作：
    • empty(); //判断堆栈是否为空
    • size(); //返回栈的大小

queue

  • 构造
    • queue<T> que;//queue采用模板类实现，queue对象的默认构造形式
    • queue(const queue &que);//拷贝构造函数
  • 赋值
    • queue& operator=(const queue &que);//重载等号操作符
  • 数据存取
    • push(elem); //往队尾添加元素
    • pop(); //从队头移除第一个元素
    • back(); //返回最后一个元素
    • front(); //返回第一个元素
  • 大小操作：
    • empty(); //判断堆栈是否为空
    • size(); //返回栈的大小

list

  • 构造
    • list<T> lst; //list采用采用模板类实现,对象的默认构造形式：
    • list(beg,end); //构造函数将[beg, end)区间中的元素拷贝给本身。
    • list(n,elem);//构造函数将n个elem拷贝给本身。
    • list(const list &lst);//拷贝构造函数。
  • 赋值
    • assign(beg, end); //将[beg, end)区间中的数据拷贝赋值给本身。
    • assign(n, elem); //将n个elem拷贝赋值给本身。
    • list& operator=(const list &lst); //重载等号操作符
  • 交换
    • swap(lst);//将lst与本身的元素互换。L1.swap(L2);
  • 大小操作
    • size();//返回容器中元素的个数
    • empty();//判断容器是否为空
    • resize(num);//重新指定容器的长度为num，若容器变长，则以默认值填充新位置。如果容器变短，则末尾超出容器长度的元素被删除。
    • resize(num, elem);//重新指定容器的长度为num，若容器变长，则以elem值填充新位置。如果容器变短，则末尾超出容器长度的元素被删除。
  • 插入和删除
    • push_back(elem);//在容器尾部加入一个元素
    • pop_back();//删除容器中最后一个元素
    • push_front(elem);//在容器开头插入一个元素
    • pop_front();//从容器开头移除第一个元素
    • insert(pos,elem);//在pos位置插elem元素的拷贝，返回新数据的位置。
    • insert(pos,n,elem);//在pos位置插入n个elem数据，无返回值。
    • insert(pos,beg,end);//在pos位置插入[beg,end)区间的数据，无返回值。
    • clear();//移除容器的所有数据
    • erase(beg,end);//删除[beg,end)区间的数据，返回下一个数据的位置。
    • erase(pos);//删除pos位置的数据，返回下一个数据的位置。
    • remove(elem);//删除容器中所有与elem值匹配的元素。
  • 数据存取
    • front(); //返回第一个元素。
    • back(); //返回最后一个元素。
  • 反转和排序
    • reverse(); //反转链表 L.reverse();
    • sort(); //链表排序 L.sort(myCompare); //指定规则，从大到小

set/multiset

  • 构造
    • set<T> st; //默认构造函数：
    • set(const set &st); //拷贝构造函数
  • 赋值
    • set& operator=(const set &st); //重载等号操作符
  • 大小操作
    • size(); //返回容器中元素的数目
    • empty(); //判断容器是否为空
  • 交换
    • swap(st); //交换两个集合容器 s1.swap(s2);
  • 插入和删除
    • insert(elem); //在容器中插入元素。
    • clear(); //清除所有元素
    • erase(pos); //删除pos迭代器所指的元素，返回下一个元素的迭代器。
    • erase(beg, end); //删除区间[beg,end)的所有元素 ，返回下一个元素的迭代器。
    • erase(elem); //删除容器中值为elem的元素。
  • 查找和统计
    • find(key);//查找key是否存在,若存在，返回该键的元素的迭代器；若不存在，返回set.end();
    • count(key);//统计key的元素个数

pair

  • 构造
    • pair<type, type> p ( value1, value2 );
    • pair<type, type> p = make_pair( value1, value2 );

map/multimap

构造 - map<T1, T2> mp; //map默认构造函数: - map(const map &mp); //拷贝构造函数 赋值 - map& operator=(const map &mp); //重载等号操作符

  • 大小操作
    • size(); //返回容器中元素的数目
    • empty(); //判断容器是否为空
  • 交换
    • swap(st); //交换两个集合容器
  • 插入和删除
    • insert(elem); //在容器中插入元素。
    • clear(); //清除所有元素
    • erase(pos); //删除pos迭代器所指的元素，返回下一个元素的迭代器。
    • erase(beg, end); //删除区间[beg,end)的所有元素 ，返回下一个元素的迭代器。
    • erase(key); //删除容器中值为key的元素。
  • 查找和统计
    • find(key);//查找key是否存在,若存在，返回该键的元素的迭代器；若不存在，返回set.end();
    • count(key);//统计key的元素个数

内建函数对象

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

遍历

  • for_each(iterator beg, iterator end, _func); // 遍历算法 遍历容器元素 // beg 开始迭代器 // end 结束迭代器 // _func 函数或者函数对象
void MyPrint(int val)
{
	cout << val << endl;
}
for_each(v.begin(), v.end(), MyPrint);

搬运

  • transform(iterator beg1, iterator end1, iterator beg2, _func); //beg1 源容器开始迭代器 //end1 源容器结束迭代器 //beg2 目标容器开始迭代器 //_func 函数或者函数对象

查找统计

  • find(iterator beg, iterator end, value);//按值查找元素，找到返回指定位置迭代器，找不到返回结束迭代器位置 // beg 开始迭代器 end 结束迭代器value 查找的元素 利用find可以在容器中找指定的元素，返回值是迭代器
  • find_if(iterator beg, iterator end, _Pred); // 按值查找元素，找到返回指定位置迭代器，找不到返回结束迭代器位置 // beg 开始迭代器 // end 结束迭代器 // _Pred 函数或者谓词（返回bool类型的仿函数） find_if按条件查找使查找更加灵活，提供的仿函数可以改变不同的策略
  • adjacent_find(iterator beg, iterator end); // 查找相邻重复元素,返回相邻元素的第一个位置的迭代器 // beg 开始迭代器 // end 结束迭代器 面试题中如果出现查找相邻重复元素，记得用STL中的adjacent_find算法
  • bool binary_search(iterator beg, iterator end, value); // 查找指定的元素，查到 返回true 否则false // 注意: 在无序序列中不可用 // beg 开始迭代器 // end 结束迭代器 // value 查找的元素 二分查找法查找效率很高，值得注意的是查找的容器中元素必须的有序序列
  • count(iterator beg, iterator end, value); // 统计元素出现次数 // beg 开始迭代器 // end 结束迭代器 // value 统计的元素 统计自定义数据类型时候，需要配合重载 operator==
  • count_if(iterator beg, iterator end, _Pred); // 按条件统计元素出现次数 // beg 开始迭代器 // end 结束迭代器 // _Pred 谓词 按值统计用count，按条件统计用count_if

排序

  • sort(iterator beg, iterator end, _Pred); // 按值查找元素，找到返回指定位置迭代器，找不到返回结束迭代器位置 // beg 开始迭代器 // end 结束迭代器 // _Pred 谓词
  • random_shuffle(iterator beg, iterator end); // 指定范围内的元素随机调整次序 // beg 开始迭代器 // end 结束迭代器 random_shuffle洗牌算法比较实用，使用时记得加随机数种子
  • merge(iterator beg1, iterator end1, iterator beg2, iterator end2, iterator dest); // 容器元素合并，并存储到另一容器中 // 注意: 两个容器必须是有序的 // beg1 容器1开始迭代器 // end1 容器1结束迭代器 // beg2 容器2开始迭代器 // end2 容器2结束迭代器 // dest 目标容器开始迭代器 merge合并的两个容器必须的有序序列
  • reverse(iterator beg, iterator end); // 反转指定范围的元素 // beg 开始迭代器 // end 结束迭代器

拷贝

  • copy(iterator beg, iterator end, iterator dest); // 按值查找元素，找到返回指定位置迭代器，找不到返回结束迭代器位置 // beg 开始迭代器 // end 结束迭代器 // dest 目标起始迭代器 利用copy算法在拷贝时，目标容器记得提前开辟空间

替换

  • replace(iterator beg, iterator end, oldvalue, newvalue); // 将区间内旧元素 替换成 新元素 // beg 开始迭代器 // end 结束迭代器 // oldvalue 旧元素 // newvalue 新元素
  • replace_if(iterator beg, iterator end, _pred, newvalue); // 按条件替换元素，满足条件的替换成指定元素 // beg 开始迭代器 // end 结束迭代器 // _pred 谓词 // newvalue 替换的新元素

交换

  • swap(container c1, container c2); // 互换两个容器的元素 // c1容器1 // c2容器2 swap交换容器时，注意交换的容器要同种类型

算术

  • accumulate(iterator beg, iterator end, value); // 计算容器元素累计总和 // beg 开始迭代器 // end 结束迭代器 // value 起始值

填充

  • fill(iterator beg, iterator end, value); // 向容器中填充元素 // beg 开始迭代器 // end 结束迭代器 // value 填充的值

集合

  • set_intersection(iterator beg1, iterator end1, iterator beg2, iterator end2, iterator dest); // 求两个集合的交集 // 注意:两个集合必须是有序序列 // beg1 容器1开始迭代器 // end1 容器1结束迭代器 // beg2 容器2开始迭代器 // end2 容器2结束迭代器 // dest 目标容器开始迭代器 求交集的两个集合必须的有序序列 目标容器开辟空间需要从两个容器中取小值 set_intersection返回值即是交集中最后一个元素的位置
  • set_union(iterator beg1, iterator end1, iterator beg2, iterator end2, iterator dest); // 求两个集合的并集 // 注意:两个集合必须是有序序列 // beg1 容器1开始迭代器 // end1 容器1结束迭代器 // beg2 容器2开始迭代器 // end2 容器2结束迭代器 // dest 目标容器开始迭代器 求并集的两个集合必须的有序序列 目标容器开辟空间需要两个容器相加 set_union返回值既是并集中最后一个元素的位置
  • set_difference(iterator beg1, iterator end1, iterator beg2, iterator end2, iterator dest); // 求两个集合的差集 // 注意:两个集合必须是有序序列 // beg1 容器1开始迭代器 // end1 容器1结束迭代器 // beg2 容器2开始迭代器 // end2 容器2结束迭代器 // dest 目标容器开始迭代器 求差集的两个集合必须的有序序列 目标容器开辟空间需要从两个容器取较大值 set_difference返回值既是差集中最后一个元素的位置

18. C++的Map

Tree与Map

  • 树结构的核心是 “层级嵌套的节点”，每个节点通常存储一个值
  • Map 的核心是 “键值对（KV）映射”，通过键快速查找值。
  • 普通的树结构（如二叉树）只能按 “节点值” 排序，普通的 Map（如哈希表）虽然查询快，但键是无序的。

Tree与Map结合

  • “树节点” 不再只存一个值，而是 存储一个键值对（Key + Value）；
  • 树的排序规则基于 “键（Key）”，而非值（Value）—— 左子树的所有节点的键 < 根节点的键，右子树的所有节点的键 > 根节点的键（二叉搜索树的特性）。
  • 由于树的有序性，Map 可以直接支持 “按键排序” 的操作（如获取键的升序 / 降序集合、查找大于 / 小于某个键的所有键值对）。
  • 平衡树保证效率：用红黑树等平衡二叉树避免了普通二叉树可能退化为链表的问题，插入、查询、删除的时间复杂度稳定在 O (log n)。
//节点结构
class Node {
    Key key;    // 键（用于排序和查找）
    Value value; // 值（实际要存储的数据）
    Node left;  // 左子节点（键 < 当前节点的键）
    Node right; // 右子节点（键 > 当前节点的键）
    // 其他辅助字段（如红黑树的颜色标记）
}

600

Map

  • STL中的Map：红黑树

  • map是一个有序的容器，它按照键的升序进行排序并存储元素。每个键唯一且不可重复，同时与一个值关联。

  • map的底层实现采用红黑树（Red-Black Tree），这是一种自平衡二叉搜索树。红黑树保持了良好的平衡性能，确保了在任何情况下对map进行插入、删除和查找操作的时间复杂度为O(logN)，其中N是元素的数量。

  • 由于红黑树的平衡特性，map适用于需要频繁查找键值对的场景。map适合在元素有序存储和访问的情况下使用，特别是当需要根据键值进行快速查找时。例如，可以使用map来实现字典、索引表、排行榜等数据结构。

unordered_map

  • STL的unordered_map容器是一个哈希表（Hash Table）实现的关联容器，它提供了高效的插入、删除和查找操作。

  • 哈希映射：unordered_map内部使用哈希函数将键映射到存储桶（bucket）中，以实现快速的查找操作。由于哈希函数的作用，元素在容器中的存储位置是根据键的哈希值决定的，而不是按照键的顺序。

  • 快速的插入和查找：unordered_map具有接近常数时间（平均情况下）的插入、删除和查找操作。通过哈希映射和O(1)的平均时间复杂度，可以实现高效的元素访问。

  • 无序性：unordered_map中的元素没有固定的顺序，与插入的顺序无关。这种无序性使得unordered_map适用于不需要保持元素顺序的需求，例如字典、索引等。

  • 唯一键：每个键在unordered_map中是唯一的，即同一个键只能插入一个值。

  • 冲突解决：当多个元素被映射到同一个存储桶时，会发生哈希冲突。unordered_map使用链地址法（chaining）来处理冲突，即在同一个存储桶中通过链表或者其他数据结构将冲突的元素链接起来。

Set和unordered_set

  • set 是一个关联型容器，和 map 一样，它的底层结构是红黑树，但和 map 不一样的是，set 是直接保存 value 的，或者说，set 中的 value 就是 key。unordered_set同理类比unordered_map

如何选择

  • 选择map还是unordered_map取决于对有序性、插入和删除操作频率以及内存占用的需求。如果需要元素有序并且较少的插入/删除操作，可以选择map；如果对有序性不敏感并且需要高效的插入/删除操作，可以选择unordered_map。

  1. 查找操作的需求：如果你更关注元素的有序性，并且需要根据键进行快速的查找操作，那么应该选择map。map中的元素按键的顺序进行排序，因此可以使用二分查找等算法来高效地查找元素。

  2. 插入和删除操作的频率：如果你需要频繁地插入和删除元素，并且对于查找操作的顺序不敏感，那么应该选择unordered_map。unordered_map使用散列表作为底层数据结构，插入和删除操作的时间复杂度通常是常数级别的，而不会受到键的顺序影响。

  3. 内存占用的考虑：由于unordered_map使用散列表，它往往需要比map更多的内存空间来存储散列桶和链表或其他解决冲突的数据结构。如果内存占用是一个重要的考虑因素，可能需要权衡使用unordered_map所带来的额外内存消耗。

  4. 键的哈希函数和相等比较：在使用unordered_map时，需要确保键类型具有良好的哈希函数和相等比较操作符。如果键类型不提供这些操作，或者它们的性能较低，可能需要手动提供自定义的哈希函数和相等比较操作符。

注意事项

  • static_cast<>

  • inline

  • 类的构造函数加冒号后面可以初始化成员变量也可以初始化父类。 类中包含以下成员，必须放在初始化列表位置进行初始化：

  1. 引用成员变量
  2. const成员变量
  3. 自定义类型成员(该类没有默认构造函数)
for (auto& t : threads) {
	t.join();
}

移动语义 右值引用

左值引用，右值引用，万能引用 完美转发 hpp文件Qt中好像用到了

可移动对象 for each