还记得一次ZJU的月赛，有一题用到了Trie树，而且对时间要求非常高，我将动态内存分配改成了静态才过，这是修改过后的Trie的代码
//-------静态空间的Trie-----------
struct TrieTree{
TrieTree* next[26];
int flag;
};
TrieTree _alloc[200000],*_p;
inline void init_alloc(){_p=_alloc;}
inline TrieTree* myalloc(){memset(_p,0,sizeof(TrieTree));return _p++;}
void insert(TrieTree* p,const char word[]){
for(int i=0;word[i];i++){
if(p->next[word[i]-'a']==NULL){
p->next[word[i]-'a']=myalloc();
}
p=p->next[word[i]-'a'];
}
p->flag=1;
}
int search(TrieTree* p,const char word[]){
for(int i=0;word[i];i++){
if(p->next[word[i]-'a']==NULL){
return 0;
}
p=p->next[word[i]-'a'];
}
return p->flag;
}
当时的题目只需要插入和查询，不存在删除，而每次case结束只要将_p指针复位就等价于释放了当前的全部节点
其实有更简便的，同样高效的解决方法，
解决方案1，重载operator new：
#include <iostream>
#include <algorithm>
using namespace std;
struct TrieTree{
static TrieTree _alloc[200000];
static TrieTree *_p;
TrieTree* next[26];
int flag;
void* operator new(size_t size){
void *res=_p++;
memset(res,0,sizeof(TrieTree));
if(_p>=_alloc+200000)_p-=200000;
return res;
}
};
TrieTree TrieTree::_alloc[200000];
TrieTree* TrieTree::_p=TrieTree::_alloc;
void insert(TrieTree* p,const char word[]){
for(int i=0;word[i];i++){
if(p->next[word[i]-'a']==NULL){
p->next[word[i]-'a']=new TrieTree();
}
p=p->next[word[i]-'a'];
}
p->flag=1;
}
int search(TrieTree* p,const char word[]){
for(int i=0;word[i];i++){
if(p->next[word[i]-'a']==NULL){
return 0;
}
p=p->next[word[i]-'a'];
}
return p->flag;
}
int main()
{
TrieTree* t=new TrieTree();
insert(t,"hello");
insert(t,"hi");
cout<<search(t,"hello")<<endl;
cout<<search(t,"hey")<<endl;
}
这样做的好处是，只要增加静态空间的代码和重载operator new的代码，其余的代码完全无需变化，在insert中仍然使用new来分配即可。这种方法应该说是最优雅的。
其实还有一个解决方案，方案2，
placement new
#include <iostream>
#include <algorithm>
using namespace std;
struct TrieTree{
TrieTree* next[26];
int flag;
};
TrieTree _alloc[200000],*_p;
inline void init_alloc(){memset(_alloc,0,sizeof(_alloc));_p=_alloc;}
void insert(TrieTree* p,const char word[]){
for(int i=0;word[i];i++){
if(p->next[word[i]-'a']==NULL){
p->next[word[i]-'a']=new(_p++) TrieTree();//注意此处new的使用
}
p=p->next[word[i]-'a'];
}
p->flag=1;
}
int search(TrieTree* p,const char word[]){
for(int i=0;word[i];i++){
if(p->next[word[i]-'a']==NULL){
return 0;
}
p=p->next[word[i]-'a'];
}
return p->flag;
}
int main()
{
init_alloc();
TrieTree* t=new(_p++) TrieTree();
insert(t,"hello");
insert(t,"hi");
cout<<search(t,"hello")<<endl;
cout<<search(t,"hey")<<endl;
}
其实C++提供从已经分配的内存空间上构造对象的方法，就是placement new，只是我当初不知道。它的用法就是在new运算符后面加上用于构造对象的空间的首地址。
placement
new主要适用于：在对时间要求非常高的应用程序中，因为这些程序分配的时间是确定的；长时间运行而不被打断的程序；以及执行一个垃圾收集器(garbage collector)。
BTW, placement new是不能被重载的