CMU 15-445 Project 0 实现字典树

原文链接：https://juejin.cn/post/7139572163371073543
项目准备

代码、手册
本文对应 2022 年的课程，Project 0 已经更新为实现字典树了。C++17 的开发环境建议直接下载 CLion，不建议自己瞎折腾。
测试

1. $ mkdir build && cd build
2. $ cmake -DCMAKE_BUILD_TYPE=DEBUG ..
3. $ make starter_trie_test
4. $ ./test/starter_trie_test

复制代码

运行上面的指令，你会得到如下输出，这不表示该项目的 5 个测试用例没过，而是没有执行。

1. [==========] Running 0 tests from 0 test suites.
2. [==========] 0 tests from 0 test suites ran. (0 ms total)
3. [ PASSED ] 0 tests.
5. YOU HAVE 5 DISABLED TESTS

复制代码

需要修改 test/primer/starter_trie_test.cpp 文件，移除测试名 DISABLED_ 前缀。

1. // TEST(StarterTest, DISABLED_TrieNodeInsertTest)
2. TEST(StarterTest, TrieNodeInsertTest)

复制代码

格式化

1. $ make format
2. $ make check-lint
3. $ make check-clang-tidy-p0

复制代码

调试日志

1. LOG_INFO("# Pages: %d", num_pages);
2. LOG_DEBUG("Fetching page %d", page_id);

复制代码

项目介绍

使用支持并发的字典树实现一个键值存储，字典树是一种高效的排序树，用于检索指定键值。这里假设键都是非空的可变长度字符串，但事实上键可以是任意类型。

上图所示字典树中存储了：HAT、HAVE、HELLO 三个键。

上图所示字典树存储了：ab=1、ac="val" 两组键值。
项目实现

只需要修改一个文件：src/include/primer/p0_trie.h
项目已经定义好了类和成员变量，以及需要实现的成员函数的签名，可以添加辅助变量或函数，但不能修改已有变量和函数签名。
任务一

文件中定义了 Trie、TrieNode、TrieNodeWithValue 三个类，建议先实现单线程版本，再改并发版本，类中的成员变量和成员函数都有注释。
任务二

实现并发安全的字典树，可以使用 BusTub 的 RwLatch 或 C++ 的 std::shared_mutex。
一些 C++ 的基操

一年多没写 C++ 了，用惯了 Go，突然用 C++ 写的脑壳疼，没用过 C++ 的小伙伴可能想编译通过都费劲，这里贴一下需要了解的 C++ 特性。
移动语义

std::unique_ptr 表示唯一的指向类型为 T 的对象的指针，因此需要使用移动语义 std::move，代码中 children_ 的类型嵌套了 std::unique_ptr，也需要使用移动语义。

1. TrieNode(TrieNode &&other_trie_node) noexcept {
2.     key_char_ = other_trie_node.key_char_;
3.     is_end_ = other_trie_node.is_end_;
4.     children_ = std::move(other_trie_node.children_);
5. }

复制代码

构造父类

TrieNodeWithValue 是 TrieNode 的子类，构造子类时，如果没有手动在子类的构造函数中构造父类，就会调用父类的默认构造函数，而代码中父类是没有默认构造函数的，所以需要手动在子类中构造父类。
需要使用 std::forward 转发右值引用。

1. TrieNodeWithValue(TrieNode &&trieNode, T value) : TrieNode(std::forward<TrieNode>(trieNode)) {
2.     this->value_ = value;
3.     this->is_end_ = true;
4. }

复制代码

父子指针转换

TrieNodeWithValue 是模板类，没法办使用多态，Trie::GetValue 需要将 unique_ptr 转换为 TrieNodeWithValue* 后调用 TrieNodeWithValue::GetValue。

1. std::unique_ptr<TrieNode> uptr = std::make_unique<TrieNodeWithValue<T>>('a', T());
2. dynamic_cast<TrieNodeWithValue<T>*>(&(*uptr))->GetValue();

复制代码

可能有更优雅的办法，但我实在是想不出来了，C++ 可真难写啊。
所有权规避

std::unique_ptr 的传递一定是使用移动语义转移 T 对象地址的所有权，但也可以不获取所有权访问 T 对象的地址，代码里的注释也引导我们使用这种方式。

1. std::unique_ptr<int> uptr(new int(1));
2. std::cout << *uptr << std::endl; // 1
4. auto *p = &uptr;
5. *(*p) = 2;
6. std::cout << *uptr << std::endl; // 2

复制代码

remove_innner 的返回值表示传入节点是否可以删除，可以删除的条件是该节点无子节点且非尾节点。函数内判断当前节点的子节点是否可以删除，并返回当前节点是否可以删除。出口是递归到了传入 key 的尾节点，取消尾节点标记，并返回是否可以删除。该函数调用前还需要判断一下 key 是否存在。
空模板变量值

GetValue 的返回值是一个模板类型，错误的时候直接 return T()，正常情况下，需要转换 TrieNode 为 TrieNodeWithValue 中获取值，上文提过该父子类转换的办法。

1. auto curr = &root_;
2. size_t i = 0;
4. while (i + 1 < key.size()) {
5.     curr = (*curr)->GetChildNode(key[i]);
6.     i++;
7. }
8. // end_node
9. curr = (*curr)->GetChildNode(key[i]);

复制代码

并发安全

这个其实很简单，前 4 个测试都通过了，Insert、Remove、GetValue 三个函数开始和结束位置加锁和解锁就可以了，需要注意的是这三个函数如果彼此调用会死锁，比如 Insert 里面调用 GetValue 判断 key 是否存在。
这里提供一个 Go 语言中 defer 解锁的简易实现，如果你不知道 defer 就在每个返回的地方都解锁就可以。

1. * When you reach the ending character of a key:
2. * 2. If the terminal node is a TrieNode, then convert it into TrieNodeWithValue by
3. * invoking the appropriate constructor.

复制代码

使用方式如下，以 Remove 为例。

1. (*curr) = std::make_unique<TrieNodeWithValue<T>>(std::move(*(*curr)), value);

复制代码

写在最后

动手开始项目前，可以先去 leetcode 过一遍 实现 Trie (前缀树)，先能写出简单的字典树再动手。如果需要代码的话可以私信我。如果想做数据库的工作欢迎找我内推（恰点内推奖金）。


免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！