Project specification
在这个项目中, 你将要实现由一个 copy on write 的 字典树 支持的 KV 存储, 字典树是一个高效且有序的数据结构, 用于根据给定的 Key 来取回 Value. 为了简化说明,我们假设 Key 是可变长度的字符串, 但是在实际情况上它们可以是任意类型.
字典树中的每个节点可以都多个子节点，表示不同的可能的下一个字符.
你将实现的 KV 存储将会将字符串 Key 来映射到任意类型的 Value, Key 的 Value 将存储在该字符串的最后一个字符上(aka. terminal
node). 比如, 考虑插入 KV 键值对 ("ab",1) 和 ("ac","val") 到字典树中.
这两个 Key 共享相同的父节点. 与 "ab" 对应的 Value 存储在左边, 而 "ac" 对应的 Value 存储在右边.
Task #1 Copy On Write Trie
在这个任务中, 你需要修改 trie.h 和 trie.cpp 来实现一个 Cow trie. 在一个 Cow trie 中, 操作不直接修改原始节点.
相反的，在修改数据时会创建一个新的节点, 并返回一个新的根节点来表示新修改的 trie. Cow 允许我们在每个操作后的任意时间以最小的花销访问
trie. 考虑插入 ("ab",2) 到上面的示例中. 我们通过重用原来 trie 两个子节点来创建一个新的节点 Node2, 并创建一个新的节点存放
Value 2.
如果我们插入 ("b",3), 我们将创建一个新的根节点, 新节点将重用原先的节点. 在这种方式下，我们可以获取每次插入前和后的 trie
的内容, 我们就可以访问那个时间点的 trie 的内部数据.
还有一个例子: 如果我们插入 ("a","abc") 然后移除 ("ab",1)，我们可以得到下面的 trie. 注意父节点可以有 Value, 以及你需要在
removal 后清除所有不必要的节点. 一个空的 trie 可以使用 nullptr 来表示.
你的 trie 必须支持 3 中操作:
Get(key): 获取 key 对应的 valuePut(key,value): 将 value 映射到 key. 如果 key 以及存在, 则覆盖原先的 value. 注意, 值的类型可能是不可复制的(i.e., std::unique_ptr< int >). 这个方法返回一个新的 trie.Delete(key): 删除 key 对应的 value. 这个方法返回一个新的 trie.
不应该直接在当前 trie 上执行这些操作. 你应该创建新的 trie 节点, 并尽可能重用现有节点.
要创建一个全新的节点(没有子节点的节点), 你可以使用 TrieNodeWithValue 构造函数来构造对象然后将其转换为 smart pointer.
要进行 Cow 创建节点, 你应该使用 TrieNode 的 Clone 函数. 要在新 trie 中重用现有节点, 你可以复制 std::shard_ptr< TrieNode >: 复制共享指针时不会复制底层数据. 你不应该在该项目中使用 new 和 delete 来手动分配内存. 当没有任何人引用底层对象时 std::shared_ptr
将会释放对象.
有关这些操作的所有规范, 请参阅起始代码中的注释. 你的实现应该参照上述方式存储数据. 不要存储 c 中的字符串终止符 \0 到你的 trie 中.
另外，请避免删除类定义中的任何 const 或者使用 mutable/const_cast 来绕过 const 检查.