Hello world
CMU15-445 Project0 Cpp Primer
💡 这个项目大概是 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。这里给出代码实现：
template <typename T>
bool Insert(const std::string &key, T value) {
if (key.empty()) {
return false;
}
TrieNode *parent = nullptr;
TrieNode *node = root_.get();
for (char key_char : key) {
parent = node;
if (node->HasChild(key_char)) {
node = node->GetChildNode(key_char)->get();
} else {
std::unique_ptr<TrieNode> child = std::make_unique<TrieNode>(key_char);
auto child_ptr = node->InsertChildNode(key_char, std::move(child));
if (child_ptr == nullptr) {
return false;
}
node = child_ptr->get();
}
}
// node is the last node of the key
// 1. node is end node, return false
if (node->IsEndNode()) {
return false;
}
// 2. node is not end node, convert it to end node
auto child_with_value = std::make_unique<TrieNodeWithValue<T>>(std::move(*node), value);
parent->RemoveChildNode(key.back());
parent->InsertChildNode(key.back(), std::move(child_with_value));
return true;
}
Read more ⟶
Update 实现
如何在 miniob 上实现 update 语句
Read more ⟶
Drop Table 实现
如何在 miniob 中实现 Drop Table
Read more ⟶