C++(1·指针作用、循环体指令、堆栈、优先队列、堆排序算法、右值引用)

发表于 2025/03/03 更新于 2025/05/05

作者 senlongan

15 分钟阅读

为什么使用指针？

高效传递对象（指针只是存储对象的内存地址，通常只需要4/8字节的空间，可以避免大数据拷贝，提高性能）
防止拷贝，和引用相同的作用

class A {
    A a;//❌ 错误: 类的定义中不能直接包含同类对象，递归下去，编译器无法计算出 A 类的大小
	A* a;//✅ 正确
	A& a;//✅ 正确
};

展开

实现数据结构和算法，实现时经常会遇到上述情况，我们只能通过指针/引用实现
多态的动态绑定需要指针
动态分配内存需要指针，

注：

动态内存：用户数据大小不确定，需要用指针在堆中动态分配内存
为什么需要指针实现, 指针只是指向一个地址，可以轻松动态的修改地址，而指向不同大小的内存

break . continue

break: 退出本次循环，继续循环外的指令

continue: 跳过本次循环体中剩余的语句，继续执行下一次循环的循环体

堆栈

堆：队头做删除操作,在队尾做插入操作

栈：仅能在栈顶进行插入和删除操作，把另一端称为栈底

priority_queue

定义：

元素根据其优先级大小有序排列，优先级高的元素会优先出队，而不是像普通队列那样遵循先进先出（FIFO）原则

优先队列也称为堆heap（底层存储结构用数组实现的），分为大顶堆和小顶堆，堆的本质是完全二叉树（逻辑结构）

完全二叉树：除最后一层外，其他层的结点个数全部达到最大值，且最后一层的结点从左侧填充
满二叉树：满二叉树是一种特殊的的完全二叉树，所有层的结点个数都是最大值

索引：

父节点索引i：左孩子:2 * i + 1, 右孩子:2 * i + 2
左/右节点i：父节点：(i-1)/2

大顶堆和小顶堆

大顶堆：arr(i)>arr(2 * i+1) && arr(i)>arr(2*i+2),每个结点的值都大于其左孩子和右孩子结点的值

小顶堆：arr(i)< arr(2 * i+1) && arr(i)< arr(2*i+2),每个结点的值都小于其左孩子和右孩子结点的值

比较函数：

c++提供了两个内置比较函数：less->构造大根堆->降序（默认），greater->构造小根堆->升序

这可能有点反直觉，是因为优先队列是优先级高的在队首，less通过a< b，也就是a的优先级更小，所以更小的排在后面

注意：

优先队列构造的堆是非线性递增/减的，但是堆顶一定是最大/小的那个，在每次取出后，堆都会重新排序，从而保证每次取出的都是优先级最高的，即最大/小的元素

堆算法：

堆排序算法，是利用堆这种数据结构所设计的一种排序算法，实现对无序序列以升/降排序，时间复杂度O(N*logN), 空间复杂度O(1)，是一个不稳定性的排序

下面的实例：大顶堆：堆构造，堆排序，堆插入，堆删除

void SiftUp(int* arr, int i) {// 上浮过程
    while (i > 0) {
        int parent = (i - 1) / 2;
        if (arr[i] > arr[parent]) {
            swap(arr[i], arr[parent]);
            i = parent;
        } else {
            break;
        }
    }
}
void SiftDown(int* arr, int start, int end)//下沉：让根节点在[start,end]区间下沉到合适的位置
{
	int tmp = arr[start];//存储下根节点的值
	//当左右孩子的最大值>根，就将根节点下沉为它，此节点上浮（sift up）到根节点位置
	//知道某次根找到了下沉的位置，或者到了叶节点
	for (int i = 2 * start + 1; i <= end; i = i * 2 + 1)
	{
		if (i < end && arr[i] < arr[i + 1])//找到左右孩子最大值
		{
			i++;
		}
        //底层元素提升：当左右孩子的最大值>根
		if (arr[i] > tmp)
		{
			arr[start] = arr[i];//此节点上浮到根节点位置
			start = i;//根节点下沉为它
		}
        //根找到了下沉的位置
		else
		{
			break;
		}
	}
	arr[start] = tmp;//此位置更新为根节点的值
}
void HeapConstruction(int* arr, int len){//堆构造
	//从最后一个元素的父节点开始到最后元素结束的区间，每次区间起点左移逐渐增大区间，直到根节点0为止，
	//这样可以保证当对以i为根的树调整时，子树是有序的
	for(int i=((len-1)-1)/2;i>=0;i--)//自底向上
	{
		SiftDown(arr, i, len - 1);
	}
}
void HeapSort(int* arr, int len)//堆排序：返回升序序列
{
	//初次构造大顶堆
	HeapConstruction(arr, len);//构造完成后我们就可以获取到所有元素中的最大元素
	//排序
	int tmp;
	//每次将当前的根与index位置（从最后一位开始，index--）置换，然后对index前的部分下沉调整，以便找到下一次的最大元素
	//也就是将每次的最大元素，从后往前依次放到数组中
	for (int i = 0; i < len - 1; i++)
	{
		tmp = arr[0];
		arr[0] = arr[len - 1-i];//交换
		arr[len - 1 - i] = tmp;//交换
		SiftDown(arr, 0, len - 1-i- 1);//对index前的部分下沉调整
	}
}
// 堆的插入操作
void HeapInsert(int* arr, int& len, int value) {
    arr[len] = value;  // 将新元素放在堆的末尾
    int i = len;       // 当前节点位置
    len++;             // 堆大小增加
	SiftUp(arr, i);    //i上浮
}
// 删除堆顶元素
void HeapDelete(int* arr, int& len) {
    if (len == 0) {
        throw "Heap is empty";
    }
    int maxValue = arr[0];     // 保存堆顶元素
    arr[0] = arr[len - 1];     // 将最后一个元素移到堆顶
    len--;                     // 堆大小减小
    SiftDown(arr, 0 , len - 1);// 下沉过程
}

展开

左值，右值，左值引用，右值引用

定义

左值是对象，有内存地址，有变量名，有值，表达式结束后不会被销毁
右值是临时对象，无内存地址，无变量名，有值，表达式结束后会销毁
非常量左值：形如：数据类型 + 变量名;
常量左值：形如： const + 数据类型 + 变量名;
非常量右值：形如：数据类型 + 变量名 = x; //这里的x
常量右值：形如： int a,b; (a + b); //这里的 a + b
对非常量的左值引用：可以绑定非常量左值
对常量的左值引用：可以绑定非常量左值、常量左值、非常量右值、常量右值
对非常量的右值引用：可以绑定非常量右值
对常量的右值引用：可以绑定非常量右值、常量右值

对于常量左值引用可以绑定到右值，但右值引用不能绑定任何类型的左值，

std::move()

可以将左值强制转换为右值，从而左值可以被右值引用绑定，这个被转换的左值中的数据将为无效的，不要轻易使用

std::ref() std cref()

引用包装器std::ref能使用reference_wrapper包装代替原本会被识别的值类型，防止拷贝，但它不能使被包装的对象变成引用

对于万能引用，虽然模板参数会推导为引用类型，但是参数仍然会发生拷贝（即使实参是引用类型）

比如bind / thread ，如果关联的函数带有引用的形参，我们应该向万能引用参数传递引用，需要用ref / cref 包装

右值引用作用：

//移动构造
MyString(MyString&& str) { 
    _len = str._len; 
    _data = str._data; 
    str._len = 0; 
    str._data = NULL;   // ! 防止在析构函数中将内存释放掉
}
//移动赋值
MyString& operator=(MyString&& str) { 
    if (this != &str) { 
        _len = str._len; 
        _data = str._data; 
        str._len = 0; 
        str._data = NULL;  // ! 防止在析构函数中将内存释放掉
    } 
    return *this; 
}

展开

转移语义：当用一个对象初始化另一个对象 / 为另一个对象赋值时，需要将对象内存的数据拷贝到新内存中，但是当我们并非关心原对象（把作为临时对象）时，我们使用右值引用，将会直接将临时对象内存的数据移动到新内存中，然后释放临时对象内存，这样仅仅发生转移数据而非拷贝数据，减少了内存并增加了运行效率
注意：把a中数据转移给对象b时，由于它们的指针都指向了同一块内存，在销毁a时调用析构，会释放掉绑定的内存，那样b获得的这块内存中的数据就不存在了，因此，我们应在移动函数内部，将右值引用的数据指针指向空，防止意外清理掉内存数据

template<typename T>
void forwardPrint(T&& arg) {
    print(std::forward<T>(arg));
}

展开

完美转发：当我们编写一个函数模板确保这些参数的原始属性（左值或右值）能够被正确传递
- 引用折叠：
  - type& & 折叠为 type&
  - type& && 折叠为 type&
  - type&& & 折叠为 type&
  - type&& && 折叠为 type&&
- 使用万能引用（T&&） 作为函数模板的参数时，编译器会根据传入的实参是左值还是右值来推导 T 的类型，可以完美保留它的性质
- std::forward依赖于引用折叠规则，根据模板参数 T 的推导结果，将参数转换为合适的左值或右值引用
含有不能共享资源的类对象：像IO、unique_ptr……

模板参数类型推断

template<typename T>//模板参数类型
void f(ParamType param);//函数参数类型
f(expr);//实参

展开

在编译阶段使用expr来推断ParamType和T这两个类型

ParamType 是一个指针或者引用
1. 忽略expr与ParamType共有的部分，expr剩余的部分作为T
ParamType 是右值引用
1. expr的类型为左值，T为expr的类型 + 左值引用，根据引用折叠规则，确定ParamType的类型, 也是左值引用
2. 忽略expr与ParamType共有的部分，expr剩余的部分作为T，不会引用折叠，ParamType的类型也是右值引用
ParamType 是普通变量
1. T为expr忽略引用，const，volatile…，剩余的部分作为T
expr 是数组
1. T为 const type *

C++

本文由作者按照 CC BY 4.0 进行授权