P0实验笔记

前置知识

书到用时方恨少，这个Project虽说前缀树我在之前就学过，但C++的基础知识还是很不牢固，所以先把一些需要用的知识点要在这里再记一下。

左值引用和右值引用

• 左值是可以放在赋值号左边的，左值必须要在内存中有实体。
• 右值出现在赋值号右边；右值可以在寄存器也可以在内存中。

int num = 10;
int &b = num;
int &c = 10; // 错误

上面。num有地址是左值，b是对num的引用，所以这是左值引用。而10是右值，所以c是右值引用，这里是错误的。
但这样又是可以的：
const int& c =10,允许使用常量左值引用操作右值。
实际开发中我们可能需要对右值进行修改（实现移动语义时就需要），显然左值引用的方式是行不通的。

右值引用介绍

右值引用也必须立即进行初始化操作，且使用右值进行初始化。

int&& a = 10;
a = 100;

上面的操作都是正确的。
右值引用 引用 右值，会使右值被存储到特定的位置。

• 左值引用的短板
  传值传参和传值返回都会产生拷贝，有的甚至是深拷贝，代价很大。而左值引用的实际意义在于做参数和做返回值都可以减少拷贝，从而提高效率。但是，左值引用的短板是不能够引用局部变量。

简单例子

#include <iostream>
#include <vector>

// 接收一个 std::vector<int> 的右值引用参数
void processVector(std::vector<int>&& vec) {
    // 对右值引用进行操作，而不进行拷贝
    for (int num : vec) {
        std::cout << num << " ";
    }
    std::cout << std::endl;
}

int main() {
    std::vector<int> nums = {1, 2, 3, 4, 5};
    // 将 nums 作为右值传递给函数
    processVector(std::move(nums));

    // 此时 nums 已被移动，不再可用
    // 这里访问 nums 将导致未定义的行为
    return 0;
}

右值引用的特性是可以绑定到临时对象（右值）上的引用，而临时对象在表达式求值后就会被销毁。因此，当我们将nums通过std::move()转换为右值引用后，它的值类别变为右值，而不再是左值。
在函数参数中接收到右值引用 vec 后，我们可以直接操作它，而不需要进行对象拷贝。这是因为右值引用的特性允许我们“窃取”临时对象的资源，而不是进行拷贝。在这种情况下，我们可以直接使用 vec 的资源（例如 std::vector 中的数据），而不需要进行额外的拷贝操作。

move移动语义

作用是将一个左值强制转化为右值，以实现移动语义。左值被 move 后变为右值，于是右值引用可以引用。

int t = 10;
//int&& rrt = t; // 编译报错，不能直接引用左值

// 2.但是右值引用可以引用被move的左值
int&& rrt = std::move(t);  //正确

右值引用意义和移动构造函数:
右值做参数，那么就会调用移动构造，而调用移动构造就会减少拷贝（如果是像 string 这样的在堆空间上存在资源的类，那么每调用一次移动构造就会少做一次深拷贝。

forward完美转发

有了move函数之后，我们又遇到了一个新的问题：

按照上面的写法，处理临时变量用右值引用T&&，处理普通变量用const引用const T&，我们需要分别建立两个函数，然后入参使用不同的类型，每个函数都要写两遍。
那么能不能避免重复，将T &&类型和const T &类型合二为一呢？

答案就是：forward函数，std::forward也被称为完美转发，即：保持原来的值属性不变：

• 如果原来的值是左值，经std::forward处理后该值还是左值。
• 如果原来的值是右值，经std::forward处理后它还是右值。
  这样一来，我们就可以使用forward函数对入参进行封装，从而保证了入参的统一性，从而可以实现一个方法处理两种类型！
  正因为如此，forward函数被大量用在了入参值类型情况不确定的C++模板中！

智能指针

std::unique_ptr是一个智能指针类模板，用于管理动态分配的对象。它提供了独占所有权的语义，意味着一个unique_ptr指针可以拥有对一个对象的唯一所有权，并负责在其生命周期结束时自动释放该对象。

• move: 转移所有权，将原指针置空。

std::unique_ptr<int> ptr1(new int(10));
std::unique_ptr<int> ptr2 = std::move(ptr1); // 移动所有权

std::vector<std::unique_ptr<int>> vec;
vec.push_back(std::make_unique<int>(20)); // 移动 unique_ptr 到容器中

• reset:更改所有权。

1. ptr.reset():销毁对象，指针置空。
2. ptr.reset(new_ptr):智能指针指向新的对象，原对象销毁。

• get：get()是 unique_ptr类的成员函数，它返回指向unique_ptr所拥有的对象的指针，即原始指针。

---

代码实现

说了这么多，如果感觉还不是很懂，就直接来看代码吧。
我这里只介绍一些比较重要的函数。

TrieNode

TrieNode(TrieNode &&other_trie_node) noexcept {
    key_char_ = other_trie_node.key_char_;
    is_end_ = other_trie_node.is_end_;
    children_.swap(other_trie_node.children_);
  }

这就是移动构造函数。
调用 children_.swap(other_trie_node.children_)，使用 std::swap函数将 other_trie_node 的 children_ 成员变量与当前对象的 children_成员变量进行交换。这样做可以实现高效的移动操作，避免不必要的复制。

std::unique_ptr<TrieNode> *InsertChildNode(char key_char, std::unique_ptr<TrieNode> &&child) {
    if (HasChild(key_char) || key_char != child->key_char_) {
      return nullptr;
    }
    children_[key_char] = std::move(child);
    return &children_[key_char];
  }

std::unique_ptr<TrieNode> *GetChildNode(char key_char) {
    auto node = children_.find(key_char);
    if (node != children_.end()) {
      return &(node->second);
    }
    return nullptr;
  }

• 为什么返回的都是智能指针的指针？

  因为智能指针对一个对象有唯一的所有权,如果我们在字典树的操作中需要不断迭代的话，需要移动指针，那就需要用到智能指针的指针了。

• 为什么要children_[key_char] = std::move(child)?

  child 是一个右值引用的 std::unique_ptr，应该直接将其移动给 children_[key_char]。child 的所有权转移给 children_[key_char]，而不是重新构造一个新的 std::unique_ptr。这样做可以避免不必要的内存分配和析构，并正确地转移所有权。

void RemoveChildNode(char key_char) {
    auto node = children_.find(key_char);
    if (node != children_.end()) {
      node->second.reset();
      children_.erase(key_char);
    }
  }

TrieNodeWithValue

TrieNodeWithValue(TrieNode &&trieNode, T value) : TrieNode(std::forward<TrieNode>(trieNode)) {
    value_ = value;
    SetEndNode(true);
  }

移动构造函数，把trieNode作为右值传递给TrieNodeWithValue，实现资源的转移。

Trie

template <typename T>
  bool Insert(const std::string &key, T value) {
     if (key.empty()) {
      return false;
    }

    latch_.WLock();
    auto cur = &root_;
    // latch_.WLock();
    auto c = key.begin();

    while (true) {
      auto x = c++;
      if (c == key.end()) {
        break;
      }
      if (cur->get()->HasChild(*x)) {
        cur = cur->get()->GetChildNode(*x);
      } else {
        cur = cur->get()->InsertChildNode(*x, std::make_unique<TrieNode>(*x));
      }
    }

    char ch = key.back();
    auto end_node = cur->get()->GetChildNode(ch);

    if (end_node != nullptr && end_node->get()->IsEndNode()) {
      latch_.WUnlock();
      return false;
    }

    if (end_node != nullptr) {
      auto new_node = new TrieNodeWithValue<T>(std::move(*(end_node->get())), value);
      end_node->reset(new_node);

      latch_.WUnlock();
      return true;
    }

    // 如果为空
    cur = cur->get()->InsertChildNode(ch, std::make_unique<TrieNode>(ch));
    // 现在还是一个中间节点，还不是TrieNodeWithValue
    auto new_node = new TrieNodeWithValue<T>(std::move(**cur), value);
    cur->reset(new_node);
    latch_.WUnlock();
    return true;
  }

bool Remove(const std::string &key) {
    if (key.empty()) {
      return false;
    }
    latch_.WLock();
    std::vector<std::unique_ptr<TrieNode> *> storage;
    std::unique_ptr<TrieNode> *node = &root_;
    for (char ch : key) {
      storage.emplace_back(node);
      std::unique_ptr<TrieNode> *next = node->get()->GetChildNode(ch);

      if (next == nullptr) {
        latch_.WUnlock();
        return false;
      }

      node = next;
    }

    if (node->get()->HasChildren()) {
      // node = node->get()->GetChildNode(key[key.size()-1]);
      node->get()->SetEndNode(false);
    } else {
      for (int i = storage.size() - 1; i >= 0; i--) {
        // 想一下， root 节点是不记录字符的
        std::unique_ptr<TrieNode> *pre = storage[i];
        if ((i < static_cast<int>(key.size() - 1)) && (node->get()->IsEndNode() || node->get()->HasChildren())) {
          break;
        }
        pre->get()->RemoveChildNode(key[i]);
        node = pre;
      }
    }

    latch_.WUnlock();
    return true;
  }

template <typename T>
  T GetValue(const std::string &key, bool *success) {
    *success = true;
    latch_.RLock();
    if (key.empty()) {
      *success = false;
      return {};
    }

    auto cur = &root_;
    for (char ch : key) {
      if (cur->get()->HasChild(ch)) {
        cur = cur->get()->GetChildNode(ch);
      } else {
        *success = false;
        latch_.RUnlock();
        return {};
      }
    }

    if (!cur->get()->IsEndNode()) {
      *success = false;
      latch_.RUnlock();
      return {};
    }

    auto flag_node = dynamic_cast<TrieNodeWithValue<T> *>(cur->get());
    if (flag_node == nullptr) {
      *success = false;
      latch_.RUnlock();
      return {};
    }

    latch_.RUnlock();
    return flag_node->GetValue();
  }
};
}