原文鏈接：https://juejin.cn/post/7139572163371073543
專案準備
代碼、手冊
本文對應 2022 年的課程，Project 0 已經更新為實作字典樹了，C++17 的開發環境建議直接下載 CLion，不建議自己瞎折騰，
測驗
$ mkdir build && cd build
$ cmake -DCMAKE_BUILD_TYPE=DEBUG ..
$ make starter_trie_test
$ ./test/starter_trie_test
運行上面的指令，你會得到如下輸出，這不表示該專案的 5 個測驗用例沒過，而是沒有執行，
[==========] Running 0 tests from 0 test suites.
[==========] 0 tests from 0 test suites ran. (0 ms total)
[ PASSED ] 0 tests.
YOU HAVE 5 DISABLED TESTS
需要修改 test/primer/starter_trie_test.cpp 檔案，移除測驗名 DISABLED_ 前綴，
// TEST(StarterTest, DISABLED_TrieNodeInsertTest)
TEST(StarterTest, TrieNodeInsertTest)
格式化
$ make format
$ make check-lint
$ make check-clang-tidy-p0
除錯日志
LOG_INFO("# Pages: %d", num_pages);
LOG_DEBUG("Fetching page %d", page_id);
專案介紹
使用支持并發的字典樹實作一個鍵值存盤，字典樹是一種高效的排序樹，用于檢索指定鍵值，這里假設鍵都是非空的可變長度字串，但事實上鍵可以是任意型別，
上圖所示字典樹中存盤了：HAT、HAVE、HELLO 三個鍵，
上圖所示字典樹存盤了：ab=1、ac="val" 兩組鍵值，
專案實作
只需要修改一個檔案：src/include/primer/p0_trie.h
專案已經定義好了類和成員變數，以及需要實作的成員函式的簽名，可以添加輔助變數或函式，但不能修改已有變數和函式簽名，
任務一
檔案中定義了 Trie、TrieNode、TrieNodeWithValue 三個類，建議先實作單執行緒版本，再改并發版本，類中的成員變數和成員函式都有注釋，
任務二
實作并發安全的字典樹，可以使用 BusTub 的 RwLatch 或 C++ 的 std::shared_mutex，
一些 C++ 的基操
一年多沒寫 C++ 了，用慣了 Go，突然用 C++ 寫的腦殼疼，沒用過 C++ 的小伙伴可能想編譯通過都費勁，這里貼一下需要了解的 C++ 特性，
移動語意
std::unique_ptr<T> 表示唯一的指向型別為 T 的物件的指標，因此需要使用移動語意 std::move，代碼中 children_ 的型別嵌套了 std::unique_ptr<T>，也需要使用移動語意，
TrieNode(TrieNode &&other_trie_node) noexcept {
key_char_ = other_trie_node.key_char_;
is_end_ = other_trie_node.is_end_;
children_ = std::move(other_trie_node.children_);
}
構造父類
TrieNodeWithValue 是 TrieNode 的子類，構造子類時，如果沒有手動在子類的建構式中構造父類，就會呼叫父類的默認建構式，而代碼中父類是沒有默認建構式的，所以需要手動在子類中構造父類，
需要使用 std::forward<TrieNode> 轉發右值參考，
TrieNodeWithValue(TrieNode &&trieNode, T value) : TrieNode(std::forward<TrieNode>(trieNode)) {
this->value_ = value;
this->is_end_ = true;
}
父子指標轉換
TrieNodeWithValue 是模板類，沒法辦使用多型，Trie::GetValue 需要將 unique_ptr<TrieNode> 轉換為 TrieNodeWithValue<T>* 后呼叫 TrieNodeWithValue::GetValue，
std::unique_ptr<TrieNode> uptr = std::make_unique<TrieNodeWithValue<T>>('a', T());
dynamic_cast<TrieNodeWithValue<T>*>(&(*uptr))->GetValue();
可能有更優雅的辦法，但我實在是想不出來了，C++ 可真難寫啊，
所有權規避
std::unique_ptr<T> 的傳遞一定是使用移動語意轉移 T 物件地址的所有權，但也可以不獲取所有權訪問 T 物件的地址，代碼里的注釋也引導我們使用這種方式，
std::unique_ptr<int> uptr(new int(1));
std::cout << *uptr << std::endl; // 1
auto *p = &uptr;
*(*p) = 2;
std::cout << *uptr << std::endl; // 2
代碼實作
大部分代碼按照注釋一步一步來就沒問題，課程規定不公開代碼，所以這里只列一些難點，
回圈迭代
這里給出一個模版，對于尾節點和非尾節點，一般需要不同的操作，
auto curr = &root_;
size_t i = 0;
while (i + 1 < key.size()) {
curr = (*curr)->GetChildNode(key[i]);
i++;
}
// end_node
curr = (*curr)->GetChildNode(key[i]);
節點轉換
在插入流程中，當迭代到最后一個字符時，發現已經有了一個 TrieNode 型別的節點，需要轉換為 TrieNodeWithValue 型別，
* When you reach the ending character of a key:
* 2. If the terminal node is a TrieNode, then convert it into TrieNodeWithValue by
* invoking the appropriate constructor.
不熟悉 C++ 的話這個操作可能有點困難，這里給出代碼，這一層又一層的括號和解參考確實不夠優雅，但一時間也想不到其他好辦法，
(*curr) = std::make_unique<TrieNodeWithValue<T>>(std::move(*(*curr)), value);
節點洗掉
根據代碼注釋的提示，Remove 函式是要遞回洗掉的，這里給出遞回的框架，
bool remove_inner(const std::string &key, size_t i, std::unique_ptr<TrieNode> *curr, bool *success) {
if (i == key.size()) {
*success = true; // Remove 的回傳值，表示成功洗掉
(*curr)->SetEndNode(false);
return !(*curr)->HasChildren() && !(*curr)->IsEndNode();
}
bool can_remove = remove_inner(key, i + 1, (*curr)->GetChildNode(key[i]), success);
if (can_remove) {
(*curr)->RemoveChildNode(key[i]);
}
return !(*curr)->HasChildren() && !(*curr)->IsEndNode();
}
remove_innner 的回傳值表示傳入節點是否可以洗掉，可以洗掉的條件是該節點無子節點且非尾節點，函式內判斷當前節點的子節點是否可以洗掉，并回傳當前節點是否可以洗掉，出口是遞回到了傳入 key 的尾節點，取消尾節點標記，并回傳是否可以洗掉，該函式呼叫前還需要判斷一下 key 是否存在，
空模板變數值
GetValue 的回傳值是一個模板型別，錯誤的時候直接 return T()，正常情況下，需要轉換 TrieNode 為 TrieNodeWithValue 中獲取值，上文提過該父子類轉換的辦法，
template <typename T>
T GetValue(const std::string &key, bool *success) {
return T();
return dynamic_cast<TrieNodeWithValue<T> *>(&(*(*curr)))->GetValue();
}
并發安全
這個其實很簡單，前 4 個測驗都通過了，Insert、Remove、GetValue 三個函式開始和結束位置加鎖和解鎖就可以了，需要注意的是這三個函式如果彼此呼叫會死鎖，比如 Insert 里面呼叫 GetValue 判斷 key 是否存在，
這里提供一個 Go 語言中 defer 解鎖的簡易實作，如果你不知道 defer 就在每個回傳的地方都解鎖就可以，
class RLock {
ReaderWriterLatch *latch_;
public:
RLock(ReaderWriterLatch *latch) : latch_(latch) { latch_->RLock(); }
~RLock() { latch_->RUnlock(); }
};
class WLock {
ReaderWriterLatch *latch_;
public:
WLock(ReaderWriterLatch *latch) : latch_(latch) { latch_->WLock(); }
~WLock() { latch_->WUnlock(); }
};
使用方式如下，以 Remove 為例，
bool Remove(const std::string &key) {
WLock w(&latch_);
if (!Exist(key)) {
return false;
}
bool success = false;
remove_inner(key, 0, &root_, &success);
return success;
}
寫在最后
動手開始專案前，可以先去 leetcode 過一遍 實作 Trie (前綴樹)，先能寫出簡單的字典樹再動手，如果需要代碼的話可以私信我，如果想做資料庫的作業歡迎找我內推（恰點內推獎金），
轉載請註明出處，本文鏈接：https://www.uj5u.com/shujuku/506171.html
標籤：其他