https://s3.ax1x.com/2021/01/21/s4crsU.png

BBing's Blog

什么是迭代器

问题

先来看一段代码:

 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;
}

上面的代码输出是多少?

为什么推荐加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;
}

数据结构与算法之跳表

一维链表

https://s3.ax1x.com/2021/03/01/6Pczfs.png
一维链表

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

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

数据结构与算法之堆

堆的结构

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

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

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

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

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

C++闭包

C++闭包

在一些现代对高级语言, 比如Python或者JavaScript中, 经常会提到闭包的概念, 但是在C++里面很少会听说闭包的概念.

C++可以实现闭包吗? 可以.

闭包函数: 可以理解为函数里面定义的函数;

闭包: 可以理解为闭包函数可以访问到外层函数的变量, 即使外层函数已经返回.

数据结构与算法之2-3-4树

平衡树

https://s3.ax1x.com/2021/01/29/yi2tDs.png
不太平衡的二叉树

对于一个普通的二叉查找树, 我们可以发现一个问题, 存在一定的可能性, 一般的二叉查找树会退化成一般的链表.

上图还没有完全退化, 但是如果查找6这个结点, 会比其他的叶子结点走更多的路程.

为了解决一般二叉查找树可能带来的退化问题, 引入了平衡树的概念.

完全二叉树和满二叉树是平衡树.

平衡树的定义就是: 左右子树的高度差不大于1的树.

数据结构与算法之二叉查找树

什么是二叉查找树

对一般容器的查找, 我们可以按顺序遍历, 找到符合要求的元素就返回; 对于元素是有序的容器, 可以使用二分查找等方法查找, 减少操作的时间复杂度.

容易知道, 一般查找的平均时间复杂度是O(n), 二分查找的平均时间复杂度是O(logn).

什么是二叉查找树?

根结点的左子树的结点都小(大)于根结点, 根结点的右子树的结点都大(小)于根结点;