CMU15-445 Project0 CppPrimer
2023-4-22|2023-4-23
wuxiaobai24
type
status
date
slug
summary
tags
category
icon
password
这个项目大概是 1月 19 号时完成的了，但是一直没有时间好好梳理一遍，拖到了年后了。虽然是 Project 0，但是如果对 C++ 的一些新语法不熟悉的话，还是会有点难受的。这里只是简单的记录过程和一些实现时的想法，不会公开所有源码。
Task 1 - Template Trie
这个任务主要实现三个类，
TrieNode，TrieNodeWithValue 和 Trie。TrieNode 是节点基类，它的实现就比较简单，只需要按照注释写就行，没有很复杂。这个基类存储了 TireNode 中的key_char，is_end和子节点指针children。并主要维护这三个成员的相关函数。TrieNodeWithValue 这是继承了TireNode的模板类，首先它既是TireNode的子类，所以它的指针可以存储在TireNode的子节点指针map中，与普通的TireNode链接在一起。同时它又是一个模板类，模板参数是存储的Value的类型，因此通过特化TireNodeWithValue可以将不同类型的值存储在该节点中。同时代码里还约定了，TireNodeWithValue的
is_end为true，而不包含值的is_end为false，这样在运行期也可以方便的判断是否为EndNode。Tire 是这个 Task 的主要难点，几乎所有代码量都在这个类中了，它主要包含以下几个接口
Insert<T>(key, value)，Remove(key)和GetValue<T>(key)。首先是
Insert<T>(key, value)，这里需要遍历key中所有字符，然后逐步沿着树进行查找或者插入操作。这里为了方便实现，所以在查找中进行插入时直接TireNode插入到树中，没有对最后一个字符进行特殊处理（最后一个字符需要插入的是TireNodeWithValue），而是在完成遍历后，再将最后一个节点转换为TireNodeWithValue。这里给出代码实现：然后是
Remove(key)接口，这个接口应该是最复杂的一个接口了。它先需要和Insert一样进行一次查找操作，不同的是这里需要用栈存储住所有遍历过的节点，然后再尝试移除最后一个节点，如果最后一个节点没有子节点，就直接删除该节点，如果有则需要把该节点转换为TireNode。最后再从栈中不停pop节点出来，看当前节点是否为 EndNode 或者存在子节点，如果是就直接退出即可，否则就需要删除该节点，并继续从栈中 pop 节点。最后是
GetValue这个接口，这个就比较简单了，只需要按key的字符不断在Tire中进行查找即可，最好再将TireNode转换为TireNodeWithValue再取值即可。这里还学到了一个技巧：dynamic_cast转换失败时返回的是nullptr。Task 2 - Concurrent Tire
让
Tire支持并发，只需要在Tire三个接口上获取对应的锁并在退出时释放即可，这个只需要注意一下别因为没有释放锁导致死锁的情况即可。Testing
文档已经写得比较全面了，但是在
MacOS上似乎还有点问题，因为默认安装了 clang@14，所以得修改一下CMakeLists.txt：