CMU15445项目笔记

学一学CMU的15445，课程地址

Project #0 - C++ Primer

C++ Bootcamp

主要针对 C++17 特性，共个文件。

references.cpp

有关引用（别名），函数传引用
move_semantics.cpp

有关移动语义和右值引用
- lvalue（左值）：refer to 内存中某个有权限访问的区域的对象
  
  rvalue（右值）：非左值的值，数据位于的区域没有权限访问（字面常量）或者没有必要访问（匿名对象），包括将亡值和纯右值
  
  赋值语句中等号左边的必须是左值，右边的随便
- 左值引用（&）和右值引用（&&）都必须立即初始化，右值引用可以通过移动的方式在浅拷贝的情况下保证拷贝的安全性，在设计和实现类时，对于需要动态申请大量资源的类，应该设计右值引用的拷贝构造函数和赋值函数，以提高应用程序的效率，具体 3. 中有讲
- std::move() 方法可以将左值转换为右值，即将亡值，方便使用移动语义，需要 <utility> 头文件
move_constructors.cpp

有关应用移动语义的拷贝构造函数和赋值重载函数

在类定义中删除左值引用的拷贝构造函数和赋值重载函数，意味着实例化后就不再允许被复制，防止双重删除或者内存泄露

References：
- C++11右值引用|移动语义|完美转发|巨巨巨详细
- C++|左值、右值、将亡值|谈谈我对它们的深入理解
templated_functions.cpp

有关模板函数

注意模板参数不一定要是 class 或者 typename，也可以是别的，但没必要
templated_classes.cpp

有关模板类
wrapper_class.cpp

有关包装类
- RAII（Resource Acquisition is Initialization）：一个实例化管理一个资源，防止双重删除或内存泄露
- 使用移动语义
iterator.cpp

有关迭代器，实现了一个双向链表（DLL）及其迭代器
namespaces.cpp

有关命名空间
vectors.cpp

有关动态数组

std::remove_if() 不能删除元素，只能将元素移到末尾，配合 erase() 函数才能删掉

emplace_back() 比 push_back() 稍快
sets.cpp

有关集合

count() 函数
unordered_maps.cpp

有关映射

count() 函数
auto.cpp

有关 auto 类型使用
unique_ptr.cpp

有关智能指针类型 unique_ptr 使用
- 需要 <memory> 头文件
- unique_ptr 保留对象的唯一所有权，没有两个 unique_ptr 指针指向同一个对象
- 初始化
  1
  2
  //利用make_unique<>()方法初始化，调用的构造函数是<>类型的构造函数
  std::unique_ptr<Point> u = std::make_unique<Point>();
- 可以通过移动语义转移所有权
shared_ptr.cpp

有关智能指针类型 shared_ptr 使用
- 需要 <memory> 头文件
- 可以有多个 shared_ptr 指针指向同一个对象
- 初始化
  1
  2
  //利用make_shared<>()方法初始化，调用的构造函数是<>类型的构造函数
  std::shared_ptr<Point> u = std::make_shared<Point>();
- 通过 use_count() 方法可以得到有多少个指针指向同个对象
- 可以通过移动语义转移所有权
mutex.cpp

有关互斥锁
- 同步原语（Synchronization Primitives）是用于支持此多线程环境下线程同步的工具和机制。这些源于主要用于管理线程之间对共享资源的访问，防止数据竞争和保证线程安全
- std::mutex 提供独占锁，确保同一时间只有一个线程可以获得互斥量，不可复制，不可移动
- 互斥量状态：
  - 解锁状态意味着共享资源可用
  - 加锁状态意味着共享资源不可用
- 需要 <mutex> 和 <thread> 头文件
- lock() 锁住互斥量，unlock() 解锁互斥量，try_lock() 尝试锁住互斥量
- 被阻塞
References：
- C++多线程——互斥量mutex
scoped_lock.cpp

有关多个互斥量的管理
- 需要 <mutex> 和 <thread> 头文件
- 当创建一个 std::scoped_lock 对象时，它尝试取得其所给互斥量的所有权。当控制权离开创建 scoped_lock 对象的作用域时，scoped_lock 会被析构，互斥量随之被释放。如果给定了多个互斥量，将使用避免死锁的算法，类似于 std::lock
- 是一个 RAII 风格的类
- scoped_lock 类不可复制，不可移动
References：
- 【C++ 17 新特性互斥锁】std::scoped_lock 的使用，管理多个互斥量
condition_variable.cpp

有关条件变量
- 需要 <condition_variable> 头文件
- 功能：
  - 拥有条件变量的线程获取互斥量
  - 循环检查某个条件，如果条件不满足则阻塞直到满足；如果满足则向下执行
  - 某个线程满足条件执行完之后调用 notify_one 或 notify_all 唤醒一个或所有等待线程
- wait() 第一个参数必须用 unique_lock
- unique_lock 不能复制，可以移动
References：
- C++11条件变量condition_variable详解
- 【C++】独占互斥锁（unique_lock）
rwlock.cpp

有关读写器锁的用法
- 用 std::shared_mutex、std::shared_lock 和 std::unique_lock
- 需要 <shared_mutex>
- std::mutex 和 std::shared_mutex 的区别：
  - std::mutex 提供独占访问，同一时间只能有一个线程持有该类型的锁
  - std::shared_mutex 提供共享访问和独占访问，允许多个线程通过持有 std::shared_lock 共享锁来只读访问，允许一个线程持有 std::unique_lock 独占锁来进行写操作，但是共享锁和独占锁不能同时存在，互斥
  - std::shared_mutex 更适用于读多写少的场景
s24_my_ptr.cpp

实现了一个 std::unique_pointer<T> 类
- 使用原始指针类型，很可能会出现内存泄露，二次释放，释放后访问的问题
- RAII 的好处
- smart_generator<int>() 和 dumb_generator<int>() 的区别

HyperLogLog 算法

HyperLogLog 算法是一种用于估计大规模数据集基数的随机化算法

基数（cardinality）：集合中不同元素的个数

时间复杂度：

插入
查询
合并两个计数器

基本原理：

基于抛硬币的原理，由连续抛硬币出现正面的概率来估算一共抛硬币的次数

相似的，我们可以将主键进行哈希，得到一个 01 串，通过统计从第零位开始连续的的个数的最大值来估算基数

为了减小偶然性，可以设置个寄存器，分别统计连续的个数的最大值，取01串的前高位作为寄存器编号，分别在各自寄存器内更新，最后综合起来计算答案即可

Presto 的实现其实就是为了减小寄存器（dense_bucket_）的大小，将超出寄存器表示范围的部分存到另一个 unordered_map（overflow_bucket_）中，因为有时某些寄存器根本没有用到，无用空间过多

代码并不难写，主要是弄懂怎么调试……使用 bustub 已经配置好的 google test 调试各个函数就好

上图是我瞎写了一通以后拿的分数，看了看 results 发现答案没问题，但是存在内存泄露，因为我寄存器是用动态分配空间的数组实现的，这就需要在类析构的时候 free() 掉，写了一个析构函数就过了，如果使用 STL 中的 vector 就不会出现内存泄露，因为 C++ 的 STL 都遵循 RAII 的原则

还有一个比较蛋疼的地方就是格式问题，格式不对就给判成分，需要注意一下

Project #1 - Buffer Pool Manager

Task #1 - LRU-K Replacement Policy

要求实现一个 LRU-K 替换算法，具体实现就是整了一个容器叫 LRU-K Replacer，然后对其中的 frames 进行计算和操作

画了个小图来表示它们之间的关系：

编写过程中用到了移动语义以及引用来保证 LRUKNode 的实例是 unique 的，防止内存泄露

CMU15445项目笔记

Project #0 - C++ Primer

C++ Bootcamp

HyperLogLog 算法

Project #1 - Buffer Pool Manager

Task #1 - LRU-K Replacement Policy

Task #2 - Disk Scheduler

关于本文

CMU15445作业

CMU15445听课笔记