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

· · 个人记录

以下内容均为我从网上的各种博客中学来的奇怪trick，不保证没有问题

众所周知，64bit 程序的指针要占 8 byte，但是，如果使用数组下标来存储数据结构则只需要用 4 byte 的 int 类型，这是因为 OI 中几乎不会遇到空间大小达到 4GB 的题

而如果使用指针写数据结构，就会每个指针浪费 4 byte，然后你就被卡空间了

所以我们考虑自己写一个指针类型一类的东西，首先我们需要一个 node 结构体

struct node{
    long long v,tg;
    node* c[2];
};

好，这就是一个十分基础的线段树的节点，更复杂的东西和这个同理

我们想定义一个指针，我们发现要让他们两个可以互相看到，所以最方便的方法是写在一块

struct node{
    struct nodp{
        int adr;
        nodp(int v=0):adr(v){}
    };
    long long v,tg;
    nodp c[2];
};

而我们又需要一个内存池，这里问题就出现了，我们需要在 nodp 里面看到这个内存池，所以肯定要放在 node 声明的前面，但这样就意味着不能开一个 node[] 数组

所以我们换一个方法，开一个其他的数组，并把它强制转成 node 数组使用

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，我们可以重载运算符了

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

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() 函数

nodp nwnode(){
    nodp ret(++ps);
    return ret;
}

注意，因为我们把 0 号位置分给空节点了，所以要从 1 开始分配。

最后出来的就是如此状物：

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！

嘛，因为它不是真正的指针，所以终究是有一些限制和坑点的

当然，大多数写的时候不会用到取址的重载，所以

nodp operator&()const{return nodp(this-st);}

这一段你可以不写

等会，这个模板似乎少了一个指针所特有的超级好用的功能！

就是如果你访问到一个空节点那么直接RE

这里我们可以：

#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 的开销还蛮大的，所以提交的时候就直接：

#define NODE_DEBUG //assert(adr)

注释掉就可以了

所以说这么麻烦你不想写那有什么用呢

其实最大的用处就在于，按照习惯辛辛苦苦写了一大坨指针版的，然后被卡空间，然后完全不想改成数组版的

这个时候，如果你的写法不是什么奇奇怪怪的毒瘤写法，那么直接把那一坨东西复制进你的 node 结构体旁边，然后把所有的 node* 全部替换成 nodp 就可以了，基本不需要改其他地方。