指针党卡空间福音，只占4byte的指针

以下内容均为我从网上的各种博客中学来的奇怪trick，不保证没有问题 众所周知，`64bit` 程序的指针要占 `8 byte`，但是，如果使用数组下标来存储数据结构则只需要用 `4 byte` 的 `int` 类型，这是因为 OI 中几乎不会遇到空间大小达到 `4GB` 的题 而如果使用指针写数据结构，就会每个指针浪费 `4 byte`，然后你就被卡空间了 所以我们考虑自己写一个指针类型一类的东西，首先我们需要一个 `node` 结构体 ```cpp struct node{ long long v,tg; node* c[2]; }; ``` 好，这就是一个十分基础的线段树的节点，更复杂的东西和这个同理 我们想定义一个指针，我们发现要让他们两个可以互相看到，所以最方便的方法是写在一块 ```cpp struct node{ struct nodp{ int adr; nodp(int v=0):adr(v){} }; long long v,tg; nodp c[2]; }; ``` 而我们又需要一个内存池，这里问题就出现了，我们需要在 `nodp` 里面看到这个内存池，所以肯定要放在 `node` 声明的前面，但这样就意味着不能开一个 `node[]` 数组 所以我们换一个方法，开一个其他的数组，并把它强制转成 `node` 数组使用 ```cpp struct node; char pool[maxsz*24/*= sizeof(node)*/]; node*st=(node*)pool; int ps; struct node{ struct nodp{ int adr; nodp(int v=0):adr(v){} }; long long v,tg; nodp c[2]; }; ``` 好了，我们现在有了一个指向池顶的指针 `st`，我们可以重载运算符了 ```cpp struct node; char pool[maxsz*24/*= sizeof(node)*/]; node*st=(node*)pool; int ps; struct node{ struct nodp{ int adr; nodp(int v=0):adr(v){} node*operator->()const{return st+adr;} node&operator* ()const{return*(st+adr);} }; long long v,tg; nodp c[2]; nodp operator&()const{return nodp(this-st);} }; ``` 这些都很直观，最后还差一点东西，就是我们众所周知普通的指针可以转成 `bool`（用于判断是否为空），我们也加上去（转成`int`的效果一样），还有要从外面访问，所以我们加一个 `typedef` ```cpp struct node; char pool[maxsz*24/*= sizeof(node)*/]; node*st=(node*)pool; int ps; struct node{ struct nodp{ int adr; nodp(int v=0):adr(v){} operator int()const{return adr;} node*operator->()const{return st+adr;} node&operator* ()const{return*(st+adr);} }; long long v,tg; nodp c[2]; nodp operator&()const{return nodp(this-st);} }; typedef node::nodp nodp; ``` 最后，加一个 `nwnode()` 函数 ```cpp nodp nwnode(){ nodp ret(++ps); return ret; } ``` 注意，因为我们把 `0` 号位置分给空节点了，所以要从 `1` 开始分配。 最后出来的就是如此状物： ```cpp struct node; char pool[maxsz*24/*= sizeof(node)*/]; node*st=(node*)pool; int ps; struct node{ struct nodp{ int adr; nodp(int v=0):adr(v){} operator int()const{return adr;} node*operator->()const{return st+adr;} node&operator* ()const{return*(st+adr);} }; long long v,tg; nodp c[2]; nodp operator&()const{return nodp(this-st);} }; typedef node::nodp nodp; nodp nwnode(){ nodp ret(++ps); return ret; } ``` 这样，我们就可以把 `nodp` 当成 `node*` 来使用了，但它只占 `4byte`！ 嘛，因为它不是真正的指针，所以终究是有一些限制和坑点的 - 你只能在给定的内存池里面开一个新的 `node`，准确来说，你的假指针只能用在内存池内的 - 由于编译器原因，你需要手动填写 `sizeof(node)` - 代码长 当然，大多数写的时候不会用到取址的重载，所以 ```cpp nodp operator&()const{return nodp(this-st);} ``` 这一段你可以不写 ------------ 等会，这个模板似乎少了一个指针所特有的超级好用的功能！ **就是如果你访问到一个空节点那么直接RE** 这里我们可以： ```cpp #define NODE_DEBUG assert(adr) struct node; char pool[maxsz*24/*= sizeof(node)*/]; node*st=(node*)pool; int ps; struct node{ struct nodp{ int adr; nodp(int v=0):adr(v){} operator int()const{return adr;} node*operator->()const{NODE_DEBUG;return st+adr;} node&operator* ()const{NODE_DEBUG;return*(st+adr);} }; long long v,tg; nodp c[2]; nodp operator&()const{return nodp(this-st);} }; const int sz=sizeof(node); typedef node::nodp nodp; nodp nwnode(){ nodp ret(++ps); return ret; } ``` 噔噔咚！这样访问到空的地方就直接RE辣！ 当然众所周知 `assert` 的开销还蛮大的，所以提交的时候就直接： ```cpp #define NODE_DEBUG //assert(adr) ``` 注释掉就可以了 ------------ 所以说这么麻烦你不想写那有什么用呢 其实最大的用处就在于，按照习惯辛辛苦苦写了一大坨指针版的，然后被卡空间，然后完全不想改成数组版的 这个时候，如果你的写法不是什么奇奇怪怪的毒瘤写法，那么直接把那一坨东西复制进你的 `node` 结构体旁边，然后把所有的 `node*` 全部替换成 `nodp` 就可以了，基本不需要改其他地方。