cmu15445.md

CMU15445 2022 笔记

1. https://15445.courses.cs.cmu.edu/fall2022/bustub/
2. https://zhuanlan.zhihu.com/p/592547524
3. https://zhuanlan.zhihu.com/p/571927310
4. https://15445.courses.cs.cmu.edu/fall2022/bustub/

Project 0

TrieNode

class TrieNode{
public:
    explicit TrieNode(char key_char){}
    TrieNode(TrieNode &&other_trie_node) noexcept{}
    virtual ~TrieNode() = default;
    bool HasChild(char key_char) const {}
    bool HasChildren() const {}
    bool isEndNode() const {}
    char GetKeyChar() const {}
    std::unique_ptr<TrieNode> *InsertChildNode(char key_char, std::unique_ptr<TrieNode> &&child) {}
    std::unique_ptr<TrieNode> *GetChildNode(char key_char){}
    void RemoveChildNode(char key_char){}
    void SetEndNode(bool is_end){}
protected:
    char key_char_;
    bool is_end_{false};
    std::unordered_map<char,std::unique_ptr<TrieNode> children_;
};

TrieNodeWithValue

template<typename T>
class TrieNodeWithValue: public TrieNode{
private:
    T value_;
public:
    TrieNodeWithValue(TrieNode &&trieNode, T value){}
    TrieNodeWithValue(char key_char, T value){}
    ~TrieNodeWithValue() override = default;
    T GetValue() const {return value_;}
};

构造父类

TrieNodeWithValue 是 TrieNode 的子类，构造子类时，如果没有手动在子类的构造函数中构造父类，就会调用父类的默认构造函数，而代码中父类是没有默认构造函数的，所以需要手动在子类中构造父类。

需要使用 std::forward<TrieNode> 转发右值引用。

TrieNodeWithValue(TrieNode &&trieNode, T value) : TrieNode(std::forward<TrieNode>(trieNode)) {
    this->value_ = value;
    this->is_end_ = true;
}

Tire

class Trie{
private:
    std::unique_ptr<TrieNode> root_;
    ReaderWriterLatch latch_;
public:
    Trie() = default;
    template<typename T>
    bool Insert(const std::string &key, T value){}
    bool Remove(const std::string &key) {}
    template<typename T>
    T GetValue(const std::string &key, bool *success){}
};

Setting Up Your Development Environment

# Linux
$ sudo build_support/packages.sh
$ mkdir build
$ cd build
$ cmake -DCMAKE_BUILD_TYPE=Debug ..
$ make -j$(nproc)

Testing

$ cd build
$ make starter_trie_test
$ ./test/starter_trie_test

Make sure that you remove the DISABLED_ prefix from the test names otherwise they will not run!

Formatting

$ make format
$ make check-lint
$ make check-clang-tidy-p0
$ make check-format

Submission

$ zip project0-submission.zip \
    src/include/primer/p0_trie.h 

参考

1. https://ym9omojhd5.feishu.cn/docs/doccnM3F37WfhkcFYREGLOk2zhe#
2. csdn晰烟

Project 1

参考

1. https://zhuanlan.zhihu.com/p/571927310

2. https://ym9omojhd5.feishu.cn/docx/doxcni6IUShGqTCf8R1WxwZ9rbg