Rika小课堂整合

第一节课:

  • 用std::vector代替数组,用std::string代替char[] ,大多数时候可以用引用代替指针,如果一定要用指针也可以用智能指针

  • 不要用typedef struct {} XXX; 而是 struct XXX {};

  • 指针和引用的区别:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
void plusUsePointer(int *a, int *b){
*a = *a + *b;
}
void plusUseReference(int &a, int &b){
a = a + b;
}

int main(){
int a = 10;
int b = 20;
plusUsePointer(&a, &b);
std::cout << a << std::endl;

a = 10;
b = 20;
plusUseReference(a, b);
std::cout << a << std::endl;
return 0;
}
表示引用的&和取地址的&有区别,放在形参中表示参数按引用传递。用指针传递需要不断取地址和解引用,而用引用传递则只需要在形参列表中加&,即可全部自动传址。

函数传参分为传值和传址,即传递copy和reference的区别。
  • 初始化的优化:

    原代码:

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    struct Point{
    int x;
    int y;
    int z;
    Point(){
    x = 0;
    y = 0;
    z = 0;
    }
    };

    修改后:

    1
    2
    3
    4
    5
    6
    7
    8
    9
    struct Point{
    int x{0};
    int y{0};
    int z{0};

    Point(int x_in, int y_in, int z_in) : x{x_in}, y{y_in}, z{z_in} {}

    Point() = default;
    };

    class默认成员private,struct默认public。

    第一个构造函数就是接受三个int参数,后面的是初始化列表,第二个就是默认构造函数,即不接受参数,使用上面大括号里的内容初始化,和不写任何构造函数是一样的。

    但是需要注意的是,一旦定义了任何一个构造函数(带参数的),默认构造函数就会消失,除非像这样手动指定= default

  • 堆和栈

    内存里的数据一部分放在堆上,一部分放在栈上。所有你直接声明的变量都在栈上,你用new声明的指针都在堆上。

    栈的优点:快。

    缺点:只能活给定的生命周期,出了函数就没了;大小不能太大,否则会Stack Overflow;必须是 已知的 大小

    堆的优点:很大,可以放巨大的东西;想用多少就声明多少,完全可以动态处理。

    缺点:慢。必须手动释放,否则会内存泄露。

    因为栈上的变量大小必须是已知的,所以可变长数组是不允许的,因此直接声明一个以变量为长度的数组会报错,需要用new做动态数组,但这就会产生另一个问题:new过后的指针需要手动delete。

    当然,动态数组基本用vector就好,但有时候可变大小的不一定是数组,可能是矩阵,如:

    1
    2
    3
    4
    5
    6
    7
    8
    struct Matrix4x4{
    float m[4][4]{0};
    }

    int main(){
    Matrix4x4 *m = new Matrix4x4();
    std::cout << m->m[0][0] << std::endl;
    }

    此时就可以使用智能指针。用std::make_shared代替原来的new,指针类型改成std::shared_ptr,指针就可以实现自动回收。智能指针的存放位置依然是在栈上。

    1
    2
    3
    4
    5
    6
    7
    8
    struct Matrix4x4{
    float m[4][4]{0};
    }

    int main(){
    std::shared_ptr<Matrix4x4> *m = std::make_shared<Matrix4x4>();
    std::cout << m->m[0][0] << std::endl;
    }
  • shared_ptr与unique_ptr

    1
    2
    3
    4
    5
    6
    7
    std::shared_ptr<Matrix4x4> m = std::make_shared<Matrix4x4>();
    std::unique_ptr<Matrix4x4> m2 = std_make_unique<Matrix4x4>();

    auto m_copy = m;
    auto m_copy2 = m2;

    auto m_copy3 = std::move(m2);

    两个都不会自动拷贝,但是shared_ptr可以被任意赋值给别人,unique_ptr保证只有一个人拥有这个对象,所以m_copy2的赋值会报错,可以用m_copy3的写法,使用move方法。移动后原来的m2就不能使用了,unique_ptr永远只有一个变量能使用,好处就是会快一些。

第二节课

  • 左值和右值

通俗地说,左值就是“可以被赋值的表达式”,而右值是不可以的。比如说a=1,a是变量,可以被赋值,1就不可以。在c++里,大致可以认为,如果一个表达式有确切的地址,那么就是左值,反之是右值。
比如声明了变量a,你可以用&a取到a的地址,但是&1是取不到1的地址的。

右值是“不可取址”而不是“不可引用”,比如对const类型的变量可以声明一个const类型的引用。

左值引用:要求传入的参数必须是左值,如&var,这种是最常见的引用。如果传入1就会报错,因为1不是左值,不可以在这里做参数。

Rika tip:顺带一提,有一个东西叫右值引用,在形参列表里以&&num的形式出现。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
void add_one_by_ref(int &num){
num++;
}

void add_one_by_val(int num){
num++;
}

void add_one_by_ptr(int *num){
*num++;
}

void add_one_on_const_ref(const int &num){// error:表达式必须是可修改的左值(对不可变引用不可以修改)
num++;
}


void main(){
int a = 1, b = 1, c = 1, d = 1;
add_one_by_ref(a); //a = 2
add one_by_val(b); //b = 1
add_one_by_ptr(&c);//c = 2
add_one_on_const_ref(d);

add one_by_ref(1);//error
add_one_by_val(1);//num = 2
add one_on_const_ref(1);
}

再复习一次ref val ptr的区别:ref-取引用,val-取复制,ptr-取指针

ref和ptr效果相同,但是不需要不断写*和&,避免反复的指针操作。

值得一提的是,对一个左值取const类型的引用,如果再取复制的话则复制仍是可变的,除非再做const声明。

1
2
3
4
5
6
7
8
std::vector<int> vec{1, 2, 3}; 
const std::vector<int> c_vec{7, 8};
std::vector<int>& ref = vec;
const std::vector<int>& c_ref = vec;
auto copy = c_ref; // a non-const copy
const auto copy = c_ref; // a const copy
auto& a_ref = ref; // a non-const reference
const auto& c_aref = ref; // a const reference
  • 解构赋值

    1
    2
    3
    4
    5
    6
    7
    int arr[] = {1, 2, 3};
    auto &[a, b, c] = arr;
    a = 10;
    b = 20;
    c = 30;
    std::cout << arr[0] << arr[1] << arr[2] << std::endl;
    // 10 20 30
  • 迭代器

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
void main(){
int arr[5] = {1, 2, 3, 4, 5};

for(int i = 0; i < 5; i++){
std::cout << arr[i]<< " ";
//1 2 3 4 5
}

for (auto i :arr){
std::cout << i << " ";
//1 2 3 4 5
}

for (auto &i :arr){
std::cout << i << " ";
//1 2 3 4 5
}

for (auto &i :arr){
i = i * 2;
}

for (auto i :arr){
std::cout << i << " ";
//2 4 6 8 10
}
}

像数组,还有很多这种类似的集合对象都定义了迭代器,用这个for(auto xxx: bbb)就能使得xxx每次为其中一个成员循环。写不写引用区别只在于不写的话i会被复制一份用来循环。

第三节课

  • 哈希表

哈希表主要是为了解决一个从k到v的映射问题。就是我有一个集合,里面有k和v的配对元素,那么在已知k的情况下,要能够找到对应的v,需要找一个数据结构来存这样的数据。

这里如果k是正整数的话,问题就比较简单,可以直接使用数组,比如存储学号,就可以将学号作为下标,可以使用学号在O(1)时间内找到特定学生。

而这样做的问题是会造成空间的浪费,因为数组下标从0开始,可能只有几千个学生但是就要用掉几十亿的空间,且这也仅限于k为正整数的情况。于是就出现了哈希表。

从哈希是什么开始讲起,哈希的目的就是,把一个可能占用很大空间的东西,映射到一个较小的空间里,并且尽量保证不冲突(即尽量保证是双射)。在上述的例子里,学号和学生还是用数组存储,但是下标不再是学号,而是学号对10007取模(举例),那么无论学号位数多长,都只需要大约10000个空间就能存下了。

把一个数据转换成哈希的方法很多种,这个转换的东西就叫哈希函数。哈希函数是不可逆的。一般来说,哈希函数应该有这样的特性:1.取值空间有限,这个原因很显然,上面说过了。2.尽量保证重码率低,比如学号,如果不是用10007而是10000取模的话,那么每一年都会有一个学号后四位相同的学生,这可能就不太合适。

但是因为哈希函数的输入取值空间是无限的,输出取值空间是有限的,所以必定存在重码的可能性,一个好的哈希函数就应该降低这种可能性。

这样我们要存k和v的关系的话,就先对k哈希,得到哈希码,然后开一个足够大的数组,把v放在这个哈希码对应的位置上。这样之后我们要找与k对应的v的时候,就先算出来k的哈希,然后直接在数组的一定位置上就能取到v了,这就是哈希表的工作原理。

关于重码率:如果我们对重码的低概率有信心,而且不太关心这个的话,可以直接默认允许重码和覆盖。更多时候我们是不允许发生覆盖的,那么这个时候我们就需要把拥有相同哈希的pair用链表的形式存起来,然后再找到这个链表,发现里面有多个目标的时候,就一个个依次做全量匹配,所以哈希表一般我们说它是O(1)的时间,但并不是严格的。万一所有的元素的哈希都一样那就退化成链表了。

一般而言,为了保证重码率低,我们需要腾出3-10倍的空间来存哈希表,比如我要存1000个学生,那么哈希取值可能就在1-3000之间,这样就能降低重码发生率。这也是哈希表的缺点,即空间占用率大。

python的字典和C++中的std::hash_map就是哈希表。

几个存pairs的方法比较起来

1.链表:插入O1,读取On,空间消耗较小

2.数组:插入O1,读取O1,空间消耗最大

3.哈希表:插入接近O1,读取接近O1,空间消耗较大

4.红黑树:插入O logn,读取O logn,空间消耗最小

  • 红黑树
    从二叉树的插入过程开始讲起。

第一个数据扔进根节点。第二个数据,我们对比两个数据的大小,如果比根节点小,就放在左子树,否则放在右子树。后续插入都这样做,如果插入的比当前节点小,就继续和左子树比,否则和右子树比,一直比到叶节点,然后把这个数据插入在这里。那么,对于n个数据,在理想情况下,我们的二叉树应该有log_2 n层。那么读取数据的时候相同,我要查学号为k的学生,先和根节点比,如果k比根节点小,就继续去左子树查,反之去右子树查。容易理解,每层需要比较一次,所以无论是插入还是查询都是O(logn)的时间。

上面说的是理想情况,也就是我们的树是一棵平衡二叉树,但是如果刚开始插入数据的时候,所有数据都是排好序的,那么就会导致所有的某一侧子树全空。那么我们的二叉树就退化成链表,查询和写入也都是O(n)的时间了。

红黑树是为了避免这种情况出现的。红黑树每一个节点都或者是红色,或者是黑色;所有的叶节点必须是黑色;不得存在一个红节点的子节点仍然是红节点,每一条路径的黑节点数量必须相同。总之就是通过这些条件,保证整棵树的最短路径和最长路径的差距不超过一倍。即最短路径上全是黑节点,最长路径是红黑交错。

然后如果存在插入一个节点之后这棵树违反了上述规则,那么就需要对树做调整,这个调整也是O(logn)的,也就是说每层至多只动一个节点。

总的来说红黑树是一个稳定(抗极端情况),性能好,占空间小的数据结构

第四节课

-


本博客所有文章除特别声明外,均采用 CC BY-SA 4.0 协议 ,转载请注明出处!