CMU15-445 FALL 2022 PROJECT #0 – C++ PRIMER (Trie)

前言

这个Trie树就很熟悉了，AC自动机的底层数据结构。不过这次要用C++11来实现还是有点挑战性的。以前写题目的时候那都是C with Class的写法，甚至Class都没，就一个结构体。甚至有些时候结构体都没，直接分几个数组开写。。。这不是一个好习惯。希望这次实验能够有所收获。

环境搭建

软件清单

• vscode
• vmware player 16
• ubuntu 20.04

搭建流程

• 在vmware虚拟机中安装Ubuntu20.04
  代码环境（在Ubuntu系统中）
• 开启Ubuntu的ssh服务，并生成rsa密钥
• 将生成的密钥公钥绑定到GitHub账号中
• vscode下载 Name: Remote – SSH 插件
• 查看Ubuntu本地局域网的网卡ip地址，根据该ip地址使用vscode ssh连接
• 按照 https://github.com/cmu-db/bustub/blob/master/README.md 中的代码环境搭建流程搭建

评测流程

• 加入 https://www.gradescope.com/courses/425272 课程，课程code为 PXWVR5

• 将代码打包为zip压缩文件，并且文件中附有完整路径(因为没仔细看提交要求，导致0分了2次，浪费了30分钟)

  You only need to include the following files with their full path in your submission zip file

    src/include/primer/p0_trie.h
  

• 提交代码，等待评测

一些坑

• 仔细看报错，仔细看报错，仔细看报错。
• 对代码格式有要求，具体的话你可以自己用clang来check一下，也可以等在线评测系统报错了，再看看报错内容。（如果你遇到 Test Failed: False is not true : Test was not run. Please check the autograder! 那就是你的代码格式不对，具体原因看报错）
• C++11标准中新增的一些内容，比如智能指针以及移动语义以及所有权机制。由于看过rust，我对这部分还是比较了解的。（其实应该先看C++11,再看rust的，哈哈哈）
• 测试用例的时候要去掉测试用例中的 DISABLED_前缀。
  

  You can disable tests in GTest by adding a DISABLED_ prefix to the test name.

• 评测提交文件的细节，上面的评测流程环节有讲到
• 一定要仔细看实验的要求。 实验要求页面链接 https://15445.courses.cs.cmu.edu/fall2022/project0/
• 所有权转移后，原变量不再拥有一个值，此时对该变量的指针都将失效。（就是说这个变量没用了）

一些细节

1. 实现移动拷贝构造函数

   这个方面我还是比较懵比的一开始，最后也是先学现用搞出来的。在实验要求页中也提醒得很清楚了，需要move而不要进行copy。

   Finally, the move constructor TrieNode(TrieNode &&other_trie_node) is used to transfer old TrieNode’s unique pointers to a new TrieNode. Make sure you are not making copies of unique pointers when transferring data.

   整个实验做下来，感觉最卡的地方，也是自己感到自己最蠢的地方就是实现key插入的函数中的一种情况。

   A TrieNode with this character exists but is not a terminal node (is_end_ == false). This means that the unique_ptr is pointing to a TrieNode object instead of a TrieNodeWithValue object. You need to invoke the TrieNodeWithValue(TrieNode &&trieNode, T value) constructor to convert the old TrieNode to a new TrieNodeWithValue.

   我最先的代码过了本地的所有评测。然后去oj进行压力更大的评测。第一次进行评测的时候获得了70分。出现错误的地方都和Insert有关，那肯定是Insert出了大问题。我重新审视了一遍代码，发现确实出了问题。

   在上面提到的情况中，我的实现是直接使用 TrieNodeWithValue(char key_char, T value) 这个构造函数生成的节点指针，先将原来的非结束节点删除，然后再把刚才用这个构造函数生成的智能指针添加到父节点的hashtable中。错误就出在这里，因为我直接删除了原有的节点，导致原有节点的子孙节点丢失了。因此我们需要将原有节点的子孙信息move到新增的结束节点中。那么这里就用到刚才编写的移动构造函数以及其子类的构造函数的另一个重载TrieNodeWithValue(TrieNode &&trieNode, T value) 。该构造函数接收一个TrieNode的智能指针的右值，也就是该函数获取了该值的所有权。如果在该构造函数内没有进行所有权的转移（比如返回值转移或者赋值转移），在这个函数返回时（即出了这个函数作用域）会将该值自动清理。

   当初犯蠢就在这里，这个真是蠢到极点了。我一开始的思路还是按照原来的写法，但是多加了一个步骤那就是transfer一下信息。就是因为我没有跳出原来的思维，导致我在这卡了好久。我要先删除节点，然后再连接新的节点，这时候会造成对已free的堆内存再次调用的错误。我想着，先把新的节点创造出来暂存一下，然后再删除，然后再连接新的节点。这时候又出现一个问题了，那就是栈不是堆，栈内的东西在出了这个作用域后是失效的。我因为这一点段错误的好多次。要么就是编译都过不去，要么就是段错误，非常搞人心态。然后我暂时先放下了，去打了把游戏，突然脑子转过来了。。。。我直接修改父节点中hashtbl中智能指针的值不就好了吗。那时候真的是瞬间清醒，游戏打到一半直接退出，改了一下提交，直接AC，神清气爽。

2. 暂存已遍历节点的信息

   那肯定是用栈来实现，那么问题来了，栈呢。由于以前做题目，栈直接手写或者用STL中的stack。但是这个实验的头文件里面没有stack，我也不知道能不能加。自己实现一个栈又感觉有点不够优雅。我一度想过用递归来实现这个函数，什么字符串切片，递归出口之类的一瞬间在脑内已经想好了。但是还是感觉，不够优雅，而且递归在这种工程化的代码中还是少用吧，毕竟实现的这个递归并不是尾递归（尾递归随便用，编译器会优化成循环）。然后我看了一眼头文件，我去，有个vector，恍然大悟。。直接用vecotr模拟一下栈不就好了吗（说不定STL中的stack也是用vecotr模拟的）。真的有被自己蠢到。

3. unordered_map与pair

   我是知道unordered_map是用hash实现的，但是我才知道unordered_map是不支持pair插入的。呜呜呜呜，还是需要补充很多知识啊。

4. vecotr中push_back和emplace_back的区别

   这是我在提交评测后出现的报错信息中发现的。报错信息让我用emplace_back替换push_back，然后我就去查阅了一下关于emplace_back的资料。（明天再更新，已经12点了，舍友要骂人了）

总结与感悟

• 那最开始肯定是放上AC截图啦
  
• 然后就是苦逼的提交记录
  
• debug相关
  这个实验我还是使用最原始的debug方案，那就是assert + printf。这个方案太原始了，后续需要改进，使用gdb工具进行debug！！