CMU 15-445 Project 0 实现字典树

原文链接：https://juejin.cn/post/7139572163371073543

项目准备

代码、手册

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

测试

$ mkdir build && cd build $ cmake -DCMAKE_BUILD_TYPE=DEBUG .. $ make starter_trie_test  $ ./test/starter_trie_test 

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

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

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

// TEST(StarterTest, DISABLED_TrieNodeInsertTest) TEST(StarterTest, TrieNodeInsertTest) 

格式化

$ make format  $ make check-lint  $ make check-clang-tidy-p0 

调试日志

LOG_INFO("# Pages: %d", num_pages); 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> 表示唯一的指向类型为 T 的对象的指针，因此需要使用移动语义 std::move，代码中 children_ 的类型嵌套了 std::unique_ptr<T>，也需要使用移动语义。

TrieNode(TrieNode &&other_trie_node) noexcept {     key_char_ = other_trie_node.key_char_;     is_end_ = other_trie_node.is_end_;     children_ = std::move(other_trie_node.children_); } 

构造父类

TrieNodeWithValue 是 TrieNode 的子类，构造子类时，如果没有手动在子类的构造函数中构造父类，就会调用父类的默认构造函数，而代码中父类是没有默认构造函数的，所以需要手动在子类中构造父类。

需要使用 std::forward<TrieNode> 转发右值引用。

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

父子指针转换

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

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

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

所有权规避

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

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

代码实现

大部分代码按照注释一步一步来就没问题，课程规定不公开代码，所以这里只列一些难点。

循环迭代

这里给出一个模版，对于尾节点和非尾节点，一般需要不同的操作。

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

节点转换

在插入流程中，当迭代到最后一个字符时，发现已经有了一个 TrieNode 类型的节点，需要转换为 TrieNodeWithValue 类型。

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

不熟悉 C++ 的话这个操作可能有点困难，这里给出代码，这一层又一层的括号和解引用确实不够优雅，但一时间也想不到其他好办法。

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

节点删除

根据代码注释的提示，Remove 函数是要递归删除的，这里给出递归的框架。

bool remove_inner(const std::string &key, size_t i, std::unique_ptr<TrieNode> *curr, bool *success) {   if (i == key.size()) {     *success = true; // Remove 的返回值，表示成功删除     (*curr)->SetEndNode(false);     return !(*curr)->HasChildren() && !(*curr)->IsEndNode();   }    bool can_remove = remove_inner(key, i + 1, (*curr)->GetChildNode(key[i]), success);    if (can_remove) {     (*curr)->RemoveChildNode(key[i]);   }   return !(*curr)->HasChildren() && !(*curr)->IsEndNode(); } 

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

空模板变量值

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

template <typename T> T GetValue(const std::string &key, bool *success) {     return T();     return dynamic_cast<TrieNodeWithValue<T> *>(&(*(*curr)))->GetValue(); } 

并发安全

这个其实很简单，前 4 个测试都通过了，Insert、Remove、GetValue 三个函数开始和结束位置加锁和解锁就可以了，需要注意的是这三个函数如果彼此调用会死锁，比如 Insert 里面调用 GetValue 判断 key 是否存在。

这里提供一个 Go 语言中 defer 解锁的简易实现，如果你不知道 defer 就在每个返回的地方都解锁就可以。

class RLock {   ReaderWriterLatch *latch_;   public:   RLock(ReaderWriterLatch *latch) : latch_(latch) { latch_->RLock(); }   ~RLock() { latch_->RUnlock(); } };  class WLock {   ReaderWriterLatch *latch_;   public:   WLock(ReaderWriterLatch *latch) : latch_(latch) { latch_->WLock(); }   ~WLock() { latch_->WUnlock(); } }; 

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

bool Remove(const std::string &key) {   WLock w(&latch_);    if (!Exist(key)) {     return false;   }   bool success = false;   remove_inner(key, 0, &root_, &success);   return success; } 

写在最后

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