C++ primer

这个lab比较简单，实际上是对C++能力和数据结构能力的锻炼，具体要求是实现一个Trie（前缀树）。

智能指针和移动构造

• 移动构造并不像rust中的所有权机制那样严格限制move的对象不能被访问

• 移动构造只是不类似copy构造那样，它有一种语意上的区别，希望构造完成新的对象之后，原来的对象的内容被清除为默认值
• 以unique_ptr为例，move并不会让原来的unique_ptr失效，只会改原来的unique_ptr为nullptr

• 所以，当我们在编写move构造函数时，实际要做的就是将原对象的指针steal到现在的对象中去，同时将原对象指针置空，原对象对应的栈空间是还在的，堆空间也没动，但是指针被偷了
• 在这个lab中，更方便，我们使用unique_ptr来管理，所以在编写move构造时，只需要move unique_ptr

move和forward

• 这里小提一嘴：move是将一个对象转换成右值引用，forward的作用则是保持对象原有的左右值属性不变，用于不同的处理流程。

前缀树Trie

可以先做一下leecode 208. 实现 Trie (前缀树) - 力扣（LeetCode）

• 每个节点有三个成员
  • 该节点对应的字符
  • Bool 该节点是否是最后一个节点
  • 字节点对应字符和指针的map
• 节点相连组成了树，树只需要维护好根节点即可
  • 对于最后一个节点，设置对应的bool flag即可，无需引入空节点

本lab的特化

智能指针的使用

• 对于每个节点，只可能构建一个指针，所以使用unique_ptr来管理对应的生命周期，同时也需要进行move在必要的时候

这个lab想要利用前缀树来进行索引，也就是将key存入前缀树，key的最后一个node需要包含对应的value，所以首先需要从普通的Node拓展到包含value的Node：

• 从Node继承而来，一个泛型class TrieNodeWithValue ：包含一个 T value_
• 对于Trie中的key，找到最后一个char，它对应的Node应该被设置为TrieNodeWithValue，设置bool flag为最后，并放入对应的value

还需要考虑一些细节

• 树的并发，加锁和解锁的时机（或许可以使用每个节点一个锁，向父节点加意向锁等复杂的管理方式，但是没必要，这里只需要一把锁即可）
• 树的遍历：不愿使用递归，迭代的过程中需要一个指针指向当前Node
  • 可以使用unique_ptr的get方法，它不影响生命周期，只用于临时使用一个原始指针
  • 整一个指向unique_ptr的指针，不断遍历
  • 两种方法其实差别不大，都不算那么优雅，我选择使用get

插入、删除和查找

这是Lab的重点

在实现时，可以引入一个空的头节点，可以方便我们的遍历。

查找:

• 从根节点开始，查找key当前对应的char是否在当前节点的childs中
  • 没找到返回false
  • 找到则当前节点指向对应字节点，key当前char换下一个
• 查找到最后一个key，找到对应的Node，满足下列条件时，返回true
  • 该Node是最后一个Node
  • 该Node可以转换为TrieNodeWithValue，同时返回对应的值

插入:

• 从跟节点开始，查找key当前的char是否在child中
  • 没找到->构建一个当前key的Node，插入child，继续遍历流程
  • 找到->当前Node切换为对应的child，key的char换下一个，继续查找
• 一般这样就OK了，但是我们还有value：
  • 在处理key的最后一个char时
    • 没找到->构建一个TrieNodeWithValue，flag设为true，value放进去，插入child
    • 找到，查看Node的flag是否设置为最后一个
      • 是，返回false
      • 不是，无需管当前child是什么类型，都调用TrieNodeWithValue对应构造函数，删除当前child，并插入新Node。

删除:

要维护一个栈

• 从根节点开始，查找key当前的char是否在child中，直到找完
  • 找到：当前Node放入栈，遍历对应的child
  • 没找到：直接返回false
• 找到之后，要将最后这个节点的bool flag设置为false（无需转换成普通Node，由于继承的特性并不影响功能，插入时也不管它的类型，所以不会造成影响）。
• 依次弹出栈，如果没孩子，就删除它，否则直接break并返回true。