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
:![notion image](https://www.notion.so/image/https%3A%2F%2Fs3-us-west-2.amazonaws.com%2Fsecure.notion-static.com%2Fefcbb15b-6a62-4f26-9e26-872edbc5484e%2FUntitled.png?table=block&id=e16b9c87-0b84-4640-9d09-aec91769c5d7)