原文链接: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 (前缀树),先能写出简单的字典树再动手。如果需要代码的话可以私信我。如果想做数据库的工作欢迎找我内推(恰点内推奖金)。
来源:https://www.cnblogs.com/suqinglee/p/16684055.html
本站部分图文来源于网络,如有侵权请联系删除。