cmu15-445/645 2022 Project0

Project0——Primer

目标：写一个支持并行插入(删除)节点、具有Key-Value功能的Trie树。

本文就简单记录一下语法知识，Trie的算法不做具体讨论。

三个类：

普通节点：三个变量：unorder_map存储的儿子节点信息、is_end、当前节点表示的字符char
叶子节点：继承于普通节点，is_end等于true，还具有value信息
Trie树：一个根节点 root，一个读写锁 latch

C++语法

下面是两种比较容易混淆的初始化方式：

1
2
3

this->root_=std::make_unique<TrieNode>('\0');//这里括号里传的是所指类型的构造函数参数，构造函数交由make_unique调用

std::unique_ptr<TrieNode> new_child(new TrieNode(c));//这里是直接用一个指针去初始化uniqe_ptr

unique_ptr没有普通赋值操作，只有移动赋值

 //下面是移动构造函数（只能传右值进去，不能传左值，配合std::move使用）
TrieNode(TrieNode &&other_trie_node) noexcept {
    this->key_char_=other_trie_node.key_char_;
    this->is_end_=other_trie_node.is_end_;
    this->children_=std::unordered_map<char, std::unique_ptr<TrieNode>>{};
    //c++17，使用[]遍历哈希表
    for(auto& [k,v]:other_trie_node.children_){
      this->children_[k]=std::move(v);//移动赋值
    }
 }

右值引用

//对于unique_ptr来说，by value和by r-value reference相同（其他的还是有所区别），只能通过move传参
//这里如果是不加引用，也只能通过move传参则是调用unique_ptr的移动构造；
  std::unique_ptr<TrieNode> *InsertChildNode(char key_char, std::unique_ptr<TrieNode> &&child) {
    if(child->key_char_!=key_char) return nullptr;
    if(this->children_.count(key_char)) return nullptr;

    this->children_[key_char]=std::move(child);
    return &(this->children_[key_char]);
  }

//注意，只要函数参数是右值类型，传左值就是不行的，左值并不会自动转换为右值
void func(int&& a){
    std::cout<<a<<end;
    return ;
}
int main(){
    int p=2;
    //func(p);//非法!!!
    func(std::move(p));//正确!!!
}

unique_ptr的遍历：

//写的时候由于unique_ptr不能拷贝，所以想用一个临时变量来对它进行遍历操作就有点麻烦，一个好的做法是使用一个指针指向unique_ptr,这样就避免了拷贝
  template <typename T>
  bool Insert(const std::string &key, T value) {
    if(key.size()==0) return false;

    std::unique_ptr<TrieNode>* current=&root_;
    for(std::size_t i=0;i<key.size();i++){
      char c=key[i];
      latch_.WLock();
      if(!(*current)->HasChild(c)) {
        std::unique_ptr<TrieNode> new_child(new TrieNode(c));
        (*current)->InsertChildNode(c, std::move(new_child));
      }
      current=(*current)->GetChildNode(c);
      latch_.WUnlock();
    }

    latch_.RLock();
    if((*current)->IsEndNode()) {
      latch_.RUnlock();
      return false;
    }
    latch_.RUnlock();

    latch_.WLock();
     //这句是将普通节点的unique_ptr重新指向一个叶子节点。reset后面跟叶子节点的指针，叶子节点的构造使用普通节点作为参数。
    (*current).reset(new TrieNodeWithValue<T>(std::move(**current),value));
    latch_.WUnlock();
    return true;
  }

读写锁：写的时候是不能读的，读的时候可以大家一起读。

llf333

cmu15-445/645 2022 Project0

Project0——Primer

C++语法

结果