让你的代码更CPP一点（前缀树示例）--粉丝服务平台-粉丝头条-fensifuwu.com

让你的代码更CPP一点（前缀树示例）

科技 07-11 1 来源：算法工程师之路

文章和资源同步更新至微信公众号：算法工程师之路

不知道各位写C++代码的童鞋们，有没有发现一个现象，自己写的CPP代码怎么那么像C代码呢？笔者也深有感触，但是自从C++11标准出现以后，CPP的代码就开始精简很多了，风格也极大的发生了变化，今天笔者就开始整理一些C++的新特性，并展示如何在实际应用中使用！让你的代码更Cpp些！

前缀树结构图

1.nullptr

nullptr是为了补充并替代NULL的，由于之前老版本的NULL定义一般为0，但有时候又被编译器定义为((void*)0)。这样就会出现混乱，特别是进行函数重载的时候，就会让编译器搞不清楚NULL的具体类型，因此，引入nullptr可以更好的区分0和空指针，因此，在新版中，尽量使用nullptr代表空指针进行初始化。

2.初始化列表

使用初始化列表的方式可以极大的简化构造函数的代码量，使得程序更加简洁。

struct TrieNode
 {
 int path, end;
 vector<TrieNode*> children_;
 TrieNode() : path(0), end(0), children_(26, nullptr){}
 };
TrieNode();

3.auto、decltype类型

在C++中最烦的就算是各种类型声明的编写，太多字母了，而且有时候也会忘记，由于他们的类型定义太多太乱了！因此C++11中使用auto对数据类型进行自动推倒。新版中，已经弃用了之前有类似功能的register关键字，变得更加强大，比如下面例子：

for(vector<int>::const_iterator itr = vec.cbegin(); itr != vec.cend(); ++itr)
// 可以改写为
for(auto itr = vec.cbegin(); itr != vec.cend(); ++itr);

是不是可以方便很多了，但是auto类型有个缺陷的地方，如果我们想要根据某个数或者表达式的类型去定义一个变量，而不进行初始化，那我们使用auto就不行了，所以C++引入了另外一个关键字decltype。

int a = 0;
decltype(a) b; // b的类型为int, b和a类型一致
decltype((a)) b = 10; // 多加一层括号，表示一个表达式，此时b类型为int&, 必须赋初值
decltype(f()) b = 2; // b的类型为函数返回值类型，注意函数不运行，编译器只是经过推理得到其返回值类型

4.范围for语句

相信学过python的同学都很清楚，在python中经常使用的for语句是for….in….，十分的方便，而在C中for循环是又丑又长，C++标准为了简化代码量，提供了新的范围for语句：for(auto c : str);

// C风格
for(std::vector<int>::iterator i = arr.begin(); i != arr.end(); ++i) {
 std::cout << *i << std::endl;
}
// C++11
for(auto &i : arr){
 cout << i << " "; // 加上引用可以为左值，用于修改
}

是不是瞬间觉得C++好多了，没有指针了，也没有很长的类型声明了，这才是撸代码的感觉啊！！！

5.智能指针（shared_ptr和make_shared）

我在刷题的时候，由于是参考了JAVA版的，在JAVA中可以靠JVM的垃圾回收机制，特别是考虑到大数据问题，在栈区建立一个链表或者树结构可能会导致空间不够，因此一般会在堆区进行建立，但是释放问题是真的很繁琐！即使new和delete已经比C中的分配内存方便多了，但还是繁琐，因此我们可以使用智能指针来让程序自动维护开辟的空间！以防止由于我们不当操作出现内存泄露和野指针的问题！

在C++11中，智能指针包含在< memory >中，分为shared_ptr、unique_ptr、weak_ptr，其中shared_ptr允许多个指针指向同一个对象，而unique_ptr为独占式的占有一个对象。最后的weak_ptr为一个弱引用，指向shared_ptr所管理的对象！

shared_ptr采用引用计数的方式管理所指向的对象。当有一个新的shared_ptr指向同一个对象时（复制shared_ptr等），引用计数加1。当shared_ptr离开作用域时，引用计数减1。当引用计数为0时，释放所管理的内存。

由于shared_ptr是一个类模板，因此不可以直接使用指针对其进行赋值！但一般不建议使用new方法对智能指针初始化，这样会造成阅读代码的困惑！建议使用make_shared函数进行初始化！当然为了代码简洁，我们可以使用auto类型进行类型推倒！

shared_ptr<int>p = new int(5); //错误
shared_ptr<int>p(new int(5));
shared_ptr<int>p = make_shared<int>(5); //建议
auto p = make_shared<int>(5);

题目：前缀树

实现一个 Trie (前缀树)，包含 insert, search, 和 startsWith 这三个操作。
示例:
Trie trie = new Trie();
trie.insert("apple");
trie.search("apple"); // 返回 true
trie.search("app"); // 返回 false
trie.startsWith("app"); // 返回 true
trie.insert("app");
trie.search("app"); // 返回 true

这次的题目是简单的实现一个前缀树的功能，笔者实现了两个版本的（简单和复杂），参考了LeetCode中大佬的答案，将代码优化的更加的CPP，简单版的题目如上面所示，仅仅实现插入和查找两个功能！而复杂版可以记录前缀为str的字符串的个数，并且支持插入和删除字符串的操作！主要目的是了解如何更加CPP的写代码，不再C风格！

具体的前缀树的操作原理自行百度，很简单的，就是如何定义每个节点，怎么进行查找判断！

class TrieTree{
public:
 TrieTree() : root_(make_shared<TrieNode>()){}
 void insert(string word_){
 auto res = root_;
 for(auto c : word_){ // 范围for语句，auto类型推导
 if (res->children_[c-'a'] == nullptr){
 res->children_[c-'a'] = make_shared<TrieNode>(); // 智能指针分配内存
 }
 res = res->children_[c-'a'];
 }
 res->isWord_ = true;
 }
 bool search(string word){
 shared_ptr<TrieNode> res = find(word);
 return res != nullptr && res->isWord_ == true;
 }
 bool startsWith(string prefix){
 return find(prefix) != nullptr;
 }
private:
 struct TrieNode
 {
 bool isWord_;
 vector<shared_ptr<TrieNode>> children_; // 孩子节点的集合
 TrieNode() : isWord_(false), children_(26, nullptr){} // 初始化列表
 };
 shared_ptr<TrieNode> find(string& prefix){
 auto res = root_;
 for(int i = 0;i < prefix.size() && res != nullptr; ++i){
 res = res->children_[prefix[i] - 'a'];
 }
 return res;
 }
 shared_ptr<TrieNode> root_; // 智能指针
};