<h1>实现</h1>

在c++中，我们非常喜欢使用指针。因为指针非常适合人们的思考方式。

所以我们来优化一下指针的速度。

你们想一下：嵌套7，8层数组和一些平等无嵌套的箭头，哪个更容易理解？

当然是前者啦

指针非常亲和人们的语言和思维习惯，所以被众多OIer所追求。

当然你做工程时写指针 throw 出一堆 Error 时当然会绝望

所以说，为了获得更好的指针体验，我们现在分析一下，为什么指针比较慢。

我们来回顾一下图的常规写法：

struct Node{
    struct Edge *firstEdge;
    // Other Attributes.
}node[MAXN];

struct Edge{
    Node s,t;
    int w;
    Edge *next;
    Edge(Node s,Node t,int w) : s(s), t(t), w(w), next(s->firstEdge) {}
    // Other Attributes.
};

这种方式的缺点在哪里呢？我们发现建边的时候：

inline void add(int u,int v,int w){
    node[u].firstEdge = new Edge(&node[u],&node[v],w);
    //or node[v].firstEdge = new Edge(&node[v],&node[u],w);
}

会调用1～2次new函数，我们看一看new函数的执行过程：

A* pa = new A(3);

等价于：

A pa = (A)malloc(sizeof(A));
pa->A::A(3);
return pa;

这是在做什么呢？它就是：获得一块内存空间、调用构造函数、返回正确的指针。

是不是很麻烦？我们能不能直接返回呢？

于是，我们手动实现new的过程。

我们这样写：

struct Node{
    struct Edge *firstEdge;
    // Other Attributes.
}node[MAXN];

struct Edge{
    Node s,t;
    int w;
    Edge *next;
    // Other Attributes.
}pool[MAXM  2],frog = pool;

Edge New(Node s,Node *t,int w){
    Edge *ret = ++frog;
    frog->s = s;frog->t = t;
    frog->w = w;frog->next = s->firstEdge;
    return ret;
}

这样我们在调用的时候只需：

inline void add(int u,int v,int w){
    node[u].firstEdge = New Edge(&node[u],&node[v],w);
    // or node[v].firstEdge = New Edge(&node[v],&node[u],w);
}

发现了吗？我们其实就是预先定义出了所有要用的边（pool），然后用一个尾指针（frog）来指向。

每次加边时，我们直接另指针后移，然后获取一个新的未被初始化过的Edge变量，对其进行初始化即可。

其他步骤和普通指针一样即可。

所以说，我们在预定义内存池时，我们必须要算好开多少空间。

那么，内存池有什么好处呢？

<h1>优点</h1>

1. 速度比new快了不少。
2. 我们在需要精确定位第$ i $条边时，不需要多定义一个$ num $成员变量，省下了空间和时间。

那么，我们再拿一个线段树的例子来加深理解。

线段树原实现（部分）

struct SegmentTree{
    int l,r,sum,tag;
    SegmentTree lc,rc;
    SegmentTree(int l,int r,SegmentTree lc,SegmentTree rc) : l(l), r(r), sum(0), tag(0), lc(lc), rc(rc) {};
    
    static SegmentTree *build(int l,int r){
        int mid = (l + r) >> 1;
        return (l == r) ? SegmentTree(l,r,NULL,NULL) : SegmentTree(l,r,build(l,mid),build(mid + 1,r));
    }
    
    // Other Attributes.
}*segt;

我们对new过程进行分析。

每次执行new时，我们相当于初始化一个SegmentTree类型的变量。那么我们可以如此初始化：

SegmentTree New(int l,int r,SegmentTree lc,SegmentTree *rc){
    SegmentTree *ret = ++frog;
    ret->l = l;ret->r = r;
    ret->lc = lc;ret->rc = rc;
    ret->sum = ret->tag = 0;
    return ret;
}

那么，现在的实现就需要这样：

struct SegmentTree;

SegmentTree New(int,int,SegmentTree ,SegmentTree *);

struct SegmentTree{
    int l,r,sum,tag;
    SegmentTree lc,rc;
    
    static SegmentTree *build(int l,int r){
        int mid = (l + r) >> 1;
        return (l == r) ? New(l,r,NULL,NULL) : New(l,r,build(l,mid),build(mid + 1,r));
    }
    
    // Other Attributes.
}pool[MAXN  4],frog = pool,*segt;

SegmentTree New(int l,int r,SegmentTree lc,SegmentTree *rc){
    SegmentTree *ret = ++frog;
    ret->l = l;ret->r = r;
    ret->lc = lc;ret->rc = rc;
    ret->sum = ret->tag = 0;
    return ret;
}

好了，相信你学会了内存池，就能抛弃掉毒瘤的数组写法和超级慢的new写法，能够获得更好的指针体验。