哪些公司可以建设网站,自己在线制作logo免费版,国外扁平化网站设计欣赏,wordpress增加英文在线测试 本地测试
Project #0 - C Primer
以下是Project #0的网址#xff0c;2022FALL的Project #0本质上是实现一棵字典树#xff0c;关于字典树的相关内容可以参考C实现字典树。
在本题中#xff0c;为了存储对应着字符串的任意类型值#xff0c;题目设计了一个Tri…在线测试 本地测试
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中我们需要实现以下功能构造函数、根据字符串和对应的值插入一系列新的节点、根据字符串删除一系列节点、根据字符串返回对应的值并返回成功与否的标记。值得注意的是我们在设计这三个函数时还需要考虑多线程的实现。
总结
移动构造函数的第一个参数一定是一个右值引用同时需要确保移动之后源对象是销毁无害的这也是右值引用的一个特点。使用移动构造函数代替拷贝构造函数不需要分配内存更能节省空间。C11提供了两种智能指针shared_ptr和unique_ptr其区别体现在shared_ptr允许多指针指向同一对象unique_ptr则独占所指向的对象。其中考虑到unique_ptr独占的特性我们能够利用这一特性来实现对象的管理值得注意的是这相应也会导致我们在函数中进行传参时无法直接使用unique_ptr需要使用get函数将其转化为裸指针。也因为基于独占的特性unique_ptr能够避免内存泄漏和更大的开销更值得使用。forward函数与move函数类似但forward函数能够保持原始实参的类型能够确保其左右值不变化。项目中内置的读写锁实际上是基于shared_mutex实现的其函数内部也是对shared_mutex的调用。其特点体现在读写锁上在进行读操作时所有线程都能够进行访问在进行写操作时只能由一个线程进行独占。因此我们为了实现多线程操作需要着重对写操作进行保护即在插入和删除时需要使用读写锁。我们在进行操作时需要多插入的多种情况进行考虑并设计相应的操作是新建节点还是转移原有节点。同时考虑到我们根据字符串进行遍历因此当字符串遍历完成时我们抵达的节点就是末端节点我们在末端节点的基础上对其进行修改即可。考虑到节点不容易进行复制我们可以直接新建节点或转移节点使用reset函数进行更新。在删除中考虑到在一些情况下我们需要删除一连串的节点我们最终通过栈进行实现。我们在进行遍历时将所有遍历到的节点指针都压入栈中而后我们不断弹出栈顶元素从下向上进行删除若其子节点不为空且子节点有孩子则说明该子节点可能被其他字符串使用不能进行删除否则可以直接删除子节点。在设计GetValue函数时我们需要考虑返回类型不同的情况最终使用强制转化dynamic_cast实现。若转换后指针不为空说明类型相同否则success需要设置为false。在执行clang-format时发现提示无权限执行脚本文件。最后查找可以发现相应的文件权限为rw可读可写不可执行文件我们可以使用sudo chmod -R 777 xxx来修改权限为rwx可读可写可执行文件最后进行执行即可。
