bustub 项目用 C++ 17 编写，但 C++ 11 已经够用。
C++ 相关教程：
关于GDB调试：
- Debugging Under Unix: gdb Tutorial
- GDB Tutorial: Advanced Debugging Tips For C/C++ Programmers
- Give me 15 minutes & I'll change your view of GDB [VIDEO]
git 命令：
PROJECT SPECIFICATION
该项目中，实现一个由并发 Trie 支持的kv存储。Trie 是一种有效的 ordered-tree 数据结构，用于检索给定键的值。为了简化解释，我们假设键都是非空的可变长度字符串，但实际上它们可以是任意类型。
Trie 中的每个节点存储一个键的单个字符，并且可以有多个子节点，这些子节点表示不同的可能的下一个字符。当到达一个键的结尾时，将设置一个标志来指示其对应的节点是一个结束节点。
在下面的示例中，trie 存储键 HELLO、 HAT 和 HAVE。
你将实现的kv存储能存储 map 到任何类型的 value 的 string key。key 对应的 value 值存储在表示该 key 的最后一个字符的结点（又称 terminal node）中。
例如，考虑在 trie 中插入 kv 对(“ ab”，1)和(“ ac”，“ val”)。这两个键共享同一个父节点 “a”。在左边的子节点中，与键 “ab” 对应的值 1 存储在节点 “b” 中，与键 “ac” 对应的值 “val” 存储在节点 “c” 中。
IMPLEMENTATION
您只需要修改 BusTub 中的一个文件 p0_ trie.h (src/include/primer/p0 _ trie.h)。除了测试代码之外，您不需要修改存储库中的任何其他文件。
函数原型和成员变量在文件中指定。该项目要求您填写所有构造函数、析构函数和成员函数的实现。如果您认为合适，可以添加任何其他的辅助函数和成员变量，但不要修改现有的函数和变量。
Task #1 - Templated Trie
在这个头文件中，我们定义了三个必须实现的类。我们建议您首先实现 Trie 类的单线程版本，然后再转向并发版本。
TrieNode Class
TrieNode 类在 Trie 中定义单个节点。TrieNode 保存 key 的一个字符，is_end flag 指示它是否标记 key string 的结束。child nodes 的 key 字符从成员变量 children_ 这个map 访问得到，它存储char 到 unique_ptr<TrieNode> 的映射。
注意：child node 为 unique_ptr，因此将它们分配给其他变量时需要小心。InsertChildNode 和 GetChildNode 都返回一个指向 unique_ptr 的指针，这样就可以在不制作 copy 或放弃所有权的情况下访问 unique_ptr 的数据。
最后，移动构造函数 TrieNode(TrieNode &&other_trie_node) 用于将旧 TrieNode 的 unique pointer 传输到新的 TrieNode。确保在传输数据时没有复制唯一指针。
TrieNodeWithValue Class
TrieNodeWithValue 类继承自 TrieNode，表示一个 terminal node，它的 key_char 是 key 的最后一个字符，该结点可保存任意类型 T的 value ，is_end_ flag 始终为 true。
当使用给定的 key 迭代一个 trie 树并到达最终字符时，你将根据不同场景调用 TrieNodeWithValue 的不同构造函数(详见 Trie Class 部分)。现在，你需要知道的是，TrieNodeWithValue (char key_char，T value) 构造函数根据给定的 key 的字符和 value 构建一个 TrieNodeWithValue。TrieNodeWithValue (TrieNode &&trieNode，T value) 构造函数从给定的 trieNode 中获取 unique_ptr 的所有权，并将它自己的 value_ 设置为给定的值。
Trie Class
Trie 类定义支持 insert、search、remove 操作的实际 Trie 树。Trie 树的根节点是所有 key 的起始节点，它本身不应该存储任何键字符。
Insert
要在 Trie 树中插入一个kv，首先要使用给定的 key 遍历该 Trie 树，若不存在 TrieNode，则插入。⚠️ 不允许插入一个重复的 key，应该返回 false。一旦到达 key 的最后一个字符，会有三种情况：
- 具有该字符的
TrieNode不存在。则需要调用TrieNodeWithValue (char key_char，T value)构造函数来创建具有指定 key_char 和 value 的 trie node。利用多态性 ——TrieNode类的unique_ptr也可存储TrieNodeWithValue类的unique_ptr。 - 具有该字符的
TrieNode存在，但不是 terminal node（is_end_==false）。这意味着unique_ptr指向的是TrieNode类对象而不是TrieNodeWithValue类对象。需要调用TrieNodeWithValue (TrieNode &&trieNode，T value)构造函数将旧TrieNode对象转为新的TrieNodeWithValue。 - 具有该字符的
TrieNode存在，且已是 terminal node（is_end_==true）这意味着unique_ptr已经指向一个TrieNodeWithValue类对象。应该立即返回 false，因为 key 不允许重复。
Remove
从 Trie 树中删除一个kv：
- 根据给定的 key 遍历该 Trie 树，若该 key 不存在，立即 return。
- 将 terminal node 的
is_end_flag 变为 false。 - 若 terminal node 没有任何child结点，将它从父结点的
children_map 中移除。 - 遍历 Trie 树并递归删除没有子结点的结点，当遇到有子结点的结点时就停止。
GetValue
对于给定的 key，返回对应的 value。若找不到 key 或提供的 type 与结点 value 的 type 不匹配，则将 success 设为 false。要检查这两种 type 是否相同，dynamic_cast raw TrieNode pointer to TrieNodeWithValue<T> pointer. 若转换结果为 nullptr 则 type T 与结点存储的 value 的类型不匹配。
Task #2 - Concurrent Trie
Trie 树需要保证 insert、search、remove 操作在多线程环境中工作。可使用 RwLatch（BusTub 对 readers-writer lock 的实现）或 C++ STL 的std::shared_mutex 来实现。
这个项目只需要你通过获取根节点的 read/write lock 来实现简单的并发控制。
GetValue函数应该从根结点获取一个 read lock（通过调用RwLatch的RLock方法）Insert和Remove操作应该从根结点获取一个 write lock（通过调用RwLatch的WLock方法）
若使用 RWLatch，请确保在函数返回之前解锁所有获取的锁，以避免死锁。
Testing
可以使用我们的测试框架来测试此任务的各个组件。我们对单元测试用例使用 GTest。
test/primer/starter_trie_test.cpp 文件包含了对以上三个类的测试。
测试前要删掉测试文件中各函数前的 DISABLED_ 前缀。
$ cd build
$ make starter_trie_test
$ ./test/starter_trie_test
提交
您将把您的实现提交给 Grescope：https://www.gradescope.com/courses/424375/
您只需在提交的 zip 文件中包含以下文件及其完整路径:
- src/include/primer/p0_trie.h
或者，在你的工作目录 (aka bustub, bustub-private, etc.) 运行