原文鏈接：https://juejin.cn/post/7139572163371073543 項目準備代碼、手冊本文對應 2022 年的課程，Project 0 已經更新為實現字典樹了。C++17 的開發環境建議直接下載 CLion，不建議自己瞎折騰。測試 $ mkdir build && ...

原文鏈接：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 (首碼樹)，先能寫出簡單的字典樹再動手。如果需要代碼的話可以私信我。如果想做資料庫的工作歡迎找我內推（_{恰點內推獎金}）。

CMU 15-445 Project 0 實現字典樹