文章和资源同步更新至微信公众号:算法工程师之路
不知道各位写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_; // 智能指针
};
资源分享
以上完整代码文件(C++版),文件名为:前缀树(简单OR复杂),请关注我的个人公众号 (算法工程师之路),回复"左神算法基础CPP"即可获得,并实时更新!希望大家多多支持哦~
公众号简介:分享算法工程师必备技能,谈谈那些有深度有意思的算法,主要范围:C++数据结构与算法/深度学习(CV),立志成为Offer收割机!坚持分享算法题目和解题思路(Day By Day)
留言与评论(共有 0 条评论) |