第 0 个 Project 名为 C++ Primer,目标是实现一个字典树(Trie),内容不难,主要是测试参与者的 Modern C++ 编程水平,对于选课的 CMU 学生如果感觉比较吃力可能就要劝退了。
Project 说明:Project #0 - C++ Primer
本节要实现的内容全部在 src/include/primer/p0_trie.h
文件中。
字典树(Trie)是一种有序的树形结构,能够存储键值对并高效地进行前缀匹配,详细介绍可以自行百度。例如插入两个键值对 ("ab", 1)
和 ("ac", "val")
,则形成下图的结构:
root 是根节点,不存储键;a 是一个非终结节点,只存储键;下层的两个节点是终结节点,除了键还要存储一个任意类型的值。每个节点有一个 map 存储以每个子节点的键索引的子节点。本节相应做出了如下设计:
TrieNode
表示非终结节点,成员为键,是否是终结节点的标记,子节点 map。TrieNodeWithValue
继承前者,表示终结节点,带有一个 T
类型的 value。二者可以通过 TrieNode
类中 is_end_
标识区分。Trie
类表示整个 Trie 树。
TrieNode
的子节点 map 存储的是子节点的智能指针 unique_ptr
而非裸指针。
注意:本节是在头文件中写代码,不要图方便写 using namespace std
!
需要注意的是移动构造函数(move constructor),由于 unique_ptr
表示独占性资源,没有拷贝构造函数,所以这里我们要用 std::move
。key_char_
和 is_end_
是简单的内置类型(primitive type),没必要使用 move 构造。
如果不理解为什么 T&&
参数需要 move
,可以参考 这个回答 或我之前的这篇博客《Effective Modern C++》学习笔记 - Item 23: 理解 std::move 和 std::forward。
注意因为 unique_ptr
是独占性指针不能拷贝,返回值是 unique_ptr
的指针。
先调用基类的构造函数,is_end_
是基类成员不能放在初始化列表中,放在函数体中赋值即可。
Trie 树的主类,这里要求实现的是增 Insert()
、删 Remove()
、查(GetValue)
三个函数。关于 lock_
下面会说明。
沿 Trie 树搜索到键的最后一个字符,过程中如果节点不存在就创建。对于最后一个键的字符分三种情况:
TrieNodeWithValue
,插入成功;is_end_
判断),将其转化为 TrieNodeWithValue
并把值赋给该节点,该操作不破坏以该键为前缀的后续其它节点(children_
不变),插入成功;先沿 Trie 树逐字符向下搜索给定键,如果中途发现不存在直接返回 false。找到后,将该节点的 is_end_
标为 false(此时虽然其值仍存在,但会被我们视为非终结节点)。如果该节点没有子节点,则可以删除。相应地还要向上回溯,如果其 parent 节点在移除该子节点后没有其它子节点,也删除。显然该函数可以有递归和非递归两种实现方式,我这里用非递归方式,在向下搜索时记录路径,回溯时反向遍历。因为使用智能指针,无需手动 delete 删除的 TrieNode
。
沿 Trie 树查找,如果键不存在,或者节点中存储的值类型与函数调用的类型 T
不一致,将 *success
标识设为 false。类型判断的方式是使用 dynamic_cast
。
要求 Trie 树能够并发访问,因此要加锁,具体也比较简单:GetValue()
时加读锁,Insert()
和 Remove
时加写锁。项目已经提供了一个读写锁类 RWLatch
,创建一个 private 成员 lock_
放在 Trie 中,上面代码也展示了加锁解锁的操作。注意解锁要覆盖所有执行路径。
将 test/primer/starter_trie_test.cpp
文件中 TEST()
包围的测试的名称的 DISABLED_
前缀去除,然后编译并运行测试:
cd build
make starter_trie_test
./test/starter_trie_test
看到如下输出说明通过所有测试:
运行代码格式化和规范检查:
make format
make check-lint
make check-clang-tidy-p0
必须改正所有提示,负责后续提交评分为 0。运行:
zip project0-submission.zip \
src/include/primer/p0_trie.h
生成压缩包,登录 GradeScope 并提交至 Project 0,得到以下结果则为完美通关~