https://cdn.jsdelivr.net/gh/caibingcheng/resources@main/images/2B2pd1.png

BBing's Blog

自由 分享 合作

不同分支存储不同内容

本站结构

根目录下是hugo框架仓库, 使用了master分支, 同时还使用了以下子仓库:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
[submodule "themes/LoveIt"]
	path = themes/LoveIt
	url = https://github.com/dillonzq/LoveIt.git
[submodule "content"]
	path = content
	url = https://github.com/***********/blog.git
	branch = content
[submodule "live2d"]
	path = static/live2d
	url = https://github.com/***********/blog.git
	branch = live2d

注意到content和live2d其实和hugo框架在同一个仓库, 但是使用的是不同的分支.


为什么推荐加const或constexpr修饰常量

const/constexpr修饰常量可以减少内存占用和拷贝操作.

这是我们在很多书上可以看到的结论, 但是为什么用const/constexpr修饰常量可以减少内存占用和拷贝操作呢?

测试

不使用const/constexpr修饰

我们先来看一个反例, 不使用const/constexpr修饰常量:

1
2
3
4
5
6
7
8
9
using namespace std;

int num = 10;

int main()
{
    int get_num = num;
    return 1;
}

什么是迭代器

问题

先来看一段代码:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <iostream>
#include <algorithm>

using namespace std;

#define ARRAY_SIZE(array) sizeof(array) / sizeof(array[0])

int main()
{
    int nums[] = {1, 2, 3, 4};

    auto print_nums = [] (auto& n) {
        cout << n << endl;
    };

    auto process_nums = [] (auto& n) {
        //do more process here
        n *= n;
    };

    for_each(nums, nums + ARRAY_SIZE(nums), process_nums);
    for_each(nums, nums + ARRAY_SIZE(nums), print_nums);
}

数组名不是指针

问题

先来看一个问题:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
#include <iostream>

using namespace std;

#define ARRAY_SIZE(array) (sizeof((array)) / sizeof((array)[0]))

int main()
{
    int num_array[] = {1, 2, 3};
    int* num = num_array;

    cout << sizeof(num_array) << endl;
    cout << ARRAY_SIZE(num_array) << endl;

    return 1;
}

上面的代码输出是多少?


数据结构与算法之跳表

一维链表

https://cdn.jsdelivr.net/gh/caibingcheng/resources@main/images/3rrOfK.png
一维链表

链表不需要一块很大的连续的存储空间是其优点, 但是对一串有序序列, 使用一维链表查询的时间复杂度是$O(n)$, 能否如查找二叉树之类, 将其查找时间复杂度降为$O(logn)$呢?

一种常用的方法是升维. 升维也是一种空间换时间的思考方式, 会提高数据结构的空间复杂度, 但是可以降低一些操作的时间复杂度.


数据结构与算法之堆

堆的结构

同二叉查找树类似, 堆也是一种特殊的二叉树:

  • 堆是一颗完全二叉树;
  • 堆的孩子结点小于或者大于父结点;

所以, 堆可以像一颗完全二叉树一样, 很自然地可以使用顺序存储; 区别于二叉查找树, 堆的孩子结点是都小于或者大于父结点.

一般地, 堆划分为小顶堆和大顶堆:

  • 父结点小于孩子结点的堆叫做小顶堆;
  • 父结点大于孩子结点的堆叫做大顶堆;