2022 FALL CMU15445：lab0

环境配置

2022官网，跟着配置即可，推荐使用linux，windows/docker官网不推荐，个人不推荐mac，因为mac的新版本发布后导致gdb使用困难

Task #1 - Templated Trie

leecode上有个相近的实现，可以先做做：208:Tire实现。对比起来只有一个remove删除和prefix查找不同，其他的都大同小异

​ 给出UML类图：

​ 基本上对着图就能写个大概，最重要的部分就是Tire里的

bool Insert(...argvs);
bool Remove(...argvs);
T GetValue(...argvs);

​ 实际在实现过程中需要一些c++11的知识，包括但不限于

• smart pointer：std::unique_ptr< ClassName>, std::make_unique< ClassName>
• move constructor and perfect forwarding：std::move(), Constructor(ClassName &&obj)
• cast：dynamic_cast< ClassName1 *>(ClassName2 *)

​ 上面的内容会用到一些基本的语法，但是使用时都是串起来用的。比如unique_ptr注定了只能用std::move传递rvalue参数和onwership，只能用移动构造而不是拷贝构造。

​ 同时，假如你使用’=‘来触发移动构造，而如果你的move constructor标注了expilcit，那么就会失败。

​ 最后的cast必须只能在单继承关系，多态时（至少一个virtual function）的指针转换里使用（这里给的继承关系很简单）

Task #2 - Concurrent Trie

​ header里面给了读写锁，但是在实现过程中多分支判断结束前都写个unlock显然非常麻烦。如果你写过/了解过smart pointer的简单实现。可以模仿lock_guard写个简单版本（RAII机制）

class RLockGuard{
  public:
    RLockGuard(ReaderWriter *latch):latch_(latch){latch_->RLock();}
    ~RLockGuard(){latch_->RUnlock();}
  private:
	ReaderWriter *latch_;
};
class WLockGuard{
  public:
    WLockGuard(ReaderWriter *latch):latch_(latch){latch_->WLock();}
    ~WLockGuard(){latch_->WUnlock();}
  private:
	ReaderWriter *latch_;
};

​ 这样就可以在开头lock，在函数结束时自动调用析构函数unlock

跑分结果

Donate