# CMU-15445-Lab0-primer
# 环境配置
使用的是 Ubuntu 22.04
编译器版本为 clang-14
实验设定的语法标志为 C++17
源码下载地址: https://github.com/cmu-db/bustub/releases/tag/v20221128-2022fall
需要下载压缩包进行解压使用,要不然有一些地方已经有了新的更新已经和课程的代码不一样了
其他的就是跟着说明过一遍命令即可
最后测试环境是否搭建完成
cd bulid/test/ | |
make starter_trie_test | |
./starter_trie_test |
出现如下内容即表示搭建完成,便可以愉快的食用了
完整代码查看:https://github.com/charmber/basedata
首先需要完成的是 TrieNode
这个类
# TrieNodeInsertTest
是测试插入一个节点,所以直接找到 InsertChildNode
这个成员函数,通过注释了解到,需要传入一个 key
,作为这个节点的键名,然后再传入一个这个 TrieNode
类节点, key
和类当中的成员变量 key_char_
要保持一致,并且在类成员变量哈希表 children_
当中不能已经存在,那么就可以创建这个树节点
children_[key_char] = std::move(child); |
因为传入的为智能指针,所以需要使用 move 来转移所有权
# RemoveChildNode
测试删除一个节点,存在就删除
if (children_.count(key_char) == 0) { | |
return; | |
} | |
children_.erase(key_char); |
其他的函数没啥难度,根据注释完成就可以
# TrieInsertTest
在完成 Insert 函数之前需要先完成 Trie()
的构造函数,把首位节点的 key
置为 '\0'
Trie() { children_ = std::make_unique<TrieNode>('\0'); } |
根据要求可以知道,
如果传入 key 为空则返回 false
传入的 key 已经存在值也返回 false
如果传入的 key 存在,但没有值,则更新他的值
如果传入的 key 不存在,则创建并更新他的值
那么只需要遍历 key 的每一个字符串,并使用函数 GetChildNode(key[i]);
获取是否存在该 key[i]
auto tmp = new_children->get()->GetChildNode(key[i]); |
如果存在,那么就把该
k[i]
的节点给保存,以便下一次循环使用如果不存在,则创建该节点
tmp = new_children->get()->InsertChildNode(key[i], std::make_unique<TrieNode>(key[i]));
但是注意,只能遍历到倒数第二个字符,因为最后一个字符需要单独判断以下两种情况
最后一个字符节点存在,那么只需要判断
is_end_
该变量是否是可赋值状态auto q = new TrieNodeWithValue<T>(std::move(*(cur->get())), value);
cur->reset(q);
创建一个新的节点,然后使用原来节点
cur->reset()
重新指向新的节点即完成值的更新如果不存在,那么就直接创建并插入该节点,并赋值
new_children->get()->InsertChildNode(key[l - 1], std::make_unique<TrieNodeWithValue<T>>(key[l - 1], value));
# GetValue
该函数是为了获取传入 key
的值,只需要遍历 key 的每一个字符即可,如果其中任意一个字符不存在,则返回空
因为遍历的是基类 TrieNode
, 而值存在子类 TrieNodeWithValue
当中,存在从基类向子类进行向下强制转换关系,使用 dynamic_cast<TrieNodeWithValue<T> *>
函数进行强制类型转换
eg:基类向子类向下强制转换需要要求基类必须存在虚函数,原因可以看我另一篇博客
auto cur = dynamic_cast<TrieNodeWithValue<T> *>(tmp->get()); |
# RemoveTest
该函数是为了测试删除某一个键
如果需要删除的键的最后一个字符还存在子节点,那么则不可以删除该节点,只需要把 is_end
置为 false 即可,下次在插入的时候就可以重新赋值
if (node->get()->HasChildren()) { | |
node->get()->SetEndNode(false); | |
} |
否则,则依次递归从最后一个字符开始删除,每一次删除该字符前都需要先判断是否存在其他子节点
if (node->get()->HasChildren()) { | |
break; | |
} |
递归的方法可以使用遍历该键的每一个字符,并获取该节点,然后保存到栈或者容器当中,在删除时候从最后一个节点从后往前遍历,然后依次重复上述两个判断即可
for (auto i : key) { | |
tmp.emplace_back(node); | |
auto next = node->get()->GetChildNode(i); | |
if (next == nullptr) { | |
return false; | |
} | |
node = next; | |
} |
依次存入 tmp
当中,如果中途出现任何一个字符没有节点则直接返回 false,删除失败
tmp[i]->get()->RemoveChildNode(key[i]); | |
node = tmp[i]; |
调用 RemoveChildNode
函数删除,并保存上一个节点的值
# ConcurrentTest1
该函数主要是测试多线程情况下的增删节点
按照多线程的处理方法在共享数据的地方加入 latch_.WLock();
和 latch_.WUnlock();
即可
在函数返回的时候别忘记解锁