标签：遍历 15 trie C++ children project 插入 Put 节点

CMU 15_445 project_0 C++ Primer

task 1 Copy-On-Write Trie

Get

Get比较简单,遍历字符串和trie,找得到就返回值,找不到就返回nullptr.

Put

每个树有一个没有value的根节点,节点的类型分为 TrieNode 类和 TrieNodeWithValue 类,TrieNode 是基类不存 value,TrieNodeWithValue 类继承 TrieNode 类保存 value,TrieNode 含有成员变量
std::map<char, std::shared_ptr<const TrieNode>> children_

如测试案例分别插入两个int和两个字符串时,第一次插入构建整个树,第二次插入test-int2的时候,由于TrieNode的成员变量 children_ 变量的 value 是一个指向 const TrieNode 类型的共享指针,所以不能直接在第一次插入的最后一个节点直接插入一个节点,因为无法修改他的 children_,需要新建一个 TrieNodeWithValue 节点保存值 23333333,那又不能由第一次插入的倒数第二个节点直接指向这个新建的节点,因为倒数第二个节点也是 const 的,无法修改 children_,所以要复制整颗树,在副本的最后节点 children_ 链接上新建的 TrieNodeWithValue 节点.

第三次插入 test-string 的时候,由于 '-' 节点有修改,复用链接了之前插入的 int2 和新插入的 string,所以 '-' 节点之前的节点都需要复制.

第四次插入时候可以整个复用之前的树,只需要复制 root 节点再链接一个新 TrieNodeWithValue 节点就好.

整颗树的构建不能从前往后构建,比如第一次插入,如果先构建了 {'t',node} children_ map,它指向的节点是 const 的,那么它指向的节点就不能再指向下一节点了,所以只能先构建最后的节点,再一层一层往上构建.

总而言之就是先遍历要插入的字符串和trie,把遍历到的节点入栈,再遍历栈,修改节点的子节点可以复用,父节点依次复制指向上一次遍历复制的节点.

Remove

删除节点分两种情况:

删除的是尾节点,则依次向上遍历到一个分支大于1或者是value节点,然后从这个节点向上复制整个树.
删除的不是尾节点则新建一个节点指向原节点的children,然后向上遍历复制整个树.

task 2 Concurrent Key-Value Store

为了实现并发的键值存储，需要使用并发原语（concurrency primitives）来同步读写操作，以防止数据丢失。并发的键值存储应该能够同时服务多个读者和一个写者。也就是说，在有人修改字典树时，读操作仍然可以在旧的根节点上进行。在有人读取时，写操作仍然可以不等待读操作完成。

此外，如果我们从字典树中获取一个值的引用，我们应该能够在不管我们如何修改字典树的情况下访问它。字典树的Get函数只返回一个指针。如果存储这个值的字典树节点被删除了，指针就会变成悬空指针（dangling pointer）。因此，在TrieStore中，我们返回一个ValueGuard对象，它同时存储了对值和对字典树结构根节点的引用，这样就可以在我们保留ValueGuard对象时访问值。

Get 操作时,先获得root lock拿到root马上释放root lock
Put 和 Remove 操作时,先生成new trie,再拿到write lock,然后拿到root lock,然后替换根节点,这样不会造成阻塞

task 3 Debugging

这个任务要求你参考trie_debug_test.cpp文件中的指示，在生成trie结构后设置一个断点，并回答一些问题。在trie_answer.h文件中填写答案。

这个我是用Clion断点调试的,三个问题比较简单,就是问有几个子节点,然后值是多少之类的.

但是这里提交 gradescope 一直通不过,后来是在这篇博文看到是因为本地和 gradescope 的随机数不一样导致的,把trie_debug_test.cpp替换成下面代码即可

  auto trie = Trie();
  trie = trie.Put<uint32_t>("65", 25);
  trie = trie.Put<uint32_t>("61", 65);
  trie = trie.Put<uint32_t>("82", 84);
  trie = trie.Put<uint32_t>("2", 42);
  trie = trie.Put<uint32_t>("16", 67);
  trie = trie.Put<uint32_t>("94", 53);
  trie = trie.Put<uint32_t>("20", 35);
  trie = trie.Put<uint32_t>("3", 57);
  trie = trie.Put<uint32_t>("93", 30);
  trie = trie.Put<uint32_t>("75", 29);

task 4 SQL String Functions

这是一个关于SQL字符串函数的任务，要求你在BusTub数据库系统中实现upper和lower两个函数，让它们能够把字符串转换成大写或小写。　　
这个任务分为两个步骤：(1) 在string_expression.h文件中实现函数的逻辑。(2) 在plan_func_call.cpp文件中注册函数，让BusTub的SQL框架能够在用户执行SQL语句时调用你的函数。　　
你可以使用bustub-shell来测试你的实现，它是一个交互式的命令行工具，可以让你输入SQL语句并看到结果。　　
你的实现应该通过所有3个sqllogictest测试用例，它们是一些用来检查你的函数是否正确的SQL语句。　　
注意：如果你在运行sqllogictest时看到BufferPoolManager is not implemented yet.这样的警告，这是正常的，你可以忽略它。

提交

所有代码google test通过之后就可以提交到 gradescope 评分了, cd 到build目录执行命令 make submit-p0,会在项目根目录生成 project0-submission.zip 文件.
登录 https://www.gradescope.com/courses/485657/ 用 2KJRB5 这个码进入2023 春季的课程然后上传提交就好了,注意所有的代码必须通过格式校验,否则测试通过了也是0分.

标签：遍历,15,trie,C++,children,project,插入,Put,节点
From： https://www.cnblogs.com/autumnnnn/p/17297711.html

CMU_15_445_project_0_C++_Primer