CMU15-445 Project.0总结

在线测试

本地测试

Project #0 - C++ Primer

以下是Project #0的网址，2022FALL的Project #0本质上是实现一棵字典树，关于字典树的相关内容可以参考C++实现字典树。

在本题中，为了存储对应着字符串的任意类型值，题目设计了一个Trie模板用于加速查询。我们可以将字符串中的每一个字符都当作是一个节点，根据字符之间的前后顺序我们可以构建出一个树结构，利用树结构进行查询能够避免我们每次都需要遍历所有存储的字符串，从而加快我们获得对应值的速度。

在每个节点当中，我们首先设计了最基础的节点类TrieNode，它包括了对应的字符key_char_，用于判断是否为字符串终点的布尔变量is_end_，以及用于记录子节点的哈希表children_。其中，在哈希表中以字符和unique_ptr为键值对进行存储。在TrieNode中，我们需要能够实现几个功能，包括了构造函数、移动构造函数、析构函数、根据key_char判断是否有对应的子节点、判断有无子节点、判断是否为字符串末端节点、获得当前节点对应的字符值、根据字符值和指向节点的指针插入新的子节点、根据字符值获得子节点、根据字符值删除子节点和修改布尔变量is_end_。

而后，我们设计了TrieNodeWithValue用于表示作为字符串终点的节点，它在其他方面与TrieNode类似，区别仅在于is_end_为真。同时我们给他添加了新属性value_用于表示字符串对应的值。在TrieNodeWithValue中，我们通向需要实现以下功能：构造函数、移动构造函数、析构函数、获得value_的值。

最后，我们需要设计Trie类，它整合了上述两个类，包括了根节点和读写锁。在Trie中，我们需要实现以下功能：构造函数、根据字符串和对应的值插入一系列新的节点、根据字符串删除一系列节点、根据字符串返回对应的值，并返回成功与否的标记。值得注意的是，我们在设计这三个函数时，还需要考虑多线程的实现。

总结

1. 移动构造函数的第一个参数一定是一个右值引用（&&），同时需要确保移动之后源对象是销毁无害的，这也是右值引用的一个特点。使用移动构造函数代替拷贝构造函数不需要分配内存，更能节省空间。
2. C++11提供了两种智能指针shared_ptr和unique_ptr，其区别体现在shared_ptr允许多指针指向同一对象，unique_ptr则独占所指向的对象。其中，考虑到unique_ptr独占的特性，我们能够利用这一特性来实现对象的管理，值得注意的是，这相应也会导致我们在函数中进行传参时无法直接使用unique_ptr，需要使用get函数将其转化为裸指针。也因为基于独占的特性，unique_ptr能够避免内存泄漏和更大的开销，更值得使用。
3. forward函数与move函数类似，但forward函数能够保持原始实参的类型，能够确保其左右值不变化。
4. 项目中内置的读写锁实际上是基于shared_mutex实现的，其函数内部也是对shared_mutex的调用。其特点体现在读写锁上，在进行读操作时所有线程都能够进行访问，在进行写操作时只能由一个线程进行独占。因此我们为了实现多线程操作，需要着重对写操作进行保护，即在插入和删除时需要使用读写锁。
5. 我们在进行操作时需要多插入的多种情况进行考虑，并设计相应的操作：是新建节点还是转移原有节点。同时考虑到我们根据字符串进行遍历，因此当字符串遍历完成时我们抵达的节点就是末端节点，我们在末端节点的基础上对其进行修改即可。
6. 考虑到节点不容易进行复制，我们可以直接新建节点或转移节点，使用reset函数进行更新。
7. 在删除中，考虑到在一些情况下，我们需要删除一连串的节点，我们最终通过栈进行实现。我们在进行遍历时，将所有遍历到的节点指针都压入栈中，而后我们不断弹出栈顶元素，从下向上进行删除，若其子节点不为空且子节点有孩子则说明该子节点可能被其他字符串使用，不能进行删除，否则可以直接删除子节点。
8. 在设计GetValue函数时，我们需要考虑返回类型不同的情况，最终使用强制转化dynamic_cast实现。若转换后指针不为空说明类型相同，否则success需要设置为false。
9. 在执行clang-format时，发现提示无权限执行脚本文件。最后查找可以发现相应的文件权限为rw可读可写不可执行文件，我们可以使用sudo chmod -R 777 xxx来修改权限为rwx可读可写可执行文件，最后进行执行即可。