CMU15-445- Project #0 - C++ Primer

CMU15-445

作为 CMU 数据库的入门课，这门课由数据库领域的大牛 Andy Pavlo 讲授（“这个世界上我只在乎两件事，一是我的老婆，二就是数据库”）。

这是一门质量极高，资源极齐全的 Database 入门课，这门课的 Faculty 和背后的 CMU Database Group 将课程对应的基础设施 (Autograder, Discord) 和课程资料 (Lectures, Notes, Homework) 完全开源，让每一个愿意学习数据库的同学都可以享受到几乎等同于 CMU 本校学生的课程体验。

亮点在于这门课程实现了一个关系型数据库的Demo–bustub，并对组成部分进行修改，最后达到完成整个数据库的目的，非常的有意思。

近年来由于CMU15-445这门课的热度大增，无论是找工作还是保研的简历上都少不了这个课程。到了可以说是人手一个的地步（还有MIT6.824），但是最后的排行榜上真正完成4个项目并且有成绩的不过100余人。在这种背景下也催生出了很多卖课的机构和个人。还有种种乱象。暂且按下不表，进入主题。

前言

先附上课程链接我原本是想要完成最新的课程即2023fall的，但是2023fall的P0直接就把我劝退了，相较于2022fall的P0我认为难度上升了不止一点。但是其他的Project的实现差别并不是太大，所以我选择了较为容易下手的2022fall的课程进行学习。

Project0-C++ Primer

还是先放上项目Project#0-C++primer链接

概述

这是一个相当于先导课程的项目，旨在培养和检验学生的现代C++编程能力 ，BusTub大量使用C17，当你上手之后可能就会发现和你印象中的C不一样。

在CMU如果你没能满分通过P0，那么你会被要求退课。

所需前置知识

我认为需要的前置知识主要包括C++11的新特性
这是在2023fall课程的一个可能是助教写的一个小demo包含了几个例子能够帮助你快速的上手c++11的新特性。

熟悉字典树能够理解字典树原理能够完成一个字典树的小demoLeetCode.208实现前缀字典树可以先把这个做了，了解一下什么是字典树。

上图就是一个字典树的简单示意图

文件结构

image.png|264

在文件中作为字典树的架子文件中包含了三个类。

TrieNode
TrieNodeWithValue
Trie

Task#1 字典树

先完成一个单线程版本的字典树，后期再考虑并发。

TrieNode

TrieNode定义了一个Trie树的一个节点。

一个包含关键字的char类型`key_char_。
一个bool类型is_node的标志来标记这个节点是否是值节点
包含一个存储类型为 char to unique_ptr<TrieNode>映射的哈希表
需要注意的点：
C++中智能指针std::unique_ptr的特性所带来的：
The InsertChildNode and GetChildNode both return a pointer to unique_ptr
这个独享类型的智能指针也不支持被复制，所以要么使用std::move()把所有权交出去，要么就用get()函数把裸指针交出去。
the move constructor TrieNode(TrieNode &&other_trie_node) is used to transfer old TrieNode’s unique pointers to a new TrieNode。因为是unique_ptr所以在传递的时候不能对指针进行复制。（解决方法就是使用move()函数）。

TrieNodeWithValue

image.png|290

这个是[[CMU15-445 Project 0 - C++ Primer#TrieNode]]类的子类，多了一个能保存任意类型的值T。而且is_end被设定为True。
根据不同的情况调用不同的构造函数。如果原本是一个普通节点就调用参数为（TrieNode&&，T），如果是创建一个全新的节点则调用参数为(char,T).

Trie Class

有一个root_节点，是整个树的根节点，而且不存储任何的值。

Insert

要插入到trie中，您需要首先使用给定的键遍历trie，如果不存在，则插入TrieNode。请注意，不允许插入重复的键，并且应该返回false。一旦到达键的结束字符，有三种可能性：

到达的节点不存在，需要调用参数为(char,T)的构造函数构造一个全新的值节点。利用“Make use of the fact that a unique_ptr to TrieNode can also store a unique_ptr to TrieNodeWithValue”这一特性可以以最后一个节点为模板（无论是不是值节点都能够成功创建）创建一个新的值节点。
到达的节点存在但不是值节点，调用（TrieNode&&，T）为参数的这样一个转换的构造函数，把普通节点转换为值节点。
存在且是值节点，直接返回false。