CMU 15-445 Project 0

project#0 主要的内容是要求你实现一个 trie 树,其目的有两个:

  • 检验你的 c++ 水平。如果你发现你在写这个 project 的时候是否吃力,那你就要考虑看看是否需要在进行这门课之前先把 c++ 的基础补充一下。

  • 测试你的开发环境。看看你的开发环境是否配置正确。若你能成功通过 project#0 的话,那么后面的 projects 就不会有环境问题。

关于学术诚信
按照 Andy 的要求,我不会把代码公布出来,只会分享做法。公开题解代码是违反学术诚信的行为!

这个 project 的思维难度不高,甚至可以说几乎没有,你需要做的只是按照注解所说明的内容把函数实现就好了。当然,在开始之前你需要对 trie 树的基本原理有所了解。

合理地使用 gdb 会对你的 coding 过程有很大的帮助,这是 project 官方给出的一些学习资料:

本 project 的难点有以下:

  • std::unique_ptr,这是 c++11 为了解决多指针问题引入的一个解决方案。这是本 project 的一大难点,你需要理解他的 ownership 的定义和用法,合理地使用 std::move() 函数来转移指针的 ownership。

  • && 右值引用。请查阅相关资料。

unique_ptr 智能指针的特性是同时只能有一个指针指向某一个地址。若这个指针被销毁了,那么其指向的对象也会被销毁。这个特性使得指针之间的赋值和参数的传递会变得十分困难。

在传递智能指针作为参数的时候,其类型通常被设置为 && 即右值引用。在调用函数的时候使用 std::move(unique_ptr) 的方式把指针传递进去:func(std::move(unique_ptr))。不能使用普通类型是因为 c++ 的普通参数的传递方式是复制,而智能指针不能直接复制,不然就会有多个指针同时指向一个地址。而 move 函数的作用是把其 ownership(所有权)进行转移,转移后原来的指针会变为 nullptr,转移后的指针就是一个典型的符合右值引用的变量。

在 class Trie 里面有一个成员变量 latch_,其作用是用来表示当前 trie 是否正在进行读取或写入。记得在实现相关函数的时候及时更改其状态。

std::make_unique<T>(args..) 函数返回一个 std::unique_ptr<T> 对象。

Note
其参数 args.. 指的是类型 T 的构造参数,而不是一个 T 对象。

我一直遇到这样一个报错:

./pics/image-20230629115100715.png

./pics/image-20230629115145573.png

其实报错信息非常多,不过这两个是用红色标出来的,其他的都是白色的信息。但是我一直找不到我的构造函数哪里有问题。直到我发现了这个信息……

./pics/image-20230629115357892.png

这是一个 note 提示,告诉我可能无法正确初始化。于是我找到对应的代码,发现我的写法是这样的:

./pics/image-20230629115500965.png

然后我查询了一下 std::make_unique() 的用法,发现他的用法是:

./pics/image-20230629115642647.png

原来他的参数是构造函数的参数!只能说 c++ 的报错提示太烂了!

  • unique_ptr:
    • .reset():重新赋值
    • .get():获取指针指向的值
  • std::move():转移 ownership
  • std::forward():传递参数时保留左值/右值性