CMU15445（2023 Spring） - Project 0. C++ Primer

文章目录

系列笔记

环境配置
Project 0. C++ Primer
Project 1. Buffer Pool
Project 2. B+Tree

作业链接

作业链接（2020，废）
作业链接
p0就是一个C++水平测试，很简单 2023的明显难不少。

TASK 1

先简单说一下看到这个数据结构时自己想到的一些问题与自己的思考：

  1. 为啥Put的实现这么奇葩，要求返回一颗新树，不会很耗资源吗？
    显而易见Put是比较耗资源的，但是没有想象中的那么耗资源，因为Trie其实不负责具体资源的分配的，Trie代表的仅仅是一些索引而已，里面只存了一堆指针。
  2. 为啥Get的实现要求先dynamic_cast到const TrieNodeWithValue<T>*，不嫌麻烦吗？*
    这其实是为了实现异类集合，想想就知道了。

Get

Get实现没啥难度，直接扫一遍key指针跟着跑就行，唯一一个小坑点是root_是个shared_ptr，不能直接做cast到裸指针，需要通过.get获取裸指针然后再做cast。

Put

Put实现开始就有点麻烦了，这个题目的主要问题是想要修改一棵树，根据题目要求，这个Put是要返回一颗新Trie的，拿官方例子中的添加[“ad”, 2]为例，如果我们自顶向下构造new trie，首先建立new root，然后我们在new root里添加一个[‘a’, Node2]，然后在Node2里添加一个[‘d’, 2]，这一步就卡住了——我们在root里存的node2的指针是指const的，加不了！

在这里插入图片描述
想清楚这一点就很好解决了，我们就自底向上构建树，先从头到尾扫一遍key，公共结点一路clone下来，非公共结点新建资源，存到栈里，然后使用最后的那个结点的child与函数参数value构造一个TrieNodeWithValue，再反向遍历key并依次弹出stack，利用map::operator[]建立一颗树即可。

Remove

Remove也就差不多的操作，首先扫一遍key，如果发现key不在Trie里或者key对应的结点压根没value，直接返回root无事发生，否则的话就入栈，然后用最后遍历到的那个结点的children去构造一个TrieNode并修改栈顶，然后依此出栈并erase掉children为empty的结点。

Task 2

没啥好说的，照着伪代码写就行，只要Task1没问题，Task2就不会有太大问题，记得写Put的时候别忘了move传value就行。