原文链接：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> 表示唯一的指向类型为 T 的对象的指针，因此需要使用移动语义 std::move，代码中 children_ 的类型嵌套了 std::unique_ptr<t></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></trienode> 转发右值引用。
TrieNodeWithValue(TrieNode &&trieNode, T value) : TrieNode(std::forward(trieNode)) {
this->value_ = value;
this->is_end_ = true;
}
父子指针转换
TrieNodeWithValue 是模板类，没法办使用多态， Trie::GetValue 需要将 unique_ptr<trienode></trienode> 转换为 TrieNodeWithValue<t>*</t> 后调用 TrieNodeWithValue::GetValue。
std::unique_ptr uptr = std::make_unique>('a', T());
dynamic_cast*>(&(*uptr))->GetValue();
可能有更优雅的办法，但我实在是想不出来了，C++ 可真难写啊。
所有权规避
std::unique_ptr<t></t> 的传递一定是使用移动语义转移 T 对象地址的所有权，但也可以不获取所有权访问 T 对象的地址，代码里的注释也引导我们使用这种方式。
std::unique_ptr 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>(std::move(*(*curr)), value);
节点删除
根据代码注释的提示， Remove 函数是要递归删除的，这里给出递归的框架。
bool remove_inner(const std::string &key, size_t i, std::unique_ptr *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
T GetValue(const std::string &key, bool *success) {
return T();
return dynamic_cast *>(&(*(*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 (前缀树)，先能写出简单的字典树再动手。如果需要代码的话可以私信我。如果想做数据库的工作欢迎找我内推（恰点内推奖金）。
Original: https://www.cnblogs.com/suqinglee/p/16684055.html
Author: 李素晴
Title: CMU 15-445 Project 0 实现字典树
原创文章受到原创版权保护。转载请注明出处：https://www.johngo689.com/611260/
转载文章受原作者版权保护。转载请注明原作者出处！